初識貝葉斯

什么貝葉斯定理、貝葉斯方法、貝葉斯網(wǎng)絡(luò)這種，外行人一聽頭就疼，這完全沒有乘法分配律乘法結(jié)合律來的親民??！實際上，他確實不親民（攤手）

那我們就從如何著手去處理貝葉斯網(wǎng)絡(luò)為目標(biāo)，好好看，好好學(xué)（這是文章基于的框架結(jié)構(gòu)，在此基礎(chǔ)上進(jìn)行了補(bǔ)充說明）。

一、貝葉斯方法

咱先整抓球，一個不透明的帶子，里面有4個除了顏色完全相同的球：2紅1綠1藍(lán)。此時你去隨手抓，那問你抓到各個顏色球的概率是多少？我想是個正常人都會說：那不50%、25%、25%？這是不論你取多少次，概率θ始終不變的事件，即不隨觀察結(jié)果X的變化而變化。

顯然??！那不然會是什么呢？

這種觀點長期統(tǒng)治著人們，或者說，統(tǒng)治著正常人，這叫頻率派觀點。直到有個叫Thomas Bayes的人出來攪局。

1.1貝葉斯方法的提出

貝葉斯不介紹了，生前民間學(xué)術(shù)“屌絲”，身后顛覆了概率史啊。這里說一下他最終發(fā)表的一篇多年后轟動世界的文章：An essay towards solving a problem in the doctrine of chances（機(jī)遇理論中一個問題的解）

回到上面這個問題，袋子里取紅球的概率θ是多少？正常人都說50%，貝葉斯說“NO！”。他認(rèn)為取的紅球的概率是個不確定的值，因為其中含有機(jī)遇的成分。

是不是不好理解了？那我們換個例子來講（這個抓球有什么機(jī)遇，我也不懂，但大佬都以這些開頭，所以咱換個例子）

78澤干了兩年程序員，現(xiàn)在想自己創(chuàng)業(yè)開個外包公司。這個結(jié)果無非“走向人生巔峰”和“欠一屁股債”，要么成功要么失敗。現(xiàn)在我們大家來估計一下他成功的概率有多大？你們可能會說：“這誰啊，兩年就創(chuàng)業(yè)，嚇?biāo)麄€鬼，不可能的。成功幾率最多5%。”而我對他的為人比較了解，他有想法，有方法，有思路，還有毅力，能吃苦，還有情調(diào)，有凝聚力，還為他人著想等，那我就估計他成功的概率有75%以上。

這種不同于最開始的“非黑即白、非0即1”的思考方式，就是貝葉斯式的思考方式。

【頻率派】把需要推斷的參數(shù)θ看作是固定的未知常數(shù)，即概率雖然是未知的，但最起碼是確定的一個值，同時，樣本X是隨機(jī)的，即不管球幾紅幾綠，事件的概率θ一定。所以頻率派重點研究樣本空間，大部分的概率計算都是針對樣本X的分布；

【貝葉斯派】認(rèn)為參數(shù)θ是隨機(jī)變量，而樣本X是固定的。由于樣本X固定，所以他們重點研究的是參數(shù)θ的分布。

這樣，貝葉斯派提出了一個思考問題的固定模式：

先驗分布π（θ）+ 樣本信息X ==> 后驗分布π（θ|x）

這意味著，新觀察到的樣本信息將修正人們以前對事物的認(rèn)知。換而言之，在得到新的樣本信息前，人們對θ的認(rèn)知是先驗分布π（θ），在得到新的樣本信息X后，人們對θ的認(rèn)知受其影響變?yōu)棣校é葇x）。

先驗信息一般來源于經(jīng)驗和歷史資料，比如在S7以前的SKT VS RNG，解說總會根據(jù)歷年比賽結(jié)果進(jìn)行一個勝負(fù)的預(yù)判來相應(yīng)解說。但從S7,S8這兩個賽季后，發(fā)現(xiàn)韓國隊不行了！那么現(xiàn)在你再看SKT VS RNG，可就不一定了不是嗎？那是不是就是X影響了π（θ）得到了π（θ|x）。

