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

概率圖模型介紹與計(jì)算01簡單介紹概率圖模型是圖論和概率論結(jié)合的產(chǎn)物，它的開創(chuàng)者是鼎鼎大名的JudeaPearl,我十分喜歡概率圖模型這個工具，它是一個很有力的多變量而且變量關(guān)系可視化的建模工具，主要包括兩個大方向：無向圖模型和有向圖模型。無向圖模型又稱馬氏網(wǎng)絡(luò)，它的應(yīng)用很多，有典型的基于馬爾科夫隨機(jī)場的圖像處理，圖像分割，立體匹配等，也有和機(jī)器學(xué)習(xí)結(jié)合求取模型參數(shù)的結(jié)構(gòu)化學(xué)習(xí)方法。嚴(yán)格的說他們都是在求后驗(yàn)概率:p(y|x)，即給定數(shù)據(jù)判定每種標(biāo)簽y的概率，最后選取最大的后驗(yàn)概率最大的標(biāo)簽作為預(yù)測結(jié)果。這個過程也稱概率推理(probabilisticinference〕。而有向圖的應(yīng)用也很廣，有向圖又稱貝葉斯網(wǎng)絡(luò)(bayesnetworks),說到貝葉斯就足以可以預(yù)見這個模型的應(yīng)用范圍咯，比方醫(yī)療診斷，絕大多數(shù)的機(jī)器學(xué)習(xí)等。但是它也有一些爭議的地方，說到這就回到貝葉斯派和頻率派幾百年的爭議這個大話題上去了，因?yàn)樨惾~斯派假設(shè)了一些先驗(yàn)概率，而頻率派認(rèn)為這個先驗(yàn)有點(diǎn)主觀，頻率派認(rèn)為模型的參數(shù)是客觀存在的，假設(shè)先驗(yàn)分布就有點(diǎn)武斷，用貝葉斯模型預(yù)測的結(jié)果就有點(diǎn)“水分”，不適用于比擬嚴(yán)格的領(lǐng)域，比方精密制造，法律行業(yè)等。好吧，如果不遵循貝葉斯觀點(diǎn)，前面講的所有機(jī)器學(xué)習(xí)模型都可以dismiss咯，我們就通過大量數(shù)據(jù)統(tǒng)計(jì)先驗(yàn)來彌補(bǔ)這點(diǎn)“缺陷”吧。無向圖和有向圖的例子如〔圖一〕所示：圖一(a)無向圖〔隱馬爾科夫〕(b)有向圖概率圖模型吸取了圖論和概率二者的長處，圖論在許多計(jì)算領(lǐng)域中扮演著重要角色，比方組合優(yōu)化，統(tǒng)計(jì)物理，經(jīng)濟(jì)等。圖的每個節(jié)點(diǎn)都可看成一個變量，每個變量有N個狀態(tài)〔取值范圍〕，節(jié)點(diǎn)之間的邊表示變量之間的關(guān)系，它除了可以作為構(gòu)建模型的語言外，圖還可以評價(jià)模型的復(fù)雜度和可行性，一個算法的運(yùn)行時(shí)間或者錯誤界限的數(shù)量級可以用圖的結(jié)構(gòu)性質(zhì)來分析，這句話說的范圍很廣，其實(shí)工程領(lǐng)域的很多問題都可以用圖來表示，最終轉(zhuǎn)換成一個搜索或者查找問題，目標(biāo)就是快速的定位到目標(biāo)，試問還有什么問題不是搜索問題？樹是圖，旅行商問題是基于圖，染色問題更是基于圖，他們具有不同的圖的結(jié)構(gòu)性質(zhì)。對于樹的時(shí)間復(fù)雜度我們是可以估算出來的，而概率圖模型的一開始的推理求解方法也是利用圖的結(jié)構(gòu)性質(zhì)，把復(fù)雜圖轉(zhuǎn)換成樹〔容易處理的圖〕的形式來求解，這個算法被稱為聯(lián)合樹算法〔junctiontreealgorithm〕。聯(lián)合樹算法簡單的說就是利用圖的條件獨(dú)立性質(zhì)把圖分解，然后以樹的形式組織，最后利用樹的良好操作性進(jìn)行推理求解〔消息傳遞〕，聯(lián)合樹算法是后續(xù)章節(jié)的重要的推理算法之一。但并不是所有的圖都能拆分成樹的形式，一般只有適宜的稀疏邊的圖才能轉(zhuǎn)成樹，因此聯(lián)合樹算法也有一定的限制。不能構(gòu)建聯(lián)合樹，那怎么推理求解？好在還有其他幾種方法，概率圖模型的第二個成分：概率，既然進(jìn)入了概率空間，那基于蒙特卡洛〔MCMC〕的采樣方法也就可以使用了，反正就是求最大后驗(yàn)概率，MCMC的求解方法也是經(jīng)常利用的工具，還有一些基于均值場(meanfield)以及變分方法(variationalmethod)的求解工具。這幾個求解方法的算法復(fù)雜度比擬如〔圖二〕所示：(圖二)

