機(jī)器學(xué)習(xí)---概率圖模型(推理：消息傳遞算法)

機(jī)器學(xué)習(xí)——概率圖模型〔推理：消息傳遞算法〕概率圖模型G(V,E)由節(jié)點(diǎn)V和邊E構(gòu)成。在之前馬爾科夫模型相關(guān)的博客中，我談到馬爾科夫模型的本質(zhì)是當(dāng)兩個人交流后，其意見〔兩個隨機(jī)變量〕同意0與不同意1的概率組合。而勢函數(shù)表達(dá)的是兩個意見相同或者相左的程度。我們搞的那么麻煩，最后想要得到的不就是每個意見正確與否〔隨機(jī)變量取不同值的概率〕嗎？與其采用解析的方法去算，去把所有其他的變量邊際掉，那干脆采用模擬的方法，讓這個消息傳遞跑起來，把系統(tǒng)迭代N次以后的結(jié)果拿出來分析。這種樸素〔Naive〕的想法，就是MessagePassing算法。1.聚類圖在執(zhí)行消息傳遞之前，我們需要指定兩件事情：1.掌握消息的人有哪些，手里都有哪些消息。2.他把這個消息告訴了誰。為了解答這兩個問題，需要從我們手里僅有的材料去構(gòu)造。P(ABCD)=P(AB)*P(BC)*P(CD)*P(DA)

-------

這里的P是未歸一化的概率。通過這個聯(lián)合概率計(jì)算式，我們獲得一種叫做聚類圖的全新圖模型。從概率圖到聚類圖如下所示。其中，聚類圖中存在Cluster和Edge.Cluster就是掌握消息的人，Cluster里的內(nèi)容就是人所掌握的消息。Edge連接了兩個交互消息的人，Edge上是兩個人交換的消息。當(dāng)然，聚類圖不僅僅是這么簡單的結(jié)構(gòu)。還有更復(fù)雜的聚類圖如下.勢函數(shù)表達(dá)的是兩個人意見相同或者相左的程度，兩個勢函數(shù)相乘那么會表達(dá)多個消息相同或相左的程度。多個勢函數(shù)相乘可以成為某個人的消息函數(shù)。對于聚類圖，有以下性質(zhì)：1.C(Clusters)由節(jié)點(diǎn)組成。2.邊上傳遞的消息，是兩個C的交集〔必須要兩個人同時知道的消息才能交流〕。3.消息函數(shù)是勢函數(shù)的乘積?？偨Y(jié)一下：消息是隨機(jī)變量，并且都是相關(guān)的。人掌握消息之間的關(guān)系。人和人之間可以傳遞消息。我們假設(shè)消息A:明天下雨B:明天下雪C:地上有水

那么人們一般都會認(rèn)為A1B1C1的可能性肯定大于A1B1C0。而E有可能是明天有灑水車。總之，不同的人掌握著不同的消息。消息與消息之間會相互影響。2.消息傳遞有了消息之后，兩個都知道同一件事情的人就會交流和這件事有關(guān)的內(nèi)容，比方2會告訴1關(guān)于C(地上有沒有水)的事情，這會改變1對消息C的看法〔概率〕。我們把消息傳遞寫成以下形式。i->j表示消息從i傳遞到j(luò)。Sij表示被傳遞的消息。通式的物理意義有以下三點(diǎn)：1.消息從i傳遞到j(luò)，i會綜合所有人給他說的信息〔把所有的δ相乘〕2.加上自己對消息組合的認(rèn)知〔把

δ相乘的結(jié)果乘以消息之間的關(guān)系〕3.去除掉不需要傳遞的局部〔把其他變量邊際掉〕以上循環(huán)一定次數(shù)后，到達(dá)某種穩(wěn)定狀態(tài)。最終計(jì)算某個人對所有消息的看法Belief〔所有穩(wěn)態(tài)輸入消息δ乘以消息關(guān)系〕這種算法會和精確解法存在一定偏差，故此僅為一種近似算法。3.聚類圖的性質(zhì)不是隨便一幅圖都可以作為聚類圖。聚類圖有3個根本要素：1.每個勢函數(shù)都被使用，且被使用一次。2.聚類圖中消息傳遞不能形成環(huán)。3.每個消息如果存在兩個知道的人，這兩個人必須要有交流途徑關(guān)于第一點(diǎn)，勢函數(shù)描述了消息之間的關(guān)系，如果漏了，那么失去了消息之間的某個信息，如果重復(fù)使用，那么某種關(guān)系被多余的加強(qiáng)了。第二點(diǎn)那么比擬有意思，其實(shí)際上描述的是一個正反應(yīng)的情況。假設(shè)有個人，編了一個謊話：明天會下雨。并且把這個謊話告訴了A，然后A又告訴B，B->C,C-D。如果恰好編這個謊話的人正好和D認(rèn)識，又正好交流了明天是否會下雨的情況。那么就“謊話到最后自己都信了”。這就對“明天下雨”這個隨機(jī)變量的概率產(chǎn)生較大的估計(jì)偏差。簡而言之就是，消息不能成環(huán)。第三點(diǎn)要表達(dá)的是，如果甲乙兩個人都知道一件事情A，那么他們一定要有交流途徑，無論直接交流還是通過其他人轉(zhuǎn)達(dá)，總之消息A一定要有在甲乙兩人之間聯(lián)通的路徑。值得注意的一點(diǎn)是，明天下雨A和地上有水C之間可能存在較強(qiáng)的相關(guān)性，就算A沒有形成環(huán)，卻通過C形成了環(huán)，最終也會對結(jié)果產(chǎn)生較大影響。比方圖中，xy強(qiáng)相關(guān)時，消息傳遞算法的表現(xiàn)并不好。有一種一定能夠滿足上訴性質(zhì)的聚類圖成為BetheClustersGraph。在使用消息傳遞算法時，優(yōu)先考慮構(gòu)造此聚類圖。該聚類圖中有兩種不同的人，一種掌握多個消息，一種掌握單種消息。這樣的聚類圖一定不會存在環(huán)。其形式如下所示:4.傳播算法的性質(zhì)一群人交換意見，如果大家最后意見都相同了。比方甲乙都認(rèn)為明天下雨的概率是0.6，乙丙都認(rèn)為明天地上有水的概率是0.7.........這種情況稱為聚類圖校準(zhǔn)了。公式表示，邊際掉無關(guān)量，兩個人對交流消息的看法是一致的。意見相同還有一個說法，就是交流過程穩(wěn)定，也就是說，在經(jīng)過無數(shù)次迭代后，消息收斂了?！鬟f公式

————————δj-i與求和無關(guān)，因?yàn)椴辉谇蠛陀騼?nèi)，故可以乘出去。發(fā)現(xiàn)i,j是對稱輪換的——————————最終得出收斂和校準(zhǔn)是等價的——————————一種新的符號————