第十一章 條件隨機場（CRF）

• 摘要
• 1 概率無向圖模型
• • 1.1 概率無向圖模型定義
  • 1.2 概率無向圖模型的因子分解
  • 1.3 D-劃分
  • 1.4 馬爾可夫隨機場在圖像中的應用
• 2 條件隨機場的定義與形式
• • 2.1 條件隨機場的定義
  • 2.2 條件隨機場的參數化形式
  • 2.3 條件隨機場的簡化形式
  • 2.4 條件隨機場的矩陣形式
• 3 條件隨機場的概率計算問題
• • 前向-后向算法
• 總結
• 參考文獻

摘要

• 條件隨機場（CRF）是給定一組輸入隨機變量條件下，另一組輸出隨機變量的條件概率分布模型，其特點是假設輸出隨機變量構成馬爾可夫隨機場。
• 條件隨機場可以用于不同的預測問題，本文僅討論在標注問題的應用。主要講述線性鏈（Linear Chain）條件隨機場，此時問題為由輸入序列對輸出序列預測的判別模型，形成對數線性模型，其學習方法通常是極大似然估計或正則化的極大似然估計。

1 概率無向圖模型

概率無向圖模型（Probabilistic Undirected Graphical Model），又稱馬爾可夫隨機場（Markov Random Field）是一個可以由無向圖表示的聯合概率分布。

1.1 概率無向圖模型定義

• 圖（Graph）是由結點（Node）及連接結點的邊（Edge）組成的集合。結點和邊的集合分別記作V和E，圖記作$G=(V,E)$.
  
• 概率圖模型是由圖表示的概率分布。設有聯合概率分布$P(Y)$，無向圖$G=(V,E)$表示概率分布$P(Y)$，即在圖G中，結點$v\in V$表示一個隨機變量$Y_v$；邊$e\in E$表示隨機變量之間的概率依賴關系。
• 給定一個聯合概率分布$P(Y)$和表示它的無向圖$G$。首先定義無向圖表示的隨機變量之間存在的成對馬爾可夫性、局部馬爾可夫性、全局馬爾可夫性。

（1）成對馬爾可夫性：設$u$和$v$是無向圖$G$中任意兩個沒有邊連接的結點，結點$u$和$v$分別對應隨機變量$Y_u$和$Y_v$，其他所有結點為$O$對應的隨機變量為$Y_O$。成對馬爾可夫性是指給定隨機變量組$Y_O$的條件下，隨機變量$Y_u$和$Y_v$是條件獨立的，即
$$P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_v|Y_O)$$

（2）局部馬爾可夫性：設$v\in V$是無向圖$G$中任意一個結點，$W$是與$v$有邊連接的所有結點，$O$是$v$和$W$以外的其他所有結點。局部馬爾可夫性是指在給定隨機變量組$Y_W$的條件下，隨機變量$Y_v$與隨機變量組$Y_O$是獨立的，即
$$P(Y_v,Y_O|Y_W)=P(Y_v|Y_W)P(Y_O|Y_W)$$
在$P(Y_O|Y_W)>0$時，等價地，
$$P(Y_v|Y_W)=P(Y_v|Y_W,Y_O)$$

（3）全局馬爾可夫性：設結點集合A，B是在無向圖G中被結點集合C分開的任意結點集合。全局馬爾可夫性是指給定隨機變量組$Y_C$條件下，隨機變量組$Y_A$和$Y_B$是條件獨立的。
$$P(Y_A,Y_B|Y_C)=P(Y_A|Y_C)P(Y_B|Y_C)$$

概率無向圖模型
設有聯合概率分布$P(Y)$，由無向圖$G=(V,E)$表示，在圖$G$中，結點表示隨機變量，邊表示隨機變量之間的依賴關系。如果聯合概率分布$P(Y)$滿足成對、局部或全局馬爾可夫性，就稱此聯合概率分布為概率無向圖模型，或馬爾可夫隨機場。

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

團與最大團
無向圖$G$中任何兩個結點均有邊連接的結點子集稱為團（clique）若C是無向圖G的一個團，并且不能再加進任何一個G的結點使其成為一個更大的團，則稱此C為最大團。

