从贝叶斯方法谈到贝叶斯网络
原文
0 引言
? ? 事實(shí)上，介紹貝葉斯定理、貝葉斯方法、貝葉斯推斷的資料、書(shū)籍不少，比如《數(shù)理統(tǒng)計(jì)學(xué)簡(jiǎn)史》，以及《統(tǒng)計(jì)決策論及貝葉斯分析 James O.Berger著》等等，然介紹貝葉斯網(wǎng)絡(luò)的中文資料則非常少，中文書(shū)籍總共也沒(méi)幾本，有的多是英文資料，但初學(xué)者一上來(lái)就扔給他一堆英文論文，因無(wú)基礎(chǔ)和語(yǔ)言的障礙而讀得異常吃力導(dǎo)致無(wú)法繼續(xù)讀下去則是非常可惜的（當(dāng)然，有了一定的基礎(chǔ)后，便可的英文資料）。
? ? 11月9日上午，機(jī)器學(xué)習(xí)班第9次課，鄒博講貝葉斯網(wǎng)絡(luò)，其幫助大家提煉了貝葉斯網(wǎng)絡(luò)的幾個(gè)關(guān)鍵點(diǎn)：貝葉斯網(wǎng)絡(luò)的定義、3種結(jié)構(gòu)形式、因子圖、以及Summary-Product算法等等，知道了貝葉斯網(wǎng)絡(luò)是啥，怎么做，目標(biāo)是啥之后，相信看英文論文也更好看懂了。
? ? 故本文結(jié)合鄒博第9次課貝葉斯網(wǎng)絡(luò)的PPT?及相關(guān)參考資料寫(xiě)就，從貝葉斯方法講起，重點(diǎn)闡述貝葉斯網(wǎng)絡(luò)，依然可以定義為一篇讀書(shū)筆記或?qū)W習(xí)筆記，有任何問(wèn)題，歡迎隨時(shí)不吝指出，thanks。
?
?
1 貝葉斯方法
? ? 長(zhǎng)久以來(lái)，人們對(duì)一件事情發(fā)生或不發(fā)生的概率，只有固定的0和1，即要么發(fā)生，要么不發(fā)生，從來(lái)不會(huì)去考慮某件事情發(fā)生的概率有多大，不發(fā)生的概率又是多大。而且概率雖然未知，但最起碼是一個(gè)確定的值。比如如果問(wèn)那時(shí)的人們一個(gè)問(wèn)題：“有一個(gè)袋子，里面裝著若干個(gè)白球和黑球，請(qǐng)問(wèn)從袋子中取得白球的概率是多少？”他們會(huì)想都不用想，會(huì)立馬告訴你，取出白球的概率就是1/2，要么取到白球，要么取不到白球，即θ只能有一個(gè)值，不是1/2，就是0，而且不論你取了多少次，取得白球的概率θ始終都是1/2，即不隨觀察結(jié)果X 的變化而變化。
? ? 這種頻率派的觀點(diǎn)長(zhǎng)期統(tǒng)治著人們的觀念，直到后來(lái)一個(gè)名叫Thomas Bayes的人物出現(xiàn)。
1.1 貝葉斯方法的提出
? ? 托馬斯·貝葉斯Thomas Bayes（1702-1763）在世時(shí)，并不為當(dāng)時(shí)的人們所熟知，很少發(fā)表論文或出版著作，與當(dāng)時(shí)學(xué)術(shù)界的人溝通交流也很少，用現(xiàn)在的話(huà)來(lái)說(shuō)，貝葉斯就是活生生一民間學(xué)術(shù)“屌絲”，可這個(gè)“屌絲”最終發(fā)表了一篇名為“An essay towards solving a problem in the doctrine of chances”，翻譯過(guò)來(lái)則是：機(jī)遇理論中一個(gè)問(wèn)題的解。你可能覺(jué)得我要說(shuō)：這篇論文的發(fā)表隨機(jī)產(chǎn)生轟動(dòng)效應(yīng)，從而奠定貝葉斯在學(xué)術(shù)史上的地位。
? ? ? ? ? ??
? ? 事實(shí)上，上篇論文發(fā)表后，在當(dāng)時(shí)并未產(chǎn)生多少影響，在20世紀(jì)后，這篇論文才逐漸被人們所重視。對(duì)此，與梵高何其類(lèi)似，畫(huà)的畫(huà)生前一文不值，死后價(jià)值連城。
? ? 回到上面的例子：“有一個(gè)袋子，里面裝著若干個(gè)白球和黑球，請(qǐng)問(wèn)從袋子中取得白球的概率θ是多少？”貝葉斯認(rèn)為取得白球的概率是個(gè)不確定的值，因?yàn)槠渲泻袡C(jī)遇的成分。比如，一個(gè)朋友創(chuàng)業(yè)，你明明知道創(chuàng)業(yè)的結(jié)果就兩種，即要么成功要么失敗，但你依然會(huì)忍不住去估計(jì)他創(chuàng)業(yè)成功的幾率有多大？你如果對(duì)他為人比較了解，而且有方法、思路清晰、有毅力、且能團(tuán)結(jié)周?chē)娜?#xff0c;你會(huì)不由自主的估計(jì)他創(chuàng)業(yè)成功的幾率可能在80%以上。這種不同于最開(kāi)始的“非黑即白非0即1”的思考方式，便是貝葉斯式的思考方式。
? ? 繼續(xù)深入講解貝葉斯方法之前，先簡(jiǎn)單總結(jié)下頻率派與貝葉斯派各自不同的思考方式：
?
- 頻率派把需要推斷的參數(shù)θ看做是固定的未知常數(shù)，即概率雖然是未知的，但最起碼是確定的一個(gè)值，同時(shí)，樣本X 是隨機(jī)的，所以頻率派重點(diǎn)研究樣本空間，大部分的概率計(jì)算都是針對(duì)樣本X 的分布；
- 而貝葉斯派的觀點(diǎn)則截然相反，他們認(rèn)為參數(shù)是隨機(jī)變量，而樣本X 是固定的，由于樣本是固定的，所以他們重點(diǎn)研究的是參數(shù)的分布。
?
? ? 相對(duì)來(lái)說(shuō)，頻率派的觀點(diǎn)容易理解，所以下文重點(diǎn)闡述貝葉斯派的觀點(diǎn)。
? ? 貝葉斯派既然把看做是一個(gè)隨機(jī)變量，所以要計(jì)算的分布，便得事先知道的無(wú)條件分布，即在有樣本之前（或觀察到X之前），有著怎樣的分布呢？
? ? 比如往臺(tái)球桌上扔一個(gè)球，這個(gè)球落會(huì)落在何處呢？如果是不偏不倚的把球拋出去，那么此球落在臺(tái)球桌上的任一位置都有著相同的機(jī)會(huì)，即球落在臺(tái)球桌上某一位置的概率服從均勻分布。這種在實(shí)驗(yàn)之前定下的屬于基本前提性質(zhì)的分布稱(chēng)為先驗(yàn)分布，或的無(wú)條件分布。
? ? 至此，貝葉斯及貝葉斯派提出了一個(gè)思考問(wèn)題的固定模式：
- 先驗(yàn)分布?+ 樣本信息??后驗(yàn)分布
? ? 上述思考模式意味著，新觀察到的樣本信息將修正人們以前對(duì)事物的認(rèn)知。換言之，在得到新的樣本信息之前，人們對(duì)的認(rèn)知是先驗(yàn)分布，在得到新的樣本信息后，人們對(duì)的認(rèn)知為。
? ??? ? 其中，先驗(yàn)信息一般來(lái)源于經(jīng)驗(yàn)跟歷史資料。比如林丹跟某選手對(duì)決，解說(shuō)一般會(huì)根據(jù)林丹歷次比賽的成績(jī)對(duì)此次比賽的勝負(fù)做個(gè)大致的判斷，再比如，某工廠每天都要對(duì)產(chǎn)品進(jìn)行質(zhì)檢，以評(píng)估產(chǎn)品的不合格率θ，經(jīng)過(guò)一段時(shí)間后便會(huì)積累大量的歷史資料，這些歷史資料便是先驗(yàn)知識(shí)，有了這些先驗(yàn)知識(shí)，便在決定對(duì)一個(gè)產(chǎn)品是否需要每天質(zhì)檢時(shí)便有了依據(jù)，如果以往的歷史資料顯示，某產(chǎn)品的不合格率只有0.01%，便可視為信得過(guò)產(chǎn)品或免檢產(chǎn)品，只每月抽檢一兩次，從而省去大量的人力物力。
? ? 而后驗(yàn)分布一般也認(rèn)為是在給定樣本的情況下的條件分布，而使達(dá)到最大的值稱(chēng)為最大后驗(yàn)估計(jì)，類(lèi)似于經(jīng)典統(tǒng)計(jì)學(xué)中的極大似然估計(jì)。
? ? 綜合起來(lái)看，則好比是人類(lèi)剛開(kāi)始時(shí)對(duì)大自然只有少得可憐的先驗(yàn)知識(shí)，但隨著不斷是觀察、實(shí)驗(yàn)獲得更多的樣本、結(jié)果，使得人們對(duì)自然界的規(guī)律摸得越來(lái)越透徹。所以，貝葉斯方法既符合人們?nèi)粘Ｉ畹乃伎挤绞?#xff0c;也符合人們認(rèn)識(shí)自然的規(guī)律，經(jīng)過(guò)不斷的發(fā)展，最終占據(jù)統(tǒng)計(jì)學(xué)領(lǐng)域的半壁江山，與經(jīng)典統(tǒng)計(jì)學(xué)分庭抗禮。
? ? 此外，貝葉斯除了提出上述思考模式之外，還特別提出了舉世聞名的貝葉斯定理。
1.2 貝葉斯定理
? ? 在引出貝葉斯定理之前，先學(xué)習(xí)幾個(gè)定義：
- 條件概率就是事件A在另外一個(gè)事件B已經(jīng)發(fā)生條件下的發(fā)生概率。條件概率表示為P(A|B)，讀作“在B條件下A的概率”。
- 聯(lián)合概率表示兩個(gè)事件共同發(fā)生的概率。A與B的聯(lián)合概率表示為或者。
- 邊緣概率（又稱(chēng)先驗(yàn)概率）是某個(gè)事件發(fā)生的概率。邊緣概率是這樣得到的：在聯(lián)合概率中，把最終結(jié)果中那些不需要的事件通過(guò)合并成它們的全概率，而消去它們（對(duì)離散隨機(jī)變量用求和得全概率，對(duì)連續(xù)隨機(jī)變量用積分得全概率），這稱(chēng)為邊緣化（marginalization），比如A的邊緣概率表示為P(A)，B的邊緣概率表示為P(B)。?
? ? 接著，考慮一個(gè)問(wèn)題：P(A|B)是在B發(fā)生的情況下A發(fā)生的可能性。
? ? 貝葉斯定理便是基于下述貝葉斯公式：
?
?
? ? 上述公式的推導(dǎo)其實(shí)非常簡(jiǎn)單，就是從條件概率推出。
?
? ? 根據(jù)條件概率的定義，在事件B發(fā)生的條件下事件A發(fā)生的概率是
?
?
?
?
? ? 同樣地，在事件A發(fā)生的條件下事件B發(fā)生的概率
?
?
? ? 整理與合并上述兩個(gè)方程式，便可以得到：
?
?
?
?
? ? 接著，上式兩邊同除以P(B)，若P(B)是非零的，我們便可以得到貝葉斯定理的公式表達(dá)式：
?
?
1.3 應(yīng)用：拼寫(xiě)檢查
? ? 經(jīng)常在網(wǎng)上搜索東西的朋友知道，當(dāng)你不小心輸入一個(gè)不存在的單詞時(shí)，搜索引擎會(huì)提示你是不是要輸入某一個(gè)正確的單詞，比如當(dāng)你在Google中輸入“Julw”時(shí)，系統(tǒng)會(huì)提示你是不是要搜索“July”，如下圖所示：
?
? ? 這叫做拼寫(xiě)檢查。根據(jù)谷歌一員工寫(xiě)的文章顯示，Google的拼寫(xiě)檢查基于貝葉斯方法。下面我們就來(lái)看看，怎么利用貝葉斯方法，實(shí)現(xiàn)"拼寫(xiě)檢查"的功能。
? ? 用戶(hù)輸入一個(gè)單詞時(shí)，可能拼寫(xiě)正確，也可能拼寫(xiě)錯(cuò)誤。如果把拼寫(xiě)正確的情況記做c（代表correct），拼寫(xiě)錯(cuò)誤的情況記做w（代表wrong），那么"拼寫(xiě)檢查"要做的事情就是：在發(fā)生w的情況下，試圖推斷出c。換言之：已知w，然后在若干個(gè)備選方案中，找出可能性最大的那個(gè)c，也就是求的最大值。
? ? 而根據(jù)貝葉斯定理，有：
? ? 由于對(duì)于所有備選的c來(lái)說(shuō)，對(duì)應(yīng)的都是同一個(gè)w，所以它們的P(w)是相同的，因此我們只要最大化
?
? ? 即可。其中：
?
- P(c)表示某個(gè)正確的詞的出現(xiàn)"概率"，它可以用"頻率"代替。如果我們有一個(gè)足夠大的文本庫(kù)，那么這個(gè)文本庫(kù)中每個(gè)單詞的出現(xiàn)頻率，就相當(dāng)于它的發(fā)生概率。某個(gè)詞的出現(xiàn)頻率越高，P(c)就越大。
- P(w|c)表示在試圖拼寫(xiě)c的情況下，出現(xiàn)拼寫(xiě)錯(cuò)誤w的概率。為了簡(jiǎn)化問(wèn)題，假定兩個(gè)單詞在字形上越接近，就有越可能拼錯(cuò)，P(w|c)就越大。舉例來(lái)說(shuō)，相差一個(gè)字母的拼法，就比相差兩個(gè)字母的拼法，發(fā)生概率更高。你想拼寫(xiě)單詞July，那么錯(cuò)誤拼成Julw（相差一個(gè)字母）的可能性，就比拼成Jullw高（相差兩個(gè)字母）。
? ? 所以，我們只要找到與輸入單詞在字形上最相近的那些詞，再在其中挑出出現(xiàn)頻率最高的一個(gè)，就能實(shí)現(xiàn)的最大值。
?
?
2 貝葉斯網(wǎng)絡(luò)
? ??貝葉斯網(wǎng)絡(luò)(Bayesian?network)，又稱(chēng)信念網(wǎng)絡(luò)(Belief Network)，或有向無(wú)環(huán)圖模型(directed?acyclic?graphical?model)，是一種概率圖模型，于1985年由Judea Pearl首先提出。它是一種模擬人類(lèi)推理過(guò)程中因果關(guān)系的不確定性處理模型，其網(wǎng)絡(luò)拓樸結(jié)構(gòu)是一個(gè)有向無(wú)環(huán)圖(DAG)。?
? ? 貝葉斯網(wǎng)絡(luò)的有向無(wú)環(huán)圖中的節(jié)點(diǎn)表示隨機(jī)變量，它們可以是可觀察到的變量，或隱變量、未知參數(shù)等。認(rèn)為有因果關(guān)系（或非條件獨(dú)立）的變量或命題則用箭頭來(lái)連接（換言之，連接兩個(gè)節(jié)點(diǎn)的箭頭代表此兩個(gè)隨機(jī)變量是具有因果關(guān)系，或非條件獨(dú)立）。若兩個(gè)節(jié)點(diǎn)間以一個(gè)單箭頭連接在一起，表示其中一個(gè)節(jié)點(diǎn)是“因(parents)”，另一個(gè)是“果(children)”，兩節(jié)點(diǎn)就會(huì)產(chǎn)生一個(gè)條件概率值。
? ? 例如，假設(shè)節(jié)點(diǎn)E直接影響到節(jié)點(diǎn)H，即E→H，則用從E指向H的箭頭建立結(jié)點(diǎn)E到結(jié)點(diǎn)H的有向弧(E,H)，權(quán)值(即連接強(qiáng)度)用條件概率P(H|E)來(lái)表示，如下圖所示：
?
? ??簡(jiǎn)言之，把某個(gè)研究系統(tǒng)中涉及的隨機(jī)變量，根據(jù)是否條件獨(dú)立繪制在一個(gè)有向圖中，就形成了貝葉斯網(wǎng)絡(luò)。其主要用來(lái)描述隨機(jī)變量之間的條件依賴(lài)，用圈表示隨機(jī)變量(random variables)，用箭頭表示條件依賴(lài)(conditional dependencies)。
2.1 貝葉斯網(wǎng)絡(luò)的定義
? ??令G = (I,E)表示一個(gè)有向無(wú)環(huán)圖(DAG)，其中I代表圖形中所有的節(jié)點(diǎn)的集合，而E代表有向連接線段的集合，且令X = (Xi)i ∈ I為其有向無(wú)環(huán)圖中的某一節(jié)點(diǎn)i所代表的隨機(jī)變量，若節(jié)點(diǎn)X的聯(lián)合概率可以表示成：
?
? ? 則稱(chēng)X為相對(duì)于一有向無(wú)環(huán)圖G?的貝葉斯網(wǎng)絡(luò)，其中，表示節(jié)點(diǎn)i之“因”，或稱(chēng)pa(i)是i的parents（父母）。?
? ? 此外，對(duì)于任意的隨機(jī)變量，其聯(lián)合概率可由各自的局部條件概率分布相乘而得出：
? ? 如下圖所示，便是一個(gè)簡(jiǎn)單的貝葉斯網(wǎng)絡(luò)：
?
?
? ? 因?yàn)閍導(dǎo)致b，a和b導(dǎo)致c，所以有
?
2.2 貝葉斯網(wǎng)絡(luò)的實(shí)例
? ? 給定如下圖所示的貝葉斯網(wǎng)絡(luò)：
?
?
? ? 其中，各個(gè)單詞、表達(dá)式表示的含義如下：
- smoking表示吸煙，其概率用P(S)表示，lung Cancer表示的肺癌，一個(gè)人在吸煙的情況下得肺癌的概率用P(C|S)表示，X-ray表示需要照醫(yī)學(xué)上的X光，肺癌可能會(huì)導(dǎo)致需要照X光，吸煙也有可能會(huì)導(dǎo)致需要照X光（所以smoking也是X-ray的一個(gè)因），所以，因吸煙且得肺癌而需要照X光的概率用P(X|C,S)表示。
- Bronchitis表示支氣管炎，一個(gè)人在吸煙的情況下得支氣管炎的概率用P(B|S)，dyspnoea表示呼吸困難，支氣管炎可能會(huì)導(dǎo)致呼吸困難，肺癌也有可能會(huì)導(dǎo)致呼吸困難（所以lung Cancer也是dyspnoea的一個(gè)因），因吸煙且得了支氣管炎導(dǎo)致呼吸困難的概率用P(D|C,B)表示。
? ? lung Cancer簡(jiǎn)記為C，Bronchitis簡(jiǎn)記為B，dyspnoea簡(jiǎn)記為D，且C = 0表示lung Cancer不發(fā)生的概率，C = 1表示lung Cancer發(fā)生的概率，B等于0（B不發(fā)生）或1（B發(fā)生）也類(lèi)似于C，同樣的，D=1表示D發(fā)生的概率，D=0表示D不發(fā)生的概率，便可得到dyspnoea的一張概率表，如上圖的最右下角所示。
2.3 貝葉斯網(wǎng)絡(luò)的3種結(jié)構(gòu)形式
? ? 給定如下圖所示的一個(gè)貝葉斯網(wǎng)絡(luò)，
?
?
? ? 從圖上可以比較直觀的看出：
- 1. x1,x2,…x7的聯(lián)合分布為
- 2. x1和x2獨(dú)立（對(duì)應(yīng)head-to-head）；
- 3. x6和x7在x4給定的條件下獨(dú)立（對(duì)應(yīng)tail-to-tail）。
? ? 根據(jù)上圖，第1點(diǎn)可能很容易理解，但第2、3點(diǎn)中所述的條件獨(dú)立是啥意思呢？其實(shí)第2、3點(diǎn)是貝葉斯網(wǎng)絡(luò)中3種結(jié)構(gòu)形式中的其中二種。為了說(shuō)清楚這個(gè)問(wèn)題，需要引入D-Separation（D-分離）這個(gè)概念。
? ? D-Separation是一種用來(lái)判斷變量是否條件獨(dú)立的圖形化方法。換言之，對(duì)于一個(gè)DAG(有向無(wú)環(huán)圖)E，D-Separation方法可以快速的判斷出兩個(gè)節(jié)點(diǎn)之間是否是條件獨(dú)立的。
2.3.1 形式1：head-to-head
? ? 貝葉斯網(wǎng)絡(luò)的第一種結(jié)構(gòu)形式如下圖所示：
? ? 所以有：P(a,b,c) = P(a)*P(b)*P(c|a,b)成立，化簡(jiǎn)后可得：
?
? ? 即在c未知的條件下，a、b被阻斷(blocked)，是獨(dú)立的，稱(chēng)之為head-to-head條件獨(dú)立，對(duì)應(yīng)本節(jié)中最開(kāi)始那張圖中的“x1、x2獨(dú)立”。
2.3.2 形式2：tail-to-tail
? ? 貝葉斯網(wǎng)絡(luò)的第二種結(jié)構(gòu)形式如下圖所示
? ? 有P(a,b,c)=P(c)*P(a|c)*P(b|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,b|c)=P(a|c)*P(b|c)。
? ? 即在c給定的條件下，a，b被阻斷(blocked)，是獨(dú)立的，稱(chēng)之為tail-to-tail條件獨(dú)立，對(duì)應(yīng)本節(jié)中最開(kāi)始那張圖中的“x6和x7在x4給定的條件下獨(dú)立”。
2.3.3 形式3：head-to-tail
? ? 貝葉斯網(wǎng)絡(luò)的第三種結(jié)構(gòu)形式如下圖所示：
? ? 有：P(a,b,c)=P(a)*P(c|a)*P(b|c)。
? ? 化簡(jiǎn)后可得：
?
? ? 即：在c給定的條件下，a，b被阻斷(blocked)，是獨(dú)立的，稱(chēng)之為head-to-tail條件獨(dú)立。
? ??插一句：這個(gè)head-to-tail其實(shí)就是一個(gè)鏈?zhǔn)骄W(wǎng)絡(luò)，如下圖所示：
? ??在xi給定的條件下，xi+1的分布和x1,x2…xi-1條件獨(dú)立。即：xi+1的分布狀態(tài)只和xi有關(guān)，和其他變量條件獨(dú)立，這種順次演變的隨機(jī)過(guò)程，就叫做馬爾科夫鏈（Markov chain）。且有：
? ? OK，今天在總結(jié)貝葉斯網(wǎng)絡(luò)中的上述3種結(jié)構(gòu)時(shí)，發(fā)現(xiàn)跟河流關(guān)系比較相像，比如：
- ①兩條小河流入一條大河，叫head-to-head，由P(a,b,c)=P(c|a,b)P(b)P(a)，可得：P(a,b) = P(a)*P(b)，即c未知的條件下，a、b被阻斷(blocked)，是獨(dú)立的。同時(shí)，也謂之匯連，且匯連是條件依賴(lài)的（C依賴(lài)于A、B的聯(lián)合分布），匯連這種情況也稱(chēng)為一個(gè)v-結(jié)構(gòu)；
- ②一條大河到某處分叉成兩條支流，稱(chēng)之為tail-to-tail，由P(a,b,c)=P(b|c)P(a|c)P(c) ，可得：P(a,b|c)=P(a|c)*P(b|c)，即在c給定的條件下，a，b被阻斷(blocked)，是獨(dú)立的。同時(shí)，也謂之分連；
- ③一條大河流到底，中間不分叉不匯入其它河流，但可能其中的某段叫什么江，另一段叫什么江，稱(chēng)之為head-to-tail，由P(a,b,c)=P(b|c)P(c|a)P(a) ，化簡(jiǎn)可得：P(a,b,c)=P(a)*P(c|a)*P(b|c)，即在c給定的條件下，a，b被阻斷(blocked)，是獨(dú)立的。同時(shí)，也謂之順連；
? ? 不知道讀者對(duì)這個(gè)河流的比喻怎么看？^_^
? ? 接著，將上述結(jié)點(diǎn)推廣到結(jié)點(diǎn)集，則是：對(duì)于任意的結(jié)點(diǎn)集A，B，C，考察所有通過(guò)A中任意結(jié)點(diǎn)到B中任意結(jié)點(diǎn)的路徑，若要求A，B條件獨(dú)立，則需要所有的路徑都被阻斷(blocked)，即滿(mǎn)足下列兩個(gè)前提之一：
? ? 最后，舉例說(shuō)明上述D-Separation的3種情況，則是如下圖所示：
?
? ? 上圖中左邊部分是head-to-tail，右邊部分的右上角是tail-to-tail，右邊部分的右下角是head-to-head。
2.4 因子圖
? ? 回到2.2節(jié)中那個(gè)實(shí)例上，如下圖所示：
?
?
? ? 對(duì)于上圖，在一個(gè)人已經(jīng)呼吸困難的情況下，其抽樣的概率是多少呢？即：
?
? ? ?咱們來(lái)一步步計(jì)算推導(dǎo)下：
?
? ? 注：解釋下上述式子的第二行到最后一行第三行的推導(dǎo)過(guò)程。最開(kāi)始，所有變量都在sigma(d=1,b,x,c)的后面（sigma表示對(duì)“求和”的稱(chēng)謂），但由于P(s)和“d=1,b,x,c”都沒(méi)關(guān)系，所以，可以提到式子的最前面。而且P(b|s)和x、c沒(méi)關(guān)系，所以，也可以把它提出來(lái)，放到sigma(b)的后面，從而式子的右邊剩下sigma(x)和sigma(c)。
? ? 此外，Variable elimination表示的是變量消除的意思。為了更好的解決此類(lèi)問(wèn)題，咱們得引入因子圖的概念。
2.4.1 因子圖的定義
? ? wikipedia上是這樣定義因子圖的：將一個(gè)具有多變量的全局函數(shù)因子分解，得到幾個(gè)局部函數(shù)的乘積，以此為基礎(chǔ)得到的一個(gè)雙向圖叫做因子圖（Factor Graph）。
? ? 比如，假定對(duì)于函數(shù)，有下述式子成立：
? ? 其中，其對(duì)應(yīng)的因子圖包括：
?
? ? 官方正式的定義果然晦澀！我相信你沒(méi)看懂。通俗來(lái)講，所謂因子圖就是對(duì)函數(shù)進(jìn)行因子分解得到的一種概率圖。一般內(nèi)含兩種節(jié)點(diǎn)，變量節(jié)點(diǎn)和函數(shù)節(jié)點(diǎn)。我們知道，一個(gè)全局函數(shù)通過(guò)因式分解能夠分解為多個(gè)局部函數(shù)的乘積，這些局部函數(shù)和對(duì)應(yīng)的變量關(guān)系就體現(xiàn)在因子圖上。舉個(gè)例子，現(xiàn)在有一個(gè)全局函數(shù)，其因式分解方程為：
? ? 其中fA,fB,fC,fD,fE為各函數(shù)，表示變量之間的關(guān)系，可以是條件概率也可以是其他關(guān)系(如馬爾可夫隨機(jī)場(chǎng)Markov Random Fields中的勢(shì)函數(shù))。
? ? 為了方便表示，可以寫(xiě)成：
? ? 其對(duì)應(yīng)的因子圖為：
?
? ? 且上述因子圖等價(jià)于：
?
? ? 所以，在因子圖中，所有頂點(diǎn)不是變量節(jié)點(diǎn)就是函數(shù)節(jié)點(diǎn)，邊線表示它們之間的函數(shù)關(guān)系。
? ? 但搞了半天，雖然知道了什么是因子圖，但因子圖到底是干嘛的呢？為何要引入因子圖，其用途和意義何在？事實(shí)上，因子圖跟貝葉斯網(wǎng)絡(luò)和馬爾可夫隨機(jī)場(chǎng)（Markov Random Fields）一樣，也是是概率圖的一種。從上文中，我們可以看到，在概率圖中，求某個(gè)變量的邊緣分布是常見(jiàn)的問(wèn)題。這問(wèn)題有很多求解方法，其中之一就是可以把貝葉斯網(wǎng)絡(luò)或馬爾科夫隨機(jī)場(chǎng)轉(zhuǎn)換成因子圖，然后用sum-product算法求解。換言之，基于因子圖可以用sum-product 算法高效的求各個(gè)變量的邊緣分布。
? ? 先舉個(gè)例子說(shuō)明如何把貝葉斯網(wǎng)絡(luò)（和馬爾科夫隨機(jī)場(chǎng)）轉(zhuǎn)換成因子圖。給定下圖所示的貝葉斯網(wǎng)絡(luò)或馬爾科夫隨機(jī)場(chǎng)：
?
?
? ? 根據(jù)各個(gè)變量對(duì)應(yīng)的關(guān)系，可得：
?
?
? ? 其對(duì)應(yīng)的因子圖為（以下兩種因子圖的表示方式皆可）：
?
?
? ? 由上述例子總結(jié)出由貝葉斯網(wǎng)絡(luò)構(gòu)造因子圖的方法：
- 貝葉斯網(wǎng)絡(luò)中的一個(gè)因子對(duì)應(yīng)因子圖中的一個(gè)結(jié)點(diǎn)
- 貝葉斯網(wǎng)絡(luò)中的每一個(gè)變量在因子圖上對(duì)應(yīng)邊或者半邊
- 結(jié)點(diǎn)g和邊x相連當(dāng)且僅當(dāng)變量x出現(xiàn)在因子g中
?
? ? 舉幾個(gè)例子。比如，對(duì)于如下的一個(gè)因子圖：
?
? ? 有：
?
?
? ? 而對(duì)于下圖所示的馬爾科夫鏈：
?
? ? 有：
?
?
? ? 另對(duì)于如下圖所示的隱馬爾科夫模型：
?
?
? ? 有：
?
?
2.4.2 Sum-product算法
? ? 下面，咱們來(lái)考慮一個(gè)問(wèn)題：即如何由聯(lián)合概率分布求邊緣概率分布。
? ? 首先回顧下聯(lián)合概率和邊緣概率的定義，如下：
?
- 聯(lián)合概率表示兩個(gè)事件共同發(fā)生的概率。A與B的聯(lián)合概率表示為或者。
- 邊緣概率（又稱(chēng)先驗(yàn)概率）是某個(gè)事件發(fā)生的概率。邊緣概率是這樣得到的：在聯(lián)合概率中，把最終結(jié)果中不需要的那些事件合并成其事件的全概率而消失（對(duì)離散隨機(jī)變量用求和得全概率，對(duì)連續(xù)隨機(jī)變量用積分得全概率）。這稱(chēng)為邊緣化（marginalization）。A的邊緣概率表示為P(A)，B的邊緣概率表示為P(B)。?
?
? ? 事實(shí)上，某個(gè)隨機(jī)變量fk的邊緣概率可由x1,x2,x3, ..., xn的聯(lián)合概率求到，具體公式為：
?
?
? ? 啊哈，啥原理呢？原理很簡(jiǎn)單，還是它：對(duì)x3外的其它變量的概率求和，最終剩下x3的概率！
? ? 此外，換言之，如果有
?
?
? ? 那么
? ? 上述式子如何進(jìn)一步化簡(jiǎn)計(jì)算呢？考慮到我們小學(xué)所學(xué)到的乘法分配率，可知a*b + a*c =?a*(b + c)，前者2次乘法1次加法，后者1次乘法，1次加法。我們這里的計(jì)算是否能借鑒到分配率呢？別急，且聽(tīng)下文慢慢道來(lái)。
? ? 假定現(xiàn)在我們需要計(jì)算計(jì)算如下式子的結(jié)果：
?
?
? ? 同時(shí)，f 能被分解如下：
?
?
? ? 借鑒分配率，我們可以提取公因子：
?
? ? ?因?yàn)樽兞康倪吘壐怕实扔谒信c他相連的函數(shù)傳遞過(guò)來(lái)的消息的積，所以計(jì)算得到：
? ? 仔細(xì)觀察上述計(jì)算過(guò)程，可以發(fā)現(xiàn)，其中用到了類(lèi)似“消息傳遞”的觀點(diǎn)，且總共兩個(gè)步驟。
? ? 第一步、對(duì)于f 的分解圖，根據(jù)藍(lán)色虛線框、紅色虛線框圍住的兩個(gè)box外面的消息傳遞：
?
?
? ? 計(jì)算可得：
?
? ? 第二步、根據(jù)藍(lán)色虛線框、紅色虛線框圍住的兩個(gè)box內(nèi)部的消息傳遞：
?
?
? ? 根據(jù)，我們有：
?
?
? ? 就這樣，上述計(jì)算過(guò)程將一個(gè)概率分布寫(xiě)成兩個(gè)因子的乘積，而這兩個(gè)因子可以繼續(xù)分解或者通過(guò)已知得到。這種利用消息傳遞的觀念計(jì)算概率的方法便是sum-product算法。前面說(shuō)過(guò)，基于因子圖可以用sum-product算法可以高效的求各個(gè)變量的邊緣分布。
? ? 到底什么是sum-product算法呢？sum-product算法，也叫belief propagation，有兩種消息：
- 一種是變量(Variable)到函數(shù)(Function)的消息：，如下圖所示
? ? 此時(shí)，變量到函數(shù)的消息為。
- 另外一種是函數(shù)(Function)到變量(Variable)的消息：。如下圖所示：
? ? 此時(shí)，函數(shù)到變量的消息為：。
? ? 以下是sum-product算法的總體框架：
?
- 1、給定如下圖所示的因子圖：
?
?
?
?
- 2、sum-product 算法的消息計(jì)算規(guī)則為：
?
?
?
- 3、根據(jù)sum-product定理，如果因子圖中的函數(shù)f 沒(méi)有周期，則有：
?
? ? 值得一提的是：如果因子圖是無(wú)環(huán)的，則一定可以準(zhǔn)確的求出任意一個(gè)變量的邊緣分布，如果是有環(huán)的，則無(wú)法用sum-product算法準(zhǔn)確求出來(lái)邊緣分布。
? ? 比如，下圖所示的貝葉斯網(wǎng)絡(luò)：
?
?
? ? 其轉(zhuǎn)換成因子圖后，為：
?
?
? ??可以發(fā)現(xiàn)，若貝葉斯網(wǎng)絡(luò)中存在“環(huán)”（無(wú)向），則因此構(gòu)造的因子圖會(huì)得到環(huán)。而使用消息傳遞的思想，這個(gè)消息將無(wú)限傳輸下去，不利于概率計(jì)算。
? ? 解決方法有3個(gè)：
- 1、刪除貝葉斯網(wǎng)絡(luò)中的若干條邊，使得它不含有無(wú)向環(huán)
? ? 比如給定下圖中左邊部分所示的原貝葉斯網(wǎng)絡(luò)，可以通過(guò)去掉C和E之間的邊，使得它重新變成有向無(wú)環(huán)圖，從而成為圖中右邊部分的近似樹(shù)結(jié)構(gòu)：
? ? 具體變換的過(guò)程為最大權(quán)生成樹(shù)算法MSWT（詳細(xì)建立過(guò)程請(qǐng)參閱此PPT?第60頁(yè)），通過(guò)此算法，這課樹(shù)的近似聯(lián)合概率P'(x)和原貝葉斯網(wǎng)絡(luò)的聯(lián)合概率P(x)的相對(duì)熵（如果忘了什么叫相對(duì)熵，請(qǐng)參閱：最大熵模型中的數(shù)學(xué)推導(dǎo)）最小。
- 2、重新構(gòu)造沒(méi)有環(huán)的貝葉斯網(wǎng)絡(luò)
- 3、選擇loopy belief propagation算法（你可以簡(jiǎn)單理解為sum-product 算法的遞歸版本），此算法一般選擇環(huán)中的某個(gè)消息，隨機(jī)賦個(gè)初值，然后用sum-product算法，迭代下去，因?yàn)橛协h(huán)，一定會(huì)到達(dá)剛才賦初值的那個(gè)消息，然后更新那個(gè)消息，繼續(xù)迭代，直到?jīng)]有消息再改變?yōu)橹埂Ｎㄒ坏娜秉c(diǎn)是不確保收斂，當(dāng)然，此算法在絕大多數(shù)情況下是收斂的。
? ? 此外，除了這個(gè)sum-product算法，還有一個(gè)max-product 算法。但只要弄懂了sum-product，也就弄懂了max-product 算法。因?yàn)閙ax-product 算法就在上面sum-product 算法的基礎(chǔ)上把求和符號(hào)換成求最大值max的符號(hào)即可！
? ? 最后，sum-product 和 max-product 算法也能應(yīng)用到隱馬爾科夫模型hidden Markov models上，后面有機(jī)會(huì)的話(huà)可以介紹。
總結(jié)
以上是生活随笔為你收集整理的从贝叶斯方法谈到贝叶斯网络的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 最优化作业第六章——共轭梯度法和鲍尔法
- 下一篇： 最优化课程笔记07——约束问题的非线性规