從樸素貝葉斯分類器到貝葉斯網(wǎng)絡(luò)（下）

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

貝葉斯網(wǎng)絡(luò)（Bayesian Network）是一種用于表示變量間依賴關(guān)系的數(shù)據(jù)結(jié)構(gòu)，有時(shí)它又被稱為信念網(wǎng)絡(luò)（Belief Network）或概率網(wǎng)絡(luò)（Probability Network）。在統(tǒng)計(jì)學(xué)習(xí)領(lǐng)域，概率圖模型（PGM，Probabilistic Graphical Models）常用來(lái)指代包括貝葉斯網(wǎng)絡(luò)在內(nèi)的更加寬泛的一類機(jī)器學(xué)習(xí)模型，例如隱馬爾可夫模型（HMM，Hidden Markov Model）也是一種PGM。

具體而言，貝葉斯網(wǎng)絡(luò)是一個(gè)有向無(wú)環(huán)圖（Directed Acyclic Graph），其中每個(gè)節(jié)點(diǎn)都標(biāo)注了定量的概率信息，并具有如下結(jié)構(gòu)特點(diǎn)：

（1）一個(gè)隨機(jī)變量集構(gòu)成了圖結(jié)構(gòu)中的節(jié)點(diǎn)集合。變量可以是離散的，也可以是連續(xù)的。

（2）一個(gè)連接節(jié)點(diǎn)對(duì)的有向邊集合反映了變量間的依賴關(guān)系。如果存在從節(jié)點(diǎn)X指向節(jié)點(diǎn)Y的有向邊，則稱X是Y的一個(gè)父節(jié)點(diǎn)。

（3）每個(gè)節(jié)點(diǎn)Xi都有一個(gè)（在給定父節(jié)點(diǎn)情況下的）條件概率分布，這個(gè)分布量化了父節(jié)點(diǎn)對(duì)其之影響。

在一個(gè)正確構(gòu)造的網(wǎng)絡(luò)中，箭頭顯式地表示了X對(duì)Y的直接影響。而這種影響關(guān)系往往來(lái)自于現(xiàn)實(shí)世界的經(jīng)驗(yàn)分析。一旦設(shè)計(jì)好貝葉斯網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，只要再為每個(gè)節(jié)點(diǎn)指定當(dāng)給定具體父節(jié)點(diǎn)時(shí)的條件概率，那么一個(gè)基本的概率圖模型就建立完成了。盡管現(xiàn)實(shí)中貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)可能非常復(fù)雜，但無(wú)論多么復(fù)雜的拓?fù)浔举|(zhì)上都是由一些基本的結(jié)構(gòu)單元經(jīng)過(guò)一定之組合演繹出來(lái)的。而且最終的拓?fù)浜蛯?duì)應(yīng)的條件概率完全可以給出所有變量的聯(lián)合分布，這種表現(xiàn)方式遠(yuǎn)比列出所有的聯(lián)合概率分布要精簡(jiǎn)得多。圖1給出了三種基本的結(jié)構(gòu)單元，下面我們將分別對(duì)它們進(jìn)行介紹。

圖1  三種基本的結(jié)構(gòu)單元
首先，如果幾個(gè)隨機(jī)變量之間是完全獨(dú)立的，那么它們之間將沒(méi)有任何的邊進(jìn)行連接。而對(duì)于樸素貝葉斯中的假設(shè)，即變量之間是條件獨(dú)立（Conditionally Independent）的，那么可以畫(huà)出此種結(jié)構(gòu)如圖1中的左圖所示。這表明在給定Y的情況下，X和Z是條件獨(dú)立的。

其次，另外一種與之相反的情況如圖1中的中圖所示。此時(shí)X和Z是完全獨(dú)立的。我們通常把左圖的情況稱為“Common Cause”，而把中圖的情況稱為“Common Effect”。

最后，對(duì)于圖1中右圖所示的鏈?zhǔn)浇Y(jié)構(gòu)，X和Z不再是相互獨(dú)立的。但在給定Y時(shí)，X和Z就是獨(dú)立的。因?yàn)镻(Z|X,Y)=P(Z|Y)。

