概率圖模型

概率圖模型是一類用圖形模式表達基於概率相關關係的模型的總稱。概率圖模型結合概率論與圖論的知識，利用圖來表示與模型有關的變量的聯合概率分佈。近10年它已成為不確定性推理的研究熱點，在人工智能、機器學習和計算機視覺等領域有廣闊的應用前景。 ^[1] 

概率圖理論共分為三個部分，分別為概率圖模型表示理論，概率圖模型推理理論和概率圖模型學習理論。 ^[2] 

基本的概率圖模型包括貝葉斯網絡、馬爾可夫網絡和隱馬爾可夫網絡。

基本的Graphical Model 可以大致分為兩個類別：貝葉斯網絡(Bayesian Network)和馬爾可夫隨機場(Markov Random Field)。它們的主要區別在於採用不同類型的圖來表達變量之間的關係：貝葉斯網絡採用有向無環圖(Directed Acyclic Graph)來表達因果關係，馬爾可夫隨機場則採用無向圖(Undirected Graph)來表達變量間的相互作用。這種結構上的區別導致了它們在建模和推斷方面的一系列微妙的差異。一般來説，貝葉斯網絡中每一個節點都對應於一個先驗概率分佈或者條件概率分佈，因此整體的聯合分佈可以直接分解為所有單個節點所對應的分佈的乘積。而對於馬爾可夫場，由於變量之間沒有明確的因果關係，它的聯合概率分佈通常會表達為一系列勢函數（potential function）的乘積。通常情況下，這些乘積的積分並不等於1，因此，還要對其進行歸一化才能形成一個有效的概率分佈——這一點往往在實際應用中給參數估計造成非常大的困難。

概率圖模型有很多好的性質：它提供了一種簡單的可視化概率模型的方法，有利於設計和開發新模型；用於表示複雜的推理和學習運算，可以簡化數學表達。 ^[3] 

概率圖模型的表示方法，研究如何利用概率網絡中的獨立性來簡化聯合概率分佈的方法表示。概率圖模型能有效處理不確定性推理，從樣本數據中準確高效地學習概率圖模型是其在實際應用中的關鍵問題。概率圖模型的表示由參數和結構兩部分組成。

（1）根據邊有無方向性分類；

根據邊有無方向性，PGM可以分為三類

1.有向圖模型，也稱為貝葉斯網（BayesianNetwork，BN），其網絡結構使用有向無環圖；

2.無向圖模型，也稱為馬爾可夫網（MarkovNetwork，MN），其網絡結構為無向圖；

3. 局部有向模型，即同時存在有向邊和無向邊的模型，包括條件隨機場（ConditionalRandomField，CRF）和鏈圖（ChainGraph）。

（2）根據表示的抽象級別不同分類。

根據表示的抽象級別不同，PGM可分兩類：

1.基於隨機變量的概率圖模型，如貝葉斯網、馬爾可夫網、條件隨機場和鏈圖等；

2.基於模板的概率圖模型．這類模型根據應用場景不同又可分為兩種：

a.為暫態模型，包括動態貝葉斯網（Dynamic Bayesian Network，DBN）和狀態觀測模型，其中狀態觀測模型又包括線性動態系統（Linear Dynamic System，LDS）和隱馬爾可夫模型（Hidden Markov Model，HMM）；

b.為對象關係領域的概率圖模型，包括盤模型（Plate Model，PM）、概率關係模型（Probabilistic Relational Model，PRM）和關係馬爾可夫網（Relational Markov Network，RMN）。 ^[4] 

總結如下 ：

（1）單個節點上的條件概率分佈的表示模型及其引起的獨立性，包括表格CPD、確定性CPD、特定上下文CPD、因果影響CPD、高斯模型和混合模型，並把單個分佈模型推廣到指數分佈族中。

（2）貝葉斯網絡中的獨立性以及圖與概率分佈的關係，高斯分佈和指數分佈族的貝葉斯網絡表示理論。馬爾可夫網絡的參數化問題及其獨立性，高斯分佈和指數分佈族的馬爾可夫網絡表示理論。

（3）兩種局部有向圖模型：條件隨機場和鏈圖。

（4）基於模板的概率模型表示，包括動態貝葉斯網絡和狀態觀測模型這兩種暫態模型。

（5）盤模型和概率關係模型這兩種對象關係領域的有向概率模型，對象關係領域的無向表示。 ^[1] 

概率圖模型學習算法分為參數學習與結構學習。基於概率圖模型學習分為概率網絡的參數學習與結構學習算法，並根據數據集是否完備而分為確定性不完備，隨機性不完備各種情況下的參數學習算法，針對結構學習算法特點的不同，結構學習算法歸納為基於約束的學習、基於評分搜索的學習、混合學習、動態規劃結構學習、模型平均結構學習和不完備數據集的結構學習。

結構學習仍然是機器學習中一個極具挑戰性的方向。結構學習並沒有固定的形式，不同的研究者往往會採取不同的途徑。比如，結構學習中一個非常重要的問題，就是如何去發現變量之間的內部關聯。對於這個問題，人們提出了多種截然不同的方法：比如，你可以先建立一個完全圖連接所有的變量，然後選擇一個子圖來描述它們的實際結構，又或者，你可以引入潛在節點(latent node)來建立變量之間的關聯。