由兩個結點組成的團有5個：$\{y_1,y_2\},\{y_1,y_3\},\{y_2,y_3\},\{y_2,y_4\},\{y_3,y_4\}$；
由三個結點組成的團有2個（最大團）：$\{y_1,y_2,y_3\},\{y_4,y_2,y_3\}$
$\{y_1,y_2,y_3,y_4\}$不是一個團，因為$y_1$和$y_4$沒有邊連接。

將概率無向圖模型的聯合概率分布表示為其最大團上的隨機變量的函數的乘積形式的操作，成為概率無向圖的因子分解。

給定概率無向圖模型，設其無向圖為G，C為G上的最大團，$Y_C$表示C對應的隨機變量。那么概率無向圖模型的概率分布$P(Y)$可寫作圖中所有最大團C上的函數，即：
$$P(Y)=\frac{1}{Z}\prod _C{\Psi }_C(Y_C)$$
其中，Z是規范化因子（Normalization Factor），由式
$$Z=\sum _Y\prod _C{\Psi }_C(Y_C)$$
給出。
規范化因子保證P(Y)構成一個概率分布。函數${\Psi }_C(Y_C)$稱為勢函數（potential function）這里要求勢函數是嚴格正的，通常定義為指數函數。
$${\Psi }_C(Y_C)=exp\{?E(Y_C)\}$$
概率無向圖模型的因子分解的因子分解由下面定理來保證。

Hammersley-Clifford定理
概率無向圖模型的聯合概率分布$Y_C$可以表示為如下形式：
$$P(Y)=\frac{1}{Z}\prod _C{\Psi }_C(Y_C)$$
$$Z=\sum _Y\prod _C{\Psi }_C(Y_C)$$
其中，C是無向圖的最大團，$Y_C$是C的結點對應的隨機變量，${\Psi }_C(Y_C)$是C上定義的嚴格正函數，乘積是在無向圖所有的最大團上進行的。

1.3 D-劃分

在模式識別中，使用概率模型時，條件獨立性起著重要的作用。條件獨立性簡化了模型的結構，降低了模型的訓練和推斷的計算量。在有向圖中，判斷一個圖是否條件獨立的方法是D-劃分。

在一個有向圖中，A，B，C是任意無交集的結點集合。從A中任意結點到B中任意結點的所有可能的路徑，如果存在以下兩種情況，則表示A到B的路徑被阻斷：

• 路徑上的箭頭以頭到尾或者尾到尾的方式交匯于這個結點，且這個結點在集合C中。
• 箭頭以頭到頭的方式交匯于這個結點，且這個結點和它的所有后繼都不在集合C中。

如果所有的路徑都被“阻隔”，那么我們說C把A從B中d-劃分開，且圖中所有變量上的聯合概率分布將會滿足A ⊥B | C（其中⊥表示獨立，式子表達為在給定C的條件下是否滿足A獨立于B）。

我們定義以下這個箭頭“→”為“tail→head”，以上圖為例，因為結點與兩個箭頭的尾部相連，所以該圖為“tail-tail”也就是概念中的尾到尾的方式，這樣的?個連接，結點A和結點B的路徑的存在使得結點相互依賴。然而，當我們以結點C為條件時，被用作條件的結點“阻隔”了從A到B的路徑，使得A和B變得（條件）獨?了。根據D-劃分的概念，若C被觀測，則路徑被堵塞。也就是說，A ⊥B | C，給定條件C的情況下，A和B條件獨立。D劃分的概念并不是通過假定或猜想得到的，它得出是有理論依據的，主要依據貝葉斯網絡和因子分解進行計算，具體的推導呢，在這里就不再多贅述。

1.4 馬爾可夫隨機場在圖像中的應用

在實際圖像應用中，馬爾科夫隨機場應用十分廣泛，在圖像降噪、圖像分割、紋理合成等領域都有涉及。下面我們舉一個圖像分割的栗子，來說明圖像分割中MRF的應用。

