導語： 理解條件隨機場CRF模型的原理，有些文章會從隱馬爾科夫模型HMM講起，再結合PGM的一些基本性質定理轉到CRF推導上來，這種講解方式需要讀者懂一些PGM的背景才好理解，否則中間會感到很突兀；另外一種講解方式是從Log-Linear模型開始，從模型架構，特徵函式，訓練最佳化方式到CRF與其的關係，我個人比較喜歡第二種方式，下面將會把我看過的相關內容整理成此篇筆記。

簡要背景-HMM&CRF

Log-Linear的基本內容

模型訓練

特徵函式

隱馬爾科夫模型HMM

CRF模型

總結

參考資料

簡要背景-HMM&CRF

在自然語言處理中，存在很多序列到序列的任務，比如機器翻譯，詞性標註，命名實體識別，都是需要對給定的輸入句子，輸出一個帶標籤的序列，如果按照PGM中對應的概念，我們會把輸入的句子中的字作為觀測序列

x = (x_0, x_1, x_2, \dots x_T)

， 把我們比較關注的任務如詞性，實體類別等作為隱含狀態序列

y = (y_0, y_1, y_2, \dots y_T)

。

我們常聽說的隱馬爾科夫模型HMM，就是去學習觀測序列與隱含狀態序列的聯合機率分佈

p(x, y)

， 而條件隨機場模型CRF學習的是條件機率

p(y|x)

，因此我們也常說CRF是一種判別模型。從掌握這兩個模型的難度上來講，HMM要容易得多，CRF的難度相對更大，CRF使用的場景也更多，如在命名實體的網路結構中，最後一層目前基本都是CRF為主，因此理解這個模型的原理還是很有必要的，從HMM到CRF之間，還有一個比較有名的模型是MEMM模型。

Log-Linear的基本內容

Log-Linear模型的身影經常出現很早的自然語言模型的語言模型中，用於描述一種條件機率，對於給定輸入序列

x, y

，以及模型引數

w

， 模型如下：