后驗分布π（θ|x）一般也認(rèn)為是在給定樣本X的情況下的θ條件分布，而使π（θ|x）達(dá)到最大的值θMD，這個θMD稱謂最大后驗估計，類似于統(tǒng)計學(xué)的極大似然估計。

這里插曲一下，似然和概率，很多人其實都不明白這是啥區(qū)別。似然（likelihood）在非正式場合中和概率（probability）幾乎相同。但在統(tǒng)計學(xué)中完全不同。概率是在特定環(huán)境下某件事發(fā)生的可能性，也就是結(jié)果沒有產(chǎn)生之前依據(jù)環(huán)境所對應(yīng)的參數(shù)來預(yù)測某件事情發(fā)生的可能性；而似然正好相反，是在確定的結(jié)果下去推測產(chǎn)生這個結(jié)果的可能環(huán)境（參數(shù)）。

結(jié)果和參數(shù)相互對應(yīng)的時候，似然和概率在數(shù)值上是相等的。了解更多似然，點擊這里

當(dāng)然除了上述思考模式，還有舉世聞名的貝葉斯定理。

1.2貝葉斯定理

先回顧幾個名詞

條件概率（又稱后驗概率）就是事件A在另外一個事件B已經(jīng)發(fā)生的條件下發(fā)生的概率P（A|B）：

P(A|B)=\frac{P(A\cap B)}{P(B)}

自己花幾個圓圈就能推導(dǎo)出這個公式了。

聯(lián)合概率表示兩個事件共同發(fā)生的概率：

P(A\cap B) or P(A,B)

邊緣概率（又稱先驗概率）是某個事件發(fā)生的概率。邊緣概率是這樣得到的：在聯(lián)合概率中，把最終結(jié)果中那些不需要的事件通過合并成它們的全概率從而消去它們（對離散隨機(jī)變量用求和得全概率，連續(xù)隨機(jī)變量用積分得全概率），這稱為邊緣化（marginalization），比如A的邊緣概率表示為P（A）,B的邊緣概率表示為P（B）。

現(xiàn)在考慮問題：P（A|B）是在B發(fā)生的情況下A發(fā)生的可能性。

（1）首先，B發(fā)生之前，對事件A發(fā)生的基本概率判斷為A的先驗概率P（A）；

（2）其次，事件B發(fā)生后，我們對事件A發(fā)生概率重新評估，稱為A的后驗概率P（A|B）；

（3）類似，事件A發(fā)生前，對B的先驗概率P（B）；

（4）事件A發(fā)生后，B后驗概率P（B|A）。

貝葉斯定理如下：

P(A|B)=\frac{P(B|A)P(A)}{P(B)}

推導(dǎo)證明如下：

P(A\cap B)={P(B|A)}{P(A)}={P(A|B)}{P(B)}

上式兩邊同時除以P（B），若P（B）非零，變得到貝葉斯定理公式表達(dá)式。

上述為傳統(tǒng)的貝葉斯公式寫法，還有另一種寫法，稱之為貝葉斯推斷。

1.3貝葉斯推斷

對條件概率公式進(jìn)行變形，得到如下形式：

P(A|B)=P(A)*\frac{P(B|A)}{P(B)}

P（A）稱為先驗概率，P（A|B）為后驗概率，而P（B|A）/P（B）稱之為可能性函數(shù)（likelyhood），這是一個調(diào)整因子，使得預(yù)估概率更接近真實概率。

貝葉斯推斷的含義：我們先預(yù)估一個先驗概率，然后加入實驗結(jié)果，看這個實驗到底是增強(qiáng)還是削弱了先驗概率，由此得到更接近事實后驗概率。

這里，可能性函數(shù)>1，意味著先驗概率被增強(qiáng)，事件A的發(fā)生可能性變大；可能性函數(shù)=1,意味著B事件無助于判斷事件A的可能性；可能性函數(shù)<1，意味著先驗概率被削弱，事件A的可能性變小。

