條件隨機場CRF

03-03

以下內容來自劉建平Pinard-博客園的學習筆記，總結如下：

1 條件隨機場CRF：從條件隨機場到線性鏈條件隨機場

條件隨機場(Conditional Random Fields, 以下簡稱CRF)是給定一組輸入序列條件下另一組輸出序列的條件概率分布模型，在自然語言處理中得到了廣泛應用。

1.1 什麼樣的問題需要CRF模型

這裡舉一個簡單的例子：假設有Bob一天從早到晚的一系列照片，Bob想考考我們，要我們猜這一系列的每張照片對應的活動，比如: 工作的照片，吃飯的照片，唱歌的照片等等。一個比較直觀的辦法就是，我們找到Bob之前的日常生活的一系列照片，然後找Bob問清楚這些照片代表的活動標記，這樣我們就可以用監督學習的方法來訓練一個分類模型，比如邏輯回歸，接著用模型去預測這一天的每張照片最可能的活動標記。

這種辦法雖然是可行的，但是卻忽略了一個重要的問題，就是這些照片之間的順序其實是有很大的時間順序關係的，而用上面的方法則會忽略這種關係。比如我們現在看到了一張Bob閉著嘴的照片，那麼這張照片我們怎麼標記Bob的活動呢？比較難去打標記。但是如果我們有Bob在這一張照片前一點點時間的照片的話，那麼這張照片就好標記了。如果在時間序列上前一張的照片里Bob在吃飯，那麼這張閉嘴的照片很有可能是在吃飯咀嚼。而如果在時間序列上前一張的照片里Bob在唱歌，那麼這張閉嘴的照片很有可能是在唱歌。

為了讓我們的分類器表現的更好，可以在標記數據的時候，可以考慮相鄰數據的標記信息。這一點，是普通的分類器難以做到的。而這一塊，也是CRF比較擅長的地方。

在實際應用中，自然語言處理中的詞性標註(POS Tagging)就是非常適合CRF使用的地方。詞性標註的目標是給出一個句子中每個詞的詞性（名詞，動詞，形容詞等）。而這些詞的詞性往往和上下文的詞的詞性有關，因此，使用CRF來處理是很適合的，當然CRF不是唯一的選擇，也有很多其他的詞性標註方法。

1.2 從隨機場到馬爾科夫隨機場

首先，我們來看看什麼是隨機場。「隨機場」的名字取的很玄乎，其實理解起來不難。隨機場是由若干個位置組成的整體，當給每一個位置中按照某種分布隨機賦予一個值之後，其全體就叫做隨機場。還是舉詞性標註的例子：假如有一個十個詞形成的句子需要做詞性標註。這十個詞每個詞的詞性可以在已知的詞性集合（名詞，動詞...)中去選擇。當我們為每個詞選擇完詞性後，這就形成了一個隨機場。

了解了隨機場，我們再來看看馬爾科夫隨機場。馬爾科夫隨機場是隨機場的特例，它假設隨機場中某一個位置的賦值僅僅與和它相鄰的位置的賦值有關，和與其不相鄰的位置的賦值無關。繼續舉十個詞的句子詞性標註的例子：　如果我們假設所有詞的詞性只和它相鄰的詞的詞性有關時，這個隨機場就特化成一個馬爾科夫隨機場。比如第三個詞的詞性除了與自己本身的位置有關外，只與第二個詞和第四個詞的詞性有關。　

1.3 從馬爾科夫隨機場到條件隨機場

CRF是馬爾科夫隨機場的特例，它假設馬爾科夫隨機場中只有X和Y兩種變數，X一般是給定的，而Y一般是在給定X的條件下的輸出。這樣馬爾科夫隨機場就特化成了條件隨機場。在我們十個詞的句子詞性標註的例子中，X是詞，Y是詞性。因此，如果我們假設它是一個馬爾科夫隨機場，那麼它也就是一個CRF。

對於CRF，給出準確的數學語言描述：設X與Y是隨機變數，P(Y|X)是給定X時Y的條件概率分布，若隨機變數Y構成的是一個馬爾科夫隨機場，則稱條件概率分布P(Y|X)是條件隨機場。

