機率圖模型學習筆記：HMM,MEMM,CRF

一、寫在前面Preface

今天看到了之前收藏吃灰的一篇寫的很好的機率圖的學習筆記，自己也想總結一下，今天還有很多事情都沒有完成，看到了之後就覺得可以花一些時間好好研究一下，總結一些這段時間的研究，因為之前在B站了完整看了sh大佬的視訊講解，對于HMM 還有MEMM，CRF也有一些自己的了解，今天正好趁着這個機會，一鼓做氣都寫一下，不往這段時間的投入，之後也不知道會不會用起，但希望想起來的時候我可以說，我曾經愛過～

因為接觸了NLP相關的東西，不得不學習這些傳統的序列模型，面試的時候也有人問我這些模型，但隻可惜當時一知半解，就随便講了一些自己是研究深度學習方面的，LSTM，RNN 之類的過關了，但知不足而後進，正是這個道理，機率圖模型在我的了解中，就是使用圖的性質，将機率進行結合，HMM，MEMM ，CRF 則是一種模型的假設，一步步遞進更好的解決序列标注的問題。

這次借助大佬的文章，将我自己的了解寫一下，僅供各位參考學習，如有不足，錯誤希望大家及時指明。機率圖模型的徹悟是關于了解生成式模型和判别式模型的關系。

我一直保持記錄部落格的習慣，是将自己的了解輸出，記錄良好的文章，可以使我保持思路清晰，也可以反複看自己了解的程度，在之後新的了解也可以加進來。

學習是一個将沒有結構的知識點融會貫通，使用一條繩子将知識點結構化，成為體系之後才可以牢牢的掌握，拿起繩子的一頭，所有東西都能拿的起來學習是一個熵減的過程，卓有成效的學習是可以使得混亂度越來越小的！記住這個思維習慣。

統計學習的思維定勢

統計機器學習所有的模型（個别instant model和優化算法以及其他的特種工程知識點除外）的工作流程都是如此：

a.訓練模型參數，得到模型（由參數唯一确定），

b.預測給定的測試資料。

拿這個流程去挨個學習模型，思路上會非常順暢。這一點可參見我另一篇文字介紹。

對初學者的關于機器學習的入門學習方式也順帶表達一下(empirical speaking)：

a.完整特征工程競賽

b.野部落格理論入門了解

c.再回到代碼深入了解模型内部

d.再跨理論，查閱經典理論巨作。這時感性理性都有一定高度，會遇到很多很大的了解上的疑惑，這時3大經典可能就可以發揮到最大作用了。

很多beginer，就比如說學CRF模型，然後一上來就擺一套複雜的公式，什麼我就問，這能了解的了嗎？這是正确的開啟姿勢嗎？當然了，也要怪那些部落客，直接整一大堆核心公式，實際上讀者的了解門檻可能就是一個過渡性的細枝末節而已。沒有上下文的教育肯定是失敗的（這一點我又想吐槽國内絕大部分大學的院校教育模式）。是以說帶有完整上下文資訊以及過程來龍去脈交代清楚才算到位吧。

而不是一上來就死啃被人推薦的“經典資料”，這一點相信部分同學會了解。好比以前大學零基礎學c++ JAVA，上來就看primr TIJ，結果浪費了時間精力一直在門外兜圈。總結方法吸取教訓，應該快速上手代碼，才是最高效的。經典最好是用來查閱的工具書，我目前是李航周志華和經典的那3本疊代輪詢看了好多輪，經常會反複查詢某些model或理論的來龍去脈；有時候要查很多相關的東西，看這些書還是難以貫通，然後發現有些人的部落格寫的會更容易去了解。是以另外，學習資料管道也要充分才行。

二、預備知識Prerequisite

2.1 機率圖

機率圖是CRF HMM 的基礎，我們需要對機率圖有個整體的認知，這樣學習的知識才不會是空中閣樓，如果看不懂，可以看過一遍之後在回過頭看，就能看明白了，都是這麼過來的。

2.1.1 概覽

在統計機率圖（probability graph models）中，參考宗成慶老師的書，是這樣的體系結構（個人非常喜歡這種類型的圖）：

在機率圖模型中，資料(樣本)由公式 G = ( V , E ) G=(V,E) G=(V,E)模組化表示：

• V V V表示節點，即随機變量（放在此處的，可以是一個token或者一個label），具體地，用 Y = ( y 1 , ⋯ , y n ) Y=(y_1,⋯,y_n) Y=(y1​,⋯,yn​)為随機變量模組化，注意 Y Y Y現在是代表了一批随機變量（想象對應一條sequence，包含了很多的token）， P ( Y ) P(Y) P(Y)為這些随機變量的分布；
• E E E表示邊，即機率依賴關系。具體咋了解，還是要在後面結合HMM或CRF的graph具體解釋。