舉例加深理解：

【1】水果糖問題

兩個一模一樣的碗，一號碗中有30顆水果糖和10顆巧克力，二號碗有水果糖和巧克力各20顆?，F(xiàn)在隨機(jī)選擇一個碗，從中摸出一顆糖，發(fā)現(xiàn)時水果糖。請問這個水果糖來自一號碗的概率是多少？

解：我們假定，H1表示碗一，H2表示碗二，有條件已知P（H1）=P（H2），即在取出水果糖之前，這兩個碗被選中的概率相同。因此P（H1）=0.5，此為先驗概率。

再假定E表示水果糖，所以問題變?yōu)橐阎狤的情況下，來自碗一的概率有多大：求P（H1|E）。我們把這個稱為后驗概率，即E事件發(fā)生后，對P（H1）的修正。

根據(jù)條件概率公式，得到

P(H1|E)=\frac{P(H1,E)}{P(E)}=\frac{P(E|H1)P(H1)}{P(E)}=P(H1)\frac{P(E|H1)}{P(E)}

已知：P（H1）=0.5，P（E|H1）=0.75，那么求出P（E）就可以得到答案，根據(jù)全概率公式（推導(dǎo)根據(jù)條件概率公式推就行了）

P(x1,x2,...,xn)=P(x1)P(x2|x1)...P(xn|x1,x2,...,xn-1)

得到：

P(E)=P(E|H1)P(H1)+P(E|H2)P(H2)

將已知帶入得P（E）=0.625，最后將結(jié)果帶入原方程，得到P（H1|E）=0.6，也就是說取出水果糖后，H1事件的可能性得到了增強(qiáng)（P（E|H1）/P（E）=0.75/0.625=1.2>1）。

1.4應(yīng)用

貝葉斯公式還有一個最經(jīng)典也是目前最廣泛的應(yīng)用：拼音糾錯，谷歌的拼音檢查就是基于貝葉斯方法。

《人工智能：現(xiàn)代方法》作者之一Peter Norvig曾寫一篇介紹如何寫一個拼寫檢查的文章（原文），使用的也是貝葉斯方法。

用戶輸入一個單詞，可能拼寫正確，也可能拼寫錯誤。如果把拼寫正確的情況記做c，錯誤記做w，那么拼寫檢查要做的事情就是：在發(fā)生w的情況下，試圖推斷出c，換而言之，就是已知w，然后在若干個備選方案中，找出可能性最大的那個c，即求P（c|w）的最大值。

P(c|w)=P(w|c)*P(c)/P(w)

由于對于所有備選的c來說，對應(yīng)的都是同一個w，所以它們的P（w）相同，因此我們只需要最大化P（w|c）*P（c）。

其中P（c）表示某個正確的單詞出現(xiàn)的“概率”，它可以用“頻率”代替。如果我們有一個足夠大的文本庫，那么這個文本庫中每個單詞的出現(xiàn)頻率，就相當(dāng)于它的發(fā)生概率。某個詞的出現(xiàn)頻率越高，P（c）就越大。比如在你輸入一個錯誤的單詞“tes”的時候，系統(tǒng)更傾向于“tea”，而不是“tee”，因為tea更常見。

當(dāng)然這其中要是深究，還有更多的可能性，比如說錯誤字母與正確字母在鍵盤上的位置，也許你是按錯了所以會拼錯，但實際上你要拼寫的單詞就是那個頻率低的單詞，是不是？在這里，初學(xué)，咱先放一放。

P（w|c）表示在試圖拼寫c的情況下，出現(xiàn)拼寫錯誤w的概率。為了簡化問題，假定兩個單詞在字形上越接近，就越有可能拼錯，P（w|c）就越大。舉例來說，相差一個字母的拼法，就比相差兩個字母的拼法，發(fā)生概率越高。你想拼寫“july”，錯誤拼成“julw”的可能性就比錯拼成“jullw”高很多。一般把這種問題稱為“編輯距離”。

