筆記轉(zhuǎn)載于GitHub項目：https://github.com/NLP-LOVE/Introduction-NLP

4. 隱馬爾可夫模型與序列標(biāo)注

第3章的n元語法模型從詞語接續(xù)的流暢度出發(fā)，為全切分詞網(wǎng)中的二元接續(xù)打分，進(jìn)而利用維特比算法求解似然概率最大的路徑。這種詞語級別的模型無法應(yīng)對 OOV(Out of Vocabulary，即未登錄詞) 問題: 00V在最初的全切分階段就已經(jīng)不可能進(jìn)人詞網(wǎng)了，更何談?wù)倩亍?/p>

例如下面一句：

頭上戴著束發(fā)嵌寶紫金冠，齊眉勒著二龍搶珠金抹額

加粗的就是相對陌生的新詞，之前的分詞算法識別不出，但人類確可以，是因為讀者能夠識別“戴著”，這些構(gòu)詞法能讓人類擁有動態(tài)組詞的能力。我們需要更細(xì)粒度的模型，比詞語更細(xì)粒度的就是字符。

具體說來，只要將每個漢字組詞時所處的位置(首尾等)作為標(biāo)簽，則中文分詞就轉(zhuǎn)化為給定漢字序列找出標(biāo)簽序列的問題。一般而言，由字構(gòu)詞是序列標(biāo)注模型的一種應(yīng)用。 在所有“序列標(biāo)注”模型中，隱馬爾可夫模型是最基礎(chǔ)的一種。

4.1 序列標(biāo)注問題

序列標(biāo)注指的是給定一個序列 ，找出序列中每個元素對應(yīng)標(biāo)簽 的問題。其中，y 所有可能的取值集合稱為標(biāo)注集。比如，輸入一個自然數(shù)序列，輸出它們的奇偶性。

image

求解序列標(biāo)注問題的模型一般稱為序列標(biāo)注器，通常由模型從一個標(biāo)注數(shù)據(jù)集 中學(xué)習(xí)相關(guān)知識后再進(jìn)行預(yù)測。再NLP問題中，x 通常是字符或詞語，而 y 則是待預(yù)測的組詞角色或詞性等標(biāo)簽。中文分詞、詞性標(biāo)注以及命名實體識別，都可以轉(zhuǎn)化為序列標(biāo)注問題。

1. 序列標(biāo)注與中文分詞

   考慮一個字符序列(字符串) x，想象切詞器真的是在拿刀切割字符串，如此，中文分詞轉(zhuǎn)化為標(biāo)注集{切，過}的序列標(biāo)注問題。

   image

分詞標(biāo)注集并非只有一種，為了捕捉漢字分別作為詞語收尾(Begin、End)、詞中(Middle)以及單字成詞(Single)時不同的成詞概率，人們提出了{(lán)B,M,E,S}這種最流行的標(biāo)注集。

image

2. 序列標(biāo)注與詞性標(biāo)注

   詞性標(biāo)注任務(wù)是一個天然的序列標(biāo)注問題：x 是單詞序列，y 是相應(yīng)的詞性序列。需要綜合考慮前后的單詞與詞性才能決定當(dāng)前單詞的詞性。
   image

3. 序列標(biāo)注與命名實體識別

   所謂命名實體，指的是現(xiàn)實存在的實體，比如人名、地名和機(jī)構(gòu)名，命名實體是 OOV 的主要組成部分。

   考慮到字符級別中文分詞和詞語級別命名實體識別有著類似的特點，都是組合短單位形成長單位的問題。所以命名實體識別可以復(fù)用BMES標(biāo)注集，并沿用中文分詞的邏輯，只不過標(biāo)注的對象由字符變?yōu)閱卧~而已。唯一不同的是，命名實體識別還需要確定實體所屬的類別。這個額外的要求依然是個標(biāo)注問題，可以通過將命名實體類別附著到BMES標(biāo)簽來達(dá)到目的。比如，構(gòu)成地名的單詞標(biāo)注為“B/M/E/S-地名”，以此類推。對于那些不構(gòu)成命名實體的單詞，則統(tǒng)-標(biāo)注為O ( Outside), 即復(fù)合詞之外。

   image

