來源：NewBeeNLP

本文長度為2700字，建議閱讀6分鐘

本文為你分享一份概率圖模型學(xué)習(xí)筆記，一起交流。

寫在前面

其實接觸概率圖模型也有一段時間了，從開始入坑NLP起，也陸陸續(xù)續(xù)看了很多關(guān)于圖模型這方面的論文、博客和教程等，但是總是不能形成一個完整的體系，所以這次就下決心花點時間好好去整理復(fù)習(xí)一下。網(wǎng)上的資料很多，但是那都是別人的，最重要的還是要學(xué)會整理融合成自己的知識。

今天這篇主要就介紹一下圖模型的基礎(chǔ)知識，后面陸續(xù)會整理HMM， CRF等比較常見常用的概率圖模型。

概率論只不過是把常識歸納為計算問題。 （皮誒爾·西蒙·拉普拉斯）

什么是概率圖

我們首先肯定都知道什么是圖。圖就是由結(jié)點和結(jié)點之間的鏈接組成的。那么概率圖就是在圖結(jié)構(gòu)的基礎(chǔ)上集成了“概率”的概念，也就是，概率圖中的結(jié)點變成了隨機(jī)變量，鏈接變成了這些隨機(jī)變量之間的概率關(guān)系（依賴關(guān)系）。

在宗成慶老師的統(tǒng)計自然語言處理一書中，有關(guān)于圖模型的整體框架，對后面理解各種類型的圖模型有非常好的幫助：

可以看到，整個圖模型的框架可以分成有向圖(也叫做貝葉斯網(wǎng)絡(luò))和無向圖(也叫做馬爾科夫網(wǎng)絡(luò))兩個部分。

• 在有向圖模型中，結(jié)點之間的鏈接有一個特定的方向，表達(dá)變量之間的因果關(guān)系；
• 在無向圖模型中，節(jié)點之間沒有方向限制，用于表達(dá)隨機(jī)變量之間的軟限制。

有向圖 VS 無向圖

有向圖

有向圖又可以稱作貝葉斯網(wǎng)絡(luò)、信念網(wǎng)絡(luò)、有向無環(huán)圖模型。

有向圖的一般模型如下所示：

在有向圖中，有個箭頭從x1指向x2，說明是由于x1“導(dǎo)致”x2，表示兩者的依賴關(guān)系。通過使用概率乘積規(guī)則，我們可以將這個有向圖表示為數(shù)學(xué)公式：

下面我們通過一個栗子更好地了解有向圖。

“草地是濕的(grass is wet)＂的原因可能有兩個：灑水器打開(S=true)或下雨(R=true)。它們之間的關(guān)系可以用一個條件概率表(conditional probability table, CPT) 來描述。比如說，我們可以看到 P(W=true|S=true,R=true)=0.99，即當(dāng)灑水器打開同時下雨的條件下，“草地濕的”概率為0.99。而“灑水器”和“下雨”的狀態(tài)又是由“天氣”決定的。所以，整體的聯(lián)合概率可以寫成：

有向圖的條件獨立判斷與d-劃分

首先我們來看三種簡單的條件獨立情況。

1、tail-to-tail

節(jié)點C鏈接的是兩個箭頭的尾部， 如下圖

根據(jù)上圖可以寫出三個隨機(jī)變量的聯(lián)合分布：

接著我們?nèi)ヅ袛郺, b兩個節(jié)點是否條件獨立，有兩種情況：

“（1）沒有變量是觀測變量”此時我們可以對a,b,c的聯(lián)合分布對c求積分，如果考慮c是離散的，可得：

可見a,b并不獨立

“（2）變量C是觀測變量” 此時我們有：

可知a,b是條件獨立的

2、head-to-tail

同樣我們分為兩種情況討論a,b的條件獨立性（這里就不具體寫出了）

3、head-to-head

也是同樣方法去分析。

一個總結(jié)（d-劃分）

對于 DAG 圖 E，如果A，B，C是三個集合（可以是單獨的節(jié)點或者是節(jié)點的集合），為了判斷 A 和 B 是否是 C 條件獨立的， 我們考慮 E 中所有 A 和 B 之間的“無向路徑” 。對于其中的一條路徑，如果滿足以下兩個條件中的任意一條，則稱這條路徑是“阻塞（block”）的：

（a）路徑中存在某個節(jié)點X是 「head-to-tial」 或者 「tail-to-tail」 節(jié)點，并且 X 是包含在 C 中的；
（b）路徑中存在某個節(jié)點X是「head-to-head」節(jié)點，并且 X 或 X 的兒子是不包含在 C 中的；

如果 A，B 間所有的路徑都是阻塞的，那么 A，B 就是關(guān)于 C 條件獨立的；否則， A，B 不是關(guān)于 C 條件獨立的。

一個栗子

給定下面一個DAG，判斷圖中a和b是否在c條件下獨立？a和b是否在f條件下獨立？

“問題1”：a到b只有一條路徑a->e->f->b，考慮路徑上除了a和b之外的節(jié)點e和f：其中e是head-to-head類型的，且e的兒子節(jié)點就是c，根據(jù)上述可知e不阻斷；對于f，是tail-to-tail類型的，且f不在c中，f也不阻斷；因此a，b不是c條件下獨立。

