死磕-CRF

02-03

寫了一篇條件隨機場的，寫完後，自己還是不是很了解，比較尷尬，所以準備再寫一篇，踏踏實實的過一遍，開始自己去看CRF的論文《Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data》，看了很久，是真的看不懂，然後發現李航的《統計學習方法》裡面專門有一章是說條件隨機場的，沿著書本方法反反覆復看了很多邊，現在準備梳理一下，看能不能說說清晰明了了。

條件隨機場

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

判別模型

判別模型是一種對未觀測數據y與已觀測數據x之間關係進行建模的方法，直接對條件概率p(y|x;θ)建模。

本文首先介紹概率無向圖模型，然後敘述條件隨機場的定義和各種表示方法，最後介紹條件隨機場的3個基本問題：概率計算、學習問題和預測問題。

概率無向圖模型

概率無向圖模型又稱為馬爾可夫隨機場，是一個可以由無向圖表示的聯合概率分布。

模型定義：

圖是由結點及連接結點的邊組成的集合，結點和邊分別記作v和e，結點和邊的集合分別記作V和E，圖記作G=(V,E)，無向圖是指邊沒有方向的圖。

概率圖模型是由圖表示的概率分布。設聯合概率分布P(Y)， $Yin gamma$ 是一組隨機變數。由無向圖G=(V,E)表示概率分布P(Y),即在圖G中，結點 $vin V$ 表示一個隨機變數 $Y_v$ ， $Y=(Y_v)_{vin V}$

;邊 $e in E$ 表示隨機變數之間的概率依賴關係。

給定一個聯合概率分布P(Y)和它的無向圖G。首先定義無向圖表示的隨機變數之間存在馬爾可夫性、局部馬爾可夫性和全局馬爾可夫性。那麼我們就先來看看這三個性質的定義。

成對馬爾可夫性

設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)$

局部馬爾可夫性：

設 $v in V$ 是無向圖G中的任意一個結點，W是與v有邊連接的所有結點，O是v，W以外的其他所有結點，v表示隨機變數是 $Y_v$ ，W表示的隨機變數組是 $Y_w$ ,O表示的隨機變數組是 $Y_O$ ,局部馬爾可夫性是指在給定隨機變數組 $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)ne0$ 時，等價地，

$P(Y_v|Y_W)=P(Y_v,|Y_W,Y_O)$

全局馬爾可夫性

設結點集合A，B是在無向圖G中被結點集合C分開的任意結點集合，結點集合A，B和C所對應的隨機變數組分別是 $Y_A,Y_B$ 和 $Y_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)滿足成對、局部或全局馬爾可夫性，就稱此聯合概率分布為概率無向圖模型，或馬爾可夫隨機場。

實際上，我們更加關心的是如何求概率無向圖模型的聯合概率分布。對於給定的概率無向圖模型，我們希望將整體的聯合概率分布寫成若干子聯合概率的乘積形式，也就是將聯合概率進行因子分解，這樣便於模型的學習與計算。

團與最大團

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

上圖中有5個團： $left{ Y_1,Y_2 right},left{ Y_2,Y_3 right},left{ Y_3,Y_4 right},left{ Y_4,Y_2 right},left{ Y_1,Y_4 right}$ 。

2個最大團： $left{ Y_1,Y_2,Y_4 right},left{ Y_2,Y_3,Y_4 right}$ 。

因子分解

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

給定概率無向圖模型，設其無向圖為G，C為G上的最大團， $Y_C$ 表示C對應的隨機變數。那麼概率無向圖模型的聯合概率分布P(Y)可寫作圖中所有最大團C上的函數 $Psi_C(Y_C)$ 的乘積形式，即：

$P(Y)=frac{1}{Z}prod_{C}^{}Psi_C(Y_C)$

其中，Z是規範化因子，由式

$Z=sum_{Y}^{}{prod_{C}^{}}Psi_C(Y_C)$

給出，規範化因子保證P(Y)構成一個概率分布，函數 $Psi_C(Y_C)$ 稱為勢函數。這裡要求勢函數是嚴格正的，通常定義為指數函數：

$Psi_C(Y_C)=expleft{ -E(Y_C) right}$