二、貝葉斯網(wǎng)絡(luò)

2.1貝葉斯網(wǎng)絡(luò)的定義

貝葉斯網(wǎng)絡(luò)（Bayesian Network），又稱信念網(wǎng)絡(luò)（Belief Network），或有向無環(huán)圖模型，十一中概率圖模型。它是一種模擬人類推理過程中因果關(guān)系的不確定性處理模型，其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一個有向無環(huán)圖（DAG，direvted acyclic graphical）。

貝葉斯網(wǎng)路中節(jié)點表示隨機(jī)變量，認(rèn)為有因果關(guān)系（或非條件獨立）的變量或命題則用剪頭來連接。

例如，假設(shè)節(jié)點E直接影響到節(jié)點H，即E-->H，則用從E指向H的箭頭建立節(jié)點E到節(jié)點H的有向?。‥，H），權(quán)值（即連接強(qiáng)度）用條件概率P（H|E）來表示。

簡而言之，把某個研究系統(tǒng)中涉及的隨機(jī)變量，根據(jù)是否條件獨立繪制在一個有向圖中，就形成了貝葉斯網(wǎng)絡(luò)。其主要用來描述隨機(jī)變量之間的條件依賴，用圈表示隨機(jī)變量（random variables），用箭頭表示條件依賴（conditional dependencies）。

關(guān)于隨機(jī)變量，這里不同于普通公式中的x，z那種未知數(shù)，之前專門研究過，但是參考的網(wǎng)址找不到了。隨手記了一些筆記，分享一下（字丑）：

手稿1：基本概念
手稿2：公式定理

令G=（I,E）表示一個有向無環(huán)圖（DAG），其中I代表圖形中所有的節(jié)點的集合，而E代表有向連接線段的集合，且令X=（Xi），i∈I為其有向無環(huán)圖中某一節(jié)點i所代表的隨機(jī)變量，若節(jié)點X的聯(lián)合概率可以表示成：

P(x)=\prod\nolimits_{i\in I}P(X_{i}|X_{pa(i)} )

則稱X為相對于一有向無環(huán)圖G的貝葉斯網(wǎng)絡(luò)，其中，pa（i）表示節(jié)點i的“因”，也可以理解為“父節(jié)點”。

2.2貝葉斯網(wǎng)絡(luò)的3種結(jié)構(gòu)形式

給訂如下圖所示的一個貝葉斯網(wǎng)絡(luò)：

示例網(wǎng)絡(luò)

由圖可知：

（1）x1，x2，......，x7的聯(lián)合分布為：

P(x1)P(x2)P(x3)P(x4|x1,x2,x3)P(x5|x1,x3)P(x6|x4)P(x7|x4,x5)

（2）x1和x2獨立（head-to-head）；

（3）x6和x7在x4給訂的條件下獨立（tail-to-tail）。

根據(jù)上圖，（1）很好理解，（2、3）所述的條件獨立是什么意思呢？其實2、3點是貝葉斯網(wǎng)絡(luò)中3個結(jié)構(gòu)的其中兩種。為了說清楚這個問題，需要引入D-Separation（D-分離）這個概念。

D-Separation是一種用來判斷變量是否條件獨立的圖形化方法。換而言之，對于一個DAG，D-Separation方法可以快速的判斷出兩個節(jié)點之間是否條件獨立。

2.2.1形式1：head-to-head

head-to-head

有：P（a，b，c）=P（a）* P（b）* P（c|a，b）成立，化簡如下：

P(a,b, c)=P(a)P(b)P(c|a,b)=P(a)P(b)\frac{P(c,a,b)}{P(a,b)}

在c未知的條件下，a、b被阻斷（blocked），是獨立的，稱之為head-to-head條件獨立，對應(yīng)本節(jié)圖1的x1，x2獨立。

2.2.2形式2：tail-to-tail

tail-to-tail