“問題2“：路徑 a->e->f->b 上的所有節(jié)點?？紤]路徑上的點e和f：節(jié)點 e 是head-to-head 類型的，e 和她的兒子節(jié)點 c 都不在 f 中，e是阻斷路徑的節(jié)點。節(jié)點 f 是tail-to-tail類型節(jié)點，且 f 節(jié)點就在 f中，所以 f 節(jié)點阻斷了路徑。結(jié)論：a 和 b是 f 下條件獨立的。

無向圖

無向圖又可以稱作馬爾科夫網(wǎng)絡(luò)、馬爾科夫隨機(jī)場，如下圖所示：

概率無向圖的判斷

這里首先給出判定條件：

如果聯(lián)合概率分布滿足成對、局部或者全局馬爾科夫性，則稱此聯(lián)合概率分布為概率無向圖模型。

接著我們來看什么是馬爾科夫性

• 成對馬爾可夫性：
• 局部馬爾可夫性：
• 全局馬爾科夫性：

條件獨立判斷

在有向圖的情形下，我們可以通過d-劃分來判斷一個特定的條件獨立性質(zhì)是否成立。那么在無向圖中，有沒有類似的判定方法呢？

還是對于A,B,C，我們考慮鏈接集合A的結(jié)點和集合B的結(jié)點的所有可能的路徑。如果所有這些路徑都通過了集合C中的一個或多個節(jié)點，那么所有這樣的路徑都被“阻隔”，可以判斷集合A與集合B在給定C的條件下獨立。

還有另一種更明了的判定方式。我們把集合C中的所有結(jié)點以及與這些結(jié)點相連的鏈接全部刪除，然后去考察A和B結(jié)點之間是否存在一條路徑，如果沒有這樣的路徑，則條件獨立性質(zhì)成立。

概率無向圖模型的因子分解

概率無向圖模型的最大特點就是易于因子分解，也就是將整體的聯(lián)合概率寫成若干子聯(lián)合概率的乘積的形式。

首先我們需要了解什么是“團(tuán)”與“最大團(tuán)”

“團(tuán)”：無向圖中任何兩個結(jié)點均有邊鏈接的結(jié)點子集；
“最大團(tuán)”：無向圖中的某一個團(tuán)C無法再加入另一個結(jié)點使其成為更大的團(tuán)，則C為最大團(tuán)

那么怎么做因子分解呢？

將概率無向圖模型的聯(lián)合概率概率分布表示為其最大團(tuán)上的隨機(jī)變量的函數(shù)的乘積形式的操作，稱為因子分解。

最后直接看公式

其中，Z(x)為歸一化因子，目的就是為了讓結(jié)果稱為概率（對比softmax理解）

后面那個phi函數(shù)稱為勢函數(shù)，通常定義為指數(shù)函數(shù)：

好的，舉個栗子：比如我們需要將上面這個無向圖進(jìn)行因子分解

• 首先，找出最大團(tuán)：(X1, X3, X4)和(X2, X3, X4)
• 求因子分解：

判別式模型 VS 生成式模型

在有監(jiān)督的模式識別或者機(jī)器學(xué)習(xí)問題中，我們可以把模型分為生成式和判別式兩種。剛接觸的時候也是對這倆模型傻傻分不清楚，無法觸及到兩者的本質(zhì)區(qū)別，然后各種翻閱知乎博客，慢慢有了一些具體的認(rèn)識?？梢詤⒖迹?/p>

機(jī)器學(xué)習(xí)“判定模型”和“生成模型”有什么區(qū)別？[1]

判別式模型與生成式模型[2]

結(jié)合下面的圖記錄一下自己的理解。

對于一個特定的機(jī)器學(xué)習(xí)問題（輸入為X，輸出或者說標(biāo)簽為Y），我們的建模思路大致有以下兩種：

• 第一種，我們從輸入X中通過特種工程提取出合適的特征，直接進(jìn)行根據(jù)特征和標(biāo)簽Y進(jìn)行學(xué)習(xí)，最終得到一個合適的模型（對應(yīng)上圖就是decision boundary）；
• 第二種，我們既然有了訓(xùn)練數(shù)據(jù)，為什么不先去了解一下數(shù)據(jù)是怎么分布的呢？如果我們可以通過某種方式得到X和Y的聯(lián)合分布，那么對于新來的測試數(shù)據(jù)，我們就可以利用這個聯(lián)合分布來求出所對應(yīng)的新標(biāo)簽Y（具體例子參考樸素貝葉斯模型可以很清楚）：

好了，上面說的第一種建模思路對應(yīng)的就是判別式模型，第二種思路對應(yīng)的就是生成式模型，總結(jié)一下：

• 判別式模型主要有：Logistic Regression、SVM、Traditional Neural Network、Nearest Neighbor、CRF、Linear Discriminant Analysis、Boosting、Linear Regression；
• 生成式模型主要有：Gaussians, Naive Bayes, Mixtures of Multinomials、Mixtures of Gaussians, Mixtures of Experts, HMMs、Sigmoidal Belief Networks, Bayesian Networks、Markov Random Fields、Latent Dirichlet Allocation
• 由生成式模型可以得到判別式模型，但由判別式模型得不到生成式模型

本文參考資料

1.機(jī)器學(xué)習(xí)“判定模型”和“生成模型”有什么區(qū)別？:

https://zhuanlan.zhihu.com/p/30941701

2.判別式模型與生成式模型:

http://www./discriminative-model-and-generative-model

編輯：于騰凱

校對：林亦霖

—完—