條件隨機場介紹（譯）Introduction to Conditional Random Fields

01-31

譯者序

該文是對CRF演算法的介紹，介紹清晰、淺顯，不對初學者設置過多的理解障礙。而且文章最後提到的學習資料，我看過部份，值得推薦。

原文鏈接：Introduction to Conditional Random Fields

正文序

想像一下，你有 Justin Bieber 一天生活中的一連串快照，你想在這些照片上面打上活動內容的標籤（吃睡、睡覺、開車等）。你會怎麼做？

一種方式是忽略這些快照的本質，建立一個圖片分類器。舉個例子，事先給定一個月的打標快照，你可能會了學到在早上6點拍的較暗的照片很可能是在睡覺，有很多明亮顏色的照片，很可以是關於跳舞，照片中有車那應該是在開車等等。

然而，忽略順序關聯，你會丟失很多信息。例如，如果你看到一張嘴張的特寫照片，那它應該打標成吃飯還是唱歌呢？如果上一張 Justin Bieber 的照片中他在吃飯或者做菜，那當前這張照片很可能是他在吃飯；但如果上一張照片中 Justin Bieber 在唱歌或者跳舞，那這張很可能是在說他也在唱歌。

因此，為了提高我們打標的準確率，我們應該結合參考相近照片，這正是條件隨機場（condition random field）所做的事情

詞性標註（Part-of-Speech Tagging）

讓我們通過更常用的詞性標註的例子來了解更多細節。

詞性標註（POS Tagging）的目標是使用類似ADJECTIVE, NOUN, PREPOSITION, VERB, ADVERB, ARTICLE的標籤對句子（一連串的詞或短語）進行打簽。

例如，句子「Bob drank coffee at Starbucks」的標註的結果就應該是「Bob (NOUN) drank (VERB) coffee (NOUN) at (PREPOSITION) Starbucks (NOUN)」。

那麼就讓我們建立一個條件隨機場來為句子做詞性標註。正如分類器所做，我們首先要設定一組特徵方程 fifi。

CRF的特徵函數（Feature Functions in a CRF）

在CRF中，每個特徵函數以下列信息作為輸入：

一個句子 s
詞在句子中的位置 i
當前詞的標籤 $l_{i}$
前一個詞的標籤 $l_{i-1}$

輸出的是一個實數值（儘管這些值一般是0或1）。

（注意：通過限制我們的特徵只依賴於當前與之前的詞的標籤，而不是句子中的任意標籤，實際上我建立了一種特殊的線性CRF，為簡單起見，本文不討論更廣義的CRF）

例如，某個特徵函數就可以用來衡量當上一個詞是「very」時，當前詞有多少程度可以被標為一個形容詞。

從特徵到概率(Features to Probabilities)

接下來，為我們的每個特徵函數 $f_{i}$ 設置一個權重值 $lambda_{j}$ （後面我會介紹如何通過訓練學習得到這些權重值）。給定一個句子 s，現在我們可以通過累加句中所有詞加權後的特徵來為s的打標結果l打分：

$score(l|s))=sum_{j=1}^{m}sum_{i=1}^{n} lambda_{j}f_{j}(s,i,l_{i}^{},l_{i-1}^{})$

（第一個求合是對遍歷特徵方程 $j$ 的求和，而內層的求合是對句子裡面的每一個位置 $i$ 進行遍歷進行求和）

最終，我們通求指數與歸一的方式將轉換這些得分轉換為0、1之間的概率值:

$p(l|s)=frac{exp[score(l|s)]}{sum_{l}exp[score(l|s)]}=frac{exp[sum_{j=1}^{m}sum_{i=1}^{n} lambda_{j}f_{j}(s,i,l_{i},l_{i-1})]}{sum_{{l}}exp[sum_{j=1}^{m}sum_{i=1}^{n}lambda_{j}f_{j}(s,i,l_{i}^{},l_{i-1}^{})]n}$

特徵方程示例（Example Feature Functions）

那麼，這些特徵方程都長什麼樣呢？詞性標註（POS tagging）的特徵例子如下：