2.1.2 有向圖 vs. 無向圖

上圖可以看到，貝葉斯網絡（信念網絡）都是有向的，馬爾科夫網絡無向。是以，貝葉斯網絡适合為有單向依賴的資料模組化，馬爾科夫網絡适合實體之間互相依賴的模組化。具體地，他們的核心差異表現在如何求 P = ( Y ) P=(Y) P=(Y)，即怎麼表示 Y = （ y 1 , ⋯ , y n ） Y=（y_1,⋯,y_n） Y=（y1​,⋯,yn​）這個的聯合機率。

1. 有向圖

對于有向圖模型，這麼求聯合機率：

P ( x 1 , ⋯ , x n ) = ∑ i = 0 P ( x i ∣ π ( x i ) ) P(x_1,⋯,x_n)=\sum_{i=0}{P(x_i|π(x_i))} P(x1​,⋯,xn​)=∑i=0​P(xi​∣π(xi​))

舉個例子，對于下面的這個有向圖的随機變量(注意，這個圖我畫的還是比較廣義的)：

應該這樣表示他們的聯合機率:

P ( x 1 , ⋯ , x n ) = P ( x 1 ) ⋅ P ( x 2 ∣ x 1 ) ⋅ P ( x 3 ∣ x 2 ) ⋅ P ( x 4 ∣ x 2 ) ⋅ P ( x 5 ∣ x 3 , x 4 ) P(x_1,⋯,x_n)=P(x_1)·P(x_2|x_1)·P(x_3|x_2)·P(x_4|x_2)·P(x_5|x_3,x_4) P(x1​,⋯,xn​)=P(x1​)⋅P(x2​∣x1​)⋅P(x3​∣x2​)⋅P(x4​∣x2​)⋅P(x5​∣x3​,x4​)

應該很好了解吧。

2. 無向圖

對于無向圖，我看資料一般就指馬爾科夫網絡(注意，這個圖我畫的也是比較廣義的)。

如果一個graph太大，可以用因子分解将 P = ( Y ) P=(Y) P=(Y)寫為若幹個聯合機率的乘積。咋分解呢，将一個圖分為若幹個“小團”，注意每個團必須是“最大團”（就是裡面任何兩個點連在了一塊，具體……算了不解釋，就是最大連通子圖），則有：

P ( Y ) = 1 Z ( x ) ∏ c ψ c ( Y c ) P(Y)=\frac{1}{Z(x)}\prod_{c}{ψ_c(Y_c)} P(Y)=Z(x)1​c∏​ψc​(Yc​)

, 其中 Z ( x ) = ∑ Y ∏ c ψ c ( Y c ) Z(x)=\sum_{Y}\prod_c{ψ_c(Y_c)} Z(x)=∑Y​∏c​ψc​(Yc​)，公式應該不難了解吧，歸一化是為了讓結果算作機率。

是以像上面的無向圖：

P ( Y ) = 1 Z ( x ) ( ψ 1 ( X 1 , X 3 , X 4 ) ⋅ ψ 2 ( X 2 , X 3 , X 4 ) ) P(Y)=\frac{1}{Z(x)}(ψ_1(X_1,X_3,X_4)·ψ_2(X_2,X_3,X_4)) P(Y)=Z(x)1​(ψ1​(X1​,X3​,X4​)⋅ψ2​(X2​,X3​,X4​))

其中，$ψ_c(Y_c)ψ_c(Y_c) $是一個最大團C上随機變量們的聯合機率，一般取指數函數的：

ψ c ( Y c ) = e − E ( Y c ) = e ∑ k λ k f k ( c , y ∣ c , x ) ψ_c(Y_c)=e^{−E(Y_c)}=e^{∑_kλ_kf_k(c,y|c,x)} ψc​(Yc​)=e−E(Yc​)=e∑k​λk​fk​(c,y∣c,x)

好了，管這個東西叫做

勢函數

。注意 e ∑ k λ k f k ( c , y ∣ c , x ) e^{∑_kλ_kf_k(c,y|c,x)} e∑k​λk​fk​(c,y∣c,x) 是否有看到CRF的影子。

那麼機率無向圖的聯合機率分布可以在因子分解下表示為：

