1.背景
序列标注是一個比較廣泛的任務，包括分詞，詞性标注，命名實體識别，關系抽取等等，甚至你也可以用來做抽取式QA，直接在文章中标注出答案。
這裡跟大家提一下分詞，很基礎也是很重要的一個任務，我說重要指的是我們應該掌握分詞有哪些算法，而不是說這是一個很好的研究方向，目前分詞可提升的空間很小了，是以不建議大家研究這個，但是可以做一些小實驗看看。
另外給大家介紹一些比較好用的中文分詞工具：
結巴分詞（比較簡單友善，我用這個來分詞）
LTP（哈工大NLP（https://www.ltp-cloud.com/），我用這個做過詞性标注和命名實體識别，有時候可能需要在詞向量的基礎上加一些人工特征，引入額外特征資訊）
Hanlp（Github文檔寫得挺不錯的（https://github.com/hankcs/HanLP），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，怎麼用于序列标注任務。
2.HMM
2.1 基本概念
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下，狀态 yt y t 隻和前一個狀态 yt−1 y t − 1 有關，與其他狀态及觀察值無關，和 yt−2 y t − 2 無關，和 xt x t 也無關
接下來還會涉及到以下三組機率參數：
狀态轉移矩陣：A = [aij]N∗N [ a i j ] N ∗ N ，表示在 t 時刻下，狀态 si s i 轉移到狀态 s_j 的機率：
aij=P(yt+1=sj|yt=si),1≤i,j≤N a i j = P ( y t + 1 = s j | y t = s i ) , 1 ≤ i , j ≤ N
觀測機率矩陣： B=[bij]N∗M，表示在狀态si下生成觀測oj的機率： B = [ b i j ] N ∗ M ， 表 示 在 狀 态 s i 下 生 成 觀 測 o j 的 概 率 ：
bij=P(xt=oj|yt=si),1≤i≤N,1≤j≤M b i j = P ( x t = o j | y t = s i ) , 1 ≤ i ≤ N , 1 ≤ j ≤ M
初始狀态機率分布： π=(π1,π2,...,πN) π = ( π 1 , π 2 , . . . , π N ) ，表示初始時刻下各狀态出現的機率：
πi=P(y1=si),1≤i≤N π i = P ( y 1 = s i ) , 1 ≤ i ≤ N
HMM可以解決以下三類推斷問題：
1）似然問題：給定模型 λ=[A,B,π] λ = [ A , B , π ] ，求解 P(x|λ) P ( x | λ )
2）解碼問題：給定模型 λ=[A,B,π] λ = [ A , B , π ] 和觀測序列x，求解 狀态序列 y
3）學習問題：給定觀測序列x，求解模型參數 λ=[A,B,π] λ = [ A , B , π ]
2.2 HMM解決序列标注問題
回到我們的序列标注問題，也就是解碼問題，這裡以分詞為例，狀态集合可以定義為{B，M，E，S}，觀測序列就是我們的句子，狀态序列y是我們的分詞結果，我們用Viterbi算法來求解最大機率對應的狀态序列y，也就是最有可能出現的狀态序列.
Viterbi算法
大家不要把viterbi算法和HMM綁定到一起，這個算法本來是用動态規劃來求最短路的，不是專門給HMM設計的，隻是恰好可以求解HMM的解碼問題。
算法基于這樣的前提：最優路徑的子路徑也一定是最優的。
算法思路大概是：從根節點出發，每走一步，比較根節點到上層節點的最短路徑+上層節點到目前節點的最短距離，遞歸計算到達該點的最短路徑，一直走到終點。
那麼viterbi算法用于HMM，就是求解給定觀測值x後機率最大的狀态序列y，如果使用窮舉法會帶來巨大的計算量，是以viterbi對狀态進行轉移，而狀态數往往是比較少的。
【【https://zh.wikipedia.org/wiki/維特比算法 講解清晰移動】
下面三張圖可以清楚的展示這過程：
一個人可以觀察到的狀态有三種 正常 發冷 頭暈，對應的狀态分别可能是健康或則發燒 健康與發燒之間轉換為狀态轉換矩陣，健康或發燒 狀态下的正常、發冷，頭暈機率為發射矩陣
回到分詞任務，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把機率連乘轉化為連加，是以機率矩陣中可能有負數
3. CRF(條件随機場）
前面介紹的HMM其實分詞結果比較一般，在很長一段時間，CRF都是序列标注任務的标配（當然現在主流做法也是LSTM套上CRF）。
3.1 基本概念
CRF是一種判别式無向圖模型，對條件分布進行模組化，建構條件機率模型p(y|x)。
1.直覺感受
令G=(V，E)表示節點與标記向量y中元素一一對應的無向圖，V是節點的集合，E是無向邊， yv y v 表示與節點v所對應的标記變量，n(v)表示節點v的鄰接節點，V/v 表示除了結點v 以外的所有結點。如果圖G的每個變量 yv y v 都滿足以下的馬爾科夫性質：
P(yv|x,yV/v)=P(yv|x,yn(v)) P ( y v | x , y V / v ) = P ( y v | x , y n ( v ) ) ]
那麼（y, x）就構成了一個條件随機場。(可以直覺了解為某個位置的指派僅與相鄰的位置指派和目前的狀态有關)
2. 通過特征函數建構結點與标簽直接的關系
CRF引入了特征函數（exp形式）來定義序列y的條件機率：
P(y|x)=1Zexp(∑j∑n−1i=1λitj(yi+1,yi,x,i)+∑k∑ni=1μksk(yi,x,i)) P ( y | x ) = 1 Z e x p ( ∑ j ∑ i = 1 n − 1 λ i t j ( y i + 1 , y i , x , i ) + ∑ k ∑ i = 1 n μ k s k ( y i , x , i ) )
其中tj和sk 其 中 t j 和 s k 都是特征函數， tj t j 用來描述兩個相鄰位置的y 之間的關系 以及x對y的影響， sk s k 描述x 在位置i 對y 的影響。特征函數是事先定義好的， λj和μk λ j 和 μ k 才是我們的參數，也就是說，CRF需要訓練的，隻是這些特征的權重。
另外，這裡還做了全局歸一化，Z是規範化因子，CRF對Y中所有可能的狀态序列做了全局的歸一化，避免了label bias的問題。（MMEN是本地歸一化）
3.2. 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比較适合大資料集，自動學習文本特征
4. LSTM-CRF
既然CRF依賴于特征模闆，而LSTM可以自動學習特征，那我們可以把LSTM和CRF結合起來。
Pytorch入門文檔中提供了一個簡單的Bi-LSTM CRF模型，有一點比較坑的是 竟然不是矩陣運算！是以還要改成矩陣運算，不然慢到你懷疑人生。
接下來分析一下這個模型：
假設fθ是LSTM的輸出矩陣，[fθ]i,t表示在時刻t下，目前輸入映射到tagi的非歸一化轉移機率，Aij是CRF的狀态轉移矩陣，表示從tagi轉移到tagj的機率 假 設 f θ 是 L S T M 的 輸 出 矩 陣 ， [ f θ ] i , t 表 示 在 時 刻 t 下 ， 當 前 輸 入 映 射 到 t a g i 的 非 歸 一 化 轉 移 概 率 ， A i j 是 C R F 的 狀 态 轉 移 矩 陣 ， 表 示 從 t a g i 轉 移 到 t a g j 的 概 率
下面定義觀測序列x 對于狀态序列y 的score是：
s(x,y,θ~)=∑Tt=1([A]yt−1,yt+[fθ]yt,t) s ( x , y , θ ~ ) = ∑ t = 1 T ( [ A ] y t − 1 , y t + [ f θ ] y t , t )
然後通過softmax函數對score進行歸一化：
p(y|x)=es(x,y,θ~)∑y~∈Yes(x,y~,θ~) p ( y | x ) = e s ( x , y , θ ~ ) ∑ y ~ ∈ Y e s ( x , y ~ , θ ~ )
其中Y表示所有可能的序列（計算稍微麻煩一些），通過極大似然機率求解 θ θ 。
訓練好之後，解碼過程依然是用viterbi算法，來求解最佳路徑。（訓練過程并不會用到viterbi算法，隻是在調用模型的時候會用到）
參考文章：
https://zhuanlan.zhihu.com/p/35620631