文獻(xiàn)[1]中給出了一個(gè)簡(jiǎn)單的貝葉斯網(wǎng)絡(luò)示例，如圖2所示。假設(shè)你在家里安裝了一個(gè)防盜報(bào)警器。這個(gè)報(bào)警器對(duì)于探測(cè)盜賊的闖入非?？煽浚桥紶栆矔?huì)對(duì)輕微的地震有所反應(yīng)。你還有兩個(gè)鄰居John和Mary，他們保證在你工作時(shí)如果聽(tīng)到警報(bào)聲就給你打電話。John聽(tīng)到警報(bào)聲時(shí)總是會(huì)給你打電話，但是他們有時(shí)候會(huì)把電話鈴聲當(dāng)成警報(bào)聲，然后也會(huì)打電話給你。另一方面，Mary特別喜歡大聲聽(tīng)音樂(lè)，因此有時(shí)候根本聽(tīng)不見(jiàn)警報(bào)聲。給定了他們是否給你打電話的證據(jù)，我們希望估計(jì)如果有人入室行竊的概率。

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

現(xiàn)在暫時(shí)忽略圖中的條件概率分布，而是將注意力集中于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)上。在這個(gè)防盜網(wǎng)絡(luò)的案例中，拓?fù)浣Y(jié)構(gòu)表明盜賊和地震直接影響到警報(bào)的概率（這相當(dāng)于一個(gè)Common Effect的結(jié)構(gòu)），但是John或者M(jìn)ary是否打電話僅僅取決于警報(bào)聲（這相當(dāng)于一個(gè)Common Cause的結(jié)構(gòu)）。因此網(wǎng)絡(luò)表示出了我們的一些假設(shè)：“John和Mary不直接感知盜賊，也不會(huì)注意到輕微的地震”（這表明當(dāng)給定隨機(jī)變量Alarm時(shí)，“盜賊或地震”都獨(dú)立于“打電話”），并且他們不會(huì)在打電話之前交換意見(jiàn)（所以在給定隨機(jī)變量Alarm時(shí)，John打電話和Mary打電話就是條件獨(dú)立的）。

注意網(wǎng)絡(luò)中沒(méi)有對(duì)應(yīng)于Mary當(dāng)前正在大聲聽(tīng)音樂(lè)或者電話鈴聲響起來(lái)使得John誤以為是警報(bào)的節(jié)點(diǎn)。這些因素實(shí)際上已經(jīng)被概括在與從Alarm到JohnCalls或者到MaryCalls這兩條邊相關(guān)聯(lián)的不確定性中了。這同時(shí)體現(xiàn)了操作中的惰性與無(wú)知：要搞清楚為什么那些因素會(huì)以或多或少的可能性出現(xiàn)在任何特殊情況下，需要大量的工作，而且無(wú)論如何我們都沒(méi)有合理的途徑來(lái)獲取相關(guān)信息。上面的概率實(shí)際上概括了各種情況的潛在無(wú)限集合，其中包括報(bào)警器可能會(huì)失效的情況（諸如環(huán)境濕度過(guò)高、電力故障、電線被切斷、警鈴里卡了一只死老鼠等等）或者John和Mary沒(méi)有打電話報(bào)告的情況（諸如出去吃午飯了、外出度假、暫時(shí)性失聰、直升機(jī)剛巧飛過(guò)而噪聲隆隆等）。如此一來(lái)，一個(gè)小小的智能體可以處理非常龐大的世界，至少是近似地處理。如果我們能夠引入附加的相關(guān)信息，近似的程度還可以進(jìn)一步地提高。

現(xiàn)在回到圖中的條件概率分布上。每一個(gè)分布都被顯示為一個(gè)條件概率表（CPT, Conditional Probability Table）。這種形式的表格適用于離散型隨機(jī)變量。本文也僅討論這種類型的表示方法。CPT中的每一行包含了每個(gè)節(jié)點(diǎn)值在給定條件下的條件概率。這個(gè)所謂的“給定條件”就是所有父節(jié)點(diǎn)取值的某個(gè)可能組合。每一行概率加起來(lái)和必需是1，因?yàn)樾兄袟l目表示了該對(duì)應(yīng)變量的一個(gè)無(wú)遺漏的情況集合。對(duì)于布爾變量，一旦知道它為真的概率是p，那么它為假的概率就應(yīng)該是1-p。所以可以省略第二個(gè)數(shù)值。通常，一個(gè)具有k個(gè)布爾父節(jié)點(diǎn)的布爾變量的CPT中有2^k個(gè)獨(dú)立的可指定概率。而對(duì)于沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)而言，它的CPT只有一行，表示了該變量可能取值的先驗(yàn)概率（例如圖中的Burglary和Earthquake對(duì)應(yīng)的CPT）。