總之，序列標(biāo)注問題是NLP中最常見的問題之一。許多應(yīng)用任務(wù)都可以變換思路，轉(zhuǎn)化為序列標(biāo)注來解決。所以一個準(zhǔn)確的序列標(biāo)注模型非常重要，直接關(guān)系到NLP系統(tǒng)的準(zhǔn)確率。機(jī)器學(xué)習(xí)領(lǐng)域為NLP提供了許多標(biāo)注模型，本著循序漸進(jìn)的原則，本章介紹其中最基礎(chǔ)的一個隱馬爾可夫模型。

4.2 隱馬爾可夫模型

隱馬爾可夫模型( Hidden Markov Model, HMM)是描述兩個時序序列聯(lián)合分布 p(x,y) 的概率模型: x 序列外界可見(外界指的是觀測者)，稱為觀測序列(obsevation sequence); y 序列外界不可見，稱為狀態(tài)序列(state sequence)。比如觀測 x 為單詞，狀態(tài) y 為詞性，我們需要根據(jù)單詞序列去猜測它們的詞性。隱馬爾可夫模型之所以稱為“隱”，是因為從外界來看，狀
態(tài)序列(例如詞性)隱藏不可見，是待求的因變量。從這個角度來講，人們也稱狀態(tài)為隱狀態(tài)(hidden state),而稱觀測為顯狀態(tài)( visible state)。隱馬爾可夫模型之所以稱為“馬爾可夫模型”，”是因為它滿足馬爾可夫假設(shè)。

1. 從馬爾可夫假設(shè)到隱馬爾可夫模型

   馬爾可夫假設(shè)：每個事件的發(fā)生概率只取決于前一個事件。

   馬爾可夫鏈：將滿足馬爾可夫假設(shè)的連續(xù)多個事件串聯(lián)起來，就構(gòu)成了馬爾可夫鏈。

   如果把事件具象為單詞，那么馬爾可夫模型就具象為二元語法模型。

隱馬爾可夫模型：它的馬爾可夫假設(shè)作用于狀態(tài)序列，

假設(shè) ① 當(dāng)前狀態(tài) Yt 僅僅依賴于前一個狀態(tài) Yt-1， 連續(xù)多個狀態(tài)構(gòu)成隱馬爾可夫鏈 y。有了隱馬爾可夫鏈，如何與觀測序列 x 建立聯(lián)系呢？

隱馬爾可夫模型做了第二個假設(shè): ② 任意時刻的觀測 x 只依賴于該時刻的狀態(tài) Yt，與其他時刻的狀態(tài)或觀測獨立無關(guān)。如果用箭頭表示事件的依賴關(guān)系(箭頭終點是結(jié)果，依賴于起點的因緣)，則隱馬爾可夫模型可以表示為下圖所示

image

狀態(tài)與觀測之間的依賴關(guān)系確定之后，隱馬爾可夫模型利用三個要素來模擬時序序列的發(fā)生過程----即初始狀態(tài)概率向量、狀態(tài)轉(zhuǎn)移概率矩陣和發(fā)射概率矩陣。

2. 初始狀態(tài)概率向量

   系統(tǒng)啟動時進(jìn)入的第一個狀態(tài) Y1 稱為初始狀態(tài)，假設(shè) y 有 N 種可能的取值，那么 Y1 就是一個獨立的離散型隨機(jī)變量，由 P(y1 | π) 描述。其中
   
   是概率分布的參數(shù)向量，稱為初始狀態(tài)概率向量。

   image

給定 π ，初始狀態(tài) Y1 的取值分布就確定了，比如采用{B,M,E,S}標(biāo)注集時概率如下：

那么此時隱馬爾可夫模型的初始狀態(tài)概率向量為 π=[0.7，0，0，0.3]，注意，句子第一個詞是單字的可能性要小一些。