P ( Y ) = 1 Z ( x ) ∏ c ψ c ( Y c ) = 1 Z ( x ) ∏ c e ∑ k λ k f k ( c , y ∣ c , x ) = 1 Z ( x ) e ∑ c ∑ k λ k f k ( y i , y i − 1 , x , i ) P(Y )=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c} ) = \frac{1}{Z(x)} \prod_{c} e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} = \frac{1}{Z(x)} e^{\sum_{c}\sum_{k}\lambda_{k}f_{k}(y_{i},y_{i-1},x,i)} P(Y)=Z(x)1​c∏​ψc​(Yc​)=Z(x)1​c∏​e∑k​λk​fk​(c,y∣c,x)=Z(x)1​e∑c​∑k​λk​fk​(yi​,yi−1​,x,i)

注意，這裡的了解還蠻重要的，注意遞推過程，敲黑闆，這是CRF的開端！

這個由

Hammersly-Clifford law

保證，具體不展開。

2.1.3 馬爾科夫假設&馬爾科夫性

這個也屬于前饋知識。

1. 馬爾科夫假設

額應該是齊次馬爾科夫假設，這樣假設：馬爾科夫鍊 （ x 1 , ⋯ , x n ) （x_1,⋯,x_n) （x1​,⋯,xn​)裡的 x i x_i xi​總是隻受 x i − 1 x_{i−1} xi−1​一個人的影響。

馬爾科夫假設這裡相當于就是個1-gram。

馬爾科夫過程呢？即，在一個過程中，每個狀态的轉移隻依賴于前n個狀态，并且隻是個n階的模型。最簡單的馬爾科夫過程是一階的，即隻依賴于 前一個狀态。

2. 馬爾科夫性

馬爾科夫性是是保證或者判斷機率圖是否為機率無向圖的條件。

三點内容：a. 成對，b. 局部，c. 全局。

我覺得這個不用展開。

2.2 判别式（generative）模型 vs. 生成式(discriminative)模型

在監督學習下，模型可以分為判别式模型與生成式模型。

重點來了。上面有提到，我了解了HMM、CRF模型的差別是從了解了判别式模型與生成式模型的那刻，并且瞬間對其他的模型有一個恍然大悟。我記得是一年前就開始糾結這兩者的差別，但我隻能說，栽在了一些爛部落格上，大部分都沒有自己的insightful了解，也就是一頓官話，也真是難以了解。後來在知乎上一直琢磨别人的答案，然後某日早晨終于豁然開朗，就是這種感覺。

好了，我要用自己的了解來轉述兩者的差別了below。

先問個問題，根據經驗，A批模型（神經網絡模型、SVM、perceptron、LR、DT……）與B批模型（NB、LDA……），有啥差別不？（這個問題需要一些模型使用經驗）應該是這樣的：

1. A批模型是這麼工作的，他們直接将資料的Y（或者label），根據所提供的features，學習，最後畫出了一個明顯或者比較明顯的邊界（具體怎麼做到的？通過複雜的函數映射，或者決策疊加等等mechanism），這一點線性LR、線性SVM應該很明顯吧。

2. B批模型是這麼工作的，他們先從訓練樣本資料中，将所有的資料的分布情況摸透，然後最終确定一個分布，來作為我的所有的輸入資料的分布，并且他是一個聯合分布 P ( X , Y ) P(X,Y) P(X,Y)注意X包含所有的特征 x i x_i xi​，Y包含所有的label)。然後我來了新的樣本資料（inference），好，我通過我學習來的模型的聯合分布 P ( X , Y ) P(X,Y) P(X,Y)，再結合新樣本給的X，通過條件機率就能出來Y：

   P ( Y ∣ X ) = P ( X , Y ) P ( X ) P(Y|X)=\frac{P(X,Y)}{P(X)} P(Y∣X)=P(X)P(X,Y)​

   好了，應該說清楚了。

1. 判别式模型

那麼A批模型對應了判别式模型。根據上面的兩句話的差別，可以知道判别模型的特征了，是以有句話說：判别模型是直接對P(Y|X)P(Y|X)模組化，就是說，直接根據X特征來對Y模組化訓練。

具體地，我的訓練過程是确定構件P(Y|X)P(Y|X)模型裡面“複雜映射關系”中的參數，完了再去inference一批新的sample。

是以判别式模型的特征總結如下：

對P(Y|X)P(Y|X)模組化

對所有的樣本隻建構一個模型，确認總體判别邊界

觀測到輸入什麼特征，就預測最可能的label

另外，判别式的優點是：對資料量要求沒生成式的嚴格，速度也會快，小資料量下準确率也會好些。

2. 生成式模型

同樣，B批模型對應了生成式模型。并且需要注意的是，在模型訓練中，我學習到的是X與Y的聯合模型P(X,Y)P(X,Y)，也就是說，我在訓練階段是隻對P(X,Y)P(X,Y)模組化，我需要确定維護這個聯合機率分布的所有的資訊參數。完了之後在inference再對新的sample計算P(Y|X)P(Y|X)，導出Y ,但這已經不屬于模組化階段了。

