[科普中國]-概率圖模型

概率圖模型

概率圖模型是一類用圖形模式表達(dá)基于概率相關(guān)關(guān)系的模型的總稱。概率圖模型結(jié)合概率論與圖論的知識，利用圖來表示與模型有關(guān)的變量的聯(lián)合概率分布。近10年它已成為不確定性推理的研究熱點，在人工智能、機(jī)器學(xué)習(xí)和計算機(jī)視覺等領(lǐng)域有廣闊的應(yīng)用前景。1

概率圖理論共分為三個部分，分別為概率圖模型表示理論，概率圖模型推理理論和概率圖模型學(xué)習(xí)理論。2

基本的概率圖模型包括貝葉斯網(wǎng)絡(luò)、馬爾可夫網(wǎng)絡(luò)和隱馬爾可夫網(wǎng)絡(luò)。

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

概率圖模型有很多好的性質(zhì)：它提供了一種簡單的可視化概率模型的方法，有利于設(shè)計和開發(fā)新模型；用于表示復(fù)雜的推理和學(xué)習(xí)運(yùn)算，可以簡化數(shù)學(xué)表達(dá)。3

概率圖模型表示理論概率圖模型的表示方法，研究如何利用概率網(wǎng)絡(luò)中的獨立性來簡化聯(lián)合概率分布的方法表示。概率圖模型能有效處理不確定性推理，從樣本數(shù)據(jù)中準(zhǔn)確高效地學(xué)習(xí)概率圖模型是其在實際應(yīng)用中的關(guān)鍵問題。概率圖模型的表示由參數(shù)和結(jié)構(gòu)兩部分組成，PGM的分類如圖1：

（1）根據(jù)邊有無方向性分類；

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

1.有向圖模型，也稱為貝葉斯網(wǎng)（BayesianNetwork，BN），其網(wǎng)絡(luò)結(jié)構(gòu)使用有向無環(huán)圖；

2.無向圖模型，也稱為馬爾可夫網(wǎng)（MarkovNetwork，MN），其網(wǎng)絡(luò)結(jié)構(gòu)為無向圖；

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

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

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

1.基于隨機(jī)變量的概率圖模型，如貝葉斯網(wǎng)、馬爾可夫網(wǎng)、條件隨機(jī)場和鏈圖等；

2.基于模板的概率圖模型．這類模型根據(jù)應(yīng)用場景不同又可分為兩種：

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

b.為對象關(guān)系領(lǐng)域的概率圖模型，包括盤模型（Plate Model，PM）、概率關(guān)系模型（Probabilistic Relational Model，PRM）和關(guān)系馬爾可夫網(wǎng)（Relational Markov Network，RMN）。4

總結(jié)如下 ：

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

（2）貝葉斯網(wǎng)絡(luò)中的獨立性以及圖與概率分布的關(guān)系，高斯分布和指數(shù)分布族的貝葉斯網(wǎng)絡(luò)表示理論。馬爾可夫網(wǎng)絡(luò)的參數(shù)化問題及其獨立性，高斯分布和指數(shù)分布族的馬爾可夫網(wǎng)絡(luò)表示理論。

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

（4）基于模板的概率模型表示，包括動態(tài)貝葉斯網(wǎng)絡(luò)和狀態(tài)觀測模型這兩種暫態(tài)模型。

（5）盤模型和概率關(guān)系模型這兩種對象關(guān)系領(lǐng)域的有向概率模型，對象關(guān)系領(lǐng)域的無向表示。1

概率圖模型學(xué)習(xí)理論概率圖模型學(xué)習(xí)算法分為參數(shù)學(xué)習(xí)與結(jié)構(gòu)學(xué)習(xí)?；诟怕蕡D模型學(xué)習(xí)分為概率網(wǎng)絡(luò)的參數(shù)學(xué)習(xí)與結(jié)構(gòu)學(xué)習(xí)算法，并根據(jù)數(shù)據(jù)集是否完備而分為確定性不完備，隨機(jī)性不完備各種情況下的參數(shù)學(xué)習(xí)算法，針對結(jié)構(gòu)學(xué)習(xí)算法特點的不同，結(jié)構(gòu)學(xué)習(xí)算法歸納為基于約束的學(xué)習(xí)、基于評分搜索的學(xué)習(xí)、混合學(xué)習(xí)、動態(tài)規(guī)劃結(jié)構(gòu)學(xué)習(xí)、模型平均結(jié)構(gòu)學(xué)習(xí)和不完備數(shù)據(jù)集的結(jié)構(gòu)學(xué)習(xí)。

結(jié)構(gòu)學(xué)習(xí)仍然是機(jī)器學(xué)習(xí)中一個極具挑戰(zhàn)性的方向。結(jié)構(gòu)學(xué)習(xí)并沒有固定的形式，不同的研究者往往會采取不同的途徑。比如，結(jié)構(gòu)學(xué)習(xí)中一個非常重要的問題，就是如何去發(fā)現(xiàn)變量之間的內(nèi)部關(guān)聯(lián)。對于這個問題，人們提出了多種截然不同的方法：比如，你可以先建立一個完全圖連接所有的變量，然后選擇一個子圖來描述它們的實際結(jié)構(gòu)，又或者，你可以引入潛在節(jié)點(latent node)來建立變量之間的關(guān)聯(lián)。