考慮c未知和已經(jīng)兩種情況：

1、在c未知的時候，有：P（a，b，c）=P（c）P（a|c）P（b|c），此時，無法得出P（a，b）=P（a）P（b），即c未知時，a、b不獨立；

2、在c已知的時候，有：P（a，b|c）=P（a，b，c）/ P（c），然后將P（a，b，c）=P（c）P（a|c）P（b|c）帶入此式中，得到：P（a，c|c）=P（a，b，c）/ P（c）=P（c）P（a|c）P（b|c）/P（c）=P（a|c）P（b|c），即c已知時，a、b獨立。

所以，在c給定的條件下，a、b被blocked，式獨立的，稱之為tail-to-tail條件獨立，對應(yīng)本節(jié)圖1中“x6，x7在x4給定的條件下獨立”。

2.2.3形式3：head-to-tail

head-to-tail

分c未知和已知兩種情況：

1、c未知時，有：P（a，b，c）=P（a）*P（c|a）*P（b|c），但無法推出P（a，b）=P（a）P（b），即c未知時，a、b不獨立；

2、c已知時，有：P（a，b|c）=P（a，b，c）/ P（c），且根據(jù)P（a，c）=P（a）P（c|a）=P（c）P（a|c），可化簡得到：P(a,b|c)=\frac{P(a,b,c)}{P(c)}=\frac{P(a)P(c|a)P(b|c)}{P(c)}=\frac{P(a,c)P(b|c)}{P(c)}=P(a|c)P(b|c)

所以在給定c的條件下，a、b被blocked，是獨立的，稱之為head-to-tail條件獨立。

head-to-tail其實就是一個鏈?zhǔn)骄W(wǎng)絡(luò)，在xi給定的條件下，xi+1的分布和x1，x2，...，xi-1條件獨立。這意味著什么？這說明xi+1的分布狀態(tài)只和xi有關(guān)，和其他變量都無關(guān)！通俗一點說，當(dāng)前狀態(tài)只跟上一狀態(tài)有關(guān)，跟上上次或上上上上上上上次狀態(tài)都無關(guān)！這種順次演變的隨機(jī)過程，就叫做馬爾科夫鏈（Markov chain）。有：

P(X_{n+1}=x|X_{0},X_{1},...,X_{n})=P(X_{n+1}=x|X_{n})

將上述節(jié)點推廣到節(jié)點集，則：對于任意的節(jié)點集A,B,C，考察所有通過A中任意節(jié)點到B中任意節(jié)點的路徑，若要求A，B條件獨立，則需要所有的路徑都被blocked，即滿足下列兩個前提之一：

A和B的“head-to-tail”和“tail-to-tail”路徑都通過C；

A和B的“head-to-head”路徑不通過C及C的子孫；

最后舉例說明上述D-Separation的3種情況（即貝葉斯網(wǎng)絡(luò)的3種結(jié)構(gòu)形式）：

結(jié)構(gòu)舉例說明

2.3因子圖

Factor Graph是概率圖的一種，概率圖有多重，最常見的就是Bayesian Network和Markov Random Fields（馬爾科夫隨機(jī)場）。

在概率圖中，求某個變量的邊緣分布是最常見的問題。這個問題有很多種求解方法，其中之一就是可以把Bayesian Network和Markov Random Fields轉(zhuǎn)換成Factor Graph，然后用sum-product算法求解。

以下圖為例：

貝葉斯網(wǎng)絡(luò)例

對于上圖，在一個人已經(jīng)呼吸困難（dyspnoea）的情況下，其抽煙（smoking）的概率是多少？

P（smoking | dyspnoea = yes）= ？

繼續(xù)推算如下：（這里我就不自己碼了，好多箭箭頭有點麻煩的，還是用原圖簡單明了）

推導(dǎo)過程

對上述推導(dǎo)過程作解釋如下：

1.第二行：對聯(lián)合概率關(guān)于b，x，c求和（在d=1的條件下），從而消去b，x，c，得到s和d=1的聯(lián)合概率；

