Sequence Labeling的發展史（HMM,MEMM,CRF）

08-12

來自專欄啊黎的NLP成長之路5 人贊了文章

在機器學習領域，序列標註問題通常使用概率圖模型來建模。本文主要介紹sequence labeling在機器學習領域的演變過程中最有代表性的三個模型：隱馬爾科夫模型（HMM），最大熵馬爾科夫模型（MEMM）和條件隨機場（CRF）。

序列標註的定義

典型的序列標註任務可以被公式化地建模。假設輸入的句子為 $m{x}=(x_1,x_2,...,x_l)$ ，其中 $x_i$ 表示句子中第 $i$ 個元素，可能是字或者詞， $l$ 表示句子 $m{x}$ 的長度。而標籤序列則用 $m{y}=(y_1,y_2,...,y_l)$ 來表示，其中 $y_i=j$ ， $j$ 的值取自一個事先定義好的有限標籤集 $Y$ ，表示第 $j$ 種標籤。因此，序列標註問題可以形式化地表示為：

$y*=argmax_{y}F(m{x},m{y}, heta)$ 。

這裡 $F$ 是模型函數， $heta$ 是模型的參數。

隱馬爾科夫模型（Hidden Markov Model, HMM）

HMM結構

隱馬爾科夫模型主要包括五個主要部分， $mu=(S,K,A,B,pi)$ ，其中 $S$ 表示狀態的集合， $K$ 表示輸出的集合， $pi,A,B$ 是隱馬爾科夫模型的參數，分別表示初始狀態的概率分布，狀態之間的轉移概率矩陣和狀態到輸出的發射概率矩陣。

如圖，HMM把序列標註任務建模成了輸入句子 $m{x}$ 是觀察序列，而 $m{y}$ 是隱藏狀態序列。

為了區分兩種矩陣中的元素，狀態轉移矩陣 $A$ 中從第 $i$ 種狀態到第 $j$ 種狀態的轉移概率表示為 $a_{ij}$ ；發射概率矩陣 $B$ 中從第 $i$ 種狀態發射到第 $k$ 種輸出的發射概率表示為 $b_i(k)$ 。

隱馬爾科夫模型是產生式模型，假設給定模型 $mu=(S,K,A,B,pi)$ ，觀察序列 $O=(O_1,O_2,...,O_t)$ 的由隱藏狀態序列 $Q=(Q_1,Q_2,...,Q_t)$ 生成過程如下， $t$ 表示時刻：

在 $t=0$ 的時候，根據初始狀態的概率分布 $pi$ ，採樣得到一個初始的狀態 $q_1=s_i$ ， $s_i$ 表示狀態集合 $S$ 中的第 $i$ 種狀態。
根據狀態 $s_i$ 的發射概率分布 $b_i(*)$ ，採樣得到輸出 $O_t=v_k$ 。
然後根據狀態轉移概率分布 $a_{i*}$ ，採樣得到下一時刻的新的狀態 $q_{t+1}=s_j$ 。
如果當前時刻 $t>T$ ，為最終時刻，則結束生成；否則重複3和4步驟。

HMM定義了序列標註任務的三個基本問題：概率計算問題，解碼問題和參數估計問題。下面將介紹前兩個問題，因為這兩個問題會涉及到序列標註最常用的兩大演算法：前向演算法和viterbi演算法，參數估計問題用EM演算法求解，展開介紹需要很長篇幅，因此不作詳細介紹，想深入了解推薦移步EM演算法學習，Rachel大大的博客學習~

概率計算問題

概率計算問題的定義是給定一個觀察序列 $O=(O_1,O_2,...,O_t)$ 和HMM模型 $heta=(A,B,pi)$ ，計算出給定 $heta$ 的情況下觀察序列 $O$ 的概率 $P(O| heta)$ 。

對於概率 $P(O| heta)$ 的計算，最直觀的方法就是窮盡所有可能的隱藏狀態序列概率連乘即可： $P(O| heta) = sum_QP(O|Q, heta)P(Q| heta) \ =sum_{qin{Q}}pi_{q1}b_{q1}(O1)prod_{t=1}^{T}a_(q_tq_{t+1})b_{q_{t+1}}(O_{t+1})$

其複雜度極其龐大，需要窮盡所有可能的 $q$ ，也就是每一時刻都有 $N$ 種可能的隱藏狀態，總共的時間長度為 $T$ ，那麼就會有 $N^T$ 個可能的狀態序列。因此需通過動態規劃的方法來計算，稱作前向演算法（forward procedure）：