四、模型推理

當(dāng)我們已經(jīng)確定了一個(gè)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)時(shí)，如何利用它進(jìn)行推理將成為焦點(diǎn)。例如現(xiàn)在我們想知道當(dāng)John和Mary都打電話時(shí)發(fā)生地震的概率。即 P(E = T | J = T, M = T) = ?

總的來(lái)說(shuō)，通常可采用的方法有三種：1）首先是利用與樸素貝葉斯類似方法來(lái)進(jìn)行推理（其中同樣用到貝葉斯公式），我們稱其為枚舉法；2）其次是一種更為常用的算法，我們稱之為消去法；3）最后還有一種基于蒙特卡洛法的近似推理方法，本文將僅討論前兩種算法。

4.1  枚舉法

為了詳細(xì)地說(shuō)明原委，我們還是從一個(gè)簡(jiǎn)單的概率論知識(shí)點(diǎn)開(kāi)始。眾所周知，由n個(gè)隨機(jī)變量X1, X2, ..., Xn構(gòu)成的向量

X = (X1, X2, ..., Xn) 稱為n維隨機(jī)向量（或稱n維隨機(jī)變量）。首先我們以二維隨機(jī)向量(X,Y)為例來(lái)說(shuō)明邊緣分布的概念。隨機(jī)向量(X,Y)的分布函數(shù)F(x,y)完全決定了其分量的概率特征。所以由F(x,y)便能得出分量X的分布函數(shù)FX(x)，以及分量Y的分布函數(shù)FY(y)。而相對(duì)于聯(lián)合分布F(x,y)，分量的分布FX(x)和FY(y)稱為邊緣分布。由

FX(x) = P{X ≤ x} = P{X ≤ x, Y ≤ +∞} = F(x, +∞)

FY(y) = P{Y ≤ y} = P{X ≤ +∞,Y ≤ y} = F(+∞, y)

可得

FX(x) = F(x, +∞)，  FY(y) = F(+∞, y)

若(X,Y)為二維離散隨機(jī)變量，則

若(X,Y)為二維連續(xù)隨機(jī)變量，設(shè)密度函數(shù)為p(x,y)，則

回想在樸素貝葉斯中所使用的策略。我們根據(jù)已經(jīng)觀察到的證據(jù)計(jì)算查詢命題的后驗(yàn)概率。并將使用全聯(lián)合概率分布作為“知識(shí)庫(kù)”，從中可以得到所有問(wèn)題的答案。這其中貝葉斯公式發(fā)揮了重要作用，而下面的示例同樣演示了邊緣分布的作用。從一個(gè)非常簡(jiǎn)單的例子開(kāi)始：一個(gè)由3個(gè)布爾變量Toothache、Cavity以及Catch （由于牙醫(yī)的鋼探針不潔而導(dǎo)致的牙齦感染）組成的定義域。其全聯(lián)合分布是一個(gè)2 × 2 × 2 的表格，如下表所示。

根據(jù)概率公理的要求，聯(lián)合分布中的所有概率之和為1 。無(wú)論是簡(jiǎn)單命題還是復(fù)合命題，我們只需要確定在其中命題為真的那些原子事件，然后把它們的概率加起來(lái)就可獲得任何命題的概率。例如，命題Cavity ∨ Toothache在 6 個(gè)原子事件中成立，所以可得

P(Cavity ∨ Toothache) = 0.108 + 0.012 + 0.072 + 0.008 + 0.165 + 0.064 = 0.28

一個(gè)特別常見(jiàn)的任務(wù)是將隨機(jī)變量的某個(gè)子集或者某單個(gè)變量的分布抽取出來(lái)，也就是我們前面提到的邊緣分布。例如，將所有Cavity取值為真的條目抽取出來(lái)在求和就得到了Cavity的無(wú)條件概率（也就是邊緣概率）

P(Cavity) = 0.108 + 0.012 + 0.072 + 0.008 = 0.2

該過(guò)程稱為邊緣化（Marginalisation），或者稱為“和出”（Summing Out）——因?yàn)槌薈avity以外的變量都被求和過(guò)程排除在外了。對(duì)于任何兩個(gè)變量集合Y和Z，可以寫(xiě)出如下的通用邊緣化規(guī)則（這其實(shí)就是前面給出的公式，我們只是做了簡(jiǎn)單的變量替換）

