03 圖模型推理算法

?

? ? ? ? ?這節(jié)了解一下概率圖模型的推理算法（Inference algorithm），也就是如何求邊緣概率（marginalization probability）。推理算法分兩大類，第一類是準(zhǔn)確推理（Exact Inference）,第二類就是近似推理（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-product）和樸素均值場(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ù)可以寫成（公式二）的形式：

?

（公式二）

? ? ? ? 配分函數(shù)就是把所有變量都積分掉得到的最終的度量值，如果要求邊緣概率就要通過(guò)積分掉其他變量得到的度量值除以配分函數(shù)，例如我們要求（圖一）中的x1的邊緣概率P(x1)：

?

（圖一）

? ? ? ?要求取P(x1),我們就要積分掉x2-x6這五個(gè)變量，寫成數(shù)學(xué)的形式如（公式三）所示：

?

（公式三）

? ? ? ?如果你對(duì)代數(shù)分配率很熟悉，外面的加法符號(hào)大sigma可以分開(kāi)寫成（公式四）的樣子：

?

（公式四）

? ? ? ? 其實(shí)（公式四）就是和積算法的雛形，因?yàn)榭梢院苊黠@的看出又有和又有積。有些同學(xué)可能要問(wèn)積分掉變量的順序?yàn)槭裁词悄菢?#xff1f;其實(shí)這個(gè)沒(méi)有準(zhǔn)則的，先積分掉哪個(gè)變量，積分的順序也會(huì)導(dǎo)致運(yùn)算量大小不一樣，求取最優(yōu)的積分變量順序是NP-hard的，下面用圖示演示下積分消除變量發(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)的變量消除順序是NP-hard的，眼看著問(wèn)題就沒(méi)法解決了，但如果圖模型是樹(shù)呢？樹(shù)這種圖模型具有良好的性質(zhì)，他的計(jì)算量不大，下面先叉開(kāi)下話題去看下樹(shù)結(jié)構(gòu)的圖模型的邊緣概率求解方法：

? ? ? 假設(shè)樹(shù)結(jié)構(gòu)的圖模型如（圖三）所示：

?

（圖三）

? ? ? ?和（公式一）類似，這個(gè)樹(shù)結(jié)構(gòu)的圖模型的分布可以分解成（公式一）的形式，因?yàn)闃?shù)可簡(jiǎn)單的分解成節(jié)點(diǎn)和邊，那么它分解的形式如（公式五）所示：

?

（公式五）

? ? ? ?把上面所述的和積算法寫成一個(gè)通用的形式公式,如（公式六）所示：

?

（公式六）

? ? ? ? 這里注意下大sigma下標(biāo)中的豎線表示排除Xs這個(gè)變量，積分掉其他變量，最終得到Xs的邊緣概率。現(xiàn)在問(wèn)題來(lái)了，在（圖三）中，如果要求變量Xs的邊緣概率就要積分掉Xs周圍的其他四個(gè)變量（Xt,Xw,Xu,Xv），這是由(公式五)中的團(tuán)塊決定的（有邊相連）,而要積分掉這周圍的四個(gè)變量就要繼續(xù)積分掉這四個(gè)變量周圍除Xs以外的其他相鄰變量，這是個(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)塊分解，如（公式八）所示：

?

（公式八）

? ? ? ? 有了這些定義，我們就可以再重新梳理下剛才的遞歸過(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)的消息，引入消息的好處就是容易描述這個(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è)變量周圍的消息都已確定，就不需要遞歸了，套用下（公式九）就可以計(jì)算邊緣概率了。計(jì)算最大邊緣概率（max-marginal）也是類似的方法，只不過(guò)是在收斂收選取最大的邊緣概率而已，雖然簡(jiǎn)單，但是應(yīng)用范圍很廣，因?yàn)楹芏鄷r(shí)候都是在尋找個(gè)極值，比如立體匹配就是這個(gè)原理。