2.第三行：最開始，所有變量都在sigma（d=1，b，x，c）的后面，但由于P（s）跟“d=1，b，x，c”都沒關(guān)系，可以提到式子的最前面。而且P（b|s）和x、c沒關(guān)系，所以也可以把它提出來，放到sigma（b）后，從而式子的右邊剩下sigma（x）和sigma（c）。

（ps：這塊看能看明白，至于為什么sigma（x）和sigma（c）不能寫在一起，我也，哈哈哈~等之后再來補(bǔ)空擋，這里先記著。）

上圖中Variable elimination表示的是變量消除的意思。為此引入因子圖的概念。

2.3.1因子圖的定義

定義異常的晦澀難懂，你光看著名字你就摸不著頭腦，所以咱先通俗來講，所謂因子圖就是對函數(shù)進(jìn)行因式分解得到的一種概率圖。一般內(nèi)含兩種節(jié)點：變量節(jié)點和函數(shù)節(jié)點。眾所周知，一個全局函數(shù)通過因式分解能夠分解為多個局部函數(shù)的乘積，這些局部函數(shù)和對應(yīng)的變量關(guān)系就體現(xiàn)在因子圖上。

舉例說明，現(xiàn)有一全局函數(shù)，其因式分解方程為：

g(x1,x2,x3,x4,x5)=f_{A}(x1)f_{B}(x2)f_{C}(x1,x2,x3)f_{D}(x3,x4) f_{E}(x3,x5)

其中fA、fB、fC、fD、fE為各函數(shù)，表示變量之間的關(guān)系，可以是條件概率也可以是其他關(guān)系（如Markov Random Fields中的勢函數(shù)）。

其因子圖為：

因子圖

在因子圖中，所有的頂點不是變量節(jié)點就是函數(shù)節(jié)點，邊線表示他們之間的函數(shù)關(guān)系。

提及馬爾科夫隨機(jī)場，就再補(bǔ)充一些概念：

我們知道，有向圖模型，稱之為貝葉斯網(wǎng)絡(luò)。但有些情況下，強(qiáng)制對某些節(jié)點之間的邊增加方向是不合適的。使用沒有方向的無向邊，形成了無向圖模型（Undirected Graphical Model,UGM），又被稱為馬爾科夫隨機(jī)場或者馬爾科夫網(wǎng)絡(luò)（MRF or Markov Network）。

DGM and UGM

回歸本文主旨，首先我們舉例說明如何把貝葉斯網(wǎng)絡(luò)（和MRF），以及把馬爾科夫鏈、隱馬爾科夫模型轉(zhuǎn)換成因子圖，以上圖為例，根據(jù)各個變量對應(yīng)的關(guān)系，可得：

P(u,w,x,y,z)=P(u)P(w)P(x|u,w)P(y|x)P(z|x)

其對應(yīng)的因子圖為（以下兩種皆可）：

因子圖

有上述例子總結(jié)出貝葉斯網(wǎng)絡(luò)構(gòu)造因子圖的方法：

·貝葉斯網(wǎng)絡(luò)中的一個因子對應(yīng)因子圖中的一個節(jié)點

·貝葉斯網(wǎng)絡(luò)中的每一個變量在因子圖上對應(yīng)邊或者半邊

·節(jié)點g和邊x相連當(dāng)且僅當(dāng)變量x出現(xiàn)在因子g中

我把繪圖的思考過程寫下來，你跟著畫一遍就會明白：

1.找出已存在的先驗概率，圖中為P（u）和P（w），那么因子對應(yīng)節(jié)點，所以先畫出P（u）和P（w）的節(jié)點，就是兩個框；然后因子P（u）中出現(xiàn)的變量是u，那么由P（u）節(jié)點引出一條邊，這條邊就是u，同理P（w）引出w邊；

先驗概率節(jié)點

