文章目錄
-
- 什麼是條件随機場？
- 前言
- 隐馬爾科夫模型HMM (生成模型)
- CRF
-
- 特征函數舉例
- 邏輯回歸
- HMM
- 學習CRF的參數
- CRF實作細節
-
- 位置1：
- 位置2
- 位置3
- 總結
什麼是條件随機場？
Random指的隐藏狀态随機變量Y和觀測狀态随機變量X。
Conditional指條件機率，是以CRF是一個判别式模型 (discriminative model)。而生成式模型則計算聯合機率分布。
關于生成模型和判别模型:
生成模型VS判别模型
機器學習面試之生成模型VS判别模型
前言
對于序列标注模型，輸入一個文本序列，輸出标注結果。在HMM和CRF模型中，輸入的文本序列對應觀測序列，标注結果對應隐藏狀态，是以模型的目的是根據觀測序列計算隐藏狀态。
隐馬爾科夫模型HMM (生成模型)
以詞性标注任務為例，給定一個觀測序列即輸入文本X，計算輸出詞性序列Y
P ( Y ∣ X ) = P ( X ∣ Y ) ∗ P ( Y ) P ( X ) P ( X , Y ) = P ( X ∣ Y ) P ( Y ) = ∏ i = 1 n p ( x i ∣ Y ) ∗ P ( Y ) = ∏ i = 1 n p ( x i ∣ y i ) ∗ P ( Y ) = p ( y 1 ) ∗ p ( y 1 ∣ x 1 ) ∏ i = 2 n p ( x i ∣ y i ) ∗ p ( y i ∣ y i − 1 ) P(Y|X)=\frac{P(X|Y)*P(Y)}{P(X)}\\ P(X,Y)=P(X|Y)P(Y)\\ =\prod_{i=1}^{n}p(x_i|Y)*P(Y)\\ =\prod_{i=1}^{n}p(x_i|y_i)*P(Y)\\ =p(y_1)*p(y_1|x_1)\prod_{i=2}^{n}p(x_i|y_i)*p(y_i|y_{i-1}) P(Y∣X)=P(X)P(X∣Y)∗P(Y)P(X,Y)=P(X∣Y)P(Y)=i=1∏np(xi∣Y)∗P(Y)=i=1∏np(xi∣yi)∗P(Y)=p(y1)∗p(y1∣x1)i=2∏np(xi∣yi)∗p(yi∣yi−1)
上述公式每一步對應一個假設
- 由輸入詞間的條件獨立性得到 ∏ i = 1 n p ( x i ∣ Y ) \prod_{i=1}^{n}p(x_i|Y) ∏i=1np(xi∣Y)
- 目前觀測結果隻與目前隐層狀态有關 ∏ i = 1 n p ( x i ∣ y i ) \prod_{i=1}^{n}p(x_i|y_i) ∏i=1np(xi∣yi)， p ( x i ∣ y i ) p(x_i|y_i) p(xi∣yi)為發射機率（emission probabilities ）。
- 馬爾科夫假設，每一個隐層狀态僅與上一個隐層狀态有關 p ( y i ∣ y i − 1 ) p(y_i|y_{i-1}) p(yi∣yi−1)， p ( y i ∣ y i − 1 ) p(y_i|y_{i-1}) p(yi∣yi−1)為轉移機率（transition probabilities），例如介詞後面跟一個名詞，則轉移機率高。
CRF
CRF使用feature function來更抽象的表達特征，使得它不再局限于HMM的兩類特征。特征函數可以表示為 f ( x , i , y i , y i − 1 ) f(x, i, y_i, y_{i-1}) f(x,i,yi,yi−1)，其中X表示輸入序列，i表示目前位置， y i y_i yi表示目前狀态，在linear-chain CRF中 y i − 1 y_{i-1} yi−1表示前一個狀态。
我們賦予每個特征函數一個權重 λ j \lambda_j λj，給定一個輸入序列，我們累加所有輸入權重的特征值标注 y y y：
s c o r e ( y ∣ x ) = ∑ j = 1 m ∑ i = 1 n λ j f j ( x , i , y i , y i − 1 ) score(y|x)=\sum_{j=1}^{m}\sum_{i=1}^{n}\lambda_jf_j(x,i,y_i,y_{i-1}) score(y∣x)=∑j=1m∑i=1nλjfj(x,i,yi,yi−1)
最終可以得到一條輸出 y y y的機率值（0~1）
p ( y ∣ x ) = e x p [ s c o r e ( y ∣ x ) ] ∑ y ′ e x p [ s c o r e ( y ′ ∣ x ) ] = e x p [ ∑ j = 1 m ∑ i = 1 n λ j f j ( x , i , y i , y i − 1 ) ] ∑ y ′ e x p [ ∑ j = 1 m ∑ i = 1 n λ j f j ( x , i , y ′ i , y ′ i − 1 ) ] p(y|x)=\frac{exp[score(y|x)]}{\sum_{y'}exp[score(y'|x)]}=\frac{exp[\sum_{j=1}^{m}\sum_{i=1}^{n}\lambda_jf_j(x,i,y_i,y_{i-1})]}{\sum_{y'}exp[\sum_{j=1}^{m}\sum_{i=1}^{n}\lambda_jf_j(x,i,{y'}_i,{y'}_{i-1})]} p(y∣x)=∑y′exp[score(y′∣x)]exp[score(y∣x)]=∑y′exp[∑j=1m∑i=1nλjfj(x,i,y′i,y′i−1)]exp[∑j=1m∑i=1nλjfj(x,i,yi,yi−1)]
特征函數舉例
我們以英文單詞的詞性模組化，這裡舉例的特征函數不僅僅局限于線性鍊CRF：
-
如果滿足條件：目前英文單詞以 ‘ly’ 結尾 && 特征函數标注 y i y_i yi為副詞
則記 f 1 ( x , i , y i , y i − 1 ) = 1 e l s e 0 f_1(x,i,y_i,y_{i-1})=1\ \ else \ 0 f1(x,i,yi,yi−1)=1 else 0，則控制該特征函數的權重 λ 1 \lambda_1 λ1傾向一個大的正值，因為以 ‘ly’ 結尾通常為副詞。
-
如果滿足條件：目前位置為1 && 輸入的結尾是問好 && 特征函數标注 y i y_i yi為動詞
則記 f 2 ( x , i , y i , y i − 1 ) = 1 e l s e 0 f_2(x,i,y_i,y_{i-1})=1\ else\ 0 f2(x,i,yi,yi−1)=1 else 0，則控制該特征函數的權重 λ 2 \lambda_2 λ2傾向一個大的正值。例如 “Is this a sentence beginning with a verb?”
-
如果滿足條件： y i − 1 y_{i-1} yi−1為形容詞 && y i y_i yi為名詞
則記 f 3 ( x , i , y i , y i − 1 ) = 1 e l s e 0 f_3(x,i,y_i,y_{i-1})=1\ \ else \ 0 f3(x,i,yi,yi−1)=1 else 0，則控制該特征函數的權重 λ 3 \lambda_3 λ3傾向一個大的正值，因為形容詞後面通常跟名詞。
-
如果滿足條件： y i − 1 y_{i-1} yi−1為介詞 && y i y_i yi為介詞
則記 f 4 ( x , i , y i , y i − 1 ) = 1 e l s e 0 f_4(x,i,y_i,y_{i-1})=1\ \ else \ 0 f4(x,i,yi,yi−1)=1 else 0，則控制該特征函數的權重 λ 4 \lambda_4 λ4為一個負值，因為介詞通常後面不再跟介詞。
假定輸入為n，一條路徑的score包含n個位置的多個特征函數的計算，要将每條路徑輸出一個機率，則需累加所有路徑的exp[score]，通過 e x p [ s c o r e ( y ) ] ∑ e x p [ s c o r e ( y ′ ) ] \frac{exp[score(y)]}{\sum exp[score(y')]} ∑exp[score(y′)]exp[score(y)]計算一個機率值（0~1）。
邏輯回歸
CRF機率的形式 p ( l ∣ x ) = e x p [ ∑ j = 1 m ∑ i = 1 n λ j f j ( x , i , y i , y i − 1 ) ] ∑ y ′ e x p [ ∑ j = 1 m ∑ i = 1 n λ j f j ( x , i , y ′ i , y ′ i − 1 ) ] p(l|x)=\frac{exp[\sum_{j=1}^{m}\sum_{i=1}^{n}\lambda_jf_j(x,i,y_i,y_{i-1})]}{\sum_{y'}exp[\sum_{j=1}^{m}\sum_{i=1}^{n}\lambda_jf_j(x,i,{y'}_i,{y'}_{i-1})]} p(l∣x)=∑y′exp[∑j=1m∑i=1nλjfj(x,i,y′i,y′i−1)]exp[∑j=1m∑i=1nλjfj(x,i,yi,yi−1)]看起來很像邏輯回歸，CRF實際上是基礎的邏輯回歸的序列化版本，邏輯回歸是一個log-linear的分類模型，CRF是一個log-linear的序列模型。
邏輯回歸介紹
HMM
根據前面對HMM的介紹，HMM模型可以定義為 p ( y 1 ) ∗ ∏ i p ( x i ∣ y i ) ∗ p ( y i ∣ y i − 1 ) p(y_1)*\prod_{i}p(x_i|y_i)*p(y_i|y_{i-1}) p(y1)∗∏ip(xi∣yi)∗p(yi∣yi−1)
将上式取log得 log p ( y , x ) = log p ( l 1 ) + ∑ i log p ( y i ∣ y i − 1 ) + ∑ i log p ( y i ∣ x i ) \log{p(y,x)}=\log{p(l_1)}+\sum_i\log{p(y_i|y_{i-1})}+\sum_i\log{p(y_i|x_i)} logp(y,x)=logp(l1)+∑ilogp(yi∣yi−1)+∑ilogp(yi∣xi)，我們可以建構一個等效于HMM的CRF模型：
- 對于轉移機率 p ( y i = b ∣ y i − 1 = a ) p(y_i=b|y_{i-1}=a) p(yi=b∣yi−1=a)，當 y i = b , y i − 1 = a y_i=b,y_{i-1}=a yi=b,yi−1=a時我們定義一組CRF轉移特征函數 f ( a , b ) ( x , i , y i , y i − 1 ) = 1 f_{(a,b)}(x,i,y_i,y_{i-1})=1 f(a,b)(x,i,yi,yi−1)=1，賦予特征函數的權重 λ ( a , b ) = log p ( y i = a ∣ y i − 1 = b ) \lambda_{(a,b)}=\log{p(y_i=a|y_{i-1}=b)} λ(a,b)=logp(yi=a∣yi−1=b)
- 對于發射機率 p ( x i = c ∣ y i = b ) p(x_i=c|y_i=b) p(xi=c∣yi=b)，當 y i = b , x i = c y_i=b,x_i=c yi=b,xi=c時定義一組發射特征函數 g ( x , y ) ( x , i , y i , y i − 1 ) = 1 g_{(x,y)}(x,i,y_i,y_{i-1})=1 g(x,y)(x,i,yi,yi−1)=1，賦予特征函數的權重 λ ( c , b ) = log p ( x i = c ∣ y i = b ) \lambda_{(c,b)}=\log{p(x_i=c|y_i=b)} λ(c,b)=logp(xi=c∣yi=b)
這樣，計算的score p ( y ∣ x ) p(y|x) p(y∣x)成比例關聯于HMM的結果。
CRF優于HMM的原因是：
- CRF可以建構更多豐富的特征，HMM隻能建構二進制轉移和發射特征，CRF可以使用全局的特征，例如上述CRF特征函數舉例2。
- CRF特征函數的權重不受限制，HMM的機率需要滿足一定的限制： 0 < = p ( x i ∣ y i ) < = 1 , ∑ x p ( x i = x ∣ y 1 ) = 1 0<=p(x_i|y_i)<=1,\ \sum_xp(x_i=x|y_1)=1 0<=p(xi∣yi)<=1, ∑xp(xi=x∣y1)=1
學習CRF的參數
采用梯度下降學習CRF的特征函數的權重。首先，随機初始化CRF模型的權重，采用梯度更新算法更新權重。
對于每一個樣本
- 計算特征權重 λ i \lambda_i λi的梯度 ∂ ∂ w j log p ( y ∣ x ) = ∑ j = 1 m f i ( x , j , y j , y j − 1 ) − ∑ y ′ ∑ j = 1 m f i ( x , j , y j ′ , y j − 1 ′ ) \frac{\partial}{\partial{w_j}}\log{p(y|x)}=\sum_{j=1}^mf_i(x,j,y_j,y_{j-1})-\sum_{y'}\sum_{j=1}^{m}f_i(x,j,y'_j,y'_{j-1}) ∂wj∂logp(y∣x)=∑j=1mfi(x,j,yj,yj−1)−∑y′∑j=1mfi(x,j,yj′,yj−1′)
- 更新權重 λ i = λ i + α [ ∑ j = 1 m f i ( x , j , y j , y j − 1 ) − ∑ y ′ ∑ j = 1 m f i ( x , j , y j ′ , y j − 1 ′ ) ] \lambda_i=\lambda_i+\alpha[\sum_{j=1}^mf_i(x,j,y_j,y_{j-1})-\sum_{y'}\sum_{j=1}^{m}f_i(x,j,y'_j,y'_{j-1})] λi=λi+α[∑j=1mfi(x,j,yj,yj−1)−∑y′∑j=1mfi(x,j,yj′,yj−1′)]
CRF實作細節
CRF的計算難點在于分母歸一化因子的計算（配分函數），這裡我推導一下計算的細節。
假定标簽數為2，序列長度為3，計算歸一化因子。在CRF模型中，隻考慮了臨近标簽的聯系，所有歸一化因子包含的路徑數應為 2 3 = 8 2^3=8 23=8條。我們按時刻t計算不同标簽（記為k）的的歸一化因子 Z t ( k ) Z_t^{(k)} Zt(k)， Z t = Z t ( 1 ) + Z t ( 2 ) + . . . + Z t ( k ) Z_t=Z_t^{(1)}+Z_t^{(2)}+...+Z_t^{(k)} Zt=Zt(1)+Zt(2)+...+Zt(k)， Z t ( k ) Z_t^{(k)} Zt(k)分别是截止到目前時刻 t t t、以标簽 1 , 2 , . . . k 1,2,...k 1,2,...k為終點的所有路徑的得分指數和。接下來，我們具體計算一下：
記編碼模型（RNN、CNN）對位置 t t t标簽k的打分為 h t ( k ) h_t^{(k)} ht(k)，标簽 i i i到 j j j的轉移機率 g i j g_{ij} gij
位置1：
初始 Z t ( k ) Z_t^{(k)} Zt(k)采用模型編碼分 h t k h_t^{k} htk
位置2
Z 2 ( 1 ) = log ( e [ Z 1 ( 1 ) + g 11 ] + e [ Z 1 ( 2 ) + g 21 ] ) + h 2 ( 1 ) = log ( e [ Z 1 ( 1 ) + g 11 + h 2 ( 1 ) ] + e [ Z 1 ( 2 ) + g 21 + h 2 ( 1 ) ] ) Z 2 ( 2 ) = log ( e [ Z 1 ( 1 ) + g 12 ] + e [ Z 1 ( 2 ) + g 22 ] ) + h 2 ( 2 ) = log ( e [ Z 1 ( 1 ) + g 12 + h 2 ( 2 ) ] + e [ Z 1 ( 2 ) + g 22 + h 2 ( 2 ) ] ) Z_2^{(1)}=\log{(e^{[Z_1^{(1)}+g_{11}]} + e^{[Z_1^{(2)}+g_{21}]})}+h_2^{(1)}=\log{(e^{[Z_1^{(1)}+g_{11}+h_2^{(1)}]} + e^{[Z_1^{(2)}+g_{21}+h_2^{(1)}]})}\\ Z_2^{(2)}=\log{(e^{[Z_1^{(1)}+g_{12}]} + e^{[Z_1^{(2)}+g_{22}]})}+h_2^{(2)}=\log{(e^{[Z_1^{(1)}+g_{12}+h_2^{(2)}]} + e^{[Z_1^{(2)}+g_{22}+h_2^{(2)}]})} Z2(1)=log(e[Z1(1)+g11]+e[Z1(2)+g21])+h2(1)=log(e[Z1(1)+g11+h2(1)]+e[Z1(2)+g21+h2(1)])Z2(2)=log(e[Z1(1)+g12]+e[Z1(2)+g22])+h2(2)=log(e[Z1(1)+g12+h2(2)]+e[Z1(2)+g22+h2(2)])
位置3
Z 3 ( 1 ) = log ( e [ Z 2 ( 1 ) + g 11 + h 3 ( 1 ) ] + e [ Z 3 ( 2 ) + g 21 + h 3 ( 1 ) ] ) Z 3 ( 2 ) = log ( e [ Z 2 ( 1 ) + g 12 + h 3 ( 2 ) ] + e [ Z 3 ( 2 ) + g 22 + h 3 ( 2 ) ] ) Z_3^{(1)}=\log{(e^{[Z_2^{(1)}+g_{11}+h_3^{(1)}]} + e^{[Z_3^{(2)}+g_{21}+h_3^{(1)}]})}\\ Z_3^{(2)}=\log{(e^{[Z_2^{(1)}+g_{12}+h_3^{(2)}]} + e^{[Z_3^{(2)}+g_{22}+h_3^{(2)}]})} Z3(1)=log(e[Z2(1)+g11+h3(1)]+e[Z3(2)+g21+h3(1)])Z3(2)=log(e[Z2(1)+g12+h3(2)]+e[Z3(2)+g22+h3(2)])
然後将 Z 2 ( 1 ) , Z 2 ( 2 ) Z_2^{(1)}, Z_2^{(2)} Z2(1),Z2(2)帶入上式
Z 3 ( 1 ) = log ( e [ Z 1 ( 1 ) + g 11 + h 2 ( 1 ) + g 11 + h 3 ( 1 ) ] + e [ Z 1 ( 2 ) + g 21 + h 2 ( 1 ) + g 11 + h 3 ( 1 ) ] ) + e [ Z 1 ( 1 ) + g 12 + h 2 ( 2 ) + g 21 + h 3 ( 1 ) ] ) + e [ Z 1 ( 2 ) + g 22 + h 2 ( 2 ) + g 21 + h 3 ( 1 ) ] ) Z_3^{(1)}=\log{(e^{[Z_1^{(1)}+g_{11}+h_2^{(1)}+g_{11}+h_3^{(1)}]} + e^{[Z_1^{(2)}+g_{21}+h_2^{(1)}+g_{11}+h_3^{(1)}]})+ e^{[Z_1^{(1)}+g_{12}+h_2^{(2)}+g_{21}+h_3^{(1)}]})} + e^{[Z_1^{(2)}+g_{22}+h_2^{(2)}+g_{21}+h_3^{(1)}]}) Z3(1)=log(e[Z1(1)+g11+h2(1)+g11+h3(1)]+e[Z1(2)+g21+h2(1)+g11+h3(1)])+e[Z1(1)+g12+h2(2)+g21+h3(1)])+e[Z1(2)+g22+h2(2)+g21+h3(1)])
同理可以計算 Z 3 ( 2 ) Z_3^{(2)} Z3(2)，這裡就不重複寫了。
總結
- 每一步實際通過 l o g s u m e x p logsumexp logsumexp 來累加到一個節點 Z t ( k ) Z_t^{(k)} Zt(k)的所有路徑指數和。
- 編碼模型分 h t ( k ) h_t^{(k)} ht(k)也可以提前指數相加進來。
簡明條件随機場CRF介紹（附帶純Keras實作）
Advanced NLP: Conditional Random Fields
CRF主體參考 Introduction to Conditional Random Fields
知乎點贊排前2的回答 如何用簡單易懂的例子解釋條件随機場（CRF）模型？它和HMM有什麼差別？
![seq2seq模型 + Attention機制[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)