序列標註任務的常見套路

04-26

Part I：背景

Part II：HMM（隱馬爾科夫模型）

Part III：CRF（條件隨機場）

Part IV：Bi-LSTM CRF

Part I：背景

序列標註是一個比較廣泛的任務，包括分詞，詞性標註，命名實體識別，關係抽取等等，甚至你也可以用來做抽取式QA，直接在文章中標註出答案。

這裡跟大家提一下分詞，很基礎也是很重要的一個任務，我說重要指的是我們應該掌握分詞有哪些演算法，而不是說這是一個很好的研究方向，目前分詞可提升的空間很小了，所以不建議大家研究這個，但是可以做一些小實驗看看。

另外給大家介紹一些比較好用的中文分詞工具：

結巴分詞（比較簡單方便，我用這個來分詞）

LTP（哈工大NLP，我用這個做過詞性標註和命名實體識別，有時候可能需要在詞向量的基礎上加一些人工特徵，引入額外特徵信息）

Hanlp（Github文檔寫得挺不錯的，Java介面，現在也有人寫了Python介面）

StandfordCoreNlp（這也是中文的，我一般用Standford工具來處理英文）

序列標註任務的一般形式：

對於待標註的一段序列 X={x1，x2，...，xn}，我們需要給每個xi預測一個tag，

先定義Tag集合是 T = {t1，t2，...，tm}，比如，分詞的Tag可以定義為{Begin，Middle，End，Single}，命名實體識別的Tag可以定義為{形容詞，名詞，動詞，.....}，

假設預測序列是 Y={y1，y2，...，yn}，那我們要計算P(Y|X)從而得到序列Y，

再定義對應的真實Label序列是 L = {l1，l1，...，ln}，那我們就對Y和L使用交叉熵計算Loss，通過梯度下降來求解參數。

這麼說來，他比較像序列分類，但是和普通分類不一樣的是，這些預測的tag之間可能是有關聯的，我們可能需要通過上一個tag的信息去預測下一個tag，比如分詞，如果上一個預測的tag是Begin，那麼下一個tag就不應該是Single。

序列標註常見的演算法有HMM（隱馬爾科夫模型），MEMM（最大熵隱馬爾科夫模型），CRF（條件隨機場），以及LSTM-CRF模型，

其中HMM和CRF都是概率圖模型，而LSTM本身也很適合序列建模問題，LSTM-CRF是目前比較主流的做法，本文主要介紹HMM，CRF和LSTM-CRF，怎麼用於序列標註任務。

Part II：HMM（隱馬爾科夫模型）

一. 基本概念

HMM是一種生成式有向圖模型，對聯合分布進行建模求解p(x, y)，大家可以去看一看西瓜書，寫得通俗又易懂，有所掌握的同學可以跳過這一段。

參考自周志華的機器學習西瓜書

如圖，HMM包括兩組變數x和y：

x={x1，x2，...，xn}屬於觀測變數，也就是我們觀測到的信息，定義觀測值集合為O $in$ {o1，...，oM}，其中M為可能的觀測值。

y={y1，y2，...，yn}屬於狀態變數，或者叫隱變數，因為y是不可觀測的，系統通常會在狀態值集合S $in$ {s1，s2，...，sN}中進行狀態轉換，其中N為可能的狀態數。

首先我們來定義以下兩個隱馬爾科夫假設：

1）觀測獨立性假設：在任意時刻t下，觀察值 $x_t$ 僅與當前的狀態值 $y_t$ 有關

（也正是這個假設限制了HMM的特徵選擇，無法考慮到上下文特徵）

2）齊次馬爾科夫假設：在任意時刻t下，狀態 $y_t$ 只和前一個狀態 $y_{t-1}$ 有關，與其他狀態及觀察值無關，和 $y_{t-2}$ 無關，和 $x_{t}$ 也無關

因此，HMM所求解的聯合概率分布可以定義為：

$P(x_1, y_1, ..., x_n, y_n) = P(y_1)P(x_1|y_1)prod_{i=2}^{n} P(y_i|y_{i-1})P(x_i|y_i)$

接下來還會涉及到以下三組概率參數：

狀態轉移矩陣：A = $[a_{ij}]_{N*N}$ ，表示在 t 時刻下，狀態 $s_i$ 轉移到狀態 $s_j$ 的概率：