Hammersley-Clifford 定理

概率無向圖模型的聯合概率分布P(Y)可以表示為如下形式：

$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上定義的嚴格正函數，乘積是在無向圖所有的最大團上進行的。

條件隨機場的定義

條件隨機場是給定的隨機變數X條件下，隨機變數Y的馬爾可夫隨機場。這裡主要介紹定義線性鏈上的特殊的條件隨機場，稱為線性鏈條件隨機場。它可以用於標註等問題，這時，在條件概率模型P(Y|X)中，Y是輸出變數，表示標記序列，X是輸入變數，表示需要標註的觀測序列。也把標記序列稱為狀態序列。學習時，利用訓練數據集通過極大似然估計或正則化的極大似然估計得到條件概率模型 $tilde{P}(Y|X)$ ;預測時，對於給定的輸入序列x，求出條件概率 $tilde{P}(Y|X)$ 最大的輸出序列 $tilde{y}$ 。

條件隨機場

設X與Y是隨機變數，P(Y|X)是在給定X的條件下Y的條件概率分布。若隨機變數Y構成一個由無向圖G=(V,E)表示的馬爾可夫隨機場，即：

$P(Y_v|X,Y_w,wne v)=P(Y_v|X,Y_w,wsim v)$

對於任意結點v成立，則稱條件概率分布P(Y|X)為條件隨機場。式中 $wsim v$ 表示在圖G=(V,E)中與結點v有邊連接的所有結點w, $wne v$ 表示結點v以外的所有結點， $Y_v$ , $Y_u$ 和 $Y_w$ 為結點v，u與w對應的隨機變數。

線性鏈條件隨機場

設 $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表示對應的輸出標記序列或者狀態序列。

線性鏈條件隨機場的參數化形式

設P(Y|X)為線性鏈條件隨機場，則在隨機變數X取值為 x的條件下，隨機變數Y取值為y的條件概率具有如下形式：

$P(y|x)=frac{1}{Z(x)}exp left{sum_{i,k}^{}{lambda_kt_k(y_{i-1},y_i,x,i)}+sum_{i,l}^{}{mu_ls_l(y_i,x,i)} right}$

其中，

$Z(x)=sum_{y}^{}{exp left{sum_{i,k}^{}{lambda_kt_k(y_{i-1},y_i,x,i)}+sum_{i,l}^{}{mu_ls_l(y_i,x,i)} right}}$

式中， $t_k$ 和 $s_l$ 是特徵函數， $lambda_k$ 和 $mu_k$ 是對應的權值。Z(x)是規範化因子，求和是在所有可能的輸出序列上進行的。

$t_k$ 是定義在邊上的特徵函數，稱為轉移特徵，依賴於當前和前一個位置， $s_l$ 是定義在結點上的特徵函數，稱為狀態特徵，依賴於當前位置。 $t_k$ 和 $s_l$ 都依賴於位置，是局部特徵函數，通常特徵函數 $t_k$ 和 $s_l$ 取之為1或0；當滿足特徵條件時取值為1，否則為0，條件隨機場完全由特徵函數 $t_k$ 和 $s_l$ 和對應的權值 $lambda_k$ , $mu_l$ 確定。線性鏈條件隨機場也是對數線性模型。

條件隨機場的簡化形式

上面我們得到條件隨機場的公式：

$P(y|x)=frac{1}{Z(x)}exp left{sum_{i,k}^{}{lambda_kt_k(y_{i-1},y_i,x,i)}+sum_{i,l}^{}{mu_ls_l(y_i,x,i)} right}$

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

為了方便起見，首先將轉移特徵和狀態特徵及其權值同統一符號表示。設有 $K_1$ 個轉移特徵， $K_2$ 個狀態特徵， $K=K_1+K_2$ ，記：

$f_k(y_{i-1},y_i,x,i)=begin{cases} & t_k(y_{i-1},y_i,x,i) k=1,2....K_1 & s_l(y_i,x,i) k=K_1+l;l=1,2....K_2 end{cases}$

然後對轉移與狀態特徵在各個位置i求和，記作：

$f_k(y,x)=sum_{i=1}^{n}{f_k(y_{i-1},y_i,x,i)}, k=1,2,.....K$

