學好概率圖模型，新的一年大展宏圖
概率圖模型為高維數據建模提供了一個非常有用的框架，它是概率論和圖論的結合。概率圖模型是一類用圖形模式表達基於概率相關關係的模型的總稱。概率圖模型結合概率論與圖論的知識,利用圖來表示與模型有關的變數的聯合概率分布。近10年它已成為不確定性推理的研究熱點,在人工智慧、機器學習和計算機視覺等領域有廣闊的應用前景。概率圖理論共分為三個部分，分別為概率圖模型表示理論，概率圖模型推理理論和概率圖模型學習理論。
基本的概率圖模型包括貝葉斯網路、馬爾可夫網路和隱馬爾可夫網路。
基本的Graphical Model可以大致分為兩個類別:貝葉斯網路(Bayesian Network)和馬爾可夫隨機場(Markov Random Field)。它們的主要區別在於採用不同類型的圖來表達變數之間的關係:貝葉斯網路採用有向無環圖(Directed Acyclic Graph)來表達因果關係，馬爾可夫隨機場則採用無向圖(Undirected Graph)來表達變數間的相互作用。這種結構上的區別導致了它們在建模和推斷方面的一系列微妙的差異。一般來說，貝葉斯網路中每一個節點都對應於一個先驗概率分布或者條件概率分布，因此整體的聯合分布可以直接分解為所有單個節點所對應的分布的乘積。而對於馬爾可夫場，由於變數之間沒有明確的因果關係，它的聯合概率分布通常會表達為一系列勢函數(potential function)的乘積。通常情況下，這些乘積的積分並不等於1，因此，還要對其進行歸一化才能形成一個有效的概率分布--這一點往往在實際應用中給參數估計造成非常大的困難。
概率圖模型把基於圖的表示方法作為高維空間上緊湊編碼複雜分布的基礎。在下圖中，節點與問題中的變數對應，而邊與兩節點變數之間的直接概率相互對應。對於每個圖模型，無論有向（左圖）或無向（右圖），我們都有對偶雙重視角來說明一個圖的結構。如圖中的獨立關係（Independence）和因子分解（Factorization）。
概率圖模型的基本性質
任意隨機變數的集合可和網路圖的頂點集合
產生聯繫，概率圖模型的基本理念是運用圖結構——團結構（clique）和割集（cut set）結構,來限制隨機變數X的分布。
一個普通的圖模型G包含頂點集合和邊緣集合
。我們重點關注無向圖模型。相反，由於邊緣具有方向性，有向無環圖成為圖模型中最為流行的一種形式。一般來說，有向圖模型比無向圖模型更難處理。
團結構是頂點集合的全連接子集。
在圖（a）中，A和B是3-cliques,而C和D是2-cliques.其中所有的團都是極大團。在圖（b）中，S為頂點割集，去掉S後，A和B就被分割成兩個子部分。
因子分解的性質
我們現在來描述團結構是如何限制隨機變數的概率分布的，對於子塊C，兼容性函數是子集的一個實值函數，取正實數。對於兼容性函數的集合，我們認為是概率分布P對圖模型G的因子化。
在這裡，Z被稱為是分割函數。需要保證概率分布P是正態化的。舉個概率分布因子分解的例子：
以上所討論的因子分解在實際運用中是非常重要的，因為它可以節省內存、提升運算效率（如果團結構的大小不太大）。
馬爾科夫性質
現在，我們用另一種視角（基於圖的割集）來詮釋圖結構是如何限制概率分布X的。讓我們引入一個叫做條件依賴的符號。考慮一個割集將圖模型分割成不連續的A、B兩個部分。
馬爾科夫隨機場的條件獨立性
無向圖的連接沒有了方向，所以父子節點之間的對稱性也消除了。所以可以使用一下兩種方法判斷是否獨立：
考慮連接集合A與集合B的節點的所有的路徑，如果所有這些路徑到通過了集合C中的一個或者多個節點，那麼所有這樣的路徑都被阻隔。因此條件獨立存在。否則的話，條件獨立的性質不一定成立。或者說一定有某個對應於該圖的概率分布不滿足條件獨立的性質。移除C中所有的節點，以及與這些節點相連的邊。然後考察是否存在一條從A中任意節點到B中任意節點的路徑。如果沒有這樣的路徑，那麼條件獨立一定存在。
一個馬爾科夫隨機場的例子：
因子分解的特徵值與馬爾科夫性質
我們簡單介紹一下Hammersley-Clifford定理
Hammersley-Clifford定理：一個嚴格為正的概率分布可以用馬爾科夫網路來表示，馬爾可科夫網路也稱馬爾科夫隨機域，其概率密度可以通過途中的子塊進行分解。
Hammersley-Clifford定理實際上是說，吉布斯分布和馬爾科夫隨機場是等價的。
馬爾科夫隨機場的核心思想：表現在圖上就是圖中某個節點的概率分布，以其鄰居為條件獨立，當以其鄰居為條件時，其他節點取任何值都不影響它的分布。吉布斯分布的核心思想：無向圖的概率可以因子化，在圖上表示就是整個圖的概率分布可以表示為該圖所包含的所有最大團的上的一個函數(因子)。
此處有詳實的數學證明
http://melodi.ee.washington.edu/courses/ee512/handout2.pdf
例子
我們提供了1個例子對以上概率圖模型的性質進行具體闡釋。
我們設定一個這樣的圖模型G=（V,E）,概率分布族（Ising model,1925）如下所示：
伊辛模型（binary variable）因子化：
伊辛模型（non-binary variable）因子化：
伊辛模型的網路估計
R語言中的IsingFit包提供了LASSO演算法對伊辛模型的估計
參考文獻：
Chen, J., & Chen, Z. (2008). Extendedbayesian information criteria for model selection with large model spaces.Biometrika, 95(3), 759-771.
Foygel, R., & Drton, M. (2011).Bayesian model choice and information criteria in sparse generalized linearmodels. arXiv preprint arXiv:1112.5635.
Ravikumar, P., Wainwright, M. J., &Lafferty, J. D. (2010). High-dimensional Ising model selection usingl1-regularized logistic regression. The Annals of Statistics, 38, 1287 - 1319.
van Borkulo, C. D., Borsboom, D., Epskamp,S., Blanken, T. F., Boschloo, L., Schoevers, R. A., & Waldorp, L. J.(2014). A new method for constructing networks from binary data. ScientificReports 4, 5918; DOI:10.1038/srep05918.
附錄：
