概率圖模型介紹與計算

1、概率圖模型介紹與計算01 簡單介紹概率圖模型是圖論和概率論結(jié)合的產(chǎn)物，它的開創(chuàng)者是鼎鼎大名的Judea Pearl,我十分喜歡概率圖模型這個工具，它是一個很有力的多變量而且變量關(guān)系可視化的建模工具，主要包括兩個大方向：無向圖模型和有向圖模型。無向圖模型又稱馬氏網(wǎng)絡(luò)，它的應(yīng)用很多，有典型的基于馬爾科夫隨機場的圖像處理，圖像分割，立體匹配等，也有和機器學(xué)習(xí)結(jié)合求取模型參數(shù)的結(jié)構(gòu)化學(xué)習(xí)方法。嚴(yán)格的說他們都是在求后驗概率:p(y|x)，即給定數(shù)據(jù)判定每種標(biāo)簽y的概率，最后選取最大的后驗概率最大的標(biāo)簽作為預(yù)測結(jié)果。這個過程也稱概率推理(probabilistic inference）。而有向圖的應(yīng)用也很

2、廣，有向圖又稱貝葉斯網(wǎng)絡(luò)(bayes networks),說到貝葉斯就足以可以預(yù)見這個模型的應(yīng)用范圍咯，比如醫(yī)療診斷，絕大多數(shù)的機器學(xué)習(xí)等。但是它也有一些爭議的地方，說到這就回到貝葉斯派和頻率派幾百年的爭議這個大話題上去了，因為貝葉斯派假設(shè)了一些先驗概率，而頻率派認(rèn)為這個先驗有點主觀，頻率派認(rèn)為模型的參數(shù)是客觀存在的，假設(shè)先驗分布就有點武斷，用貝葉斯模型預(yù)測的結(jié)果就有點“水分”，不適用于比較嚴(yán)格的領(lǐng)域，比如精密制造，法律行業(yè)等。好吧，如果不遵循貝葉斯觀點，前面講的所有機器學(xué)習(xí)模型都可以dismiss咯，我們就通過大量數(shù)據(jù)統(tǒng)計先驗來彌補這點“缺陷”吧。無向圖和有向圖的例子如（圖一）所示：圖一 (

3、a)無向圖（隱馬爾科夫） (b)有向圖概率圖模型吸取了圖論和概率二者的長處，圖論在許多計算領(lǐng)域中扮演著重要角色，比如組合優(yōu)化，統(tǒng)計物理，經(jīng)濟等。圖的每個節(jié)點都可看成一個變量，每個變量有N個狀態(tài)（取值范圍），節(jié)點之間的邊表示變量之間的關(guān)系，它除了可以作為構(gòu)建模型的語言外，圖還可以評價模型的復(fù)雜度和可行性，一個算法的運行時間或者錯誤界限的數(shù)量級可以用圖的結(jié)構(gòu)性質(zhì)來分析，這句話說的范圍很廣，其實工程領(lǐng)域的很多問題都可以用圖來表示，最終轉(zhuǎn)換成一個搜索或者查找問題，目標(biāo)就是快速的定位到目標(biāo)，試問還有什么問題不是搜索問題？樹是圖，旅行商問題是基于圖，染色問題更是基于圖，他們具有不同的圖的結(jié)構(gòu)性質(zhì)。對于樹的

4、時間復(fù)雜度我們是可以估算出來的，而概率圖模型的一開始的推理求解方法也是利用圖的結(jié)構(gòu)性質(zhì)，把復(fù)雜圖轉(zhuǎn)換成樹（容易處理的圖）的形式來求解，這個算法被稱為聯(lián)合樹算法（junction tree algorithm）。聯(lián)合樹算法簡單的說就是利用圖的條件獨立性質(zhì)把圖分解，然后以樹的形式組織，最后利用樹的良好操作性進行推理求解（消息傳遞），聯(lián)合樹算法是后續(xù)章節(jié)的重要的推理算法之一。但并不是所有的圖都能拆分成樹的形式，一般只有合適的稀疏邊的圖才能轉(zhuǎn)成樹，因此聯(lián)合樹算法也有一定的限制。不能構(gòu)建聯(lián)合樹，那怎么推理求解？好在還有其他幾種方法，概率圖模型的第二個成分：概率，既然進入了概率空間，那基于蒙特卡洛（MCM

5、C）的采樣方法也就可以使用了，反正就是求最大后驗概率，MCMC的求解方法也是經(jīng)常利用的工具，還有一些基于均值場(mean field)以及變分方法(variational method)的求解工具。這幾個求解方法的算法復(fù)雜度比較如（圖二）所示：(圖二)  推理求解算法性能比較（圖二）中的幾種求解方法也都是概率圖模型或者統(tǒng)計機器學(xué)習(xí)里經(jīng)常使用的方法，MCMC方法和變分方法都起源于統(tǒng)計物理，最近很火的深度學(xué)習(xí)也算是概率圖模型的一個應(yīng)用，盡管你要反對，我也要把它劃到概率圖模型下.，RBM,CRBM,DBM都是很特殊的概率圖模型，整個思路從建模到求解方法都是圍繞著求取圖模型節(jié)點的最大后驗概率

6、來開展的。MCMC求解方法就不說了，深度學(xué)習(xí)里已經(jīng)用的很多咯，而變分方法（variational method）很有吸引力，andrew ng的師傅Michael Jordan認(rèn)為把變分方法用在統(tǒng)計機器學(xué)習(xí)中的有希望的方法是把凸分析和極家族分布函數(shù)鏈接起來，既然有凸分析，那么就會伴隨著凸松弛(convex relaxtion),因為數(shù)據(jù)是離散的，具體可以看前面的關(guān)于凸松弛的博文介紹。另外還有一些圖模型特有的求解方法，比如belief propagation(sum-product algorithm)n或者expectation propagation等求解方法。上面算是對概率圖模型做了個簡單

7、的介紹，接下的來的博文就是按照下面的提綱來記錄一下學(xué)習(xí)筆記，在盡量不違背honor code的情況下，用原來Daphne koller教授的作業(yè)來做輔助介紹。一、介紹圖模型定義二、利用基于變分方法的極家族和凸分析來求邊緣概率三、逼近求解方法，如belief-propagation、expectation-propagation等四、均值場求解方法等各種優(yōu)化求解方法五、結(jié)構(gòu)化學(xué)習(xí)02 概率圖模型定義翻開Jordan和Wainwright著作的書，正文開始（第二章）就說概率圖模型的核心就是：分解（factorization）。的確是這樣的，對于復(fù)雜的概率圖模型，要在復(fù)雜交織的變量中求取某個變量的邊

8、緣概率，常規(guī)的做法就是套用貝葉斯公式，積分掉其他不相干的變量，假設(shè)每個變量的取值狀態(tài)為N，如果有M個變量，那么一個圖模型的配置空間就有NM，指數(shù)增長的哦，就這個配置空間已經(jīng)讓我們吃不消了，不可以在多項式時間內(nèi)計算完成，求邊緣概率就沒辦法開展下去了。此時分解就派上用場咯，我們想法找到一些條件獨立，使得整個概率圖模型分解成一個個的團塊，然后求取團塊的概率，這樣就可以把大區(qū)域的指數(shù)增長降為小區(qū)域的指數(shù)增長。畢竟10020這樣的計算量比25*（420）的計算量大多咯。好了，不說這么抽象了，下面進入正題：（圖一）（圖二）無向圖模型又稱馬爾科夫隨機場（markov random filed）無向圖模型的分

9、解就是通過團塊（clique）來完成，所謂團塊就是全連接的最大子圖，如（圖二）所示，(a)圖的1，2，3，4，4，5，6，6，7都是全連接的最大子圖，假設(shè)團塊用C表示，為每個團塊分配一個兼容函數(shù)(compatibility function)，它的作用就是把團塊取值狀態(tài)映射到正實值空間，說白了就是給這個團塊一個度量，可以是概率，也可以是取值狀態(tài)和真實標(biāo)簽之間的差值平方和，根據(jù)應(yīng)用而定，這個兼容函數(shù)有時又被稱為勢函數(shù)（potential function）,有了兼容函數(shù)，無向圖模型就可以通過（公式二）分解：（公式二）（公式二）中的Z是歸一化的常量，學(xué)名叫配分函數(shù)(partition functi

10、on)，一歸一化就成概率了，不歸一化不滿足概率和為1的性質(zhì)。為了能在圖模型中直觀的看到團塊，可以用因子圖（factor graph）來表示無向圖模型，如（圖二）(b)所示，和黑塊連接的頂點表示全部互相連接（全連接），一個黑塊部分表示一個團塊，所以上面分解又多了一個名字：因子分解(factorization)。上面說了很多枯燥的定義，目標(biāo)只有一個，引出兩種圖模型的分解公式：（公式一）和（公式二），那為什么可以分解成那個樣子？現(xiàn)在通過兩個小例子說明一下：對于有向圖模型，如（圖三）所示模型，一個人的聰明程度（Intelligence）可以影響他的年級（Grade:癡呆的讀高年級的概率低，聰明的一般走

11、的比較遠），而且對他的成績（SAT）也有高低影響。當(dāng)我們知道一個人的聰明度后，年級和成績還有關(guān)系嗎？二本就根本沒有關(guān)系，在這里不要想多，其實很簡單，給定一個物體后，那么這個物體上的兩個屬性值就決定了，已經(jīng)存在的事實，所以二者是獨立的。樸素貝葉斯就是根據(jù)這個條件獨立做的分解。（圖三）另外注意一下，這里給定的是父親節(jié)點，（公式一）中也強調(diào)了這點，如果不給父親節(jié)點，條件獨立就變的稍微復(fù)雜一些，如（圖四）中有一個比（圖三）稍微復(fù)雜一些的有向圖模型：（圖四）在（圖四）中Difficulty表示試卷難度，Intelligence表示考生聰明度，如果什么都不給，這二者是獨立的，因為試卷難度和考生沒有關(guān)系，所

12、謂的高考很難，但是這跟我有什么關(guān)系？我又不參加高考.，但是如果一旦給定空考生的年級（grade）,情況就變得不一樣了，比如考生考到了博士，如果他不聰明，那說明啥？說明卷子不難，水的很，如果卷子很難，考生一定很聰明，所以這中間有個因果推理關(guān)系。這就是Judea peal提出的explain away問題（Even if two hidden causes are independent in the prior, they can become dependent when we observe an effect that they can both influence）,在前面的博文目標(biāo)檢測

13、（ObjectDetection）原理與實現(xiàn)(三)也解釋了這個問題，如果這個例子沒有解釋清楚，可以看下前面的例子。對于無向圖模型的條件獨立就要簡單一些，是從圖論的可達性（reachability）考慮，也可從圖的馬爾科夫性入手，如（圖五）所示：（圖五）（圖五）是個標(biāo)準(zhǔn)的隱馬爾科夫模型（HMM），當(dāng)給定X2時，就相當(dāng)于在X2除切了一刀，在X2前后之間的變量都相互獨立。獨立就可以分解了，比如條件概率獨立公式：P(A,B|C)=P(A|C)*P(B|C),團塊兼容函數(shù)也是如此。如果X1-X5我們都給定，那這個模型分解的團塊都是相似的，每個圖塊都可以用一個通用的標(biāo)記來表示，因此圖模型里又提了一種盤子表

14、示法（plate notation），如（圖六）所示：（圖六）（圖六）不是表示的HMM的盤子模型，而是LDA模型的盤子模型，只是讓大家了解一下通用分解模版的表示方法，其實很多時候這個表示方法反而不是那么清晰，南加州大學(xué)有一個做機器學(xué)習(xí)的博士生就在吐槽這個表示方法，有興趣的可以去看看（ 鏈接 ）。今天算是了解一下概率圖模型的基本定義和兩個分解公式，這兩個分解公式只是給出了圖模型不好求概率的一個解決方法的切入點，下節(jié)就來學(xué)習(xí)一下概率圖模型如何通過分解來進行邊緣概率推理求解。03 圖模型推理算法這節(jié)了解一下概率圖模型的推理算法（Inference algorithm），也就是如何

15、求邊緣概率（marginalization probability）。推理算法分兩大類，第一類是準(zhǔn)確推理（Exact Inference）,第二類就是近似推理（Approximate Inference）。準(zhǔn)確推理就是通過把分解的式子中的不相干的變量積分掉（離散的就是求和）；由于有向圖和無向圖都是靠積分不相干變量來完成推理的，準(zhǔn)確推理算法不區(qū)分有向圖和無向圖，這點也可以在準(zhǔn)確推理算法：和積算法（sum-product）里體現(xiàn)出來，值得一提的是有向圖必須是無環(huán)的，不然和積算法不好使用。如果有向圖包含了環(huán)，那就要使用近似推理算法來求解，近似推理算法包含處理帶環(huán)的和積算法（”loopy” sum-p

16、roduct）和樸素均值場算法（naive mean field），下面就來了解下這兩種推理算法的工作原理。假如給一個無向圖，他包含數(shù)據(jù)節(jié)點X和標(biāo)簽Y,它可以分解成（公式一）的形式：（公式一）有些人一開始覺得（公式一）很奇怪，貌似和上一節(jié)的無向圖分解有點不一樣，其實是一樣的，稍微有點不同的是把不同的團塊區(qū)分對待了，這里有兩種團塊，比如（公式一）右邊第一項是歸一化常量配分函數(shù)，第二項可能是先驗概率，而第二項就可能是給定標(biāo)簽時樣本的概率。這里用可能這個措辭，表示這些勢函數(shù)只是一個抽象的函數(shù)，他可以根據(jù)你的應(yīng)用來變化，它就是對兩種不同團塊的度量。如果X的取值狀態(tài)只有兩個，那么配分函數(shù)可以寫成（公式二

17、）的形式：（公式二）配分函數(shù)就是把所有變量都積分掉得到的最終的度量值，如果要求邊緣概率就要通過積分掉其他變量得到的度量值除以配分函數(shù)，例如我們要求（圖一）中的x1的邊緣概率P(x1)：（圖一）要求取P(x1),我們就要積分掉x2-x6這五個變量，寫成數(shù)學(xué)的形式如（公式三）所示：（公式三）如果你對代數(shù)分配率很熟悉，外面的加法符號大sigma可以分開寫成（公式四）的樣子：（公式四）其實（公式四）就是和積算法的雛形，因為可以很明顯的看出又有和又有積。有人可能要問積分掉變量的順序為什么是那樣？其實這個沒有準(zhǔn)則的，先積分掉哪個變量，積分的順序也會導(dǎo)致運算量大小不一樣，求取最優(yōu)的積分變量順序是NP-har

18、d的，下面用圖示演示下積分消除變量發(fā)生的事情。(01)(02)(03)(04)(05)（圖二）（圖二）中注意觀察下每次積分掉一個變量后，原來的團塊就因為少了一個變量變成了一個新的團塊，新的團塊使得圖被三角剖分了，尤其在倒數(shù)第二個圖更明顯，消除變量x4后形成新的團塊（x2,x3）,使得x2,x3之間建立了一條連接（藍線所示），這個三角化添加的邊在圖論里被成為弦（chord），全部完成三角化的圖也稱端正圖（moral graph）。而邊緣概率計算量的復(fù)雜度取決于剩下的變量形成的團塊大小，如（圖二）中紅色的部分，變量消除的順序也會影響新團塊的大小，尋找一個最優(yōu)的變量消除順序十分必要，但是尋找最優(yōu)的變

19、量消除順序是NP-hard的，眼看著問題就沒法解決了，但如果圖模型是樹呢？樹這種圖模型具有良好的性質(zhì)，他的計算量不大，下面先叉開下話題去看下樹結(jié)構(gòu)的圖模型的邊緣概率求解方法：假設(shè)樹結(jié)構(gòu)的圖模型如（圖三）所示：（圖三）和（公式一）類似，這個樹結(jié)構(gòu)的圖模型的分布可以分解成（公式一）的形式，因為樹可簡單的分解成節(jié)點和邊，那么它分解的形式如（公式五）所示：（公式五）把上面所述的和積算法寫成一個通用的形式公式,如（公式六）所示：（公式六）這里注意下大sigma下標(biāo)中的豎線表示排除Xs這個變量，積分掉其他變量，最終得到Xs的邊緣概率?，F(xiàn)在問題來了，在（圖三）中，如果要求變量Xs的邊緣概率就要積分掉Xs周圍

20、的其他四個變量（Xt,Xw,Xu,Xv），這是由(公式五)中的團塊決定的（有邊相連）,而要積分掉這周圍的四個變量就要繼續(xù)積分掉這四個變量周圍除Xs以外的其他相鄰變量，這是個遞歸過程。而動態(tài)規(guī)劃其實也是遞歸，所以本質(zhì)上和積算法（sum-product）是個非連續(xù)的動態(tài)規(guī)劃算法。下面用數(shù)學(xué)語言更進一步的梳理下這個遞歸算法流程，先做幾個定義：對于任意的屬于V的節(jié)點變量s,它的臨域可以定義成（公式七）的樣子：（公式七）用表示和要計算邊緣概率節(jié)點變量相連的子樹，如變量s,但是子樹不能越過變量s,如（圖三）中的Tt,Tw,Tu,Tv都是子樹，每個子樹上的變量用表示，那么每個子樹又可以做團塊分解，如（公式八

21、）所示：（公式八）有了這些定義，我們就可以再重新梳理下剛才的遞歸過程，要計算變量Xs的邊緣概率，就要計算其臨域上的邊緣概率，然后再臨域的臨域上的邊緣概率，其實就是子樹上的邊緣概率，最終會遞歸到整個樹的葉子節(jié)點上，葉子節(jié)點計算完成后傳到父親節(jié)點，以后依次向上傳，最終傳遞到變量Xs上，這個過程其實叫消息傳遞（Message-Passing）,有時也叫置信傳播（BeliefPropagation）,有了消息的概念，那（公式八）就可以變成（公式九）的樣子：（公式九）（公式九）中k表示歸一化常量，Mts表示從變量Xt傳向Xs的消息，其實就是從子樹上傳遞過來的，然后P表示子樹的子樹上傳遞過來的消息，引入消

22、息的好處就是容易描述這個遞歸過程，另外也容易擴展到其他帶環(huán)的圖上，因為動態(tài)規(guī)劃是遞歸的，遞歸用消息傳播來表示，那么帶環(huán)的圖用消息傳遞的方法求解，我們就說其實用了動態(tài)規(guī)劃算法，這個話題就不扯遠了。另外有了消息傳播機制，上述的計算邊緣概率的方法還可以擴展一下，使得可以同時計算所有節(jié)點的邊緣概率，這就使得計算速度大大提高。我們可以讓每個節(jié)點都同時沿著邊向其臨域傳送消息，消息如（公式十）所示：（公式十）這樣其實是傳播了2倍于邊數(shù)的消息，然后開始迭代，第二輪迭代時用第一輪傳播來過來的子樹上的消息更新當(dāng)前消息，然后依次迭代下去，迭代n次后，消息值收斂，這樣每個變量周圍的消息都已確定，就不需要遞歸了，套用下（公式九）就可以計算邊緣概率了。計算最大邊緣概率（max-marginal）也是類似的方法，只不過是在收斂收選取最大的邊緣概率而已，雖然簡單，但是應(yīng)用范圍很廣，因為很多時候都是在尋找個極值，比