用 $w_k$ 表示特徵 $f_k(y,x)$ 的權值，即

$w_k=begin{cases} & lambda_k k=1,2....K_1 & mu_l k=K_1+l;l=1,2....K_2 end{cases}$

於是條件隨機場可表示為：

$P(y|x)=frac{1}{Z(X)}expleft{ sum_{k=1}^{K}{w_kf_k(y,x)} right}$

$Z(x)=sum_{y}^{}{expleft{ sum_{k=1}^{K}{w_kf_k(y,x)} right}}$

若以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{expleft{ wcdot F(y,x) right}}{Z_w(x)}$

其中

$Z_w(x)=sum_{y}^{}{expleft{ wcdot F(y,x) right}}$

條件隨機場的矩陣形式

條件隨機場還可以由矩陣表示，假設 $P_w(y|x)$ 是由：

$P(y|x)=frac{1}{Z(X)}expleft{ sum_{k=1}^{K}{w_kf_k(y,x)} right}$

$Z(x)=sum_{y}^{}{expleft{ sum_{k=1}^{K}{w_kf_k(y,x)} right}}$

給出的線性鏈條件隨機場，表示對給定觀測序列x,相應的標記序列y的條件概率。引進特殊的起點和終點狀態標記 $y_0=start$ , $y_{n+1}=stop$ ,這時 $P_w(y|x)$ 可以通過矩陣形式表示。

對觀測序列x的每一個位置i=1,2,.....n+1，定義一個m階矩陣(m是標記 $y_i$ 取值的個數)

$M_i(x)=left[ M_i(y_{i-1},y_i|x) right]$

$M_i(y_{i-1},y_i|x) =expleft{ W_i(y_{i-1},y_i|x) right}$

$W_i(y_{i-1},y_i|x) =sum_{i=1}^{K}{w_kf_k(y_{i-1},y_i,x,i)}$

這樣，給定觀測序列x。標記序列y的非規範化概率可以通過n+1個矩陣的乘積 $prod_{i}^{n+1}M（y_{i-1},y_i|x）$ 表示，於是，條件概率 $P_w(y|x)$ 是

$P_w(y|x)=frac{1}{Z_w(x)}prod_{i=1}^{n+1}M（y_{i-1},y_i|x）$

其中 $Z_w(x)$ 為規範化因子，是n+1個矩陣的乘積的(start，stop)元素:

. $Z_w(x)=(M_1(x)M_2(x)......M_{n+1}(x))_{start,stop}$

注意， $y_0=start$ 與 $y_{n+1}=stop$ 表示開始狀態與終止狀態，規範化因子 $Z_w(x)$ 是以start為起點，stop為終點通過狀態的所有路徑 $y_1,y_2.....y_n$ 的非規範化概率 $prod_{i}^{n+1}M（y_{i-1},y_i|x）$ 之和。

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

條件概率計算問題是給定條件隨機場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_i(y|x)=begin{cases} & 1 y=start & 0 否則 end{cases}$

遞推公式

$alpha _{i}^{T}(y_i|x)=alpha _{i-1}^{T}(y_{i-1}|x)M_i(y_{i-1},y_i|x) , i=1,2,...n+1$

又可表示為

$alpha _{i}^{T}(x)=alpha _{i-1}^{T}(x)M_i(x)$

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

同樣的對每個指標i=0,1,........n+1,定義後向向量 $beta_i(x)$ :

$beta_i(y|x)=begin{cases} & 1 y=stop & 0 否則 end{cases}$

$beta_i(y_i|x)=M_i(y_i,y_{i+1}|x)beta_{i-1}(y_{i+1}|x)$

又可以表示為

$beta_i(x)=M_{i+1}(x)beta_{i+1}(x)$

$beta_i(y_i|x)$ 表示在位置i的標記為 $y_i$ 並且從i+1到n的後部分標記序列的非規範化概率。

由前向-後向向量不難得到：

$Z(x)=alpha_{n}^{T}(x)cdot1=1^Tcdotbeta_1(x)$

這裡，1是元素均為1的m維列向量。

概率計算