if = ADVERB 且第i個詞以「-ly」結尾；否則，為0。
- 如果該特徵的權重值 $lambda_{1}$ 為取值較大的正數，則該特徵表明我們傾向於將以 -ly 結果的單詞標記為ADVERB。
if , = VERB 且句子以問號結尾；否則，為0。
- 同樣，如果該特徵的權重值 $lambda_{2}$ 為取值較大的正數，就偏向於將問句里的第一個詞標為VERB（例如「Is this a sentence beginning with a verb?」）。
if = ADJECTIVE 且 = NOUN；否則，為0。
- 同樣，如果權重值為正，表明形容詞後面傾向於跟著名詞。
if = PREPOSITION 且=PRE POSITION。
- 如果該特徵方程的權重值 $lambda _{4}$ 為負，意味著介詞後面一般不會緊跟著一個介詞，所以我們應該避免這樣的標註。

就是這樣！總結起來就是：為了構建一個條件隨機場，你需要定義一連串的特徵方程（以整個句子、當前位置和相近位置的標籤為輸入），然後為它們賦值，再做累加，如果必要，在最後將累加得分轉換為一個概率值。

看起來像是邏輯回歸(Smells like Logistic Regression...)

CRF的概率公式 $p(l|s)=frac{exp[score(l|s)]}{sum_{l}exp[score(l|s)]} = frac{exp[sum_{j=1}^{m}sum_{i=1}^{n} lambda_{j}f_{j}(s,i,l_{i},l_{i-1})]}{sum_{l}exp[sum_{j=1}^{m}sum_{i=1}^{n} lambda_{j}f_{j}(s,i,l_{i}^{},l_{i-1}^{})]}$ 看起來會有些眼熟.

這是因為實際上CRF就是序列版本的邏輯回歸（logistic regression）。正如邏輯回歸是分類問題的對數線性模型，CRF是序列標註問題的對數線性模型。

看著像HMM（Looks like HMMs…）

回顧隱馬可夫模型（Hidden Markov Model）它是另一種用於詞性標註（和序列標註）的模型。CRF使用任意的特徵函數組用於得到標註得分，HMM採用生成方式進行標註，定義如下：

$p(l,s)=p(l_{1})prod_{i}p(l_{i}|l_{i-1})p(w_{i}|l_{i})$

其中

$p(l_{i}|l_{i-1})$ 為轉移概率（例如，一個介詞後面緊跟著一個名詞的概率）。
$p(w_{i}|l_{i})$ 為發射概率（例如，當已知是名詞，會出現「dad」的概率）。

那麼，HMM與CRF比較會是如何? CRF更加強大- CRF可以為任何HMM能夠建模的事物建模，甚至更多。以下的介紹就可以說明這一點。

設HMM概率的對數為 $log p(l,s)=log p(l_{0})+sum_{i}log p(l_{i}|l_{i-1})+sum_{i}log p(w_{i}|l_{i})$ 。如果我們將這些對數概率值看作二進位的轉換指示符與發射指示符的權重，這就完全具備了CRF的對數線性形式。

也就是說，我們可以對任意的HMM建立等價的CRF：

為每個HMM的轉換概率 $p(l_{i}=y|l_{i-1}=x)$ ，定義一組轉換形式為 $f_{x,y}(s,i,l_{i},l_{i-1})=1$ if $l_{i}=y$ 且 $l_{i-1}=x$ 的CRF轉換特徵。給定每個特徵權重值為 $w_{x,y}=log p(l_{i}=y|l_{i-1}=x)$ 。
類似的，為每個HMM的發射概率 $p(w_{i}=z|l_{i}=x)$ ，定義一組CRF發射特徵形如 $g_{x,y}(s,i,l_{i},l_{i-1})$ if $w_{i}=z$ 且 $l_{i}=x$ 。給定每個特徵的權重值為 $w_{x,z}=log p(w_{i}=z|l_{i}=x)$ 。

這樣，使用這些特徵方程由CRF計算得到的 $p(l|s)$ 是與相應的HMM計算得到的得分是精確成正比的，所以每個HMM都存在某個對等的CRF。

但是，出於以下兩個原因，CRF同樣可以為更為豐富的標籤分布建模：

CRF可以定義更加廣泛的特徵集。而HMM在本質上必然是局部的（因為它只能使用二進位的轉換與發射特徵概率，導致每個詞僅能依賴當前的標籤，而每個標籤僅依賴於上一個標籤），而CRF就可以使用更加全局的特徵。例如，在上文提到的詞性標註特徵中就有一個特徵，如果句子的結尾包含問號，那麼句子中的第一個字為動詞（VERB）的概率會增加。
CRF可以有任意權重值。HMM的概率值必須滿足特定的約束（例如， $0<=p(w_{i}|l_{i})<=1$ ， $sum_{w}p(w_{i}=w|l_{i})=1$ ）,而CRF沒有限制（例如， $log p(w_{i}|l_{i})$ 可以是任意它想要的值）。