p(y|x;w) = \frac{exp(w \cdot F(x, y))}{\sum_{y

或者非矩陣相乘的形式：

p(y|x;w) = \frac{exp(\sum_{j=1}^J w_j f_j(x, y))}{Z(x,w)} \\

其中

w_j

是整個模型的引數，是需要學習的，

f_j(x, y)

被稱為

特徵函式

，其描述了觀測序列

x

和隱含狀態序列

y

的某種規則/關係，後續將會對其做舉例說明；

Z(x, w)

是歸一化因子，因為我們的輸出是條件機率，需要滿足取值在

[0, 1]

之間，所以不能省略了該項，

Z(x, w)

有個專門的名詞

partition function

，其形式為：

Z(x, w) = \sum_{y

看完上面的公式，需要注意的幾點是：

x

，

y

是序列，在訓練集中相當於一個個序列對，

x = (x_0, x_1, x_2, \dots x_T)

，

y = (y_0, y_1, y_2, \dots y_T)

，另外整個隱含狀態的個數是有限個數的，比如詞性的個數，一般是動詞，名詞，副詞等，命名實體中，實體的標籤可能為人名，地名，公司名等，而

x

也可能是從一個有限集合中抽取出來的，比如從3000個漢字中抽取出來的構成觀測序列；

特徵函式

f_j(x, y)

的個數

J

，與定義的匹配模版有關；

y

表示的一個具體的隱含狀態序列，用於區別分子中的

y

，也可以用其他符號來表示；

特徵函式

f_j(x, y)

的取值可以是實數值，一般的取值為

\{0, 1\}

，即我們常說指示函式，

x, y

滿足某種條件輸出為1，否則為0，在後面有例子；

w

是模型的要學習的引數集合，引數個數跟

f_j(x,y)

特徵函式的個數有關，這裡是

J

個，需要透過訓練資料進行引數的估計；

對公式的右半部分取

\log

得到如下形式：

\log(p(y|x;w)) = \sum_{j=1}^J w_j f_j(x, y) - \log(\sum_{y

可以發現上述公式，右半部分中的第一項是關於

f_j(x, y)

的線性組合（Linear），第二部分不依賴於標籤

y

， 當固定

x, w

後，就可以說

\log(p(y|x;w))

就是

\log

後的關於特徵函式的線性組合，同時對於上述公式，我們可以得到幾個感性結論：

由於我們是需要使得似然函式（log似然函式）的取值最大，那麼就需要將等式右邊的第一部分取值越大越好，第二部分取值越小越好；

對於第一部分由於

x,y

是訓練集中的出現的觀測序列和隱含標籤狀態序列對，

w_j f_j(x,y)

是取值越大比較符合直覺；

對於第二部分，

y

不是訓練集中的樣本

w_j f_j(x,y)

取值越小符合直覺，由於有exp，所以取值接近於0，比較符合直覺；

模型訓練

回到我們的目標，或者說具體的任務，比如輸入一個句話進行命名實體識別，

中文命名實體識別_02_從Log-Linear模型到CRF

x

觀測序列是文字，狀態序列

y

是定義好的實體類別的集合，而我們更關心的就是給定一個輸入

x

，模型能夠給我們一個與真實標籤更像的更一致的

y

，即

p(y|x)

， 而不是

p(x, y)

， 因此，我們的可以利用最大似然估計對Log-Linear模型引數估計。假設訓練集中有

n

個訓練樣本

\{ (x_i, y_i) \}_{i=1}^n

， 似然函式（不帶正則化的）可以寫為：

\begin{aligned} L(w) = \prod_{i=1}^n p(y_i|x_i;w)\\ L(w) = \sum_{i=1}^n \log(p(y_i|x_i;w)) \end{aligned} \\

利用最大似然估計出模型的引數

w^*

：

w^* = \arg \max_{w} \sum_{i=1}^n \log(p(y_i|x_i;w) \\

顯然，我們可以利用梯度上升最佳化演算法來求解引數

w^*

；結合似然函式和

\log

後

p(y|x;w)

展開形式，可以得到最終的似然函式為（注： 為了簡潔起見，將

x_i,y_i

的下標

i

去除了）：

\begin{aligned} L(w) &= \sum_{i=1}^n \Big(\sum_{j=1}^J w_j f_j(x, y) - \log(\sum_{y

先對等式右邊的第一部分求導：

\frac{d}{dw_j}(\sum_{j=1}^J w_j f_j(x, y)) = f_j(x, y) \\

對第二部分進行求導：

\begin{aligned} \frac{d}{dw_j}(\log(\sum_{y

對於上式的第一步到第二步，如果有點繞的話，可以想象如下的一個等式：

\begin{aligned} \frac{\sum_{i=1}^3 a_i \cdot b_i}{D} &= \frac{a_1b_1 + a_2b_2 + a_3b_3}{D} \\ &= a_1 \frac{b_1}{D} + a_2 \frac{b_2}{D} + a_3 \frac{b_3}{D}\\ &= \sum_{i=1}^3 (a_i \cdot \frac{b_i}{D}) \end{aligned} \\

同時，我們還發現，根據Log-Linear模型的定義，得到了

p(y

； 綜上，最終對於

w_j

求導之後的公式為（注：加上了樣本編碼的下標

i

）：

\frac{dL(w)}{d w_j} = \sum_{i=1}^n f_j(x_i, y_i) - \sum_{i=1}^n \sum_{y

有了上述求導公式，可以對模型中的

J

個引數

w_j

依次求導，利用梯度上升（

由於我們是需要最大化似然函式

）最佳化演算法，依次迭代模型的引數：

w_j \leftarrow w_j + \alpha \frac{dL(w)}{d w_j} \\

心細的同學應該發現了，我們的公式中出現了一個不太好計算的

p(y

，會對這項的求解產生疑問，後面會專門對這個做一下解釋，現在姑且把這一項認為是已知的，很好求解，對於整個Log-Linear模型的求解形成了完整的認識。在第三篇內容中，我們會專門針對動態規劃演算法，前向演算法和後向演算法進行介紹，這樣來推匯出

p(y

會更好理解。

特徵函式

我們對於模型的特徵應該都是很熟悉了，比如年齡，性別都可以是一個特徵列，而對於特徵函式可能就不那麼熟悉了，特徵函式

f_j(x,y)

的特點為：

輸出是實數，取值一般為0或者1，在自然語言處理中，經常可以看到類似onehot的編碼方式，所以輸出為0/1也是挺合情合理的；

設計

f_j(x,y)

可以是隻跟

x

，或者只跟

y

有關，比如

f_j(x \ starts \ A) = 1

，表示對於輸入的句子中，只要存在字母A開頭的單詞就輸出1，與其對應的標籤y序列無關；

由於

x,y

是序列對，

f_j(x, y)

特徵函數理論上有無窮個規則模版的，但是在實際模型中，會做一些簡化處理，方便計算，如CRF模型中，只考慮相鄰狀態標籤，以及位置關係

想象一下一個更具體的例子，我們的n-gram語言模型，如2-gram，需要對語料庫中相鄰的兩個字進行切分，如果我們把第一字和第二字的具體取值生成一個特徵函式的話，即只要出現了語料庫中這樣的2-gram的詞，就輸出1，那麼我們就可以得到非常多的特徵函式；

隱馬爾科夫模型HMM

說到HMM，模型為觀測序列

x

和隱含標籤狀態序列

y

的聯合機率分佈，並且做了如下限制：

當前時刻的隱含狀態

y_t

只跟上一時刻的隱含狀態有關

y_{t-1}

，與其他時刻無關；

當前時刻的觀測

x_t

只與當前時刻的隱含狀態

y_t

有關

因此，HMM模型可以表示為：

p(x,y) = p(y_1)p(x_1|y_1)\prod_{t=2}^T p(y_t|y_{t-1}) p(x_t| y_t) \\

在上式中，有兩部分機率連乘得到，即轉移機率

A = p(y_t|y_{t-1})

和發射機率

B = p(x_t| y_t)

，在實際的HMM中，除了上述兩個轉移機率和發射機率，還有一個狀態初始機率分佈

\pi

。

對

p(x,y)

取

\log

得到：

\begin{aligned} \log p(x,y) &= \log p(y_1)p(x_1|y_1) + \sum_{t=2}^T \log p(y_t|y_{t-1}) + \sum_{t=2}^T \log p(x_t| y_t) \\ &= w_0 + w_{01} + w_{12} + \cdots + w_{t-1 t} + w_{00} + w_{11} + \cdots + w_{tt} \end{aligned} \\

由於在給定了HMM之後，我們就可以確定轉移機率和發射機率各個取值了，即上述形式，在結合Log-Linear中的特徵函式

f_j(x, y)

以及模型引數

w_j

，我們可以做一下等價：

f_j(x,y)

可以包含訓練語料中的前後相鄰兩個標籤，以及在給定標籤之後的觀測值

特徵函式的權重為機率的

\log

取值

CRF模型

有了上述Log-Linear模型的鋪墊，我們發現只需要對特徵函式做一些限制，就可以得到我們要講的CRF模型（沒有特別說明指的是linear-chain CRF），先看CRF模型在特徵函式上做了什麼限制：

f_j(x,y)

需要把整個

x

輸入，即考慮全部的輸入；

新增了一個

x

序列中的詞的位置編碼資訊

i

，即需要告訴特徵函式當前作用的位置是輸入序列

x

中的第幾個輸入；

當前詞/字的對應的標籤

y_i

；

上一個詞/字的標籤

y_{i-1}

；

因此，CRF模型的特徵函式可以表示為：

f_j(x, y) = \sum_{i=1}^T f_j(x,y_{i-1}, y_i, i) \\

其中

T

表示序列的長度，一般把

f_j(x,y_{i-1}, y_i, i)

叫做

low-level

特徵函式，low-level特徵函式會掃過整個輸入序列，最終求和之後匯聚到

f_j(x,y)

上，這樣做的好處在於，我們模型中的特徵函式

f_j(x,y)

的個數可以是固定的，同時我們的訓練樣本/測試樣本的長度是可變的，這樣做到一種相容。

由此，根據Log-Linear模型的形式，可以得到CRF模型的形式為：

\begin{aligned} p(y|x;w) &= \frac{exp(\sum_{j=1}^J w_j f_j(x, y))}{Z(x,w)} \\ &= \frac{exp(\sum_{j=1}^J w_j \sum_{i=1}^T f_j(x,y_{i-1}, y_i, i) )}{Z(x,w)} \\ &= \frac{exp(\sum_{j=1}^J \sum_{i=1}^T w_j f_j(x,y_{i-1}, y_i, i) )}{Z(x,w)} \end{aligned} \\

上述公式是CRF的簡化形式，很多書籍會從PGM的一些概念開始，如

團與最大團

，

Hammersley-Clifford定理

，

勢函式

，最後根據馬爾科夫隨機場，條件隨機場定義等一步步推導到線性鏈條件CRF的引數化形式，總體上來說理解難度很更大點，這裡拋棄了這些概念，發現從Log-Linear更容易接受，下面部分內容可以和李航的統計機器學習的部分內容開始接上了，我們根據上述簡化的CRF公式，複雜化一下，將特徵函式拆分成兩部分（總的個數是一樣的）：

轉移特徵函式

：

t_k(x,y_{i-1},y_i, i)

， 表示特徵函式依賴於當前和上一時刻的標籤，有

K

個；

狀態特徵函式

：

s_l(x,y_i,i)

： 表示特徵函式只依賴於當前時刻的標籤，有

L

個；

最終，可以把上述公式等價為：

\begin{aligned} p(y|x;w) &= \frac{exp(\sum_{j=1}^J \sum_{i=1}^T w_j f_j(x,y_{i-1}, y_i, i) )}{Z(x,w)} \\ &= \frac{1}{Z(x,w)}exp\Big( \sum_{k=1}^K \sum_{i=1}^T \lambda_k t_k(x,y_{i-1}, y_i, i) + \sum_{l=1}^L \sum_{i=0}^T \mu_l s_l(x, y_i, i) \Big) \end{aligned} \\

下面直接改編一下統計機器學習上的一個例子來直觀地展示一下CRF模型：假定輸入觀測序列

x = (x_0,x_1, x_2)

， 輸出標記（狀態序列）

y=(y_0,y_1,y_2)

，其中狀態的取值為

\mathcal{Y} = \{red,black\}

，即

y_i

的取值只能是red或者black，同時分別給定了5個轉移特徵函式

t_k

和3個狀態函式

s_l

：

轉移特徵函式為：

\begin{aligned} t_1 &= t_1(x, y_{i-1}=red, y_i=black, i=\ 1 or \ 2),\lambda_1 = 1 \\ t_2 &= t_2(x, y_0=red, y_1=red, i=1), \lambda_2 = 0.5 \\ t_3 &= t_2(x, y_1=black, y_2=red, i=2), \lambda_3 = 1 \\ t_4 &= t_4(x, y_0=black, y_1=red, i=1), \lambda_4 = 1 \\ t_5 &= t_5(x, y_1=black, y_2=balck, i=2), \lambda_5 = 0.2 \\ \end{aligned} \\

狀態特徵函式為：

\begin{aligned} s_1 &= s_1(x,y_0=red,i=0), \mu_1 = 1 \\ s_2 &= s_2(x,y_i=black,i=0\ or \ 1), \mu_2 = 0.5 \\ s_3 &= s_3(x,y_i=red,i=1\ or \ 2), \mu_3 = 0.8 \\ s_4 &= s_4(x,y_2=black,i=2), \mu_4 = 0.5 \\ \end{aligned} \\

對於給定的觀測序列

x

，求狀態序列

y=(y_0,y_1,y_2)=(red,black,black)

的非規範化的條件機率。直接根據上述CRF的公式，即可得到：

\begin{aligned} p(y|x;w) &\propto exp\Big( \sum_{k=1}^K \sum_{i=1}^T \lambda_k t_k(x,y_{i-1}, y_i, i) + \sum_{l=1}^L \sum_{i=0}^T \mu_l s_l(x, y_i, i) \Big) \\ &= exp\Big( \sum_{k=1}^5 \sum_{i=1}^2 \lambda_k t_k(x,y_{i-1}, y_i, i) + \sum_{l=1}^4 \sum_{i=0}^2 \mu_l s_l(x, y_i, i) \Big) \\ \end{aligned} \\

依次對上述公式進行展開：

\begin{aligned} \sum_{k=1}^5 \sum_{i=1}^2 \lambda_k t_k(x,y_{i-1}, y_i, i) &= \begin{matrix} \lambda_1 \cdot \Big(t_1(x,y_0, y_1, 1) + t_1(x, y_1,y_2,2) \Big) + \\ \lambda_2 \cdot \Big(t_2(x,y_0, y_1, 1) + t_2(x, y_1,y_2,2) \Big) + \\ \lambda_3 \cdot \Big(t_3(x,y_0, y_1, 1) + t_3(x, y_1,y_2,2) \Big) + \\ \lambda_4 \cdot \Big(t_4(x,y_0, y_1, 1) + t_4(x, y_1,y_2,2) \Big) + \\ \lambda_5 \cdot \Big(t_5(x,y_0, y_1, 1) + t_5(x, y_1,y_2,2) \Big) \\ \end{matrix} \\ &= \begin{matrix} 1 \cdot \Big(t_1(x,y_0=red, y_1=black, 1) + t_1(x, y_1=black,y_2=black,2) \Big) + \\ 0.5 \cdot \Big(t_2(x,y_0=red, y_1=black, 1) + t_2(x, y_1=black,y_2=black,2) \Big) + \\ 1 \cdot \Big(t_3(x,y_0=red, y_1=black, 1) + t_3(x, y_1=black,y_2=black,2) \Big) + \\ 1 \cdot \Big(t_4(x,y_0=red, y_1=black, 1) + t_4(x, y_1=black,y_2=black,2) \Big) + \\ 0.2 \cdot \Big(t_5(x,y_0=red, y_1=black, 1) + t_5(x, y_1=black,y_2=black,2) \Big) \\ \end{matrix} \\ &= \begin{matrix} 1 \cdot (1 + 0 ) + \\ 0.5 \cdot (0 + 0 ) + \\ 1 \cdot (0 + 0 ) + \\ 1 \cdot (0 + 0 ) + \\ 0.2 \cdot (0+ 1) \\ \end{matrix} \\ &= 1.2 \end{aligned} \\

同理：

\begin{aligned} \sum_{l=1}^4 \sum_{i=0}^2 \mu_l s_l(x, y_i, i) &= \begin{matrix} 1.0 \cdot (1 + 0 + 0 ) + \\ 0.5 \cdot (0 + 1 + 0 ) + \\ 0.8 \cdot (0 + 0 + 0) + \\ 0.5 \cdot (0 + 0 + 1 ) \ \\ \end{matrix} = 2 \end{aligned} \\

最終：

p(y_0=red, y_1=black, y_2=black) \propto exp(3.2)

總結

我們從Log-Linear的模型開始講起，涉及到了其中重要的概念

特徵函式

，特徵函式也是CRF模型中的重要組成部分，關於Log-Linear重要的是其引數最佳化過程，我們也得到了，只不過在梯度上升的公式中出現了一個不太好計算的東西，比較耗時，我們沒有去碰它，等下一篇文章講解完動態規劃相關內容在來解決這個問題。最後，根據CRF模型的特點，引入其特徵函式的構造方式，由於CRF就是一種Log-Linear模型，其最佳化方式是一致的，後面又引入了一個CRF的例子，讓大家對特徵函式加深一下映象，計算了一下非規範化的條件機率。

參考資料

李航的統計機器學習，新手慎入，講的太簡潔

周志華西瓜書，一上來就是勢函式，天吶，我的PGM全部忘光了

真香 Michael Collins，

http：//www。

cs。columbia。edu/~mcolli

ns/loglinear。pdf

真香 ichael Collins，Log-Linear Models， MEMMs， and CRFs

真香 Log-linear models and conditional random fields

https：//

cseweb。ucsd。edu/~elkan/

250Bwinter2012/loglinearCRFs。pdf

中文命名實體識別_02_從Log-Linear模型到CRF

同名微信公眾號，內容檢索更方便，排版更友好，歡迎新增：一直學習一直爽