1.4 從條件隨機場到線性鏈條件隨機場

注意在CRF的定義中，我們並沒有要求X和Y有相同的結構。而實現中，我們一般都假設

X和Y有相同的結構，即:

一般考慮如下圖所示的結構：X和Y有相同的結構的CRF就構成了線性鏈條件隨機場(Linear chain Conditional Random Fields,以下簡稱 linear-CRF)。

在十個詞的句子的詞性標記中，詞有十個，詞性也是十個，因此，如果假設它是一個馬爾科夫隨機場，那麼它也就是一個linear-CRF。

我們再來看看 linear-CRF的數學定義：

設 $X=(X_{1},X_{2}，...,X_{n}),Y=(Y_{1},Y_{2},...,Y_{n})$ 均為線性鏈表示的隨機變數序列，在給定隨機變數序列 $X$ 的情況下，隨機變數 $Y$ 的條件概率分布 $P(Y|X)$ 構成條件隨機場，即滿足馬爾科性：

則稱 $P(Y|X)$ 為線性鏈條件隨機場。

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

對於上一節講到的linear-CRF，我們如何將其轉化為可以學習的機器學習模型呢？

這是通過特徵函數和其權重係數來定義的。什麼是特徵函數呢？

在linear-CRF中，特徵函數分為兩類，第一類是定義在Y節點上的節點特徵函數，這類特徵函數只和當前節點有關，記為：

其中， $L$ 是定義在該節點的節點特徵函數的總個數， $i$ 是當前節點在序列的位置。

第二類是定義在Y上下文的局部特徵函數，這類特徵函數只和當前節點和上一個節點有關，記為：

其中 $K$ 是定義在該節點的局部特徵函數的總個數， $i$ 是當前節點在序列的位置。之所以只有上下文相關的局部特徵函數，沒有不相鄰節點之間的特徵函數，是因為linear-CRF滿足馬爾科夫性。

無論是節點特徵函數還是局部特徵函數，它們的取值只能是0或者1。即滿足特徵條件或者不滿足特徵條件。同時，我們可以為每個特徵函數賦予一個權值，用以表達我們對這個特徵函數的信任度。假設 $t_{k}$ 的權重係數是 $lambda_{k}$ ， $s_{l}$ 的權重係數是 $u_{l}$ ，則linear-CRF由所有的 $t_{k},lambda_{k},s_{l},u_{l}$ 共同決定。

此時我們得到了linear-CRF的參數化形式如下：

其中， $Z(x)$ 為規範化因子：

回到特徵函數本身，每個特徵函數定義了一個linear-CRF的規則，則其係數定義了這個規則的可信度。所有的規則和其可信度一起構成了linear-CRF的最終的條件概率分布。

1.6 線性鏈條件隨機場實例

這裡我們給出一個linear-CRF用於詞性標註的實例，為了方便，我們簡化了詞性的種類。假設輸入的都是三個詞的句子，即 $X=(X_{1}，,X_{2}，,X_{3})$ ，輸出的詞性標記為 $Y=(Y_{1}，,Y_{2}，Y_{3})$ ，其中 $Yinleft{ 1(名詞),2(動詞) ight}$

這裡只標記出取值為1的特徵函數如下：

求標記(1,2,2)的非規範化概率。

利用linear-CRF的參數化公式，我們有：

帶入(1,2,2)有：

1.7 線性鏈條件隨機場的簡化形式

在上幾節裡面，我們用 $s_{l}$ 表示節點特徵函數，用 $t_{k}$ 表示局部特徵函數，同時也用了不同的符號表示權重係數，導致表示起來比較麻煩。其實我們可以對特徵函數稍加整理，將其統一起來。

假設在某一節點我們有 $K_{1}$ 個局部特徵函數和 $K_{2}$ 個節點特徵函數，總共有 $K=K_{1}+K_{2}$ 個特徵函數。用一個特徵函數 $f_{k}(y_{i-1},y_{i},x,i)$ 來統一表示如下：