3. 狀態(tài)轉(zhuǎn)移矩陣

   Yt 如何轉(zhuǎn)移到 Yt+1 呢？根據(jù)馬爾可夫假設(shè)，t+1 時的狀態(tài)僅僅取決于 t 時的狀態(tài)，既然一共有 N 種狀態(tài)，那么從狀態(tài) Si 到狀態(tài) Sj 的概率就構(gòu)成了一個 NN 的方陣，稱為狀態(tài)轉(zhuǎn)移矩陣 A：
   
   其中下標(biāo) i、j 分別表示狀態(tài)的第 i、j 種取值。狀態(tài)轉(zhuǎn)移概率的存在有其實際意義，在中文分詞中，標(biāo)簽 B 的后面不可能是 S，于是就有 P(Yt+1 = S | Yt = B) = 0。同樣，詞性標(biāo)注中的“形容詞->名詞”“副詞->動詞”也可通過狀態(tài)轉(zhuǎn)移概率來模擬，這些概率分布參數(shù)不需要手動設(shè)置，而是通過語料庫上的統(tǒng)計自動學(xué)習(xí)*。

4. 發(fā)射概率矩陣

   有了狀態(tài) Yt 之后，如何確定觀測 Xt 的概率分布呢？根據(jù)隱馬爾可夫假設(shè)②，當(dāng)前觀測 Xt 僅僅取決于當(dāng)前狀態(tài) Yt。也就是說，給定每種 y，x 都是一個獨立的離散型隨機(jī)變量，其參數(shù)對應(yīng)一個向量。 假設(shè)觀測 x 一共有 M 種可能的取值，則 x 的概率分布參數(shù)向量維度為 M。由于 y 共有 N 種，所以這些參數(shù)向量構(gòu)成了 NM 的矩陣，稱為發(fā)射概率矩陣B*。

   

   其中，第 i 行 j 列的元素下標(biāo) i 和 j 分別代表觀測和狀態(tài)的第 i 種和第 j 種取值。

5. 隱馬爾可夫模型的三個基本用法

   • 樣本生成問題：給定模型，如何有效計算產(chǎn)生觀測序列的概率？換言之，如何評估模型與觀測序列之間的匹配程度？

   • 序列預(yù)測問題：給定模型和觀測序列，如何找到與此觀測序列最匹配的狀態(tài)序列？換言之，如何根據(jù)觀測序列推斷出隱藏的模型狀態(tài)？

   • 模型訓(xùn)練問題：給定觀測序列，如何調(diào)整模型參數(shù)使得該序列出現(xiàn)的概率最大？換言之，如何訓(xùn)練模型使其能最好地描述觀測數(shù)據(jù)？

   前兩個問題是模式識別的問題：1) 根據(jù)隱馬爾科夫模型得到一個可觀察狀態(tài)序列的概率(評價)；2) 找到一個隱藏狀態(tài)的序列使得這個序列產(chǎn)生一個可觀察狀態(tài)序列的概率最大(解碼)。第三個問題就是根據(jù)一個可以觀察到的狀態(tài)序列集產(chǎn)生一個隱馬爾科夫模型（學(xué)習(xí)）。

4.3 隱馬爾可夫模型的訓(xùn)練

1. 案例假設(shè)和模型構(gòu)造

   設(shè)想如下案例:某醫(yī)院招標(biāo)開發(fā)“智能”醫(yī)療診斷系統(tǒng)，用來輔助感冒診斷。已知①來診者只有兩種狀態(tài):要么健康，要么發(fā)燒。②來診者不確定自己到底是哪種狀態(tài)，只能回答感覺頭暈、體寒或正常。醫(yī)院認(rèn)為，③感冒這種病，只跟病人前一天的狀態(tài)有關(guān)，并且，④當(dāng)天的病情決定當(dāng)天的身體感覺。有位來診者的病歷卡上完整地記錄了最近 T 天的身體感受(頭暈、體寒或正常)，請預(yù)測這 T 天的身體狀態(tài)(健康或發(fā)燒)。由于醫(yī)療數(shù)據(jù)屬于機(jī)密隱私，醫(yī)院無法提供訓(xùn)練數(shù)據(jù)，但根據(jù)醫(yī)生經(jīng)驗，感冒發(fā)病的規(guī)律如下圖所示(箭頭上的數(shù)值表示概率)：

   image