Probabilistic Graphical Model的另外一個重要的發(fā)展方向是非參數(shù)化。與傳統(tǒng)的參數(shù)化方法不同，非參數(shù)化方法是一種更為靈活的建模方式——非參數(shù)化模型的大?。ū热绻?jié)點的數(shù)量）可以隨著數(shù)據(jù)的變化而變化。一個典型的非參數(shù)化模型就是基于狄利克萊過程(Dirichlet Process)的混合模型。這種模型引入狄利克萊過程作為部件(component)參數(shù)的先驗分布，從而允許混合體中可以有任意多個部件。這從根本上克服了傳統(tǒng)的有限混合模型中的一個難題，就是確定部件的數(shù)量。在近幾年的文章中，非參數(shù)化模型開始被用于特征學(xué)習(xí)。在這方面，比較有代表性的工作就是基于Hierarchical Beta Process來學(xué)習(xí)不定數(shù)量的特征。3

概率圖模型的推理算法根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)與查詢問題類型的不同，概率圖模型的推理算法有：

（1）貝葉斯網(wǎng)絡(luò)與馬爾可夫網(wǎng)絡(luò)中解決概率查詢問題的精確推理算法與近似推理算法,其中具體包括精確推理中的VE算法、遞歸約束算法和團(tuán)樹算法,以及近似推理中的變分近似推理和抽樣近似推理算法；
（2）解決MAP查詢問題的常用推理算法；
（3）混合網(wǎng)絡(luò)的連續(xù)與混合情況闡述其推理算法；
（4）暫態(tài)網(wǎng)絡(luò)的精確推理、近似推理以及混合情況下的推理。5

基于Graphical Model 的統(tǒng)計推斷除了最簡單的一些模型，統(tǒng)計推斷在計算上是非常困難的。一般而言，確切推斷(exact inference)的復(fù)雜度取決于模型的tree width。對于很多實際模型，這個復(fù)雜度可能隨著問題規(guī)模增長而指數(shù)增長。于是，人們退而求其次，轉(zhuǎn)而探索具有多項式復(fù)雜度的近似推斷(approximate inference)方法。

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

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

（2）Belief propagation。這種方法最初由Judea Pearl提出用于樹狀結(jié)構(gòu)的統(tǒng)計推斷。后來人們直接把這種算法用于帶環(huán)的模型（忽略掉它本來對樹狀結(jié)構(gòu)的要求）——在很多情況下仍然取得不錯的實際效果，這就是loop belief propagation。在進(jìn)一步的探索的過程中，人們發(fā)現(xiàn)了它與Bethe approximation的關(guān)系，并由此逐步建立起了對loopy belief propagation的理論解釋，以及刻畫出它在各種設(shè)定下的收斂條件。值得一提的是，由于Judea Pearl對人工智能和因果關(guān)系推斷方法上的根本性貢獻(xiàn)，他在2011年獲得了計算機(jī)科學(xué)領(lǐng)域的最高獎——圖靈獎。

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

（3）蒙特卡羅采樣(Monte Carlo sampling)。與基于優(yōu)化的方法不同，蒙特卡羅方法通過對概率模型的隨機(jī)模擬運(yùn)行來收集樣本，然后通過收集到的樣本來估計變量的統(tǒng)計特性（比如，均值）。采樣方法有三個方面的重要優(yōu)點。第一，它提供了一種有嚴(yán)謹(jǐn)數(shù)學(xué)基礎(chǔ)的方法來逼近概率計算中經(jīng)常出現(xiàn)的積分（積分計算的復(fù)雜度隨著空間維度的提高呈幾何增長）。第二，采樣過程最終獲得的是整個聯(lián)合分布的樣本集，而不僅僅是對某些參數(shù)或者變量值的最優(yōu)估計。這個樣本集近似地提供了對整個分布的更全面的刻畫。比如，你可以計算任意兩個變量的相關(guān)系數(shù)。第三，它的漸近特性通?？梢员粐?yán)格證明。對于復(fù)雜的模型，由variational inference或者belief propagation所獲得的解一般并不能保證是對問題的全局最優(yōu)解。在大部分情況下，甚至無法了解它和最優(yōu)解的距離有多遠(yuǎn)。如果使用采樣，只要時間足夠長，是可以任意逼近真實的分布的。而且采樣過程的復(fù)雜度往往較為容易獲得理論上的保證。

蒙特卡羅方法本身也是現(xiàn)代統(tǒng)計學(xué)中一個非常重要的分支。對它的研究在過去幾十年來一直非?；钴S。在機(jī)器學(xué)習(xí)領(lǐng)域中，常見的采樣方法包括Gibbs Sampling, Metropolis-Hasting Sampling (M-H),Importance Sampling, Slice Sampling, 以及Hamiltonian Monte Carlo。其中，Gibbs Sampling由于可以納入M-H方法中解釋而通常被視為M-H的特例——雖然它們最初的motivation是不一樣的。1