2.發(fā)現(xiàn)因子P（x|u，w）知，x是u和w下的條件概率，故做節(jié)點P（x|u，w），然后將邊u和w與之相連，并有該節(jié)點引出x邊；

推導(dǎo)節(jié)點

3.有因子P（y|x）和P（z|x）發(fā)現(xiàn)基于條件x引出兩個變量y和z，那么此時需要將X邊拆分成兩條邊（我猜想這個可能就叫半邊，沒有專門去查），并分別接入到P（y|x）和P（z|x）節(jié)點，再由各自節(jié)點對應(yīng)引出y邊與z邊，結(jié)束作圖。

邊的拆分

對馬爾科夫鏈轉(zhuǎn)換的因子圖和隱馬爾科夫模型轉(zhuǎn)換而成的因子圖，做法相同。這里等以后專門講馬爾科夫的時候再仔仔細(xì)細(xì)說。這里把圖貼出來給大家了解一下（應(yīng)該可以很快看明白）：

P_{XYZ} (x,y,z)=P_{X}(x)P_{Y|X}(y|x)P_{Z|Y}(z|y)

馬爾科夫鏈

P(x0,x1,x2,...,xn,y1,y2,...,yn)=P(x0)\prod_{k=1}^n P(x_{k}|x_{k-1})P(y_{k}|y_{k-1})

隱馬爾科夫模型

到這，我們算把因子圖講透了，現(xiàn)在看看維基百科上是這樣定義因子圖的：將一個具有多變量的全局函數(shù)因子分解，得到幾個局部函數(shù)的乘積，以此為基礎(chǔ)得到的一個雙向圖叫做因子圖。

怎么樣，這樣直接看定義，你懂嗎？

2.3.2sum-product算法

我們已經(jīng)學(xué)會如何畫因子圖了，下面來思考這樣一個問題：如何由聯(lián)合概率分布求邊緣概率分布？

這里給出公式：

def:\bar{f_{k}}(x_{k}) =\sum_{x_{1},...,x_{n},except(x_{k})} f(x_{1},...,x_{n})

對Xk以外的其他變量的概率求和，最終剩下Xk的概率。這就是該定義的原理。你明白了嗎？我有點迷糊反正，可能說成話好理解，但是這個公式未免也太模糊了點（f真的萬能）。

其實可以這么理解：

如果有：

f(x_{1},...,x_{n})=f_{1}(x_{1})f_{2}(x_{2})\cdot \cdot \cdot f_{n}(x_{n})

那么：

\bar{f_{k}}(x_{k})=(\sum_{x_{1}}f_{1}(x_{1}))\cdot \cdot \cdot (\sum_{x_{k-1}}f_{k-1}(x_{k-1}))f_{k}(x_{k})\cdot \cdot \cdot (\sum_{x_{n}}f_{n}(x_{n}))

就是說把除了xk以外的所有隨機(jī)變量的概率求出來，這個f就表示一個多項式，是關(guān)于f括號里面x的。然后概率上面有一橫，表示的是不發(fā)生概率。

好吧，其實這塊我也沒太明白，先埋個坑，以后回來填。

現(xiàn)在假定我們要計算：

\bar{f_{3}}(x_{3}) =\sum_{x_{1},...,x_{7},except(x_{3})} f(x_{1},...,x_{7})

同時，f能被分解成如下因子圖（看到這里你大概能明白一點我上面說的f是多項式是什么意思了）：

f分解后的因子圖

我們都知道乘法分配律：a * b + a * c = a * (b + c)，等號左邊兩乘一加，等號右邊一加一乘，效率不用多說。現(xiàn)在我們就借助分配律的思想，把因子圖給分配咯！

借鑒分配律，提取公因子

怎么看公因子很簡單，例如X3是有f1（x1）和f2（x2）通過f3這個函數(shù)得來的（即因子圖那節(jié)所述，P（x3|x1，x2）），而之后的f5需要x3做因子（條件），所以自然左邊這個框就成了公因子。

因為變量的邊緣概率等于所有與他相連的函數(shù)傳遞過來的消息的乘積，所以計算得到：