定義前向變數

$alpha_t(i)=P(O_1,O_2,...,O_t,q_t=s_i| heta)$

表示在時間 $t$ ，輸出序列 $O=(O_1,O_2,...,O_t)$ ，並且位於狀態 $s_i$ 的概率。

那麼

$P(O| heta)=sum_{s_i}P(O_1,O_2,...,O_T,q_T=s_i| heta)=sum_{i=1}^{N}alpha_T(i)$ 。

前向變數可以通過動態規劃的方法遞歸計算：

$alpha_{t+1}(j)=(sum_{i=1}^{N}alpha_t(i)a_{ij})b_j(O_{t+1})$ 。

初始條件為：

$alpha_1(i)=pi_ib_i(O_1)$ 。

前向演算法其複雜度降低到了 $O(N^2T)$ 。

前向演算法其實非常容易理解， $alpha_t(i)$ 表示在時間 $t$ ，HMM輸出序列 $O=O_1O_2...O_t$ ，並且位於狀態 $s_i$ ，那麼在時間 $t+1$ 時，輸出序列為 $O=O_1O_2...O_tO_{t+1}$ 並且狀態為 $s_j$ 就應該是所有的狀態 $s_i$ 都轉移到 $s_j$ ，而且 $s_j$ 發射出狀態 $O_{t+1}$ 。

解碼問題

其目的是對於一個給定的觀察序列 $O=O_1O_2...O_T$ 和模型 $heta=(A,B,pi)$ ，求解出「最優」的隱狀態序列 $Q=q_1q_2...q_T$ 。最優的隱狀態序列不是由每一時刻 $t$ 的發射出觀察狀態 $O_t$ 的隱狀態 $q_t$ 組成，而是需要考慮隱狀態之間的概率轉移關係，考慮序列性的約束，確保序列性的最優。因此Andrew J. Viterbi提出了一種動態規劃的快速計算演算法，Viterbi演算法，其思想跟前向演算法類似。

定義維特比變數

$delta_t(i)=max_{q_1q_2...q_{t-1}}P(q_1q_2...q_t=s_i,O=O_1O_2...O_t| heta)$

為在時間 $t$ 隱狀態為 $s_t$ ，並且輸出觀察序列為 $O=O_1O_2...O_T$ 的最大概率。

遞歸計算：

$delta_t(j)=max_i[delta_{t-1}a_{ij}]b_j(O_j(Ot))$

同時記錄最優路徑：

$p_t(j)=argmax_i[delta_{t-1}(i)a_{ij}]b_j(O_t)$

其初始條件為：

$delta_1(i)=pi_ib_i(O_1)$

$p_1(i)=0$

終止條件為遞歸計算到 $T$ 時刻：

$q_T=argmax_i[delta_T(i)]$

狀態回溯求解最優路徑：

$q_t=p_{t+1}(q_{t+1})$

Viterbi演算法的時間複雜度與前向演算法一樣，為 $O(N^2T)$ 。

最大熵馬爾科夫模型（Maximum-Entropy Markov Model, MEMM）

由於HMM是產生式模型，[McCallum et al., 2000]認為這樣的建模方式存在兩個問題：

在很多序列標註任務重，需要用大量的特徵來刻畫觀察序列。（比如命名實體識別中的英文大小寫，位置，上下文等等）
很多問題是在已知觀察序列的情況下求解狀態序列。（也就是人為理解的序列標註應該是句子（觀察序列）決定標籤（狀態序列））

因此直接採用最大熵條件概率模型結合馬爾科夫模型來建模序列標註。

MEMM結構

MEMM的序列標註問題定義為，已知觀察序列 $O=O_1O_2...O_T$ ，求解狀態序列 $S=S_1S_2...S_T$ ，並使得條件概率 $P(S=S_1S_2...S_T|O=O_1O_2...O_T)$ 最大，而且該條件概率滿足馬爾科夫假設，也就是條件概率依賴於當前時刻的觀察狀態和前一時刻的標籤狀態：

$P(S|O)=prod_{t=1}^{T}P(S_t|S_{t-1},O_t)$

因此可以用最大熵分類器來建模基於前一時刻標籤狀態 $S_{t-1}=s$ 和當前時刻的觀察輸出 $O_t=o$ 的當前標籤狀態 $S_t=s$ 的概率：

$P(s|s,o)=frac{1}{Z(s,o)}exp(sum_alambda_{a}f_{a}(o,s,s))$