也就是說(shuō)，Y的分布可以通過(guò)根據(jù)任何包含Y的聯(lián)合概率分布對(duì)所有其它變量進(jìn)行求和消元得到。根據(jù)乘法規(guī)則，這條規(guī)則的一個(gè)變形涉及條件概率而不是聯(lián)合概率：

這條規(guī)則稱為條件化。以后會(huì)發(fā)現(xiàn)，對(duì)于涉及概率表達(dá)式的所有種類的推導(dǎo)過(guò)程，邊緣 化和條件化具有非常強(qiáng)大的威力。

在大部分情況下，在給定關(guān)于某些其它變量的條件下，我們會(huì)對(duì)計(jì)算某些變量的條件概率產(chǎn)生感興趣。條件概率可以如此找到：首先根據(jù)條件概率的定義式得到一個(gè)無(wú)條件概率的表達(dá)式，然后再根據(jù)全聯(lián)合分布對(duì)表達(dá)式求值。例如，在給定牙疼的條件下，可以計(jì)算蛀牙的概率為

P(Cavity | Toothache) = P(Cavity ∧ Toothache) / P(Toothache) 

=( 0.108 +0.012) / (0.108 + 0.012 + 0.016 + 0.064) = 0.6

為了驗(yàn)算，還可以計(jì)算已知牙疼的條件下，沒(méi)有蛀牙的概率為

P(┐Cavity | Toothache) = P(┐Cavity ∧ Toothache) / P(Toothache) 

=( 0.016 +0.064) / (0.108 + 0.012 + 0.016 + 0.064) = 0.4

注意這兩次計(jì)算中的項(xiàng) 1/P(Toothache) 是保持不變的，與我們計(jì)算的Cavity的值無(wú)關(guān)。事實(shí)上，可以把它看成是P(Cavity I Toothache)  的一個(gè)歸一化常數(shù)，保證其所包含的概率相加等于1，也就是忽略P(Toothache) 的值，這一點(diǎn)我們?cè)?a href='/map/pusubeiyesi/' style='color:#000;font-size:inherit;'>樸素貝葉斯部分已經(jīng)講過(guò)。

此外，我們將用α來(lái)表示這樣的常數(shù)。用這個(gè)符號(hào)我們可以把前面的兩個(gè)公式合并寫(xiě)成一個(gè)：

P(Cavity | Toothache) =α P(Cavity, Toothache) 

=α [P(Cavity, Toothache, Catch) + P(Cavity, Toothache, ┐Catch)]

=α [〈0.108, 0.016〉+〈0.012, 0.064〉] = α〈0.12, 0.08〉=〈0.6, 0.4〉

在很多概率的計(jì)算中，歸一化都是一個(gè)非常有用的捷徑。

從這個(gè)例于里可以抽取出一個(gè)通用推理過(guò)程。我們將只考慮查詢僅涉及一個(gè)變量的情況。我們將需要使用一些符號(hào)表示：令X 為查詢變量（前面例子中的Cavity）；令E 為證據(jù)變量集合（也就是給定的條件，即前面例子中的Toothache ）， e 表示其觀察值；并令 Y 為其余的未觀測(cè)變量（就是前面例于中的Catch） 。查詢?yōu)镻(X I e)，可以對(duì)它求值：

其中的求和針對(duì)所有可能的y （也就是對(duì)未觀測(cè)變量Y的值的所有可能組合）。注意變量 X, E 以及Y一起構(gòu)成了域中所有布變量的完整集合，所以P(X, e, y)只不過(guò)是來(lái)自全聯(lián)合分布概率的一個(gè)子集。算法對(duì)所有X和Y的值進(jìn)行循環(huán)以枚舉當(dāng) e 固定時(shí)所有的原子事件，然后根據(jù)全聯(lián)合分布的概率表將它們的概率加起來(lái)，最后對(duì)結(jié)果進(jìn)行歸一化。

下面我們就用枚舉法來(lái)解決本節(jié)開(kāi)始時(shí)拋出的問(wèn)題： P(E = T | J = T, M = T) = ?

P(E|j,m) = α P(E, j, m)

其中，我們用小寫(xiě)字母 j 和 m 來(lái)表示 J = T，以及M = T（也就是給定J和M）。但表達(dá)式的形式是P(E|j,m)而非P(e|j,m)，這是因?yàn)槲覀円獙 = T 和 E = F這兩個(gè)公式合并起來(lái)寫(xiě)成一個(gè)。同樣，α 是標(biāo)準(zhǔn)化常數(shù)。然后就要針對(duì)其他未觀測(cè)變量（也就是本題中的Burglary和Alarm）的值的所有可能組合進(jìn)行求和，則有