結合NB過一遍生成式模型的工作流程。學習階段，模組化：P(X,Y)=P(X|Y)P(Y)P(X,Y)=P(X|Y)P(Y)（當然，NB具體流程去隔壁參考）,然後P(Y|X)=P(X,Y)P(X)P(Y|X)=P(X,Y)P(X)。

另外，LDA也是這樣，隻是他更過分，需要确定很多個機率分布，而且模組化抽樣都蠻複雜的。

是以生成式總結下有如下特點：

對P(X,Y)P(X,Y)模組化

這裡我們主要講分類問題，是以是要對每個label（yiyi）都需要模組化，最終選擇最優機率的label為結果，是以沒有什麼判别邊界。（對于序列标注問題，那隻需要構件一個model）

中間生成聯合分布，并可生成采樣資料。

生成式模型的優點在于，所包含的資訊非常齊全，我稱之為“上帝資訊”，是以不僅可以用來輸入label，還可以幹其他的事情。生成式模型關注結果是如何産生的。但是生成式模型需要非常充足的資料量以保證采樣到了資料本來的面目，是以速度相比之下，慢。

這一點明白後，後面講到的HMM與CRF的差別也會非常清晰。

最後identity the picture below:

2.3 序列模組化

為了号召零門檻了解，現在解釋如何為序列問題模組化。

序列包括時間序列以及general sequence，但兩者無異。連續的序列在分析時也會先離散化處理。常見的序列有如：時序資料、本文句子、語音資料、等等。

廣義下的序列有這些特點：

節點之間有關聯依賴性/無關聯依賴性

序列的節點是随機的/确定的

序列是線性變化/非線性的

……

對不同的序列有不同的問題需求，常見的序列模組化方法總結有如下：

拟合，預測未來節點（或走勢分析）：

正常序列模組化方法：AR、MA、ARMA、ARIMA

回歸拟合

Neural Networks

判斷不同序列類别，即分類問題：HMM、CRF、General Classifier（ML models、NN models）

不同時序對應的狀态的分析，即序列标注問題：HMM、CRF、RecurrentNNs

在本篇文字中，我們隻關注在2. & 3.類問題下的模組化過程和方法。

三、HMM

3.1 了解HMM

3.2 模型運作過程

3.2.1 學習過程

3.2.2 序列标注（解碼）過程

3.2.3 序列機率過程

四、MEMM

4.1 了解MEMM

4.2 模型運作過程

4.2.1 學習過程

4.2.2 序列标注過程

4.2.3 序列機率過程

4.3 标注偏置？

五、CRF

我覺得一旦有了一個清晰的工作流程，那麼按部就班地，沒有什麼很難了解的地方，因為整體架構已經胸有成竹了，剩下了也隻有添磚加瓦小修小補了。有了上面的過程基礎，CRF也是類似的，隻是有方法論上的細微差別。

5.1 了解CRF

請看第一張機率圖模型構架圖，CRF上面是馬爾科夫随機場（馬爾科夫網絡），而條件随機場是在給定的随機變量X（具體，對應觀測序列 o 1 , ⋯   , o i o_{1}, \cdots, o_{i} o1​,⋯,oi​）條件下，随機變量Y（具體，對應隐狀态序列 i 1 , ⋯   , i i i_{1}, \cdots, i_{i} i1​,⋯,ii​）的馬爾科夫随機場。

廣義的CRF的定義是： 滿足 P ( Y v ∣ X , Y w , w ≠ v ) = P ( Y v ∣ X , Y w , w ∼ v ) P(Y_{v}|X,Y_{w},w \neq v) = P(Y_{v}|X,Y_{w},w \sim v) P(Yv​∣X,Yw​,w​=v)=P(Yv​∣X,Yw​,w∼v)的馬爾科夫随機場叫做條件随機場（CRF）。

不過一般說CRF為序列模組化，就專指CRF線性鍊（linear chain CRF）：

在2.1.2中有提到過，機率無向圖的聯合機率分布可以在因子分解下表示為：

P ( Y ∣ X ) = 1 Z ( x ) ∏ c ψ c ( Y c ∣ X ) = 1 Z ( x ) ∏ c e ∑ k λ k f k ( c , y ∣ c , x ) = 1 Z ( x ) e ∑ c ∑ k λ k f k ( y i , y i − 1 , x , i ) P(Y | X)=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c}|X ) = \frac{1}{Z(x)} \prod_{c} e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} = \frac{1}{Z(x)} e^{\sum_{c}\sum_{k}\lambda_{k}f_{k}(y_{i},y_{i-1},x,i)} P(Y∣X)=Z(x)1​c∏​ψc​(Yc​∣X)=Z(x)1​c∏​e∑k​λk​fk​(c,y∣c,x)=Z(x)1​e∑c​∑k​λk​fk​(yi​,yi−1​,x,i)

