概率圖模型介紹與計(jì)算

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

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

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

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

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

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

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

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

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

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

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

12、謂的高考很難，但是這跟我有什么關(guān)系？我又不參加高考.，但是如果一旦給定空考生的年級(jí)（grade）,情況就變得不一樣了，比如考生考到了博士，如果他不聰明，那說(shuō)明啥？說(shuō)明卷子不難，水的很，如果卷子很難，考生一定很聰明，所以這中間有個(gè)因果推理關(guān)系。這就是Judea peal提出的explain away問(wèn)題（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)檢測(cè)

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

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

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

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

17、）的形式：（公式二）配分函數(shù)就是把所有變量都積分掉得到的最終的度量值，如果要求邊緣概率就要通過(guò)積分掉其他變量得到的度量值除以配分函數(shù)，例如我們要求（圖一）中的x1的邊緣概率P(x1)：（圖一）要求取P(x1),我們就要積分掉x2-x6這五個(gè)變量，寫(xiě)成數(shù)學(xué)的形式如（公式三）所示：（公式三）如果你對(duì)代數(shù)分配率很熟悉，外面的加法符號(hào)大sigma可以分開(kāi)寫(xiě)成（公式四）的樣子：（公式四）其實(shí)（公式四）就是和積算法的雛形，因?yàn)榭梢院苊黠@的看出又有和又有積。有人可能要問(wèn)積分掉變量的順序?yàn)槭裁词悄菢?？其?shí)這個(gè)沒(méi)有準(zhǔn)則的，先積分掉哪個(gè)變量，積分的順序也會(huì)導(dǎo)致運(yùn)算量大小不一樣，求取最優(yōu)的積分變量順序是NP-har

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

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

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

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

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