? ? ? ?說(shuō)完了樹(shù)結(jié)構(gòu)圖模型的和積算法，就要回來(lái)說(shuō)一般圖的和積算法了，通過(guò)上面可以看到樹(shù)結(jié)構(gòu)的圖模型具有容易計(jì)算的優(yōu)點(diǎn)，那對(duì)于一般圖模型如果能轉(zhuǎn)成樹(shù)也可以套用上面所述方法，我們可以把節(jié)點(diǎn)分組以團(tuán)塊的形式放在樹(shù)的節(jié)點(diǎn)上，但是要注意連續(xù)性，因?yàn)橐话銏D中的節(jié)點(diǎn)邊可以很復(fù)雜，比如有環(huán)的圖，那么一個(gè)節(jié)點(diǎn)變量就可以屬于多個(gè)團(tuán)塊。因此團(tuán)塊樹(shù)也要保持原有圖的這種特性，不然求解不正確，因此團(tuán)塊樹(shù)的定義就要來(lái)了，如（圖四）所示：

?

（圖四）

? ? ? ?這段話不好翻譯，也沒(méi)見(jiàn)過(guò)中文對(duì)應(yīng)的術(shù)語(yǔ)，因此只能直接貼圖了，滿足這種定義的團(tuán)塊樹(shù)又稱聯(lián)合樹(shù)，聯(lián)合樹(shù)其實(shí)就是說(shuō)滿足團(tuán)塊之間的連續(xù)性，每個(gè)相臨團(tuán)塊之間都有公共變量，又成分割變量(separator-S)，如（圖五）的C圖中的矩形所示：

?

（圖五）

? ? ? ?在（圖五）中a圖是有環(huán)的一般圖模型，要想把a(bǔ)圖轉(zhuǎn)成聯(lián)合樹(shù)圖，必須把其三角化，也就是說(shuō)每三個(gè)變量圍成一個(gè)環(huán)，多于3個(gè)的必須添加弦邊，這其實(shí)是回應(yīng)了上面最初的和積算法，Lauritzen在參考文獻(xiàn)[3]中也對(duì)這種處理方法給出了證明，有興趣的可以翻閱下。

? ? ? ?對(duì)于一般圖轉(zhuǎn)聯(lián)合樹(shù)的步驟來(lái)個(gè)總結(jié)，如（圖六）所示：

?

（圖六）

? ? ? ?聯(lián)合樹(shù)建立后，就可以把樹(shù)結(jié)構(gòu)的消息傳遞算法推廣到聯(lián)合樹(shù)上，樹(shù)的節(jié)點(diǎn)由原來(lái)的單一變量變成了團(tuán)塊，那如何傳遞消息？其實(shí)也簡(jiǎn)單，每次傳消息時(shí)積分掉和非公共變量的變量，然后用公共變量的消息傳遞就行了，如（圖七）所示：

?

（圖七）

? ? ? （圖七）中上半部分表示消息的內(nèi)容，套用樹(shù)結(jié)構(gòu)消息傳遞方式，迭代收斂就行了，不過(guò)能否收斂還是一個(gè)值得深究的問(wèn)題，今天就不展開(kāi)了，理解聯(lián)合樹(shù)算法的核心就是理解消息到底是什么，看的很暈的就帶著這個(gè)問(wèn)題再看一遍咯^.^，另外逼近推理的變分方法需要用到極家族函數(shù)和凸分析來(lái)做統(tǒng)一框架，因此下節(jié)開(kāi)始學(xué)習(xí)極家族函數(shù)。

參考文獻(xiàn)：

?

? ? [1] Graphical models, exponential families, and variational inference. Martin Wain wright and Michael Jordan
? ? [2] Probabilistic Graphical Models. Daphne Koller
? ? [3] ?Graphical Models.S. L. Lauritzen

轉(zhuǎn)載請(qǐng)注明來(lái)源：http://blog.csdn.net/marvin521/article/details/10858655

總結(jié)

以上是生活随笔為你收集整理的机器学习理论与实战（十五）概率图模型03的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。