\bar{f_{3}}(x_{3})=(\sum_{x_{1},x_{2}}f_{1}(x_{1})f_{2}(x_{2})f_{3}(x_{1},x_{2},x_{3}) ) (\sum_{x_{4},x_{5}}f_{4}(x_{4})f_{5}(x_{3},x_{4},x_{5})(\sum_{x_{6},x_{7}}f_{6}(x_{5},x_{6},x_{7})f_{7}(x_{7})))

觀察上述計算過程，可以發(fā)現(xiàn)類似于“消息傳遞”的觀點，且總共有兩個步驟：

1.對于f的分解圖，根據(jù)左框（藍(lán)色）、右框（紅色）所包圍的兩個box外面的消息傳遞：

外部消息傳遞
化簡理解

2.根據(jù)紅藍(lán)框為主的兩個box內(nèi)部的消息傳遞：

內(nèi)部消息傳遞

看上圖消息傳遞的方向（箭頭），根據(jù)\vec{\mu }_{x_{1}}(x_{1}) def:f_{1}(x_{1}),\vec{\mu }_{x_{2}}(x_{2}) def:f_{2}(x_{2})

我們可以推導(dǎo)出：

\vec{\mu_{x_{3}} } (x_{3})= \sum_{x_{1},x_{2}}\vec{\mu_{x_{1}} }(x_{1})\vec{\mu_{x_{2}} }(x_{2})f_{3}(x_{1},x_{2},x_{3})

\overleftarrow{\mu_{x_{5}} }(x_{5}) = \sum_{x_{6},x_{7}}\vec{\mu_{x_{7}} }(x_{7})f_{6}(x_{5},x_{6},x_{7})

\overleftarrow{\mu_{x_{3}}}(x_{3})= \sum_{x_{4},x_{5}}\vec{\mu_{x_{4}} }(x_{4})\overleftarrow{\mu_{x_{5}} }(x_{5})f_{5}(x_{3},x_{4},x_{5})

這樣就將一個概率分布寫成了兩個因子的乘積，而這兩個因子可以繼續(xù)分解或者通過已知條件得到。這種利用消息傳遞的觀念計算概率的方法就是sum-product算法。基于因子圖可以用該算法高效地求出各個變量的邊遠(yuǎn)分布。

sum-product算法，又稱belief propagation，有兩種消息：

一種是變量（variable）到函數(shù)（function）的消息m_{x\rightarrow f}如下圖所示：

變量-->函數(shù)

此時，m_{x\rightarrow f}=1

另一種是函數(shù)到變量的消息m_{f\rightarrow x}如下圖所示：

函數(shù)-->變量

此時，m_{f\rightarrow x} = f(x)

sum-product算法總體框架

如果因子圖是無環(huán)圖，則一定可以準(zhǔn)確地求出任意一個變量的邊遠(yuǎn)分布；如果是有環(huán)圖，則無法用該算法準(zhǔn)確求出邊遠(yuǎn)分布。解決方法有3個：

1、刪除貝葉斯網(wǎng)絡(luò)中的若干邊，使其不含有無向環(huán)

2、重新構(gòu)造沒有環(huán)的貝葉斯網(wǎng)絡(luò)

3、選擇loopy belief propagation算法（sum-product的遞歸版算法），該算法選擇環(huán)中某個消息，隨機(jī)賦初值，然后用sum-product算法，迭代下去，因為環(huán)的存在所以一定會達(dá)到賦值的消息，然后更新該消息，繼續(xù)迭代，直至沒有消息改變?yōu)橹?。缺點是不能確保收斂。

最后，該算法有個類似的max-product算法，弄懂了sum的，max的幾乎完全一樣。另這兩個算法也能夠應(yīng)用到隱馬爾科夫模型（hidden Morkov models）上。至于馬爾科夫系列，下個專題咱再見~

我們沒能力發(fā)現(xiàn)知識，我們只是知識的寄生蟲

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容