其中 $Z(s,o)$ 為歸一化因子， $f_a(o,s,s)$ 為特徵函數， $lambda_a$ 為該特徵函數對應的權重，是需要學習的參數。我認為從神經網路的角度看，最大熵模型就是由一層最簡單的前向神經網路加上softmax激活函數構成的一個分類模型。通常的 $f_a(o,s,s)$ 為二值函數，表示是否當前狀態三元組 $(o,s,s)$ 屬於某特徵定義。由大量經驗得知，定義的特徵函數越多，最大熵模型的效果越好。因此對於一個特定的狀態三元組 $(o,s,s)$ ，特徵表示通常很高維而且很稀疏。

MEMM的概率求解問題和解碼問題都很簡單：

對於一個標籤狀態序列的概率為 $P(S|O, heta)=prod_iP_i(s|s,o)$ 。

對於解碼問題，MEMM貪心地取當前時刻概率分布中最大對應的標籤作為當前時刻的解碼標籤： $hat{s}_t=argmax_iP(s|s,o)$ 。

條件隨機場（Conditional Random Field, CRF）

最大熵馬爾科夫模型雖然結合了隱馬爾科夫模型和最大熵模型的最大特點，但是仍然忽略了標籤之間的約束關係，只求在當前時刻的最大條件概率。舉個例子，在命名實體識別中，I-LOC不可能是在B-PER的後一個標籤，但是MEMM會解碼出這樣的標籤序列。這種問題稱為標註偏置問題。因此基於MEMM的基礎上，加入標籤之間的約束的條件隨機場被提出。條件隨機場也是一個基於條件概率的判別模型，定義為 $P(Y|X)=P(S|O)$ ，用 $X$ 和 $Y$ 代替前面的 $O$ 和 $S$ ，分別表示輸入觀察序列和標籤序列。

CRF結構

條件隨機場的定義基本與MEMM一樣：

$P(y_t|y_{t-1},x)=1=frac{1}{Z(y_{t-1},x)}exp(sum_jlambda_jt_j(y_{t-1},y_t,X,t)+sum_kmu_ks_k(y_t,X,t))$

其中 $t_j(y_{t-1},y_t,X,t)$ 是轉移函數，表示對於觀察序列 $X$ 的標註序列在 $t-1$ 和 $t$ 時刻上的標記的轉移概率， $s_k(y_t,X,t)$ 是狀態函數，表示對於觀察序列 $X$ 其 $t$ 時刻的標記概率， $lambda_j$ 和 $s_k$ 分別是 $t_j(y_{t-1},y_t,X,t)$ 和 $s_k(y_t,X,t)$ 的權重，需要經過訓練更新得到。同樣CRF也擁有HMM的優點和屬性，其概率求解問題和解碼問題跟HMM一樣，都是使用前饋演算法和viterbi演算法求解即可。

CRF模型除了序列標註層的約束對於序列標註的效果提升的很重要以外，還有另外一部分也很重要，那就是特徵函數的定義。CRF的特徵函數定義其實跟MEMM的幾乎一樣，通常都是二值函數：

觀察序列的特徵 $s_k(y_t,X,t)$ 可以定義為：

轉移函數可以定義為：

實際上CRF或MEMM在實際應用中存在著兩個非常明顯的缺點：

在實際應用中 $[X_t=特定詞，y_t=某標籤]$ 通常會在詞集合和標籤集合中排列組合構造，因此其特徵數量隨著詞集合和標籤集合的數量增加而指數增加，常常會導致人工特徵維度達到億級別。更不用說 $[X_t=特定詞，y_{t-1}=某標籤，y_t=某標籤]$ 這種更複雜的組合了。因此在實際的代碼實現中，我們通常會忽略三元組特徵的 $X_t$ 屬性，單純只考慮 $[y_{t-1}=某標籤，y_t=某標籤]$ 的特徵，也就是只考慮一個全局的標籤概率轉移矩陣。
另一方面特徵的定義是領域特定的，意思是命名實體識別任務所定義的特徵函數不能遷移到詞性標註任務中使用，不同任務又必須定義不同的特徵函數。

為了解決特徵工程的這些缺點和問題，深度學習作為自動學習和提取深度特徵的有效工具，使用深度神經網路來代替傳統機器學習CRF的人工特徵工程模型在這兩年不斷被提出，在下一篇文章中會主要介紹近年來DL+CRF的一些模型演變過程。

主要參考文獻

宗成慶. 統計自然語言處理 [M]. 清華大學出版社, 2013.