圖像其實就是一個典型的馬爾科夫隨機場，因為在圖像中每個像素點和周圍的點都有或多或少的聯系，和距離遠的點沒有關系，與周圍像素點的關系最大。正如下圖所示，該圖中的每個像素對應一個結點，每個結點之間存在關聯。當我們進行圖像分割時，我們只需要知道每個像素點的分類標簽，當然就可以很好地對圖片進行分割了。從聚類角度講，就是一個圖像聚類問題，把具有相同性質的像素點設置為一類。也就是一個標簽分類問題，比如把一副圖像分割成4類，那么每一個像素點必定屬于這四類中的某一類，假設四類為1，2，3，4類，L=4,那么分割就是給每個像素點找一個標簽類。

根據貝葉斯公式$$P(Y|X)=\frac{P(X|Y)P(Y)}{P(X)}$$.
假設待分割圖像是S，其大小是$m\times n$，圖像中的像素點為$p\in S$，W為分割的結果，假設圖像分為四類：$W_1,W_2,W_3,W_4$，可以得出：
$$P(W|S)=\frac{P(S|W)P(W)}{P(S)}$$
其中$P(W)$為先驗概率，$P(S|W)$為條件概率，$P(S|W)$為給定$W$條件下得到$S$的概率，W為觀察值，S就是隱馬爾可夫隨機場中包含的概率轉移鏈。

同時$P(S|W)$是$P(W|S)$的似然函數，似然函數用來描述已知隨機變量輸出結果時，未知參數的可能取值。例如，對于一枚正反對稱的硬幣上拋10次這樣的事件，我們可以問硬幣落地時十次都是正面向上的概率是多少；而對于一枚硬幣上拋10次，落地都是正面向上這樣的事件，我們可以問，這枚硬幣正反面對稱的似然程度是多少？我們的任務是求$P(W|S)$，根據輸入圖像得到分類信息，而$P(S|W)$則是知道了分類信息去求這個分類信息表示的像素點的概率，表示我們分好類的各個像素點和真實的像素點分布是否匹配的關系。

$P(S)$是我們輸入圖像的分布，是一個確定的值，不需要再進行計算和求解。問題就轉化為

• $P(S|W)$是我們要求$P(W|S)$的似然函數。
• $P(W)$是這個模型的先驗概率。
  通過計算以上兩點來計算我們所要求的$P(W|S)$

首先，我們給每個像素點設定類別標簽，然后求每個像素點是標簽L的概率，初始標簽是可以隨機給定的，也可以使用聚類算法進行預處理，那么如何體現馬爾可夫隨機場呢？

馬爾可夫隨機場告訴我們像素之間的關聯性，也就是說究竟這個像素跟周圍那些像素相關，關聯度為多少？我們可以根據像素點之間的領域分類情況得出該像素點是否需要更新。但在實際計算中往往只是計算這個像素點周圍標記信息的次數來判斷這個像素點屬于哪個分類標記，通過Hammersley-cilfford定理我們可以看出，吉布斯分布和馬爾可夫隨機場是等價的，也就是說可以用求圖像Gibbons隨機場的概率P代替$P(W)$。吉布斯分布的公式如下：
$$P(W)=z^{?1}exp(?\frac{1}{T}{U}_2(W))$$

所以只要吉布斯分布的能量函數確定了，那么馬爾可夫隨機場也就確定了。所以$P(W)$可以通過吉布斯分布的勢能函數去計算。而求$P(S|W)$即利用標記信息去估計這個像素點的值，假設某個類的標記分類中的像素點分布滿足高斯分布，就可以根據某一像素點的值判斷它在哪個分類中。

$P(S|W)$就是已知分類標簽，那么它的像素值（灰度）是S的概率，現在就假設W=1，某個像素點灰度為S，表示的意思就是在第一類里面像素灰度為S的概率。因為分類標簽在前面說到，每次迭代的時候有一個分類標簽，可以把屬于第一類的所有點都挑出來，考慮每個點都是獨立的，并且認為每一類里面的所有點服從高斯分布，那么在每一類里面可以根據這一類里面的這些點建立一個屬于這一類的高斯密度函數。