對 $f_{k}(y_{i-1},y_{i},x,i)$ 在各個序列位置求和得到：

$f_{k}(y_{i-1},y_{i},x,i)$ 對應的權重係數 $w_{k}$ 如下：

這樣，linear-CRF的參數化形式簡化為：

其中， $Z(x)$ 為規範化因子：

則linear-CRF的參數化形式簡化為內積形式如下：

1.8 線性鏈條件隨機場的矩陣形式

將linear-CRF的參數化形式寫成矩陣形式。為此定義一個 $m imes m$ 的矩陣 $M$ ， $m$ 為 $y$ 所有可能的狀態的取值個數。 $M$ 定義如下：

引入起點和終點標記 $y_{0}=start,y_{n+1}=stop$ ，這樣，標記序列 $y$ 的非規範化概率可以通過 $n+1$ 個矩陣元素的乘積得到，即：

其中， $Z_{w}(x)$ 為規範化因子。

2 前向後向演算法評估標記序列概率

linear-CRF需要解決的三個問題：評估，學習和解碼。

這三個問題和HMM是非常類似的，本節關注於第一個問題：評估。

2.1 linear-CRF的三個基本問題

linear-CRF第一個問題是評估，即給定 linear-CRF的條件概率分布 $P(y|x)$ ，在給定輸入序列 $x$ 和輸出序列 $y$ 時，計算條件概率 $P(y_{i}|x)$ 和 $P(y_{i-1},y_{i}|x)$ 以及對應的期望。

linear-CRF第二個問題是學習，即給定訓練數據集 $X$ 和 $Y$ ，學習linear-CRF的模型參數 $w_{k}$ 和條件概率 $P_{w}(y|x)$ 。

linear-CRF第三個問題是解碼，即給定 linear-CRF的條件概率分布 $P(y|x)$ ，和輸入序列 $x$ ，計算使條件概率最大的輸出序列 $y$ 。

2.2 linear-CRF的前向後向概率概述

要計算條件概率 $P(y_{i}|x)$ 和 $P(y_{i-1},y_{i}|x)$ ，也可以使用和HMM類似的方法，使用前向後向演算法來完成。首先我們來看前向概率的計算。

定義 $alpha_{i}(y_{i}|x)$ 表示序列位置 $i$ 的標記是 $y_{i}$ 時，在位置 $i$ 之前的部分標記序列的非規範化概率。之所以是非規範化概率是因為我們不想加入一個不影響結果計算的規範化因子 $Z(x)$ 在分母裡面。

定義了下式：

這個式子定義了在給定 $y_{i-1}$ 時，從 $y_{i-1}$ 轉移到 $y_{i}$ 的非規範化概率。

這樣，可以得到序列位置 $i+1$ 的標記是 $y_{i+1}$ 時，在位置 $i+1$ 之前的部分標記序列的非規範化概率 $alpha_{i+1}(y_{i+1}|x)$ 的遞推公式：

在起點處，我們定義：

假設我們可能的標記總數是 $m$ ，則 $y_{i}$ 的取值就有 $m$ 個，用 $alpha_{i}(x)$ 表示這 $m$ 個值組成的前向向量如下：

這樣遞推公式可以用矩陣乘積表示：

同樣的，定義 $eta_{i}(y_{i}|x)$ 表示序列位置 $i$ 的標記是 $y_{i}$ 時，在位置 $i$ 之後的從 $i+1$ 到 $n$ 的部分標記序列的非規範化概率。

這樣，可以得到序列位置 $i+1$ 的標記是 $y_{i+1}$ 時，在位置 $i$ 之後的部分標記序列的非規範化概率 $eta_{i}(y_{i}|x)$ 的遞推公式：

在終點處，我們定義：

如果用向量表示，則有：

由於規範化因子 $Z(x)$ 的表達式是：

也可以用向量來表示 $Z(x)$ ：

其中， $1$ 是 $m$ 維全1向量。

2.3 linear-CRF的前向後向概率計算

有了前向後向概率的定義和計算方法，我們就很容易計算序列位置 $i$ 的標記是 $y_{i}$ 的條件概率 $P(y_{i}|x)$ ：

