分類算法之貝葉斯網(wǎng)絡(luò)(Bayesian networks)

在上一篇文章中我們討論了樸素貝葉斯分類。樸素貝葉斯分類有一個限制條件，就是特征屬性必須有條件獨立或基本獨立（實際上在現(xiàn)實應(yīng)用中幾乎不可能做到完全獨立）。當(dāng)這個條件成立時，樸素貝葉斯分類法的準(zhǔn)確率是最高的，但不幸的是，現(xiàn)實中各個特征屬性間往往并不條件獨立，而是具有較強的相關(guān)性，這樣就限制了樸素貝葉斯分類的能力。這一篇文章中，我們接著上一篇文章的例子，討論貝葉斯分類中更高級、應(yīng)用范圍更廣的一種算法——貝葉斯網(wǎng)絡(luò)（又稱貝葉斯信念網(wǎng)絡(luò)或信念網(wǎng)絡(luò)）。

2.2、重新考慮上一篇的例子

上一篇文章我們使用樸素貝葉斯分類實現(xiàn)了SNS社區(qū)中不真實賬號的檢測。在那個解決方案中，我做了如下假設(shè)：

i、真實賬號比非真實賬號平均具有更大的日志密度、各大的好友密度以及更多的使用真實頭像。

ii、日志密度、好友密度和是否使用真實頭像在賬號真實性給定的條件下是獨立的。

但是，上述第二條假設(shè)很可能并不成立。一般來說，好友密度除了與賬號是否真實有關(guān)，還與是否有真實頭像有關(guān)，因為真實的頭像會吸引更多人加其為好友。因此，我們?yōu)榱双@取更準(zhǔn)確的分類，可以將假設(shè)修改如下：

i、真實賬號比非真實賬號平均具有更大的日志密度、各大的好友密度以及更多的使用真實頭像。

ii、日志密度與好友密度、日志密度與是否使用真實頭像在賬號真實性給定的條件下是獨立的。

iii、使用真實頭像的用戶比使用非真實頭像的用戶平均有更大的好友密度。

上述假設(shè)更接近實際情況，但問題隨之也來了，由于特征屬性間存在依賴關(guān)系，使得樸素貝葉斯分類不適用了。既然這樣，我去尋找另外的解決方案。

下圖表示特征屬性之間的關(guān)聯(lián)：

上圖是一個有向無環(huán)圖，其中每個節(jié)點代表一個隨機變量，而弧則表示兩個隨機變量之間的聯(lián)系，表示指向結(jié)點影響被指向結(jié)點。不過僅有這個圖的話，只能定性給出隨機變量間的關(guān)系，如果要定量，還需要一些數(shù)據(jù)，這些數(shù)據(jù)就是每個節(jié)點對其直接前驅(qū)節(jié)點的條件概率，而沒有前驅(qū)節(jié)點的節(jié)點則使用先驗概率表示。

例如，通過對訓(xùn)練數(shù)據(jù)集的統(tǒng)計，得到下表（R表示賬號真實性，H表示頭像真實性）：

縱向表頭表示條件變量，橫向表頭表示隨機變量。上表為真實賬號和非真實賬號的概率，而下表為頭像真實性對于賬號真實性的概率。這兩張表分別為“賬號是否真實”和“頭像是否真實”的條件概率表。有了這些數(shù)據(jù)，不但能順向推斷，還能通過貝葉斯定理進行逆向推斷。例如，現(xiàn)隨機抽取一個賬戶，已知其頭像為假，求其賬號也為假的概率：

也就是說，在僅知道頭像為假的情況下，有大約35.7%的概率此賬戶也為假。如果覺得閱讀上述推導(dǎo)有困難，請復(fù)習(xí)概率論中的條件概率、貝葉斯定理及全概率公式。如果給出所有節(jié)點的條件概率表，則可以在觀察值不完備的情況下對任意隨機變量進行統(tǒng)計推斷。上述方法就是使用了貝葉斯網(wǎng)絡(luò)。

2.3、貝葉斯網(wǎng)絡(luò)的定義及性質(zhì)

有了上述鋪墊，我們就可以正式定義貝葉斯網(wǎng)絡(luò)了。

一個貝葉斯網(wǎng)絡(luò)定義包括一個有向無環(huán)圖（DAG）和一個條件概率表集合。DAG中每一個節(jié)點表示一個隨機變量，可以是可直接觀測變量或隱藏變量，而有向邊表示隨機變量間的條件依賴；條件概率表中的每一個元素對應(yīng)DAG中唯一的節(jié)點，存儲此節(jié)點對于其所有直接前驅(qū)節(jié)點的聯(lián)合條件概率。

