機率圖模型是用圖來表示變數機率依賴關係的理論，結合機率論與圖論的知識，利用圖來表示與模型有關的變數的聯合機率分布。由圖靈獎獲得者Pearl開發出來。機率圖模型理論分為機率圖模型表示理論，機率圖模型推理理論和機率圖模型學習理論。近10年它已成為不確定性推理的研究熱點，在人工智慧、機器學習和計算機視覺等領域有廣闊的套用前景。
基本介紹
- 中文名：機率圖模型
- 外文名：probabilistic graphical model
- 英文簡寫：PGM
- 提出者：Pearl
- 定義：用圖形表示機率關係模型
- 套用領域：人工智慧、計算機視覺等
模型,表示理論,學習理論,推理算法,統計推斷,
模型
機率圖模型是一類用圖形模式表達基於機率相關關係的模型的總稱。機率圖模型結合機率論與圖論的知識，利用圖來表示與模型有關的變數的聯合機率分布。近10年它已成為不確定性推理的研究熱點，在人工智慧、機器學習和計算機視覺等領域有廣闊的套用前景。
機率圖理論共分為三個部分，分別為機率圖模型表示理論，機率圖模型推理理論和機率圖模型學習理論。
基本的Graphical Model 可以大致分為兩個類別：貝葉斯網路(Bayesian Network)和馬爾可夫隨機場(Markov Random Field)。它們的主要區別在於採用不同類型的圖來表達變數之間的關係：貝葉斯網路採用有向無環圖(Directed Acyclic Graph)來表達因果關係，馬爾可夫隨機場則採用無向圖(Undirected Graph)來表達變數間的相互作用。這種結構上的區別導致了它們在建模和推斷方面的一系列微妙的差異。一般來說，貝葉斯網路中每一個節點都對應於一個先驗機率分布或者條件機率分布，因此整體的聯合分布可以直接分解為所有單個節點所對應的分布的乘積。而對於馬爾可夫場，由於變數之間沒有明確的因果關係，它的聯合機率分布通常會表達為一系列勢函式（potential function）的乘積。通常情況下，這些乘積的積分並不等於1，因此，還要對其進行歸一化才能形成一個有效的機率分布——這一點往往在實際套用中給參數估計造成非常大的困難。
機率圖模型有很多好的性質：它提供了一種簡單的可視化機率模型的方法，有利於設計和開發新模型；用於表示複雜的推理和學習運算，可以簡化數學表達。
表示理論
機率圖模型的表示方法，研究如何利用機率網路中的獨立性來簡化聯合機率分布的方法表示。機率圖模型能有效處理不確定性推理，從樣本數據中準確高效地學習機率圖模型是其在實際套用中的關鍵問題。機率圖模型的表示由參數和結構兩部分組成，PGM的分類如圖1：
（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）。
總結如下 ：
（1）單個節點上的條件機率分布的表示模型及其引起的獨立性，包括表格CPD、確定性CPD、特定上下文CPD、因果影響CPD、高斯模型和混合模型，並把單個分布模型推廣到指數分布族中。
（3）兩種局部有向圖模型：條件隨機場和鏈圖。
（4）基於模板的機率模型表示，包括動態貝葉斯網路和狀態觀測模型這兩種暫態模型。
（5）盤模型和機率關係模型這兩種對象關係領域的有向機率模型，對象關係領域的無向表示。
學習理論
機率圖模型學習算法分為參數學習與結構學習。基於機率圖模型學習分為機率網路的參數學習與結構學習算法，並根據數據集是否完備而分為確定性不完備，隨機性不完備各種情況下的參數學習算法，針對結構學習算法特點的不同，結構學習算法歸納為基於約束的學習、基於評分搜尋的學習、混合學習、動態規劃結構學習、模型平均結構學習和不完備數據集的結構學習。
結構學習仍然是機器學習中一個極具挑戰性的方向。結構學習並沒有固定的形式，不同的研究者往往會採取不同的途徑。比如，結構學習中一個非常重要的問題，就是如何去發現變數之間的內部關聯。對於這個問題，人們提出了多種截然不同的方法：比如，你可以先建立一個完全圖連線所有的變數，然後選擇一個子圖來描述它們的實際結構，又或者，你可以引入潛在節點(latent node)來建立變數之間的關聯。
Probabilistic Graphical Model的另外一個重要的發展方向是非參數化。與傳統的參數化方法不同，非參數化方法是一種更為靈活的建模方式——非參數化模型的大小（比如節點的數量）可以隨著數據的變化而變化。一個典型的非參數化模型就是基於狄利克萊過程(Dirichlet Process)的混合模型。這種模型引入狄利克萊過程作為部件(component)參數的先驗分布，從而允許混合體中可以有任意多個部件。這從根本上克服了傳統的有限混合模型中的一個難題，就是確定部件的數量。在近幾年的文章中，非參數化模型開始被用於特徵學習。在這方面，比較有代表性的工作就是基於Hierarchical Beta Process來學習不定數量的特徵。
推理算法
根據網路結構與查詢問題類型的不同，機率圖模型的推理算法有：
（1）貝葉斯網路與馬爾可夫網路中解決機率查詢問題的精確推理算法與近似推理算法,其中具體包括精確推理中的VE算法、遞歸約束算法和團樹算法,以及近似推理中的變分近似推理和抽樣近似推理算法；
（2）解決MAP查詢問題的常用推理算法；
（3）混合網路的連續與混合情況闡述其推理算法；
（4）暫態網路的精確推理、近似推理以及混合情況下的推理。
（2）解決MAP查詢問題的常用推理算法；
（3）混合網路的連續與混合情況闡述其推理算法；
（4）暫態網路的精確推理、近似推理以及混合情況下的推理。
統計推斷
除了最簡單的一些模型，統計推斷在計算上是非常困難的。一般而言，確切推斷(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是不一樣的。