$a_{ij}=P(y_{t+1}=s_{j}|y_{t}=s_{i}), 1leq i, jleq N$

觀測概率矩陣：B = $[b_{ij}]_{N*M}$ ，表示在狀態 $s_i$ 下生成觀測 $o_j$ 的概率：

$b_{ij}=P(x_{t}=o_{j}|y_{t}=s_{i}), 1leq ileq N, 1leq jleq M$

初始狀態概率分布： $pi = (pi_{1}, pi_2, ..., pi_N)$ ，表示初始時刻下各狀態出現的概率：

$pi_i = P(y_1 = s_i), 1leq i leq N$

HMM可以解決以下三類推斷問題：

1）似然問題：給定模型 $lambda = [A, B, pi]$ ，求解 $P(x|lambda)$

2）解碼問題：給定模型 $lambda = [A, B, pi]$ 和觀測序列x，求解狀態序列 y

3）學習問題：給定觀測序列x，求解模型參數 $lambda = [A, B, pi]$

二. HMM解決序列標註問題

回到我們的序列標註問題，也就是解碼問題，這裡以分詞為例，狀態集合可以定義為{B，M，E，S}，觀測序列就是我們的句子，狀態序列y是我們的分詞結果，我們用Viterbi演算法來求解最大概率對應的狀態序列y，也就是最有可能出現的狀態序列。

Viterbi演算法

大家不要把viterbi演算法和HMM綁定到一起，這個演算法本來是用動態規劃來求最短路的，不是專門給HMM設計的，只是恰好可以求解HMM的解碼問題。

演算法基於這樣的前提：最優路徑的子路徑也一定是最優的。

演算法思路大概是：從根節點出發，每走一步，比較根節點到上層節點的最短路徑+上層節點到當前節點的最短距離，遞歸計算到達該點的最短路徑，一直走到終點。

維基百科這張動圖我覺得可以說明一切，然而我上傳不了GIF格式

引用自維基百科-維特比演算法

那麼viterbi演算法用於HMM，就是求解給定觀測值x後概率最大的狀態序列y，如果使用窮舉法會帶來巨大的計算量，所以viterbi對狀態進行轉移，而狀態數往往是比較少的。

回到分詞任務，tag集合是{B，M，E，S}，假設現在觀測序列是「我喜歡吃海底撈」：

第一步「我」對應的狀態y1有4種取值，取最大概率應該是tag S

第二步「喜」對應的狀態y2也有4種，根據y1計算出最大概率應該是tag B

第三步「歡」對應的狀態y3也有4種，根據y2計算出最大概率是tag E

......

可以看到，這裡只需要計算4*4*7次，而窮舉法卻需要計算4^7次！

另外，結巴分詞對viterbi演算法做了一些改進：

1）PrevStatus轉移條件，比如，狀態B的前一狀態只能是E或者S。

2）終止條件，最後一個狀態只能是E或者S，表示詞的結尾。

3）取log把概率連乘轉化為連加，所以概率矩陣中可能有負數。

Part III：CRF（條件隨機場）

前面介紹的HMM其實分詞結果比較一般，在很長一段時間，CRF都是序列標註任務的標配（當然現在主流做法也是LSTM套上CRF）。

一. 基本概念

CRF是一種判別式無向圖模型，對條件分布進行建模，構建條件概率模型p(y|x)。

令G=<V，E>表示節點與標記向量y中元素一一對應的無向圖，V是節點的集合，E是無向邊， $y_v$ 表示與節點v所對應的標記變數，n(v)表示節點v的鄰接節點，如果圖G的每個變數 $y_v$ 都滿足以下的馬爾科夫性質：

$P(y_v|x, y_{V/{v}}) = P(y_v |x, y_{n(v)})$

那麼（y, x）就構成了一個條件隨機場。

來........繼續翻開我們的西瓜書第326頁鏈式CRF：

引用自周志華機器學習-鏈式CRF

CRF引入了特徵函數（exp形式）來定義序列y的條件概率：

$P(y|x)=frac{1}{Z}exp(sum_{j}^{}{sum_{i=1}^{n-1}lambda_i t_j(y_{i+1}, y_i, x, i)}+sum_{k}^{}{sum_{i=1}^{n}mu_k s_k( y_i, x, i)})$