為此可以得到每一個點的$P(s|W_1),P(s|W_2),P(s|W_3),P(s|W_4)$分布，通過計算每一個點屬于4類的概率，得到最大似然函數，然后通過乘以$P(W)$得到的概率越大，所屬的類別的可能性越高。這樣就完成了以此迭代，所有的點屬于的類別更新一遍，在這個新的類標簽下進行下一次迭代。

2 條件隨機場的定義與形式

2.1 條件隨機場的定義

條件隨機場是給定隨機變量X條件下，隨機變量Y的馬爾可夫隨機場。本文主要介紹定義在線性鏈上的特殊的條件隨機場，稱為線性鏈條件隨機場。線性條件隨機場可以用于標注等問題。在條件概率模型$P(Y|X)$中，Y是輸出變量，表示標記序列，X是輸入變量，表示需要標注的觀測序列，也把標記序列稱為狀態序列。

條件隨機場
設$X$與$Y$是隨機變量，$P(Y|X)$是在給定X的條件下Y的條件概率分布。若隨機變量Y構成一個由無向圖$G=(V,E)$表示的馬爾可夫隨機場，即
$$P(Y_v|X,Y_w,w=v)=P(Y_v|X,Y_w,w～v)$$
對任意結點v成立，則稱條件概率分布$P(Y|X)$為條件隨機場。式中$w～v$表示在圖$G=(V,E)$中與結點v有邊連接的所有結點w，$w=v$表示結點v以外的所有結點，$Y_v,Y_u,Y_w$為結點$v,u,w$對應的隨機變量。

在定義中，并沒有要求X和Y具有相同的結構。現實中，一般假設X和Y有相同的圖結構。

線性鏈條件隨機場
設
$$X=(X_1,X_2,?,X_n),Y=(Y_1,Y_2,?,Y_n)$$
均為線性鏈表示的隨機變量序列，若在給定隨機變量序列X的條件下，隨機變量序列Y的條件概率分布$P(Y|X)$構成條件隨機場，即滿足馬爾可夫性：
$$P(Y_i|X,Y_1,?,Y_{i?1},Y_{i+1},?,Y_n)=P(Y_i|X,Y_{i?1},Y_{i+1})$$
$$i=1,2,?,n(在i=1和n時只考慮單邊)$$
則稱$P(Y|X)$為線性鏈條件隨機場。在標注問題中，X表示輸入觀測序列，Y表示對應的輸出標記序列或狀態序列。

2.2 條件隨機場的參數化形式

線性鏈條件隨機場的參數化形式
設$P(Y|X)$為線性鏈條件隨機場，則在隨機變量X取值為x的條件下，隨機變量Y取值為y的概率的條件概率具有如下形式：
$$P(y|x)=\frac{1}{Z(x)}exp(\sum _{i,k}{\lambda }_k{t}_k(y_{i?1},y_i,x,i)+\sum _{i,l}{\mu }_l{s}_l(y_i,x,i))$$
$$Z(x)=\sum _{y}exp(\sum _{i,k}{\lambda }_k{t}_k(y_{i?1},y_i,x,i)+\sum _{i,l}{\mu }_l{s}_l(y_i,x,i))$$
式子中，$t_k$和$s_l$是特征函數，${\lambda }_k$和${\mu }_l$是對應的權值，$Z(x)$是規范化因子，求和是在所有可能的輸出序列上進行的。

2.3 條件隨機場的簡化形式

條件隨機場式中同一特征在各個位置都有定義，可以對同一特征在各個位置求和，將局部特征函數轉化為一個全局特征函數，這樣就可以將條件隨機場寫成權值向量和特征向量的內積形式，即條件隨機場的簡化形式。

若以$w$表示權值向量，即$$w=(w_1,w_2,?,w_k{)}^T$$
以$F(y,x)$表示全局特征向量，即$$F(y,x)=(f_1(y,x),f_2(y,x),?,f_K(y,x){)}^T$$
則條件隨機場可以寫成向量$w$與$F(y,x)$內積的形式：$$P_w(y|x)=\frac{exp(w?F(y,x))}{Z_w(x)}$$
其中，$$Z_w(x)=\sum _{y}exp(w?F(y,x))$$