根據(jù)圖2中所示之貝葉斯網(wǎng)絡(luò)，應(yīng)該很容易可以寫(xiě)出下列關(guān)系式。

如果你無(wú)法輕易地看出這種關(guān)系，也可以通過(guò)公式推導(dǎo)一步一步的得出。首先，在給定條件a的情況下，J和M條件獨(dú)立，所以有P(j,m|a) = P(j|a)P(m|a)。B和E獨(dú)立，所以有P(b)P(E)=P(b,E)。進(jìn)而有P(b)P(E)P(a|b,E)=P(a,b,E)。在給定a的時(shí)候，b、E和j、m獨(dú)立（對(duì)應(yīng)圖1中的第3種情況），所以有P(j,m|a) = P(j,m|a,b,E)。由這幾個(gè)關(guān)系式就能得出上述結(jié)論。

下面我們來(lái)循環(huán)枚舉并加和消元。

在計(jì)算上還可以稍微做一點(diǎn)改進(jìn)。因?yàn)镻(E)對(duì)于ΣaΣb來(lái)說(shuō)是一個(gè)常數(shù)，所以可以把它提出來(lái)。這樣就避免了多次乘以P(E)所造成的低效。

上式中所有的值都可以基于CPT求得，算術(shù)當(dāng)然是很繁雜的，我們這里不具體給出最終的結(jié)果。但一個(gè)顯而易見(jiàn)的事實(shí)是當(dāng)變量的數(shù)目變多時(shí)，全聯(lián)合分布的表長(zhǎng)增長(zhǎng)是相當(dāng)驚人的！所以我們非常希望能夠有一種更輕巧的辦法來(lái)替代這種枚舉法，于是便有了下面將要介紹的消去法。

4.2  消去法

變量消去算法（Variable Elimination Algorithm）是一種基于動(dòng)態(tài)規(guī)劃思想設(shè)計(jì)的算法。而且在算法執(zhí)行的過(guò)程中需要使用因子表來(lái)儲(chǔ)存中間結(jié)果，當(dāng)再次需要使用時(shí)無(wú)需重新計(jì)算而只需調(diào)用已知結(jié)果，這樣就降低了算法執(zhí)行的時(shí)間消耗。

Each factor is a matrix indexed by the values of its argument variable. 例如，與P(j|a)和P(m|a)相對(duì)應(yīng)的因子fJ(A)和fM(A)只依賴于A，因?yàn)镴和M在我們的問(wèn)題里是已知的，因此fJ(A)和fM(A)都是兩個(gè)元素的矩陣（也是向量）

在這種記法中括號(hào)里的參數(shù)表示的是變量，而下標(biāo)僅僅是一種記號(hào)，所以你也可以使用f4(A)和f5(A)來(lái)代替fJ(A)和fM(A)。但我們這里使用J和M來(lái)作為下標(biāo)的意圖是考慮用P( _ | A)的 _ 來(lái)作為標(biāo)記。所以P(a|b,E)可以寫(xiě)成fA(A, B, E)，注意因?yàn)锳，B,  E都是未知的，所以fA(A, B, E) 就是一個(gè)2×2×2的矩陣，即數(shù)據(jù)分析師培訓(xùn)

最初的因子表是經(jīng)CPT改造而來(lái)的，如下圖所示。

然后進(jìn)行自底向上的計(jì)算，Step1: fJ(A)×fM(A) = fJM(A)，A仍然是變量，則有

此時(shí)新產(chǎn)生的因子表為

Step2: fA(A, B, E)×fJM(A) = fAJM(A, B, E)，即

此時(shí)新產(chǎn)生的因子表為

Step3:  

此時(shí)新產(chǎn)生的因子表為

Step4:

此時(shí)新產(chǎn)生的因子表為

Step5:

此時(shí)新產(chǎn)生的因子表為

Step6:

此時(shí)新產(chǎn)生的因子表為

由此便可根據(jù)上表算得問(wèn)題之答案

P(E=T | j,m) = P(E=T | j,m) / [P(E=T | j,m) + P(E=F | j,m)]  = 0.0037/(0.0037 + 0.0069) = 0.3491

最后總結(jié)一下消去算法的執(zhí)行步驟：