代碼下載下傳：基于隐馬爾可夫模型的有監督詞性标注
詞性标注（Part-of-Speech tagging 或 POS tagging)是指對于句子中的每個詞都指派一個合适的詞性，也就是要确定每個詞是名詞、動詞、形容詞或其他詞性的過程，又稱詞類标注或者簡稱标注。詞性标注是自然語言進行中的一項基礎任務，在語音識别、資訊檢索及自然語言處理的許多領域都發揮着重要的作用。
詞性标注本質上是一個分類問題，對于句子中的每一個單詞W，找到一個合适的詞類類别T，也就是詞性标記，不過詞性标注考慮的是整體标記的好壞，既整個句子的序列标記問題。對于分類問題，有很多現成的數學模型和架構可以套用，譬如HMM、最大熵模型、條件随機場、SVM等等，在本部落格中我們介紹基于隐馬爾可夫模型（HMM）的詞性标注。
1 隐馬爾可夫模型（HMM）
隐馬爾科夫模型(HMM)是什麼？說白了，就是一個數學模型，用一堆數學符号和參數表示而已，包括隐藏狀态集合、觀察狀态集合、初始機率向量, 狀态轉移矩陣A，混淆矩陣B。
在wiki上一個比較好的HMM例子，淺顯易懂地介紹了HMM的基本概念和問題，初次接觸HMM的人可以首先看一下這個例子。在Hidden Markov Models網站，更加詳細地介紹了HMM，在此我們借用該網站中的例子和圖進一步介紹HMM。
想象一個這樣的場景：一個詩人因為抨擊當權派被打入地牢中，在暗無天日的地牢中詩人不想無所事事，整日沉淪，是以他每天都在牆上寫詩抒發情感。某日，他在地牢的牆角發現一些苔藓。在毫無生機的地牢裡能發現另一種生命讓他深感欣慰，每天都與苔藓對話。幾天之後他發現一個現象，苔藓有時濕潤，有時幹燥，他猜想這可能和外面未知的天氣有關。
根據上面的描述，我們可以構造一個HMM，然後利用苔藓的狀态來預測天氣。首先，天氣是未知的狀态，是需要推測的量，在HMM中就是隐藏狀态。為了簡化起見，假設詩人被捕的地牢外面隻有三種天氣狀态：晴天（Sun）、雨天（Rain）和陰天（Cloud），如圖一所示。
圖一 天氣狀态轉換圖
狀态轉換可以分為确定型的和非确定型的，交通燈的狀态轉換是确定型的，也即在紅燈之後我們肯定知道下一個狀态是綠燈。但是天氣狀态的轉換是非确定型的，也即今天是晴天，不能确定明天是什麼天氣（即使現在的天氣預報非常準确，我們還是無法100%知道明天的天氣，其實明天的世界有很大的不确定型）。不确定型的狀态轉換需要采用機率模型來描述它們之間的狀态變化。圖二描述了地牢外面天氣的狀态轉移矩陣：
圖二 天氣的狀态轉移矩陣
上述矩陣是行随機的（row stochastic），每一行的機率相加是1，含義是不管昨天什麼天氣，今天肯定是（sun,cloud,rain）天氣中的一種，隻是每一種天氣發生的機率不同。假設有N個狀态，隐藏狀态的狀态轉移矩陣就是一個N*N的矩陣，通常稱為A。
此外，我們還需要一個不同天氣發生的先驗機率，也即地牢外面常年統計獲得的三種天氣發生機率，通常稱為
。假定（sun,cloud,rain）發生的先驗機率為：
現在我們已經有HMM的兩個參數，還缺一個關于觀測狀态的參數。在地牢中，詩人可以觀測的量隻有苔藓的狀态，為簡化起見，假設苔藓的變化隻有四種狀态：非常潮濕（Soggy）、潮濕（Damp）、幹燥（Dryish）和非常幹燥（Dry）。這些可觀測的狀态都和隐藏的天氣相關，如圖三所示。每一個隐藏的天氣狀态都可能會産生苔藓的四種狀态，又隻是機率不同而已。為了描述這個機率，需要引入一個混淆矩陣（confuse matrix），又叫發射矩陣。用來描述不同天氣狀态下産生苔藓不同狀态的機率，如圖四所示。
圖三 隐藏天氣狀态和觀測狀态之間的關系
混淆矩陣描述了HMM的第三個參數，通常稱為B。假定有M個可觀測狀态，則混淆矩陣是N*M的矩陣，并且每一行的機率為1，表示在某個天氣狀态下，苔藓肯定屬于（Soggy，Damp，Dryish，Dry）中的一種狀态。
圖四 HMM的混淆矩陣
整個HMM就是由上述三元組構成，可以用HMM
表示。知道了這三個參數，我們就可以完全了解整個HMM。HMM可以用來解決三個問題：
- 給定一個模型，如何計算某個特定的觀測序列的機率；
- 給定一個模型和某個特定的觀測序列，如何找到最可能産生這個輸出的隐藏狀态序列；
- 給定足夠的觀測資料，如何估計HMM的三個參數 。
基于隐馬爾可夫模型的有監督詞性标注
在語音識别領域，主要關注第一和第三個問題，在詞性标注中主要關注第二和第三個問題。解決第一個問題的用途是：在有多個HMM的情況下，選擇使機率最大的HMM。在語音識别領域，需要對每個詞建構一個HMM模型，就将語音識别成機率最大的HMM對應的詞。解決第二個問題的用途是可以知道觀測序列最有可能的隐藏狀态序列，詞性标注就是解決這個問題。第三個問題對所有應用HMM的人來說都非常重要，但是也最難，也即訓練模型參數。HMM的三個參數并不是憑空想出來的，而是訓出來的。
第一個問題可以通過前向算法快速解決，第二個問題需要利用Viterbi算法解決，第三個問題則有兩種方法解決：有監督或者無監督。有監督的參數訓練通過标注訓練集統計獲得相關參數，難度較低；無監督的參數訓練則通過鮑姆-韋爾奇算法疊代訓練獲得，難度很大。在此我們介紹有監督的詞性标注，也即HMM參數的訓練通過統計語料庫獲得。
2 詞性标注
詞性标注的目的就是對給定的句子先分詞，然後給每一個詞标注不同的詞性。很明顯可以看出，HMM中的可觀測序列就是詞性标注中給定句子的分詞，而隐藏狀态就是不同的詞性，詞性的先驗機率即是參數是以，為了實作對句子的詞性标注，我們需要首先利用語料庫訓練一個HMM，然後再對句子進行分詞和标注。
2.1 中文分詞
我們首先介紹中文分詞。這是因為使用者輸入的是一個完整的句子，并不能直接得到可觀測序列。采用統計語言模型的中文分詞，效果已經非常好，可以認為中文分詞是一個已經解決了的問題。不過，這又需要訓練一個新的馬爾可夫模型，不屬于本部落格考慮的範圍。在此，我們實作了一種最簡單的中文分詞：總左往右掃描句子，然後查找詞庫，找到最長的詞比對，遇到不認識的字串就分割成單字詞。
在代碼中，我們有一個接近35w的詞庫，詞庫中的詞語按照unicode碼排序，可以友善地查找。在分詞時，首先将詞庫讀到記憶體中，然後将句子按照從左往右最長比對原則查找詞庫。由于詞庫按照unicode碼排序，是以我們可以采用二分快速查找詞組。查找時，我們首先讀取原始句子的第一個字，定位到該字在詞庫中的起始位置和結束位置，然後進行二分查找即可。在查找的過程中記錄起始和結束位置之間所有詞的最大長度，然後從最大長度開始查找詞庫，長度逐一遞減，直到找到為止。圖五簡單描述了分詞的過程：
圖五 中文分詞示意圖
2.2 HMM參數訓練
HMM需要訓練的參數有三個，即
。
表示詞性的先驗機率，A表示詞性之間的狀态轉移矩陣，B表示詞性到詞的發射矩陣或者混淆矩陣。本部落格采用有監督的方式訓練上述三個參數。有監督的方式，也即通過統計語料庫中的相關資訊訓練參數。圖六是我們采用的語料庫的部分截圖，每一行都是一個完整的被标注過的句子。
圖六 部分語料庫
HMM參數訓練就是通過分析上述語料庫獲得HMM的三個參數。通過解析上述語料庫我們可以獲得：每個詞性出現的次數，每個詞性及其後繼詞性出現的次數和詞性對應的詞。統計完這些資訊之後就可以以頻率代替機率獲得三個參數的值。
統計上述資訊的關鍵是解析語料庫，解析通過下面三句正規表達式完成：
// 擷取預料語料庫中的一個個不同的詞組(以空格分開)，詞組後附有相應的詞性
text = content.toString().split("\\s{1,}");
// 去除詞性标注，隻儲存詞組
phrase = content.toString().split("(/[a-z]*\\s{0,})");//"/"後面跟着一個或者多個字母然後是多個空格
// 擷取語料庫中從前往後的所有詞組的詞性
characters = content.toString().split("[0-9|-]*/|\\s{1,}[^a-z]*"); //開頭的日期或者空格+非字母作為分隔符
注釋已經詳細解釋了正規表達式的含義，在此不再贅述。獲得上述資訊之後，我們就可以很容易地統計相關資訊，進而利用頻率算機率。詞性先驗機率的計算沒有任何難度。隐藏狀态轉移矩陣按照公式：
來計算，
表示不同的兩個詞性前後出現的次數，
表示詞性
出現的次數。可觀測狀态的發射矩陣按照公式：
來計算，
表示某個詞和某個詞性同時出現的次數。在計算頻率的時候，由于有些值非常小，為了避免後面計算過程中的下溢，我們統一将計算的結果乘以100。個人不能保證這種方法的可靠性，事實上，對于頻數為零或者頻數很小的情況，我們需要按照古德-圖靈估計重新計算（數學之美P34），之後求最優隐藏序列需要采用log方式。在此，為了簡便，忽略這些細節（不要在意這些細節☺）。假設通過分析語料庫，最後獲得了N個詞性，M個詞組，則
就是一個長度為N的向量，A是一個N*N的句子，B就是一個N*M的矩陣。後面對句子進行詞性标注時，要確定分詞後的詞組都在M中，否則就超出了HMM的處理能力。
2.3 再次分詞
一般情況下，完成HMM參數訓練之後，我們就可以利用HMM完成一些具體的事情。不過，在這之前對于我們的詞性标注系統，還需要進一步分詞。我們采用的分詞方法是從左往右，最大比對模式。但是程式中采用的語料庫卻傾向于最小比對模式。是以我們初次分詞的結果有可能不在語料庫中。在此我們将語料庫不能識别的詞組再次進行分詞嘗試讓算法找到更多的詞。
再次分詞的算法很簡單。既然我們已經統計了HMM中出現過的所有可觀測狀态M，則将分詞的結果在所有的狀态中查找即可。找不到的分詞分成兩部分作為新的分詞。
2.4 Viterbi算法
終于要說到大名鼎鼎的Viterbi算法了，但是從難度上來說，它遠不如模型的參數訓練麻煩，是以其實它很簡單。為了更數學化的描述該算法，我們先聲明幾個符号：
- ：隐藏狀态的先驗機率；
基于隐馬爾可夫模型的有監督詞性标注 - ：隐藏狀态的轉移矩陣，每一項表示從狀态
基于隐馬爾可夫模型的有監督詞性标注 轉移到狀态 基于隐馬爾可夫模型的有監督詞性标注 的機率 基于隐馬爾可夫模型的有監督詞性标注 ； 基于隐馬爾可夫模型的有監督詞性标注 - ：隐藏狀态産生觀測狀态的發射矩陣或混淆矩陣，每一項表示隐藏狀态
基于隐馬爾可夫模型的有監督詞性标注 産生觀測狀态 基于隐馬爾可夫模型的有監督詞性标注 的機率 基于隐馬爾可夫模型的有監督詞性标注 ； 基于隐馬爾可夫模型的有監督詞性标注
在介紹Viterbi算法在計算隐藏狀态序列的優越性之前，我們先考慮窮舉算法。還是考慮一開始的詩人天氣預測問題。假設詩人連續三天觀測到苔藓的狀态為（dry，damp，soggy），現在要求最可能的天氣狀态。最簡單但是最笨的方法是将三天的所有天氣組合羅列出來，然後求每一種組合的機率，選擇機率最大的組合即可，如圖七所示。
圖七 觀測序列的所有可能隐藏序列組合
按照上面窮舉算法，最可能的狀态序列求法如下：
假定有T個可觀測狀态，給定一個隐藏狀态序列，計算複雜度為O(2T)，是以總的複雜度為O(2TNT)。顯然這個複雜度為指數級，無法應用到實際中，基于動态規劃的Viterbi算法應運而生。
既然要求最可能的隐藏狀态序列，則其必然滿足該序列發生的可能性最大，同時子序列也滿足最優子結構： x0,x1,…,xt發生的機率也必須最大，否則可以替換成機率更大的序列，進而産生更好的序列，這與前提沖突。DP算法有兩個關鍵點：遞歸方程和初始化。假定我們現在已經求得了最可能發生的前 t個隐藏狀态，在求 t+1個狀态時，我們需要從第 t個狀态中選擇最優的一個狀态。由于在時刻 t，共有 N個可以選擇的隐藏狀态，是以 t+1時刻的計算就是從這 N個狀态中選擇一個使 t+1狀态機率最大的。初始化主要是依賴于先驗機率。由此可得Viterbi算法的步驟：
- 令 ，i=0,1,…,N-1；
基于隐馬爾可夫模型的有監督詞性标注 - 對t=1,2,…,T-1，i=0,1,…,N-1，計算：
基于隐馬爾可夫模型的有監督詞性标注 - 在時刻T-1會得到以N個不同狀态結尾的機率，選擇機率最大的狀态：
基于隐馬爾可夫模型的有監督詞性标注 - 計算最大機率不是目的，目的是要找到使機率最大的隐藏序列，這就需要儲存每一步計算過程中選擇的最優狀态，然後回溯即可。
Viterbi算法的計算可以通過圖八說明。黃色的一列是需要初始化的列，紅色方格的計算依賴綠色的列，最後結果是藍色列中的最大值。計算完成之後，再通過回溯找到最優的隐藏狀态序列。
圖八Viterbi算法的矩陣計算過程
有了Viterbi算法，我們就可以快速獲得最優的隐藏序列，由于圖八中的矩陣總共有N*T個元素，每個元素的計算複雜度為O(N)，是以總的複雜度為O(TN2)。在實際的實作過程中，我們最好将隐藏狀态和觀測狀态交換一下位置，也即對上述矩陣進行轉置，這是因為如果按照圖八的方式，每一列元素實際上是不相鄰的，這會導緻非常嚴重的cache缺失，進而會使計算性能下降，圖示隻是為了描述友善才這樣畫的。
3 總結
針對詞性标注，我們在利用HMM時需要解決兩個問題：HMM三個參數的訓練和尋找最優隐藏序列。在詞性标注領域，存在非常多的語料庫，是以我們采用有監督的訓練方式獲得HMM參數，然後利用Viterbi算法求最優隐藏序列。整個算法的關鍵在于了解HMM，隻有真正了解了，後面的所有任務都可以輕而易舉地解決。
4 參考資料
[1] 數學之美3,4,5,26章；
[2] 隐馬爾可夫模型；
[3] A revealing introduction to hiddenmarkov models；
[4] HMM在自然語言進行中的應用一：詞性标注。