2.4 條件隨機場的矩陣形式

3 條件隨機場的概率計算問題

條件隨機場的概率計算問題是給定條件隨機場$P(Y|X)$，輸入序列x和輸出序列y，計算條件概率$P(Y_i=y_i|x),P(Y_{i?1}=y_{i?1},Y_i=y_i|x)$以及相應的數學期望的問題。為了方便起見，像隱馬爾可夫模型那樣，引入前向-后向向量，遞歸地計算以上概率及期望值。這樣的算法稱為前向-后向算法。

前向-后向算法

對每個指標$i=0,1,?,n+1$，定義前向向量${\alpha }_i(x)$
$${\alpha }_0(y|x)=\{\begin{array}{ll}1,& y=start\\ 0,& otherwise\end{array}$$
遞推公式為${\alpha }_i^T(x)={\alpha }_{i?1}^T(x)M_i(x)$

${\alpha }_i(y_i|x)$表示在位置i的標記是$y_i$并且從1到i的前部分標記序列的非規范化概率，$y_i$可取的值有m個，所以${\alpha }_i(x)$是m維列向量。

對每個指標$i=0,1,?,n+1$，定義前向向量${\beta }_i(x)$
$${\beta }_{n+1}(y_{n+1}|x)=\{\begin{array}{ll}1,& y_{n+1}=stop\\ 0,& otherwise\end{array}$$
遞推公式為${\beta }_i(x)=M_{i+1}(x){\beta }_{i+1}(x)$

${\beta }_i(y_i|x)$表示在位置i的標記是$y_i$，并且從i+1到n的后部分標記序列的非規范化概率。

總結

• 概率無向圖模型是由無向圖表示的聯合概率分布。無向圖上的結點之間的連接關系表示了聯合分布的隨機變量集合之間的條件獨立性，即馬爾可夫性。因此，概率無向圖模型也稱為馬爾可夫隨機場。概率無向圖模型或馬爾可夫隨機場的聯合概率分布，可以分解為無向圖最大團上的正值函數的乘積的形式。
• 條件隨機場是給定輸入隨機變量X條件下，輸出隨機變量Y的條件概率分布模型，其形式為參數化的對數線性模型。條件隨機場的最大特點是假設輸出變量之間的聯合概率分布構成概率無向圖模型，即馬爾可夫隨機場。條件隨機場是判別模型。
• 線性鏈條件隨機場是定義在觀測序列與標記序列上的條件隨機場。線性鏈條件隨機場一般表示為給定觀測序列條件下的標記序列的條件概率分布，由參數化的對數線性模型表示。模型包含特征及相應的權值，特征是定義在線性鏈的邊與結點上的。線性鏈條件隨機場模型的參數形式是最基本的形式，其他形式是其簡化與變形，參數形式的數學表達式是
  $$P(y|x)=\frac{1}{Z(x)}exp(\sum _{i,k}{\lambda }_k{t}_k(y_i?1,y_i,x,i)+\sum _{i,l}{u}_l{s}_l(y_i,x,i))$$
  其中，
  $$Z(x)=\sum _{y}exp(\sum _{i,k}{\lambda }_k{t}_k(y_{i?1},y_i,x,i)+\sum _{i,l}{u}_l{s}_l(y_i,x,i))$$
• 線性鏈條件隨機場的概率計算通常利用前向-后向算法。
• 條件隨機場的學習方法通常是極大似然估計或正則化的極大似然估計法。即在給定訓練數據下，通過極大化訓練數據的對數似然函數估計模型參數，具體算法有改進的迭代尺度算法、梯度下降算法、擬牛頓法。
• 線性鏈條件隨機場的一個重要應用是標注。維比特算法是給定觀測序列求條件概率最大的標記序列的方法。

參考文獻

李航《統計學習方法》第二版

https://blog.csdn.net/weixin_44193282/article/details/108276221

總結

以上是生活随笔為你收集整理的机器学习理论《统计学习方法》学习笔记：第十一章 条件随机场（CRF）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。