根據(jù)已知條件①②，病情狀態(tài)(健康、發(fā)燒)可作為隱馬爾可夫模型的隱狀態(tài)(上圖藍(lán)色狀態(tài))，而身體感受(頭暈、體寒或正常)可作為隱馬爾可夫模型的顯狀態(tài)(圖中白色狀態(tài))。條件③符合隱馬爾可夫模型假設(shè)一，條件④符 合隱馬爾可夫模型假設(shè)二。這個案例其實描述了一個隱馬爾可夫模型， 并且參數(shù)已經(jīng)給定。構(gòu)造模型代碼見：

import numpy as np
from pyhanlp import *
from jpype import JArray, JFloat, JInt

to_str = JClass('java.util.Arrays').toString

## 隱馬爾可夫模型描述
states = ('Healthy', 'Fever')
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
transition_probability = {
    'Healthy': {'Healthy': 0.7, 'Fever': 0.3},
    'Fever': {'Healthy': 0.4, 'Fever': 0.6},
}
emission_probability = {
    'Healthy': {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
    'Fever': {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
observations = ('normal', 'cold', 'dizzy')


def generate_index_map(lables):
    index_label = {}
    label_index = {}
    i = 0
    for l in lables:
        index_label[i] = l
        label_index[l] = i
        i += 1
    return label_index, index_label


states_label_index, states_index_label = generate_index_map(states)
observations_label_index, observations_index_label = generate_index_map(observations)



def convert_map_to_matrix(map, label_index1, label_index2):
    m = np.empty((len(label_index1), len(label_index2)), dtype=float)
    for line in map:
        for col in map[line]:
            m[label_index1[line]][label_index2[col]] = map[line][col]
    return JArray(JFloat, m.ndim)(m.tolist())

def convert_observations_to_index(observations, label_index):
    list = []
    for o in observations:
        list.append(label_index[o])
    return list

def convert_map_to_vector(map, label_index):
    v = np.empty(len(map), dtype=float)
    for e in map:
        v[label_index[e]] = map[e]
    return JArray(JFloat, v.ndim)(v.tolist())  # 將numpy數(shù)組轉(zhuǎn)為Java數(shù)組


## pi：初始狀態(tài)概率向量
## A：狀態(tài)轉(zhuǎn)移概率矩陣
## B：發(fā)射概率矩陣
A = convert_map_to_matrix(transition_probability, states_label_index, states_label_index)
B = convert_map_to_matrix(emission_probability, states_label_index, observations_label_index)
observations_index = convert_observations_to_index(observations, observations_label_index)
pi = convert_map_to_vector(start_probability, states_label_index)

FirstOrderHiddenMarkovModel = JClass('com.hankcs.hanlp.model.hmm.FirstOrderHiddenMarkovModel')
given_model = FirstOrderHiddenMarkovModel(pi, A, B)

2. 樣本生成算法

   它的生成過程就是沿著隱馬爾可夫鏈走 T 步：

   • 根據(jù)初始狀態(tài)概率向量采樣第一個時刻的狀態(tài) Y1 = Si，即 Y1 ~ π。
   • Yt 采樣結(jié)束得到 Si 后，根據(jù)狀態(tài)轉(zhuǎn)移概率矩s陣第 i 行的概率向量，采樣下一時刻的狀態(tài) Yt+1。
   • 對每個 Yt = Si，根據(jù)發(fā)射概率矩陣的第 i 行采樣 Xt。
   • 重復(fù)步驟 2 共計 T-1 次，重復(fù)步驟 3 共計 T 次，輸出序列 x 與 y。

   代碼如下(接上)，直接通過模型進(jìn)行生成：

   ## 第一個參數(shù)：序列最低長度
   ## 第二個參數(shù)：序列最高長度
   ## 第三個參數(shù)：需要生成的樣本數(shù)
   for O, S in given_model.generate(3, 5, 2):
       print(" ".join((observations_index_label[o] + '/' + states_index_label[s]) for o, s in zip(O, S)))
   

3. 隱馬爾可夫模型的訓(xùn)練

   樣本生成后，我們就可以利用生成的數(shù)據(jù)重新訓(xùn)練，通過極大似然法來估計隱馬爾可夫模型的參數(shù)。參數(shù)指的是三元組(π，A，B)。

   利用給定的隱馬爾可夫模型 P生成十萬個樣本，在這十萬個樣本上訓(xùn)練新模型Q，比較新舊模型參數(shù)是否一致。

   trained_model = FirstOrderHiddenMarkovModel()
   
   ## 第一個參數(shù)：序列最低長度
   ## 第二個參數(shù)：序列最高長度
   ## 第三個參數(shù)：需要生成的樣本數(shù)
   trained_model.train(given_model.generate(3, 10, 100000))
   print('新模型與舊模型是否相同：', trained_model.similar(given_model))
   

   輸出：

   新模型與舊模型是否相同： True
   

   運行后一般都成立，由于隨機(jī)數(shù)，僅有小概率發(fā)生失敗。

4.4 隱馬爾可夫模型的預(yù)測

隱馬爾可夫模型最具實際意義的問題當(dāng)屬序列標(biāo)注了：給定觀測序列，求解最可能的狀態(tài)序列及其概率。

1. 概率計算的前向算法

   給定觀測序列 x 和一個狀態(tài)序列 y，就可以估計兩者的聯(lián)合概率 P(x,y)，聯(lián)合概率就是一種結(jié)果的概率，在這些結(jié)果當(dāng)中找到最大的聯(lián)合概率就是找到最有可能的結(jié)果預(yù)測。聯(lián)合概率：P(x,y) = P(y) P(x|y)，下面我們來分別求出P(y)和P(x|y)

• 順著隱馬爾可夫鏈走，首先 t=1 時初始狀態(tài)沒有前驅(qū)狀態(tài)，發(fā)生概率由 π 決定：

  

• 接著對 t >= 2，狀態(tài) Yt 由前驅(qū)狀態(tài) Yt-1 轉(zhuǎn)移而來，轉(zhuǎn)移矩陣由矩陣 A 決定：

  

  所以狀態(tài)序列的概率為上面式子的乘積：

  

• P(y) 我們已經(jīng)求出來了，下面要求 P(x|y)

  對于每個 Yt = Si，都會“發(fā)射”一個 Xt = Oj，發(fā)射概率由矩陣 B 決定：

  

• 那么給定一個狀態(tài)序列 Y，對應(yīng)的 X 的概率累積形式：

  

• 最后帶入聯(lián)合概率公式得：
  

將其中的每個 Xt、Yt 對應(yīng)上實際發(fā)生序列的 Si、Oj，就能帶入(π,A,B)中的相應(yīng)元素，從而計算出任意序列的概率，最后找出這些概率的最大值就得到預(yù)測結(jié)果。找出概率最大值要用到維特比算法。

2. 搜索狀態(tài)序列的維特比算法

   理解了前向算法之后，找尋最大概率所對應(yīng)的狀態(tài)序列無非是一個搜索問題。具體說來，將每個狀態(tài)作為有向圖中的一個節(jié)點， 節(jié)點間的距離由轉(zhuǎn)移概率決定，節(jié)點本身的花費由發(fā)射概率決定。那么所有備選狀態(tài)構(gòu)成一幅有 向無環(huán)圖，待求的概率最大的狀態(tài)序列就是圖中的最長路徑，此時的搜索算法稱為維特比算法，如圖下圖所示：

   image

上圖從左往右時序遞增，虛線由初始狀態(tài)概率決定，實線則是轉(zhuǎn)移概率。由于受到觀測序列的約束，不同狀態(tài)發(fā)射觀測的概率不同，所以每個節(jié)點本身也必須計算自己的花費，由發(fā)射概率決定。又由于 Yt+1 僅依賴于 Yt，所以網(wǎng)狀圖可以動態(tài)規(guī)劃的搜索，也就是維特比算法：

• 初始化，t=1 時初始最優(yōu)路徑的備選由 N 個狀態(tài)組成，它們的前驅(qū)為空。
  
  其中，δ 存儲在時刻 t 以 Si 結(jié)尾的所有局部路徑的最大概率。ψ 存儲局部最優(yōu)路徑末狀態(tài) Yt 的前驅(qū)狀態(tài)。

• 遞推，t >= 2 時每條備選路徑像貪吃蛇一樣吃入一個新狀態(tài)，長度增加一個單位，根據(jù)轉(zhuǎn)移概率和發(fā)射概率計算花費。找出新的局部最優(yōu)路徑，更新 δ、ψ 兩個數(shù)組。
  

• 終止，找出最終時刻 δt,i 數(shù)組中的最大概率 P*，以及相應(yīng)的結(jié)尾狀態(tài)下標(biāo) i*t。
  

• 回溯，根據(jù)前驅(qū)數(shù)組 ψ 回溯前驅(qū)狀態(tài)，取得最優(yōu)路徑狀態(tài)下標(biāo)。
  

預(yù)測代碼如下(接上面代碼)：

pred = JArray(JInt, 1)([0, 0, 0])
prob = given_model.predict(observations_index, pred)
print(" ".join((observations_index_label[o] + '/' + states_index_label[s]) for o, s in
               zip(observations_index, pred)) + " {:.3f}".format(np.math.exp(prob)))

輸出為：

normal/Healthy cold/Healthy dizzy/Fever 0.015

觀察該結(jié)果，“/”隔開觀測和狀態(tài)，最后的 0.015 是序列的聯(lián)合概率。

4.5 隱馬爾可夫模型應(yīng)用于中文分詞

HanLP 已經(jīng)實現(xiàn)了基于隱馬爾可夫模型的中文分詞器 HMMSegmenter，并且實現(xiàn)了訓(xùn)練接口。代碼詳見：

hmm_cws.py：https://github.com/NLP-LOVE/Introduction-NLP/tree/master/code/ch04/hmm_cws.py

4.6 性能評測

如果隱馬爾可夫模型中每個狀態(tài)僅依賴于前一個狀態(tài)， 則稱為一階；如果依賴于前兩個狀態(tài)，則稱為二階。既然一階隱馬爾可夫模型過于簡單，是否可以切換到二階來提高分?jǐn)?shù)呢？

答案是可以的，跟一階類似，這里不再詳細(xì)介紹二階隱馬爾可夫模型，詳細(xì)請看原書。

這里我們使用 MSR語料庫進(jìn)行評測，結(jié)果如下表所示：

可以看到，二階隱馬爾可夫模型的 Roov 有少許提升，但綜合 F1 反而下降了。這說明增加隱馬爾可夫模型的階數(shù)并不能提高分詞器的準(zhǔn)確率，單靠提高轉(zhuǎn)移概率矩陣的復(fù)雜度并不能提高模型的擬合能力，我們需要從別的方面想辦法。目前市面上一些開源分詞器仍然停留在一階隱馬爾可夫模型的水平，比如著名的結(jié)巴分詞，它們的準(zhǔn)確率也只能達(dá)到80%左右。

4.7 總結(jié)

這一章我們想解決的問題是新詞識別，為此從詞語級模型切換到字符級模型，將中文分詞任務(wù)轉(zhuǎn)換為序列標(biāo)注問題。作為新手起步，我們嘗試了最簡單的序列標(biāo)注模型----隱馬爾可夫模型。隱馬爾可夫模型的基本問題有三個：樣本生成、參數(shù)估計、序列預(yù)測。

然而隱馬爾可夫模型用于中文分詞的效果并不理想，雖然召回了一半的 OOV，但綜合 F1 甚至低于詞典分詞。哪怕升級到二階隱馬爾可夫模型， F1 值依然沒有提升。 看來樸素的隱馬爾可夫模型不適合中文分詞，我們需要更高級的模型。

話說回來，隱馬爾可夫模型作為入門模型，比較容易上手，同時也是許多高級模型的基礎(chǔ)。打好基礎(chǔ)，我們才能挑戰(zhàn)高級模型。

4.8 GitHub項目

HanLP何晗--《自然語言處理入門》筆記：

https://github.com/NLP-LOVE/Introduction-NLP

項目持續(xù)更新中......

目錄