推理求解算法性能比擬〔圖二〕中的幾種求解方法也都是概率圖模型或者統(tǒng)計(jì)機(jī)器學(xué)習(xí)里經(jīng)常使用的方法，MCMC方法和變分方法都起源于統(tǒng)計(jì)物理，最近很火的深度學(xué)習(xí)也算是概率圖模型的一個應(yīng)用，盡管你要反對，我也要把它劃到概率圖模型下^.^，RBM,CRBM,DBM都是很特殊的概率圖模型，整個思路從建模到求解方法都是圍繞著求取圖模型節(jié)點(diǎn)的最大后驗(yàn)概率來開展的。MCMC求解方法就不說了，深度學(xué)習(xí)里已經(jīng)用的很多咯，而變分方法〔variationalmethod〕很有吸引力，andrewng的師傅MichaelJordan認(rèn)為把變分方法用在統(tǒng)計(jì)機(jī)器學(xué)習(xí)中的有希望的方法是把凸分析和極家族分布函數(shù)鏈接起來，既然有凸分析，那么就會伴隨著凸松弛(convexrelaxtion),因?yàn)閿?shù)據(jù)是離散的，具體可以看前面的關(guān)于凸松弛的博文介紹。另外還有一些圖模型特有的求解方法，比方beliefpropagation(sum-productalgorithm)n或者expectationpropagation等求解方法。上面算是對概率圖模型做了個簡單的介紹，接下的來的博文就是按照下面的提綱來記錄一下學(xué)習(xí)筆記，在盡量不違背honorcode的情況下，用原來Daphnekoller教授的作業(yè)來做輔助介紹。一、介紹圖模型定義二、利用基于變分方法的極家族和凸分析來求邊緣概率三、逼近求解方法，如belief-propagation、expectation-propagation等四、均值場求解方法等各種優(yōu)化求解方法五、結(jié)構(gòu)化學(xué)習(xí)02概率圖模型定義翻開Jordan和Wainwright著作的書，正文開始〔第二章〕就說概率圖模型的核心就是：分解〔factorization〕。確實(shí)是這樣的，對于復(fù)雜的概率圖模型，要在復(fù)雜交織的變量中求取某個變量的邊緣概率，常規(guī)的做法就是套用貝葉斯公式，積分掉其他不相干的變量，假設(shè)每個變量的取值狀態(tài)為N，如果有M個變量，那么一個圖模型的配置空間就有N^M，指數(shù)增長的哦，就這個配置空間已經(jīng)讓我們吃不消了，不可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算完成，求邊緣概率就沒方法開展下去了。此時(shí)分解就派上用場咯，我們想法找到一些條件獨(dú)立，使得整個概率圖模型分解成一個個的團(tuán)塊，然后求取團(tuán)塊的概率，這樣就可以把大區(qū)域的指數(shù)增長降為小區(qū)域的指數(shù)增長。畢竟100^20這樣的計(jì)算量比25*〔4^20〕的計(jì)算量大多咯。好了，不說這么抽象了，下面進(jìn)入正題：〔圖一〕〔圖二〕無向圖模型又稱馬爾科夫隨機(jī)場〔markovrandomfiled〕無向圖模型的分解就是通過團(tuán)塊〔clique〕來完成，所謂團(tuán)塊就是全連接的最大子圖，如〔圖二〕所示，(a)圖的｛1，2，3，4｝，｛4，5，6｝，｛6，7｝都是全連接的最大子圖，假設(shè)團(tuán)塊用C表示，為每個團(tuán)塊分配一個兼容函數(shù)(compatibilityfunction)，它的作用就是把團(tuán)塊取值狀態(tài)映射到正實(shí)值空間，說白了就是給這個團(tuán)塊一個度量，可以是概率，也可以是取值狀態(tài)和真實(shí)標(biāo)簽之間的差值平方和，根據(jù)應(yīng)用而定，這個兼容函數(shù)有時(shí)又被稱為勢函數(shù)〔potentialfunction〕,有了兼容函數(shù)，無向圖模型就可以通過〔公式二〕分解：〔公式二〕〔公式二〕中的Z是歸一化的常量，學(xué)名叫配分函數(shù)(partitionfunction)，一歸一化就成概率了，不歸一化不滿足概率和為1的性質(zhì)。為了能在圖模型中直觀的看到團(tuán)塊，可以用因子圖〔factorgraph〕來表示無向圖模型，如〔圖二〕(b)所示，和黑塊連接的頂點(diǎn)表示全部互相連接〔全連接〕，一個黑塊局部表示一個團(tuán)塊，所以上面分解又多了一個名字：因子分解(factorization)。上面說了很多枯燥的定義，目標(biāo)只有一個，引出兩種圖模型的分解公式：〔公式一〕和〔公式二〕，那為什么可以分解成那個樣子？現(xiàn)在通過兩個小例子說明一下：對于有向圖模型，如〔圖三〕所示模型，一個人的聰明程度〔Intelligence〕可以影響他的年級〔Grade:癡呆的讀高年級的概率低，聰明的一般走的比擬遠(yuǎn)〕，而且對他的成績〔SAT〕也有上下影響。當(dāng)我們知道一個人的聰明度后，年級和成績還有關(guān)系嗎？二本就根本沒有關(guān)系，在這里不要想多，其實(shí)很簡單，給定一個物體后，那么這個物體上的兩個屬性值就決定了，已經(jīng)存在的事實(shí)，所以二者是獨(dú)立的。樸素貝葉斯就是根據(jù)這個條件獨(dú)立做的分解?！矆D三〕另外注意一下，這里給定的是父親節(jié)點(diǎn)，〔公式一〕中也強(qiáng)調(diào)了這點(diǎn)，如果不給父親節(jié)點(diǎn)，條件獨(dú)立就變的稍微復(fù)雜一些，如〔圖四〕中有一個比〔圖三〕稍微復(fù)雜一些的有向圖模型：〔圖四〕在〔圖四〕中Difficulty表示試卷難度，Intelligence表示考生聰明度，如果什么都不給，這二者是獨(dú)立的，因?yàn)樵嚲黼y度和考生沒有關(guān)系，所謂的高考很難，但是這跟我有什么關(guān)系？我又不參加高考^.^，但是如果一旦給定空考生的年級〔grade〕,情況就變得不一樣了，比方考生考到了博士，如果他不聰明，那說明啥？說明卷子不難，水的很，如果卷子很難，考生一定很聰明，所以這中間有個因果推理關(guān)系。這就是Judeapeal提出的explainaway問題〔Eveniftwohiddencausesareindependentintheprior,theycanbecomedependentwhenweobserveaneffectthattheycanbothinfluence〕,在前面的博文《目標(biāo)檢測〔ObjectDetection〕原理與實(shí)現(xiàn)(三)》也解釋了這個問題，如果這個例子沒有解釋清楚，可以看下前面的例子。對于無向圖模型的條件獨(dú)立就要簡單一些，是從圖論的可達(dá)性〔reachability〕考慮，也可從圖的馬爾科夫性入手，如〔圖五〕所示：〔圖五〕〔圖五〕是個標(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我們都給定，那這個模型分解的團(tuán)塊都是相似的，每個圖塊都可以用一個通用的標(biāo)記來表示，因此圖模型里又提了一種盤子表示法〔platenotation〕，如〔圖六〕所示：〔圖六〕〔圖六〕不是表示的HMM的盤子模型，而是LDA模型的盤子模型，只是讓大家了解一下通用分解模版的表示方法，其實(shí)很多時(shí)候這個表示方法反而不是那么清晰，南加州大學(xué)有一個做機(jī)器學(xué)習(xí)的博士生就在吐槽這個表示方法，有興趣的可以去看看〔鏈接〕。今天算是了解一下概率圖模型的根本定義和兩個分解公式，這兩個分解公式只是給出了圖模型不好求概率的一個解決方法的切入點(diǎn)，下節(jié)就來學(xué)習(xí)一下概率圖模型如何通過分解來進(jìn)行邊緣概率推理求解。03圖模型推理算法這節(jié)了解一下概率圖模型的推理算法〔Inferencealgorithm〕，也就是如何求邊緣概率〔marginalizationprobability〕。推理算法分兩大類，第一類是準(zhǔn)確推理〔ExactInference〕,第二類就是近似推理〔ApproximateInference〕。準(zhǔn)確推理就是通過把分解的式子中的不相干的變量積分掉〔離散的就是求和〕；由于有向圖和無向圖都是靠積分不相干變量來完成推理的，準(zhǔn)確推理算法不區(qū)分有向圖和無向圖，這點(diǎn)也可以在準(zhǔn)確推理算法：和積算法〔sum-product〕里表達(dá)出來，值得一提的是有向圖必須是無環(huán)的，不然和積算法不好使用。如果有向圖包含了環(huán)，那就要使用近似推理算法來求解，近似推理算法包含處理帶環(huán)的和積算法〔”loopy”sum-product〕和樸素均值場算法〔naivemeanfield〕，下面就來了解下這兩種推理算法的工作原理。假設(shè)給一個無向圖，他包含數(shù)據(jù)節(jié)點(diǎn)X和標(biāo)簽Y,它可以分解成〔公式一〕的形式：〔公式一〕有些人一開始覺得〔公式一〕很奇怪，貌似和上一節(jié)的無向圖分解有點(diǎn)不一樣，其實(shí)是一樣的，稍微有點(diǎn)不同的是把不同的團(tuán)塊區(qū)分對待了，這里有兩種團(tuán)塊，比方〔公式一〕右邊第一項(xiàng)為哪一項(xiàng)歸一化常量配分函數(shù)，第二項(xiàng)可能是先驗(yàn)概率，而第二項(xiàng)就可能是給定標(biāo)簽時(shí)樣本的概率。這里用可能這個措辭，表示這些勢函數(shù)只是一個抽象的函數(shù)，他可以根據(jù)你的應(yīng)用來變化，它就是對兩種不同團(tuán)塊的度量。如果X的取值狀態(tài)只有兩個，那么配分函數(shù)可以寫成〔公式二〕的形式：〔公式二〕配分函數(shù)就是把所有變量都積分掉得到的最終的度量值，如果要求邊緣概率就要通過積分掉其他變量得到的度量值除以配分函數(shù)，例如我們要求〔圖一〕中的x1的邊緣概率P(x1)：〔圖一〕要求取P(x1),我們就要積分掉x2-x6這五個變量，寫成數(shù)學(xué)的形式如〔公式三〕所示：〔公式三〕如果你對代數(shù)分配率很熟悉，外面的加法符號大sigma可以分開寫成〔公式四〕的樣子：〔公式四〕其實(shí)〔公式四〕就是和積算法的雛形，因?yàn)榭梢院苊黠@的看出又有和又有積。有人可能要問積分掉變量的順序?yàn)槭裁词悄菢?？其?shí)這個沒有準(zhǔn)那么的，先積分掉哪個變量，積分的順序也會導(dǎo)致運(yùn)算量大小不一樣，求取最優(yōu)的積分變量順序是NP-hard的，下面用圖示演示下積分消除變量發(fā)生的事情。(01)(02)(03)(04)(05)〔圖二〕〔圖二〕中注意觀察下每次積分掉一個變量后，原來的團(tuán)塊就因?yàn)樯倭艘粋€變量變成了一個新的團(tuán)塊，新的團(tuán)塊使得圖被三角剖分了，尤其在倒數(shù)第二個圖更明顯，消除變量x4后形成新的團(tuán)塊〔x2,x3〕,使得x2,x3之間建立了一條連接〔藍(lán)線所示〕，這個三角化添加的邊在圖論里被成為弦〔chord〕，全部完成三角化的圖也稱端正圖〔moralgraph〕。而邊緣概率計(jì)算量的復(fù)雜度取決于剩下的變量形成的團(tuán)塊大小，如〔圖二〕中紅色的局部，變量消除的順序也會影響新團(tuán)塊的大小，尋找一個最優(yōu)的變量消除順序十分必要，但是尋找最優(yōu)的變量消除順序是NP-hard的，眼看著問題就沒法解決了，但如果圖模型是樹呢？樹這種圖模型具有良好的性質(zhì)，他的計(jì)算量不大，下面先叉開下話題去看下樹結(jié)構(gòu)的圖模型的邊緣概率求解方法：假設(shè)樹結(jié)構(gòu)的圖模型如〔圖三〕所示：〔圖三〕和〔公式一〕類似，這個樹結(jié)構(gòu)的圖模型的分布可以分解成〔公式一〕的形式，因?yàn)闃淇珊唵蔚姆纸獬晒?jié)點(diǎn)和邊，那么它分解的形式如〔公式五〕所示：〔公式五〕把上面所述的和積算法寫成一個通用的形式公式,如〔公式六〕所示：〔公式六〕這里注意下大sigma下標(biāo)中的豎線表示排除Xs這個變量，積分掉其他變量，最終得到Xs的邊緣概率?，F(xiàn)在問題來了，在〔圖三〕中，如果要求變量Xs的邊緣概率就要積分掉Xs周圍的其他四個變量〔Xt,Xw,Xu,Xv〕，這是由(公式五)中的團(tuán)塊決定的〔有邊相連〕,而要積分掉這周圍的四個變量就要繼續(xù)積分掉這四個變量周圍除Xs以外的其他相鄰變量，這是個遞歸過程。而動態(tài)規(guī)劃其實(shí)也是遞歸，所以本質(zhì)上和積算法〔sum-product〕是個非連續(xù)的動態(tài)規(guī)劃算法。下面用數(shù)學(xué)語言更進(jìn)一步的梳理下這個遞歸算法流程，先做幾個定義：對于任意的屬于V的節(jié)點(diǎn)變量s,它的臨域可以定義成〔公式七〕的樣子：〔公式七〕用表示和要計(jì)算邊緣概率節(jié)點(diǎn)變量相連的子樹，如變量s,但是子樹不能越過變量s,如〔圖三〕中的Tt,Tw,Tu,Tv都是子樹，每個子樹上的變量用表示，那么每個子樹又可以做團(tuán)塊分解，如〔公式八〕所示：〔公式八〕有了這些定義，我們就可以再重新梳理下剛剛的遞歸過程，要計(jì)算變量Xs的邊緣概率，就要計(jì)算其臨域上的邊緣概率，然后再臨域的臨域上的邊緣概率，其實(shí)就是子樹上的邊緣概率，最終會遞歸到整個樹的葉子節(jié)點(diǎn)上，葉子節(jié)點(diǎn)計(jì)算完成后傳到父親節(jié)點(diǎn)，以后依次向上傳，最終傳遞到變量Xs上，這個過程其實(shí)叫消息傳遞〔Message-Passing〕,有時(shí)也叫置信傳播〔BeliefPropagation〕,有了消息的概念，那〔公式八〕就可以變成〔公式九〕的樣子：〔公式九〕〔公式九〕中k表示歸一化常量，Mts表示從變量Xt傳向Xs的消息，其實(shí)就是從子樹上傳遞過來的，然后P表示子樹的子樹上傳遞過來的消息，引入消息的好處就是容易描述這個遞歸過程，另外也容易擴(kuò)展到其他帶環(huán)的圖上，因?yàn)閯討B(tài)規(guī)劃是遞歸的，遞歸用消息傳播來表示，那么帶環(huán)的圖用消息傳遞的方法求解，我們就說其實(shí)用了動態(tài)規(guī)劃算法，這個話題就不扯遠(yuǎn)了。另外有了消息傳播機(jī)制，上述的計(jì)算邊緣概率的方法還可以擴(kuò)展一下，使得可以同時(shí)計(jì)算所有節(jié)點(diǎn)的邊緣概率，這就使得計(jì)算速度大大提高。我們可以讓每個節(jié)點(diǎn)都同時(shí)沿著邊向其臨域傳送消息，消息如〔公式十〕所示：〔公式十〕這樣其實(shí)是傳播了2倍于邊數(shù)的消息，然后開始迭代，第二輪迭代時(shí)用第一輪傳播來過來的子樹上的消息更新當(dāng)前消息，然后依次迭代下去，迭代n次后，消息值收斂，這樣每個變量周圍的消息都已確定，就不需要遞歸了，套用下〔公式九〕就可以計(jì)算邊緣概率了。計(jì)算最大邊緣概率〔max-marginal〕也是類似的方法，只不過是在收斂收選取最大的邊緣概率而已，雖然簡單，但是應(yīng)用范圍很廣，因?yàn)楹芏鄷r(shí)候都是在尋找個極值，比方立體匹