貝葉斯網(wǎng)絡(luò)有一條極為重要的性質(zhì)，就是我們斷言每一個節(jié)點在其直接前驅(qū)節(jié)點的值制定后，這個節(jié)點條件獨立于其所有非直接前驅(qū)前輩節(jié)點。

這個性質(zhì)很類似Markov過程。其實，貝葉斯網(wǎng)絡(luò)可以看做是Markov鏈的非線性擴展。這條特性的重要意義在于明確了貝葉斯網(wǎng)絡(luò)可以方便計算聯(lián)合概率分布。一般情況先，多變量非獨立聯(lián)合條件概率分布有如下求取公式：

而在貝葉斯網(wǎng)絡(luò)中，由于存在前述性質(zhì)，任意隨機變量組合的聯(lián)合條件概率分布被化簡成

其中Parents表示xi的直接前驅(qū)節(jié)點的聯(lián)合，概率值可以從相應(yīng)條件概率表中查到。

貝葉斯網(wǎng)絡(luò)比樸素貝葉斯更復(fù)雜，而想構(gòu)造和訓(xùn)練出一個好的貝葉斯網(wǎng)絡(luò)更是異常艱難。但是貝葉斯網(wǎng)絡(luò)是模擬人的認知思維推理模式，用一組條件概率函數(shù)以及有向無環(huán)圖對不確定性的因果推理關(guān)系建模，因此其具有更高的實用價值。

2.4、貝葉斯網(wǎng)絡(luò)的構(gòu)造及學(xué)習(xí)

構(gòu)造與訓(xùn)練貝葉斯網(wǎng)絡(luò)分為以下兩步：

1、確定隨機變量間的拓撲關(guān)系，形成DAG。這一步通常需要領(lǐng)域?qū)＜彝瓿桑胍⒁粋€好的拓撲結(jié)構(gòu)，通常需要不斷迭代和改進才可以。

2、訓(xùn)練貝葉斯網(wǎng)絡(luò)。這一步也就是要完成條件概率表的構(gòu)造，如果每個隨機變量的值都是可以直接觀察的，像我們上面的例子，那么這一步的訓(xùn)練是直觀的，方法類似于樸素貝葉斯分類。但是通常貝葉斯網(wǎng)絡(luò)的中存在隱藏變量節(jié)點，那么訓(xùn)練方法就是比較復(fù)雜，例如使用梯度下降法。由于這些內(nèi)容過于晦澀以及牽扯到較深入的數(shù)學(xué)知識，在此不再贅述，有興趣的朋友可以查閱相關(guān)文獻。

2.5、貝葉斯網(wǎng)絡(luò)的應(yīng)用及示例

貝葉斯網(wǎng)絡(luò)作為一種不確定性的因果推理模型，其應(yīng)用范圍非常廣，在醫(yī)療診斷、信息檢索、電子技術(shù)與工業(yè)工程等諸多方面發(fā)揮重要作用，而與其相關(guān)的一些問題也是近來的熱點研究課題。例如，Google就在諸多服務(wù)中使用了貝葉斯網(wǎng)絡(luò)。

就使用方法來說，貝葉斯網(wǎng)絡(luò)主要用于概率推理及決策，具體來說，就是在信息不完備的情況下通過可以觀察隨機變量推斷不可觀察的隨機變量，并且不可觀察隨機變量可以多于以一個，一般初期將不可觀察變量置為隨機值，然后進行概率推理。下面舉一個例子。

還是SNS社區(qū)中不真實賬號檢測的例子，我們的模型中存在四個隨機變量：賬號真實性R，頭像真實性H，日志密度L，好友密度F。其中H，L，F(xiàn)是可以觀察到的值，而我們最關(guān)系的R是無法直接觀察的。這個問題就劃歸為通過H，L，F(xiàn)的觀察值對R進行概率推理。推理過程可以如下表示：

1、使用觀察值實例化H,L和F，把隨機值賦給R。

2、計算。其中相應(yīng)概率值可以查條件概率表。

由于上述例子只有一個未知隨機變量，所以不用迭代。更一般得，使用貝葉斯網(wǎng)絡(luò)進行推理的步驟可如下描述：

1、對所有可觀察隨機變量節(jié)點用觀察值實例化；對不可觀察節(jié)點實例化為隨機值。

2、對DAG進行遍歷，對每一個不可觀察節(jié)點y，計算，其中wi表示除y以外的其它所有節(jié)點，a為正規(guī)化因子，sj表示y的第j個子節(jié)點。

3、使用第三步計算出的各個y作為未知節(jié)點的新值進行實例化，重復(fù)第二步，直到結(jié)果充分收斂。

4、將收斂結(jié)果作為推斷值。

以上只是貝葉斯網(wǎng)絡(luò)推理的算法之一，另外還有其它算法，這里不再詳述。