權重學習（Learing Weights）

讓我們回到如何學習CRF的權重這個問題。有一種方式是使用梯度上升（gradient ascent）。

假設我們有一組訓練樣本（包括句子與相關的詞性標註標籤結果）。一開始，為我們的CRF模型隨機初始化權重值。為了使這些隨機初始的權重值最終調整為正確的值，遍歷每個訓練樣本，執行如下操作：

遍歷每個特徵函數 $f_{i}$ ，並為 $lambda_{i}$ 計算訓練樣本的對數概率梯度值:

$frac{partial }{partial w_{j}} log p(l|s)=sum_{j=1}^{m}f_{i}(s,j,l_{j},l_{j-1})-sum_{l}p(l|s)sum_{j=1}^{m}f_{i}(s,j,l_{j}^{},l_{j-1}^{})$

注意，梯度公式中的第一項是特徵 $f_{i}$ 在正確標註下的貢獻，梯度公式中的第二項是特徵 $f_{i}$ 在當前模型中的貢獻。這就是你所期望的梯度上升所要採用的公式。
將 $lambda_{i}$ 朝著梯度方向移動：

$lambda_{i} = lambda_{i}+alpha [sum_{j=1}^{m}f_{i}(s,j,l_{j},l_{j-1})-sum_{l}p(l|s)sum_{j=1}^{m}f_{i}(s,j,l_{j}^{},l_{j-1}^{})]$

其中α是某個學習率（learning rate）。

重複上述步驟，直到達到某種停止條件（例如，更新值已低於某個閾值）。

換而言之，每一步都是在抽取，當前模型與我們想要學習到的模型的差異，然後將 $lambda_{i}$ 朝正確的方向移動。

找到最佳標註（Finding the Optimal Labeling）

假設我們已經訓練好了CRF模型，這時來了一個新的句子，我們應當如何去標註它？

最直接的方式，就是為每個可能的標註 $l$ 計算 $p(l|s)$ ，接著選取一種概率值最大的打標。然而，對一個大小為k標籤組和一個長度為m的句子，有 $k^{m}$ 種可能的打標方式，這就方式得檢查的打准方式是指數級的個數。

一種更好的辦法是使（線性鏈式）CRF滿足最佳子結構（optimal substructure）的屬性，使得我們可以使用一種（多項式時間複雜度）動態規劃演算法去找到最佳標註，類似於HMM的Viterbi演算法。

更有趣的應用(A More Interesting Application)

好吧，詞性標註略顯無聊，除了它還有很多種其他的標註方法。那現實中什麼時候還會用到CRF呢？

假設你想要從Twitter上了解人們想要在聖誕節上得到什麼樣的禮物：

如何才能找出哪些詞代表禮物呢？

為了收集到上圖中的數據，我只是簡單的去匹配形如「I want XXX for Christmas」和「I got XXX for Christmas」的句式。然而，一個更加複雜的CRF變種就可以做GIFT詞標註（甚至可以添加其也的類似GIFT-GIVER、GIFT-RECEIVER的標籤以獲取更豐富的信息），將其轉換為詞性標註問題來看待。我們可以基於類似「如果上一個詞是一個GITF-RECIVER且它的前一個詞是『gave』，那這個詞就是一個GITF」或者「如果後面緊跟著的兩個詞是for Christmas，那麼這個詞就是一個GIFT」的規則去構建特徵。

最後（Fin）

我將以下列隨想做為結束：

我刻意跳過了條件隨機場的圖模型框架，因為我不覺這些會對CRF的初次理解有什麼幫助。但如果你想了解更多，Daphne Koller有從一月開始的免費的線上圖模型教程。
或者，你對CRF在NLP上的許多應用(類似詞性標註、命名實體抽取)更感興趣，Manning和Jurafsky正在提供這樣的NLP課程。
我還對CRF:HMM與Logistic Regression:Naive Bayes之間做了一些對比。下圖（來自於 Sutton 和 McCallum的 introduction to conditional random fields）就是對此的總結，同時也展示了CRF的圖模型特性：

20161127首發於http://3dobe.com

本站鏈接：條件隨機場介紹（譯）Introduction to Conditional Random Fields