Probabilistic Graphical Model的另外一個重要的發展方向是非參數化。與傳統的參數化方法不同，非參數化方法是一種更為靈活的建模方式——非參數化模型的大小（比如節點的數量）可以隨着數據的變化而變化。一個典型的非參數化模型就是基於狄利克萊過程(Dirichlet Process)的混合模型。這種模型引入狄利克萊過程作為部件(component)參數的先驗分佈，從而允許混合體中可以有任意多個部件。這從根本上克服了傳統的有限混合模型中的一個難題，就是確定部件的數量。在近幾年的文章中，非參數化模型開始被用於特徵學習。在這方面，比較有代表性的工作就是基於Hierarchical Beta Process來學習不定數量的特徵。 ^[3] 

根據網絡結構與查詢問題類型的不同，概率圖模型的推理算法有：

（1）貝葉斯網絡與馬爾可夫網絡中解決概率查詢問題的精確推理算法與近似推理算法,其中具體包括精確推理中的VE算法、遞歸約束算法和團樹算法,以及近似推理中的變分近似推理和抽樣近似推理算法；

（2）解決MAP查詢問題的常用推理算法；

（3）混合網絡的連續與混合情況闡述其推理算法；

（4）暫態網絡的精確推理、近似推理以及混合情況下的推理。 ^[5] 

除了最簡單的一些模型，統計推斷在計算上是非常困難的。一般而言，確切推斷(exact inference)的複雜度取決於模型的tree width。對於很多實際模型，這個複雜度可能隨着問題規模增長而指數增長。於是，人們退而求其次，轉而探索具有多項式複雜度的近似推斷(approximate inference)方法。

主流的近似推斷方法有三種：

（1）基於平均場逼近(mean field approximation)的variational inference。這種方法通常用於由Exponential family distribution所組成的貝葉斯網絡。其基本思想就是引入一個computationally tractable的upper bound逼近原模型的log partition function，從而有效地降低了優化的複雜度。EM算法就屬於這類型算法的一種特例。

（2）Belief propagation。這種方法最初由Judea Pearl提出用於樹狀結構的統計推斷。後來人們直接把這種算法用於帶環的模型（忽略掉它本來對樹狀結構的要求）——在很多情況下仍然取得不錯的實際效果，這就是loop belief propagation。在進一步的探索的過程中，人們發現了它與Bethe approximation的關係，並由此逐步建立起了對loopy belief propagation的理論解釋，以及刻畫出它在各種設定下的收斂條件。值得一提的是，由於Judea Pearl對人工智能和因果關係推斷方法上的根本性貢獻，他在2011年獲得了計算機科學領域的最高獎——圖靈獎。

基於message passing的方法在最近十年有很多新的發展。Martin Wainwright在2003年提出Tree-reweighted message passing，這種方法採用mixture of trees來逼近任意的graphical model，並利用mixture coefficient和edge probability之間的對偶關係建立了一種新的message passing的方法。這種方法是對belief propagation的推廣。Jason Johnson等人在2005年建立的walk sum analysis為高斯馬爾可夫隨機場上的belief propagation提供了系統的分析方法。這種方法成功刻畫了belief propagation在高斯場上的收斂條件，也是後來提出的多種改進型的belief propagation的理論依據。Thomas Minka在他PhD期間所建立的expectation propagation也是belief propagation的在一般Graphical Model上的重要推廣。

（3）蒙特卡羅採樣(Monte Carlo sampling)。與基於優化的方法不同，蒙特卡羅方法通過對概率模型的隨機模擬運行來收集樣本，然後通過收集到的樣本來估計變量的統計特性（比如，均值）。採樣方法有三個方面的重要優點。第一，它提供了一種有嚴謹數學基礎的方法來逼近概率計算中經常出現的積分（積分計算的複雜度隨着空間維度的提高呈幾何增長）。第二，採樣過程最終獲得的是整個聯合分佈的樣本集，而不僅僅是對某些參數或者變量值的最優估計。這個樣本集近似地提供了對整個分佈的更全面的刻畫。比如，你可以計算任意兩個變量的相關係數。第三，它的漸近特性通常可以被嚴格證明。對於複雜的模型，由variational inference或者belief propagation所獲得的解一般並不能保證是對問題的全局最優解。在大部分情況下，甚至無法瞭解它和最優解的距離有多遠。如果使用採樣，只要時間足夠長，是可以任意逼近真實的分佈的。而且採樣過程的複雜度往往較為容易獲得理論上的保證。

蒙特卡羅方法本身也是現代統計學中一個非常重要的分支。對它的研究在過去幾十年來一直非常活躍。在機器學習領域中，常見的採樣方法包括Gibbs Sampling, Metropolis-Hasting Sampling (M-H),Importance Sampling, Slice Sampling, 以及Hamiltonian Monte Carlo。其中，Gibbs Sampling由於可以納入M-H方法中解釋而通常被視為M-H的特例——雖然它們最初的motivation是不一樣的。 ^[1]