2.4 linear-CRF的期望計算

有了上一節計算的條件概率，我們也可以很方便的計算聯合分布 $P(x,y)$ 和條件分布 $P(y|x)$ 的期望。

2.5 linear-CRF前向後向演算法總結

以上就是linear-CRF的前向後向演算法。

注意到我們上面的非規範化概率 $M_{i+1}(y_{i+1},y_{i}|x)$ 起的作用和HMM中的隱藏狀態轉移概率很像。但是這兒的概率是非規範化的，也就是不強制要求所有的狀態的概率和為1。而HMM中的隱藏狀態轉移概率也規範化的。從這一點看，linear-CRF對序列狀態轉移的處理要比HMM靈活。

3 模型學習與維特比演算法解碼

linear-CRF的第二個問題與第三個問題的求解。第二個問題是模型參數學習的問題，第三個問題是維特比演算法解碼的問題。

3.1 linear-CRF模型參數學習思路

求解這個問題有很多思路，比如梯度下降法，牛頓法，擬牛頓法。也可以使用最大熵模型中使用的改進的迭代尺度法(improved iterative scaling, IIS)來求解。

3.2 linear-CRF模型參數學習之梯度下降法求解

在使用梯度下降法求解模型參數之前，我們需要定義我們的優化函數，一般極大化條件分布 $P_{w}(y|x)$ 的對數似然函數如下：

有了 $w$ 的導數表達式，就可以用梯度下降法來迭代求解最優的 $w$ 了。注意在迭代過程中，每次更新 $w$ 後，需要同步更新 $P_{w}(x,y)$ 以用於下一次迭代的梯度計算。

以上就是linear-CRF模型參數學習之梯度下降法求解思路總結。

3.3 linear-CRF模型維特比演算法解碼思路

現在我們來看linear-CRF的第三個問題：解碼。

在這個問題中，給定條件隨機場的條件概率 $P(y|x)$ 和一個觀測序列 $x$ ，要求出滿足 $P(y|x)$ 最大的序列 $y$ 。

這個解碼演算法最常用的還是和HMM解碼類似的維特比演算法。

維特比演算法本身是一個動態規劃演算法，利用了兩個局部狀態和對應的遞推公式，從局部遞推到整體，進而得解。對於具體不同的問題，僅僅是這兩個局部狀態的定義和對應的遞推公式不同而已。

3.4 linear-CRF模型維特比演算法流程

現在我們總結下 linear-CRF模型維特比演算法流程：

輸入：模型的 $K$ 個特徵函數，和對應的 $k$ 個權重。觀測序列 $x=(x_{1},x_{2},...,x_{n})$ ，可能的標記個數 $m$

輸出：最優標記序列 $y^{*}=(y_{1}^{*},y_{2}^{*},...,y_{n}^{*})$

3.5 linear-CRF模型維特比演算法實例

下面用一個具體的例子來描述 linear-CRF模型維特比演算法，例子的模型來源於《統計學習方法》。

3.6 linear-CRF vs HMM

linear-CRF模型和HMM模型有很多相似之處，尤其是其三個典型問題非常類似，除了模型參數學習的問題求解方法不同以外，概率估計問題和解碼問題使用的演算法思想基本也是相同的。同時，兩者都可以用於序列模型，因此都廣泛用於自然語言處理的各個方面。

現在來看看兩者的不同點。

最大的不同點是linear-CRF模型是判別模型，而HMM是生成模型，即linear-CRF模型要優化求解的是條件概率P(y|x),則HMM要求解的是聯合分布P(x,y)。第二，linear-CRF是利用最大熵模型的思路去建立條件概率模型，對於觀測序列並沒有做馬爾科夫假設。而HMM是在對觀測序列做了馬爾科夫假設的前提下建立聯合分布的模型。

只有linear-CRF模型和HMM模型才是可以比較討論的。但是linear-CRF是CRF的一個特例，CRF本身是一個可以適用於很複雜條件概率的模型，因此理論上CRF的使用範圍要比HMM廣泛的多。