大家好，今天介紹自然語言處理中經典的隱馬爾科夫模型(HMM)。HMM早期在語音識別、分詞等序列標註問題中有著廣泛的應用。
了解HMM的基礎原理以及應用，對於了解NLP處理問題的基本思想和技術發展脈絡有很大的好處。本文會詳細講述HMM的基本概念和原理，並詳細介紹其在分詞中的實際應用。
作者 | 小Dream哥
編輯 | 言有三
1 馬爾科夫隨機過程
設隨機變量X(t)隨時間t(t=t1,t2,t3...tn)而變化，E為其狀態空間，若隨機變量x滿足馬爾科夫性，如下：
即X在tn時刻的狀態只與其前一時刻時狀態的值有關，則稱該隨機變量的變化過程是馬爾科夫隨機過程，隨機變量滿足馬爾科夫性。
2 隱馬爾科夫模型（HMM）
如圖所示為馬爾科夫模型的圖結構
基於此圖結構可知，HMM模型滿足如下的性質：
(1) 它基於觀測變量來推測未知變量；
(2) 狀態序列滿足馬爾科夫性；
(3) 觀測序列變量X在t時刻的狀態僅由t時刻隱藏狀態yt決定。
同時，隱馬爾科夫模型是一種概率圖模型，它將學習任務歸結於計算變量的概率分布。通過考慮聯合概率P(Y,X)來推斷Y的分布。
考慮馬爾科夫性質以及隨機變量Y在t時刻的狀態僅由y(t-1)決定，觀測序列變量X在t時刻的狀態僅由yt決定，有：
從而可以推出聯合概率：
總的來說，馬爾科夫模型式利用已知的觀測序列來推斷未知變量序列的模型。
例如在分詞任務中，中文的句子「請問今天的天氣怎麼樣？」就是可以被觀測到的序列，而其分詞的標記序列就是未知的狀態序列「請問/今天/深圳/的/天氣/怎麼樣/？」這種分詞方式對應的標記序列為「BEBEBESBEBME」
標記序列：標籤方案中通常都使用一些簡短的英文字符[串]來編碼。
標籤列表如下，在分詞任務中，通常用BMES標記。
B，即Begin，表示開始
M，即Mediate，表示中間
E，即End，表示結尾
S，即Single，表示單個字符
3 HMM模型的幾個重要概率矩陣
仔細分析此聯合概率表達式，可知其分為三個部分：
(1) 初始狀態概率P(y1)
初始概率矩陣是指序列頭的狀態分布，以分詞為例，就是每個句子開頭，標記分別為BMES的概率。
(2) 狀態轉移概率P(yi|yi-1)
狀態轉移概率是指狀態序列內，兩個時刻內不同狀態之間轉移的狀態分布。以分詞為例，標記狀態總共有BMES四種，因此狀態轉移概率構成了一個4*4的狀態轉移矩陣。這個矩陣描述了4種標記之間轉化的概率。例如，P(yi=」E」|yi-1=」M」)描述的i-1時刻標為「M」時，i時刻標記為「E」的概率。
(3) 輸出觀測概率P(xi|yi)
輸出觀測概率是指由某個隱藏狀態輸出為某個觀測狀態的概率。以分詞為例，標記狀態總共有BMES四種，詞表中有N個字，則輸出觀測概率構成了一個4*N的輸出觀測概率矩陣。這個矩陣描述了4種標記輸出為某個字的概率。例如，P(Xi=」深」|yi=」B」)描述的是i時刻標記為「B」時，i時刻觀測到到字為「深」的概率。
4 HMM在分詞應用中的實戰
經過上面的講述，各位讀者可能還是會對HMM有一種似懂非懂的感覺。所以這一節中介紹其在分詞應用中的實踐，通過完整實際的思路介紹和代碼講解，相信各位讀者能夠對HMM模型有一個準確的認識。
假設有詞序列Y = y1y2....yn，HMM分詞的任務就是根據序列Y進行推斷，得到其標記序列X= x1x2....xn，也就是計算這一個概率：
根據貝葉斯公式：
當語料確定時
可以認為是常數，所以只需計算
這樣的話，就是要計算3小節的那三個概率矩陣，當獲得上述三個矩陣之後，便可以根據維特比算法計算出一個詞序列對應概率最大的分詞標記序列，就此也就完成了分詞的任務。那我們就還剩下2個任務：
4.1 根據語料計算三個概率矩陣
當獲得了分好詞的語料之後，三個概率可以通過如下方式獲得：
(1)初始狀態概率P(y1)
統計每個句子開頭，序列標記分別為B，S的個數，最後除以總句子的個數，即得到了初始概率矩陣。
(2) 狀態轉移概率P(yi|yi-1)
根據語料，統計不同序列狀態之間轉化的個數，例如count(yi=」E」|yi-1=」M」)為語料中i-1時刻標為「M」時，i時刻標記為「E」出現的次數。得到一個4*4的矩陣，再將矩陣的每個元素除以語料中該標記字的個數，得到狀態轉移概率矩陣。
(3) 輸出觀測概率P(xi|yi)
根據語料，統計由某個隱藏狀態輸出為某個觀測狀態的個數，例如count(xi=」深」|yi=」B」)為i時刻標記為「B」時，i時刻觀測到字為「深」的次數。得到一個4*N的矩陣，再將矩陣的每個元素除以語料中該標記的個數，得到輸出觀測概率矩陣。
我們看一下該部分的代碼：
Pi = {k: v*1.0/line_num for k,v in Pi_dict.items()} A = {k: { k1: v1/ Count_dict[k] for k1, v1 in v.items()} for k, v in A_dict.items() }B= {k: { k1: v1/ Count_dict[k] for k1, v1 in v.items()} for k,v in B_dict.items() } line_num為預料中句子的個數；
Pi_dic記錄了語料中句子中開頭標記的個數。
Count_dict記錄了預料中「BMES」四個標記的個數；
A_dict記錄了不同序列狀態之間轉化的個數；
B_dict記錄了不同隱藏狀態輸出為某個觀測狀態的個數。
4.2 維特比算法
訓練結束之後，便可獲得三個概率矩陣，那麼該如何利用上述矩陣，獲得一個句子的最大概率分詞標記序列，即完成分詞任務呢？下面就是我們要介紹的維特比算法。
設Q是所有可能狀態的集合Q={q1,q2,....qN}，V={v1,v2,...vM}是所有可能的觀測集的集合。其中N是可能的狀態數（例如標記個數4：「BMES」），M是可能的觀測狀態數（例如字典中字的個數）。
一個隱馬爾可夫模型由一個三元組(Pi,A,B)確定，I是長度為T的狀態序列，O是對應的觀測序列，先用數學符號表示上述的三個概率矩陣：
初始概率矩陣，表示序列開頭，序列狀態為yi的概率
狀態轉移矩陣，表示序列狀態由yi轉為yj的概率
輸出狀態矩陣，表示序列狀態為yi時，輸出字為xj的概率
進而，為了敘述方便，引入兩個變量：
定義時刻t狀態為i的所有單個路徑(i1,i2,i3,...,it)中概率最大值為，簡單記為delta(i)：
由其定義可得其遞推公式：
下為時刻t狀態為i的所有單個路徑中，概率最大的路徑的第t-1個節點，簡單記為kethe(i)：
先闡述一下維特比算法的基本流程：
(1) 計算初始轉態概率
通過上述公式，得到t=1時刻，隱藏狀態取各個值(BMES)時的概率。
(2) 逐漸遞推到t=2,3,4.....T
通過上述公式，分別得到各個時刻，隱藏狀態取各個值時的概率最大的路徑以及其前一時刻節點狀態
(3) 終止
選取T時刻中，取值最大的那個狀態為T時刻的狀態。
(4) 回溯最優路徑
根據前面計算的結果，反推得到各個時刻隱藏狀態的取值
可能還有同學對這個過程不是很理解，我們舉分詞的例子，詳細介紹一下這個過程。
維特比算法是計算一個概率最大的路徑，如圖要計算「我愛中國」的分詞序列：
第一個詞為「我」，通過初始概率矩陣和輸出觀測概率矩陣分別計算delta1("B")=P(y1=」S」)P(x1=」我」|y1=」S」)，delta1("M")=P(y1=」B」)P(x1=」我」|y1=」B」)，delta1("E")=P(y1=」M」)P(x1=」我」|y1=」M」)，delta1("S")=P(y1=」E」)P(x1=」我」|y1=」E」)，
並設kethe1("B")=kethe1("M")=kethe1("E")=kethe1("S")=0；
同理利用公式分別計算：
delta2("B")，delta2("M")，delta2("E")，delta2("S")。圖中列出了delta2("S")的計算過程，就是計算：
P(y2=」S」|y1=」B」)P(x2=」愛」|y2=」S」)P(y2=」S」|y1=」M」)P(x2=」愛」|y2=」S」)P(y2=」S」|y1=」E」)P(x2=」愛」|y2=」S」)P(y2=」S」|y1=」S」)P(x2=」愛」|y2=」S」)其中P(y2=」S」|y1=」S」)P(x2=」愛」|y2=」S」)的值最大，為0.034，因此delta2("S")，kethe2("S")="S"，同理，可以計算出delta2("B")，delta2("M")，delta2("E")及kethe2("B")，kethe2("M")，kethe2("E")。
同理可以獲得第三個和第四個序列標記的delta和kethe。
到最後一個序列，delta4("B")，delta4("M")，delta4("E")，delta4("S")中delta4("S")的值最大，因此，最後一個狀態為」S」。
最後，回退，
i3 = kethe4("S") ="B"i2 =kethe3("B") = "S"i1 = kethe2("S") ="S"求得序列標記為：「SSBE」。
總結
HMM的基本原理和其在分詞中的應用就講到這裡了，從上述分析可以看出，HMM時非常適合用於序列標註問題的。但是HMM模型引入了馬爾科夫假設，即T時刻的狀態僅僅與前一時刻的狀態相關。但是，語言往往是前後文相互照應的，所以HMM可能會有它的局限和問題，讀者可以思考一下，如何解決這個問題。
下期預告：條件隨機場（CRF）原理與應用