而線上性鍊CRF示意圖中，每一個( I 1   O i I_1~O_i I1​ Oi​）對為一個最大團,即在上式中c = i。并且線性鍊CRF滿足 P ( I i ∣ O , I 1 , ⋯   , I n ) = P ( I i ∣ O , I i − 1 , I i + 1 ) P(I_{i}|O,I_{1},\cdots, I_{n}) = P(I_{i}|O,I_{i-1},I_{i+1}) P(Ii​∣O,I1​,⋯,In​)=P(Ii​∣O,Ii−1​,Ii+1​)。

是以CRF的模組化公式如下：

Z ( O ) ∏ i ψ i ( I i ∣ O ) = 1 Z ( O ) ∏ i e ∑ k λ k f k ( O , I i − 1 , I i , i ) = 1 Z ( O ) e ∑ i ∑ k λ k f k ( O , I i − 1 , I i , i ) {Z(O)} \prod_{i}\psi_{i}(I_{i}|O ) = \frac{1}{Z(O)} \prod_{i} e^{\sum_{k}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)} = \frac{1}{Z(O)} e^{\sum_{i}\sum_{k}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)} Z(O)i∏​ψi​(Ii​∣O)=Z(O)1​i∏​e∑k​λk​fk​(O,Ii−1​,Ii​,i)=Z(O)1​e∑i​∑k​λk​fk​(O,Ii−1​,Ii​,i)

我要敲黑闆了，這個公式是非常非常關鍵的，注意遞推過程啊，我是怎麼從∏∏跳到e∑e∑的。

不過還是要多啰嗦一句，想要了解CRF，必須判别式模型的概念要深入你心。正因為是判别模型，是以不廢話，我上來就直接為了确定邊界而去模組化，因為我創造出來就是為了這個分邊界的目的的。比如說序列求機率（分類）問題，我直接考慮找出函數分類邊界。是以才為什麼會有這個公式。是以再看到這個公式也别懵逼了，he was born for discriminating the given data from different classes. 就這樣。不過待會還會具體介紹特征函數部分的東西。

除了模組化總公式，關鍵的CRF重點概念在MEMM中已強調過：判别式模型、特征函數。

1. 特征函數

   上面給出了CRF的模組化公式：

P ( I ∣ O ) = 1 Z ( O ) e ∑ i T ∑ k M λ k f k ( O , I i − 1 , I i , i ) P(I | O)=\frac{1}{Z(O)} e^{\sum_{i}^{T}\sum_{k}^{M}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)} P(I∣O)=Z(O)1​e∑iT​∑kM​λk​fk​(O,Ii−1​,Ii​,i)

下标i表示我目前所在的節點（token）位置。

下标k表示我這是第幾個特征函數，并且每個特征函數都附屬一個權重 λ k λ_k λk​，也就是這麼回事，每個團裡面，我将為 t o k e n i token_i tokeni​構造M個特征，每個特征執行一定的限定作用，然後模組化時我再為每個特征函數權重求和。

Z ( O ) Z(O) Z(O)是用來歸一化的，為什麼？想想LR以及softmax為何有歸一化呢，一樣的嘛，形成機率值。

再來個重要的了解。 P ( I ∣ O ) P(I|O) P(I∣O)這個表示什麼？具體地，表示了在給定的一條觀測序列 O = ( o 1 , ⋯ , o i ) O=(o_1,⋯,o_i) O=(o1​,⋯,oi​)條件下，我用CRF所求出來的隐狀态序列 I = ( i 1 , ⋯ , i i ) I=(i1,⋯,ii) I=(i1,⋯,ii)的機率，注意，這裡的I是一條序列，有多個元素（一組随機變量），而至于觀測序列 O = ( o 1 , ⋯ , o i ) O=(o_1,⋯,o_i) O=(o1​,⋯,oi​)，它可以是一整個訓練語料的所有的觀測序列；也可以是在inference階段的一句sample，比如說對于序列标注問題，我對一條sample進行預測，可能能得到Pj(I|O)（j=1,…,J）Pj(I|O)（j=1,…,J）J條隐狀态I，但我肯定最終選的是最優機率的那條（by viterbi）。這一點希望你能了解。

對于CRF，可以為他定義兩款特征函數：轉移特征&狀态特征。

我們将模組化總公式展開：

P(I|O)=1Z(O)e∑Ti∑Mkλkfk(O,Ii−1,Ii,i)=1Z(O)e[∑Ti∑Jjλjtj(O,Ii−1,Ii,i)+∑Ti∑Llμlsl(O,Ii,i)]