其中 $t_j$ 和 $s_k$ 都是特徵函數， $t_j$ 用來描述兩個相鄰位置的y 之間的關係以及x對y的影響， $s_k$ 描述x 在位置i 對y 的影響。特徵函數是事先定義好的， $lambda_j$ 和 $mu_k$ 才是我們的參數，也就是說，CRF需要訓練的，只是這些特徵的權重。

另外，這裡還做了全局歸一化，Z是規範化因子，CRF對Y中所有可能的狀態序列做了全局的歸一化，避免了label bias的問題。（MMEN是本地歸一化）

二. CRF解決序列標註問題

我們需要事先定義特徵函數，因此CRF開源工具提供了特徵模板，Unigram /Bigram Template，自動生成特徵函數。

假設L是標註的類別數量，N是從模板中擴展出來的字元串種類數量，

Unigram Template是一元模板，反映了訓練樣例的情況（比如詞性和對應的標註情況），一個模型生成的特徵函數的個數總數為L*N，

Bigram Template是二元模板，自動產生當前output token和前一個output token的組合，最終產生L * L * N種特徵。（如果類別數很大，會產生非常多的特徵）

現在特徵函數有了，那我們就可以求解概率了，然後進行解碼，Viterbi演算法大家還記得嗎？我們依然要用viterbi演算法尋找最佳標註路徑。viterbi演算法並不是只能用於HMM，我們只要定義好概率的計算方式，就可以用上viterbi演算法來求最佳路徑了。

現在我們來分析一下，CRF在序列標註任務上的地位：

1）解決HMM的觀測獨立性限制特徵選擇的問題（此時MEMM表示自己也可以），CRF會用到了上下文信息作為特徵。

2）解決MEMM對節點進行歸一化所造成的label bias問題，CRF是全局歸一化。

3）對特徵的融合能力強，在消歧和新詞發現上表現得比較好

那麼，我們現在把LSTM加入PK陣營：（先假定我們在LSTM上接softmax進行序列標註）

1）LSTM在序列建模問題上表現很強勢大家都知道，可以capsule到較為長遠的上下文信息，從這一點來看，CRF......猝。但是LSTM也可能會增加模型複雜度，耗費時間。

2）CRF對整個序列來計算似然概率，而LSTM方法是對單步似然進行疊加，從原理上CRF更加符合序列標註任務，考慮到整個序列的標註情況。

3）CRF比較適合小數據集（因為LSTM在缺少數據的情況下可能會過擬合），LSTM比較適合大數據集，自動學習文本特徵。

Part IV：LSTM-CRF

既然CRF依賴於特徵模板，而LSTM可以自動學習特徵，那我們可以把LSTM和CRF結合起來。

Pytorch入門文檔中提供了一個簡單的Bi-LSTM CRF模型，有一點比較坑的是竟然不是矩陣運算！所以還要改成矩陣運算，不然慢到你懷疑人生。

接下來分析一下這個模型：

引用自參考論文[1]

假設 $f_ heta$ 是LSTM的輸出矩陣， $[f_ heta]_{i, t}$ 表示在時刻t下，當前輸入映射到tag i 的非歸一化轉移概率， $A_{ij}$ 是CRF的狀態轉移矩陣，表示從tag i 轉移到tag j 的概率，

下面定義觀測序列x 對於狀態序列y 的score是：

$s(x, y, ilde{ heta} ) = sum_{t=1}^{T}{([A]_{y_{t-1},y_t}+[f_ heta]_{y_t, t})}$

我改了一下論文的公式形式，感覺可能會比較好看一點，公式的思想是一樣的。

然後通過softmax函數對score進行歸一化：

$p(y|x) = frac{e^{s(x,y, ilde{ heta})}}{sum_{ ilde{y} in Y}^{}{e^{s(x, ilde{y}, ilde{ heta})}}}$

其中Y表示所有可能的序列（計算稍微麻煩一些），通過極大似然概率求解 $heta$ 。

訓練好之後，解碼過程依然是用viterbi演算法，來求解最佳路徑。（訓練過程並不會用到viterbi演算法，只是在調用模型的時候會用到）

參考論文：[1]Bidirectional LSTM-CRF Models for Sequence Tagging