按照向前-向後向量的定義，很容易計算標記序列在位置i是標記 $y_i$ 的條件概率和位置i-1與i是標記 $y_{i-1}$ 和 $y_i$ 的條件概率：

$P(Y_i=y_i|x)=frac{alpha_{i}^{T}(y_i|x)beta_i(y_i|x)}{Z(x)}$

$P(Y_{i-1}=y_{i-1},Y_i=y_i|x)=frac{alpha_{i-1}^{T}(y_{i-1}|x)M_i(y_{i-1},y_i|x)beta_i(y_i|x)}{Z(x)}$

其中， $Z(x)=alpha_{n}^{T}(x)cdot1$

期望值的計算

利用前向-後向向量，可以計算出特徵函數關於聯合分布P(X,Y)和條件分布P(Y|X)的數學期望。特徵函數 $f_k$ 關於條件分布P(Y|X)的數學期望是：

$E_{P(Y|X)}[f_k]=sum_{y}^{}{P(y|x)f_k(y,x)} =sum_{i=1}^{n+1}{sum_{y_{i-1}y_i}^{}{ f_k(y_{i-1},y_i,x,i)frac{alpha_{i-1}^{T}(y_{i-1|}|x)M_i(y_{i-1},y_i|x)beta_i(y_i|x)}{Z(x)} }} k=1,2,3....K$

其中， $Z(x)=alpha_{n}^{T}(x)cdot1$ .

假設經驗分布為 $tilde{P}(X)$ ,特徵函數 $f_k$ 關於聯合分布P(X,Y)的數學期望是：

$E_{P(X,Y)}[f_k]=sum_{x,y}^{}{P(x,y)sum_{i=1}^{n+1}{f_k(y_{i-1},y_i,x,i)}} =sum_{x}^{}{tilde{P}(x)sum_{y}^{}{P(y|x)}sum_{i=1}^{n+1}{f_k(y_{i-1},y_i,x,i)}} =sum_{x}^{}{tilde{P}(x)}sum_{i=1}^{n+1}{sum_{y_{i-1}y_i}^{}{ f_k(y_{i-1},y_i,x,i)frac{alpha_{i-1}^{T}(y_{i-1|}|x)M_i(y_{i-1},y_i|x)beta_i(y_i|x)}{Z(x)} }} k=1,2,3....K$

其中， $Z(x)=alpha_{n}^{T}(x)cdot1$

以上是特徵函數數學期望的一般計算公式，對於給定的觀測序列x與標記序列y，可以通過一次前向掃描計算 $alpha_i$ 及Z(x),通過一次後向掃描計算 $beta_i$ ,從而計算所有的概率和特徵的期望。

條件隨機場的學習演算法

給定訓練數據集估計條件隨機場模型參數問題，叫做條件隨機場的學習問題。條件隨機場模型實際上是定義在時序數據上的對數線形模型，其學習方法包括極大似然估計和正則化的極大似然估計。具體的優化實現演算法有改進的迭代尺度法IIS、梯度下降法以及擬牛頓法。這裡不再展開，有需求的去看李航《統計學習方法》吧。

條件隨機場的預測演算法

條件隨機場的預測問題是給定條件隨機場P(Y|X)和輸入序列(觀測序列)x,求條件概率最大的輸出序列 $y^*$ ,即對觀察序列進行標註。條件隨機場的預測演算法是著名的維特比演算法，下一篇文章見會介紹維特比演算法，這裡也不做展開。

如果你認真看過《統計學習方法》，你會發現，本篇文章基本是上面的原文，這樣寫的原因有兩個：1.我搜索了網路上，沒有看見對條件隨機場系統介紹的，都是說得比較模糊，所以寫這篇出來做個影子，讓大家知道其實《統計學習方法》裡面有系統介紹。2.我對條件隨機場看了很多遍，一直不能很好的理解，所以就決定抄一遍書上的內容，感覺還是有一點用處的，比開始懂了一些。

介於NLP有些演算法這麼難以理解，也給我接下來怎麼走有一點啟發吧，如果簡單的演算法，我會吃透，如果複雜的演算法，我暫時不會花力氣去搞懂它，而是直接調tf已有的演算法包去直接用。

今天就先到這裡，晚安。

參考資料：

1.李航《統計學習方法》

2.Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data