P(I|O)=1Z(O)e∑iT∑kMλkfk(O,Ii−1,Ii,i)=1Z(O)e[∑iT∑jJλjtj(O,Ii−1,Ii,i)+∑iT∑lLμlsl(O,Ii,i)]

其中：

tj 為 i 處 的 轉 移 特 征 ， 對 應 權 重 t j 為i處的轉移特征，對應權重tj 為i處的轉移特征，對應權重tj為i處的轉移特征，對應權重\lambda_{j},每個,每個token_{i}KaTeX parse error: Expected '}', got 'EOF' at end of input: …n是‘I’，0other sl為i處的狀态特征，對應權重sl 為 i 處 的 狀 态 特 征 ， 對 應 權 重 μ l , 每 個 , 每 個 t o k e n i 為i處的狀态特征，對應權重\mu_{l},每個,每個token_{i} 為i處的狀态特征，對應權重μl​,每個,每個tokeni​都有L個特征

舉個例子：

sl=1(o,i)={10滿足特定狀态條件，比如目前token的POS是‘V’，other

sl=1(o,i)={1滿足特定狀态條件，比如目前token的POS是‘V’，0other

不過一般情況下，我們不把兩種特征差別的那麼開，合在一起：

P(I|O)=1Z(O)e∑Ti∑Mkλkfk(O,Ii−1,Ii,i)

P(I|O)=1Z(O)e∑iT∑kMλkfk(O,Ii−1,Ii,i)

滿足特征條件就取值為1，否則沒貢獻，甚至你還可以讓他打負分，充分懲罰。

再進一步了解的話，我們需要把特征函數部分摳出來：

Score=∑iT∑kMλkfk(O,Ii−1,Ii,i)

Score=∑iT∑kMλkfk(O,Ii−1,Ii,i)

是的，我們為tokenitokeni打分，滿足條件的就有所貢獻。最後将所得的分數進行log線性表示，求和後歸一化，即可得到機率值……完了又扯到了log線性模型。現在稍作解釋：

log-linear models take the following form:

P(y|x;ω)=exp(ω·ϕ(x,y))∑y′∈Yexp(ω·ϕ(x,y′))

P(y|x;ω)=exp(ω·ϕ(x,y))∑y′∈Yexp(ω·ϕ(x,y′))

我覺得對LR或者sotfmax熟悉的對這個應該秒懂。然後CRF完美地滿足這個形式，是以歸入到了log-linear models之中。

5.2 模型運作過程

模型的工作流程，跟MEMM是一樣的：

step1. 先預定義特征函數fa(o,i)fa(o,i)，

step2. 在給定的資料上，訓練模型，确定參數λkλk

step3. 用确定的模型做序列标注問題或者序列求機率問題。

可能還是沒做到100%懂，結合例子說明：

……

5.2.1 學習訓練過程

一套CRF由一套參數λλ唯一确定（先定義好各種特征函數）。

同樣，CRF用極大似然估計方法、梯度下降、牛頓疊代、拟牛頓下降、IIS、BFGS、L-BFGS等等。各位應該對各種優化方法有所了解的。其實能用在log-linear models上的求參方法都可以用過來。

嗯，具體詳細求解過程貌似問題不大。

5.2.2 序列标注過程

還是跟HMM一樣的，用學習好的CRF模型，在新的sample（觀測序列o1,⋯,oio1,⋯,oi）上找出一條機率最大最可能的隐狀态序列i1,⋯,iii1,⋯,ii。

隻是現在的圖中的每個隐狀态節點的機率求法有一些差異而已,正确将每個節點的機率表示清楚，路徑求解過程還是一樣，采用viterbi算法。

啰嗦一下，我們就定義i處的局部狀态為δi(I)δi(I),表示在位置i處的隐狀态的各種取值可能為I，然後遞推位置i+1處的隐狀态，寫出來的DP轉移公式為：

δi+1=max1≤j≤m{δi(I)+∑iT∑kMλkfk(O,Ii−1,Ii,i)}

δi+1=max1≤j≤m{δi(I)+∑iT∑kMλkfk(O,Ii−1,Ii,i)}

這裡沒寫規範因子Z(O)Z(O)是因為不規範化不會影響取最大值後的比較。

具體還是不展開為好。

5.2.3 序列求機率過程

跟HMM舉的例子一樣的，也是分别去為每一批資料訓練建構特定的CRF，然後根據序列在每個MEMM模型的不同得分機率，選擇最高分數的模型為wanted類别。隻是貌似很少看到拿CRF或者MEMM來做分類的，直接用網絡模型不就完了不……

應該可以不用展開，吧……

5.3 CRF++分析

本來做task用CRF++跑過baseline,後來在對CRF做調研時，非常想透析CRF++的工作原理，以identify以及verify做的各種假設猜想。當然，也看過其他的CRF實作源碼。

是以幹脆寫到這裡來，結合CRF++執行個體講解過程。

有一批語料資料，并且已經tokenized好了：

Nuclear

theory

devoted

major

efforts

……

并且我先确定了13個标注元素：

B_MAT

B_PRO

B_TAS

E_MAT

E_PRO

E_TAS

I_MAT

I_PRO

I_TAS

O

S_MAT

S_PRO

S_TAS

1. 定義模闆

按道理應該是定義特征函數才對吧？好的，在CRF++下，應該是先定義特征模闆，然後用模闆自動批量産生大量的特征函數。我之前也蠻confused的，用完CRF++還以為模闆就是特征，後面就搞清楚了：每一條模闆将在每一個token處生産若幹個特征函數。

CRF++的模闆（template）有U系列（unigram）、B系列(bigram)，不過我至今搞不清楚B系列的作用，因為U模闆都可以完成2-gram的作用。

U00:%x[-2,0]

U01:%x[-1,0]

U02:%x[0,0]

U03:%x[1,0]

U04:%x[2,0]

U05:%x[-2,0]/%x[-1,0]/%x[0,0]

U06:%x[-1,0]/%x[0,0]/%x[1,0]

U07:%x[0,0]/%x[1,0]/%x[2,0]

U08:%x[-1,0]/%x[0,0]

U09:%x[0,0]/%x[1,0]

B

是以，U00 - U09 我定義了10個模闆。

2. 産生特征函數

是的，會産生大量的特征。

U00 - U04的模闆産生的是狀态特征函數；U05 - U09的模闆産生的是轉移特征函數。

在CRF++中，每個特征都會try每個标注label（這裡有13個），總共将生成 N ∗ L = i ∗ k ′ ∗ L N∗L=i∗k^′∗L N∗L=i∗k′∗L個特征函數以及對應的權重出來。N表示每一套特征函數 N = i ∗ k ′ N=i∗k^′ N=i∗k′，L表示标注集元素個數。

比如訓練好的CRF模型的部分特征函數是這樣存儲的：

22607 B

790309 U00:%

3453892 U00:%)

2717325 U00:&

2128269 U00:’t

2826239 U00:(0.3534

2525055 U00:(0.593–1.118

197093 U00:(1)

2079519 U00:(1)L=14w2−12w−FμνaFaμν

2458547 U00:(1)δn=∫−∞En+1ρ˜(E)dE−n

1766024 U00:(1.0g

2679261 U00:(1.1wt%)

1622517 U00:(100)

727701U00:(1000–5000A)

2626520 U00:(10a)

2626689 U00:(10b)

……

2842814U07:layer/thicknesses/Using

2847533 U07:layer/thicknesses/are

2848651 U07:layer/thicknesses/in

331539 U07:layer/to/the

1885871U07:layer/was/deposited ……（數量非常龐大）

其實也就是對應了這樣的一個特征函數：

func1 = if (output = B and feature=”U02:一”) return 1 else return 0

func2 = if (output = M and feature=”U02:一”) return 1 else return 0

func3 = if (output = E and feature=”U02:一”) return 1 else return 0

func4 = if (output = S and feature=”U02:一”) return 1 else return 0

比如模闆U06會從語料中one by one逐句抽出這些各個特征：

一/個/人/……

個/人/走/……

3. 求參

對上述的各個特征以及初始權重進行疊代參數學習。

在CRF++ 訓練好的模型裡，權重是這樣的：

0.3972716048310705

0.5078838237171732

0.6715316559507898

-0.4198827647512405

-0.4233310655891150

-0.4176580083832543

-0.4860489836004728

-0.6156475863742051

-0.6997919485753300

0.8309956709647820

0.3749695682658566

0.2627347894057647

0.0169732441379157

0.3972716048310705

0.5078838237171732

0.6715316559507898 ……（數量非常龐大，與每個label的特征函數對應，我這有300W個）

4. 預測解碼

這個就看不到viterbi怎麼走的了。

結果是這樣的：

Nuclear B_TAS

theory E_TAS

devoted O

major O

efforts O ……

5.4 LSTM+CRF

LSTM+CRF這個組合其實我在知乎上答過問題，然後順便可以整合到這裡來。

1、perspectively

大家都知道，LSTM已經可以勝任序列标注問題了，為每個token預測一個label（LSTM後面接:分類器）；而CRF也是一樣的，為每個token預測一個label。

但是，他們的預測機理是不同的。CRF是全局範圍内統計歸一化的條件狀态轉移機率矩陣，再預測出一條指定的sample的每個token的label；LSTM（RNNs，不區分here）是依靠神經網絡的超強非線性拟合能力，在訓練時将samples通過複雜到讓你窒息的高階高緯度異度空間的非線性變換，學習出一個模型，然後再預測出一條指定的sample的每個token的label。

2、LSTM+CRF

既然LSTM都OK了，為啥researchers搞一個LSTM+CRF的hybrid model?

哈哈，因為a single LSTM預測出來的标注有問題啊！舉個segmentation例子(BES; char level)，plain LSTM 會搞出這樣的結果：

input: “學習出一個模型，然後再預測出一條指定”

expected output: 學/B 習/E 出/S 一/B 個/E 模/B 型/E ，/S 然/B 後/E 再/E 預/B 測/E……

real output: 學/B 習/E 出/S 一/B 個/B 模/B 型/E ，/S 然/B 後/B 再/E 預/B 測/E ……

看到不，用LSTM，整體的預測accuracy是不錯indeed, 但是會出現上述的錯誤：在B之後再來一個B。這個錯誤在CRF中是不存在的，因為CRF的特征函數的存在就是為了對given序列觀察學習各種特征（n-gram，視窗），這些特征就是在限定視窗size下的各種詞之間的關系。然後一般都會學到這樣的一條規律（特征）：B後面接E，不會出現E。這個限定特征會使得CRF的預測結果不出現上述例子的錯誤。當然了，CRF還能學到更多的限定特征，那越多越好啊！

好了，那就把CRF接到LSTM上面，把LSTM在time_step上把每一個hidden_state的tensor輸入給CRF，讓LSTM負責在CRF的特征限定下，依照新的loss function，學習出一套新的非線性變換空間。

最後，不用說，結果還真是好多了呢。

LSTM+CRF codes, here. Go just take it.

六、總結

1. 總體對比

應該看到了熟悉的圖了，現在看這個圖的話，應該可以很清楚地get到他所表達的含義了。這張圖的内容正是按照生成式&判别式來區分的，NB在sequence模組化下拓展到了HMM；LR在sequence模組化下拓展到了CRF。

2. HMM vs. MEMM vs. CRF

将三者放在一塊做一個總結：

1. HMM -> MEMM：

   HMM模型中存在兩個假設：一是輸出觀察值之間嚴格獨立，二是狀态的轉移過程中目前狀态隻與前一狀态有關。但實際上序列标注問題不僅和單個詞相關，而且和觀察序列的長度，單詞的上下文，等等相關。MEMM解決了HMM輸出獨立性假設的問題。因為HMM隻限定在了觀測與狀态之間的依賴，而MEMM引入自定義特征函數，不僅可以表達觀測之間的依賴，還可表示目前觀測與前後多個狀态之間的複雜依賴。

2. MEMM -> CRF:
   1. CRF不僅解決了HMM輸出獨立性假設的問題，還解決了MEMM的标注偏置問題，MEMM容易陷入局部最優是因為隻在局部做歸一化，而CRF統計了全局機率，在做歸一化時考慮了資料在全局的分布，而不是僅僅在局部歸一化，這樣就解決了MEMM中的标記偏置的問題。使得序列标注的解碼變得最優解。
   2. HMM、MEMM屬于有向圖，是以考慮了x與y的影響，但沒講x當做整體考慮進去（這點問題應該隻有HMM）。CRF屬于無向圖，沒有這種依賴性，克服此問題。

有了這道開胃菜，接下來，讀者可以完成這些事情：完善細節算法、閱讀原著相關論文達到徹底了解、了解相關拓展概念、理論創新……

六、總結 Referrence

《統計學習方法》，李航

《統計自然語言處理》，宗成慶

《 An Introduction to Conditional Random Fields for Relational Learning》， Charles Sutton， Andrew McCallum

《Log-Linear Models, MEMMs, and CRFs》，ichael Collins

https://www.zhihu.com/question/35866596

https://www.cnblogs.com/en-heng/p/6201893.html

https://www.cnblogs.com/en-heng/p/6201893.html

https://github.com/timvieira/crf

https://github.com/shawntan/python-crf

http://videolectures.net/cikm08_elkan_llmacrf/

https://www.jianshu.com/p/55755fc649b1

https://www.cnblogs.com/pinard/p/7068574.html

https://www.zhihu.com/question/20279019

http://www.hankcs.com/ml/crf-code-analysis.html

http://blog.csdn.net/aws3217150/article/details/69212445

http://www.hankcs.com/nlp/the-crf-model-format-description.html

https://www.cnblogs.com/syx-1987/p/4077325.html

原文連結：https://blog.csdn.net/Scotfield_msn/article/details/79195517