本文首先簡要介紹樸素貝葉斯，再將其擴展到隱馬爾科夫模型。我們不僅會討論隱馬爾科夫模型的基本原理，同時還從樸素貝葉斯的角度討論它們間的關(guān)系與局限性。
隱馬爾科夫模型是用于標(biāo)注問題的統(tǒng)計機器學(xué)習(xí)模型，是一種生成模型。隱馬爾科夫模型是關(guān)于時序的概率模型，它描述了由一個隱藏的馬爾科夫鏈隨機生成不可觀測的狀態(tài)隨機序列，再由各個狀態(tài)生成一個觀測而產(chǎn)生觀測隨機序列的過程。本文將重點介紹這種經(jīng)典的機器學(xué)習(xí)模型。
簡介
機器學(xué)習(xí)一個經(jīng)典的問題就是學(xué)習(xí)一個能區(qū)分兩個或多個類別的分類器，即在給定訓(xùn)練樣本下能預(yù)測新樣本所屬的類別。機器學(xué)習(xí)分類器經(jīng)常用于處理 NLP 任務(wù)，例如將郵件根據(jù)內(nèi)容分類為垃圾郵件或正常郵件，將新聞按內(nèi)容分為不同的主題等。但除了這種分類任務(wù)，NLP 還有很多都涉及到另一種與結(jié)構(gòu)有關(guān)的預(yù)測，這種結(jié)構(gòu)化預(yù)測一般可用概率圖表示。
NLP 中一個經(jīng)典的案例就是詞性標(biāo)注問題。在該任務(wù)中，x_i 表示一個個的單詞，y_i 表示對應(yīng) x_i 的詞性（如名詞、動詞和形容詞等）。對于這種任務(wù)來說，輸入的和輸出都是一個序列，即給定一個單詞序列，模型的輸出為對應(yīng)單詞的標(biāo)注序列，這種序列是與對應(yīng)位置和上下文相關(guān)，所以是一種與結(jié)構(gòu)相關(guān)的預(yù)測。
在這種序列預(yù)測問題中，數(shù)據(jù)由（x, y）的序列組成，即一個樣本可描述為（x_1, x_2,...,x_m，y_1, y_2, ..., y_m）。我們要學(xué)習(xí)的是在給定一個 x 的序列下，各種 y 序列的概率是多少，即：
在大多數(shù)問題中，這些序列具有順序相關(guān)性。即 x 近鄰的值與 y 近鄰的值具有相關(guān)性，或者也可以說 x_i 的近鄰決定了 y_i 的屬性。例如在英語中，介詞 to（x_i）后面所帶的單詞常常是動詞（y_i）。當(dāng)然在機器學(xué)習(xí)中還有其它的任務(wù)涉及序列數(shù)據(jù)，例如在時序建模中，我們需要使用所有前面的觀測值 y 在 t+1 步時預(yù)測新的 y。在序列監(jiān)督學(xué)習(xí)中，我們必須序列地預(yù)測所有 y 值。
隱馬爾科夫模型（HMM）是第一個針對序列分類所提出的算法。當(dāng)然還有其它很多的序列模型，不過本文會從樸素貝葉斯模型開始逐步擴展到 HMM。
樸素貝葉斯分類器
樸素貝葉斯（分類器）是一種生成模型，它會基于訓(xùn)練樣本對每個可能的類別建模。在預(yù)測中，樸素貝葉斯分類器在給定一個觀察樣本下，它會計算所有可能類別的概率并返回最可能由觀察樣本生成的類別。也就是說，樸素貝葉斯分類器會預(yù)測新樣本最可能生成的類別是什么。相比之下，如 Logistic 回歸那樣的判別模型會嘗試學(xué)習(xí)訓(xùn)練樣本中的哪些特征最可能對區(qū)分類別起作用。
樸素貝葉斯模型在給定特征下最大化后驗概率而返回最可能的類別：
其中 y 為類別，x arrow 為一個觀察樣本的特征向量。
NB 分類器是基于貝葉斯定理的，若我們將貝葉斯定理代入到上式，那么條件概率可以寫為：
在訓(xùn)練中，對于一個給定的觀察樣本，我們可以用上式計算給定觀察樣本下是某個類別的概率，這樣迭代地可以計算所有類別的概率。又因為分母對所有項都是相同的，且不影響最大化概率的結(jié)果，上式可以簡寫為以下：
如果我們將向量按分量分解出來，那么原式可以寫為：
這個式子非常難以計算，因為它涉及到估計所有特征可能的組合。因此，我們可以根據(jù)樸素貝葉斯假設(shè)放寬各特征的條件。樸素貝葉斯定理假設(shè)：「給定一個類別，每一個特征都與其它特征條件獨立」。該假設(shè)可以表示為 p(x_i | y, x_j)=p(x_i | y)，其中 i 不等于 j。在給定類別 y 的條件下，概率 p(x_i∣y) 是相互獨立的，因此也就能如下簡單地乘積表示聯(lián)合分布：
將上式帶入后驗概率可得：
上式就是我們最終得到的樸素貝葉斯模型，我們根據(jù)樸素貝葉斯假設(shè)大大地簡化了計算。
訓(xùn)練
樸素貝葉斯的訓(xùn)練主要由計算特征和類別的頻率而實現(xiàn)。以下描述的過程需要對每一個類別 y_i 都執(zhí)行一次計算。為了計算先驗概率，我們簡單地通過計算所有樣本中類別 y_i 占的比率而估計類別出現(xiàn)的概率：
為了計算似然度估計，我們需要計算 x_i 和 y_i 一同出現(xiàn)的次數(shù)占 y_i 所出現(xiàn)次數(shù)的比率，來估計在 y_i 出現(xiàn)的情況下，x_i 出現(xiàn)的概率：
該計算式將產(chǎn)生一個關(guān)于訓(xùn)練樣本中所有類別特征的大型同現(xiàn)矩陣。
分類
當(dāng)我們給一個新的樣本進行分類，假設(shè)該樣本的特征為 x_1、w_3、w_5。那么對于每一個類別 y_i，我們需要計算：
上式可以分解為：
該式需要對每一個類別 y_i 都執(zhí)行一次計算，因此我們可以選出在這些特征出現(xiàn)的情況下，最可能出現(xiàn)的類別是什么。
從樸素貝葉斯到隱馬爾科夫模型
前面展示的模型預(yù)測了在給定觀察樣本下最可能出現(xiàn)的類別。要想預(yù)測觀察序列 x=(x_1, …, x_n) 對應(yīng)的類別序列 y=(y_1, …, y_n)，可以使用多個樸素貝葉斯模型的累乘而構(gòu)建一個序列模型：
該模型包括兩個方面：
每個序列位置只有一個特征，即假設(shè)每個特征都以類 y_i 為基礎(chǔ)獨立生成時每個觀察結(jié)果對應(yīng)的特征。
該模型不捕捉可觀察變量 x_i 之間的互動。
但是，假設(shè)在連續(xù)序列位置 y_i 上存在依賴項是合理的，還記得上文中關(guān)于詞性標(biāo)注的示例嗎？這就是一階馬爾科夫模型，其引入了馬爾科夫假設(shè)：「特定狀態(tài)的概率僅依賴于前一個狀態(tài)」。
更常見的形式是：
其中 Y 代表所有可能的標(biāo)簽序列 y arrow 的集合。
隱馬爾科夫模型
隱馬爾科夫模型（HMM）是一個序列分類器。和其他的機器學(xué)習(xí)算法一樣，它可以被訓(xùn)練，即給定觀察結(jié)果的標(biāo)注序列，然后使用學(xué)得的參數(shù)給觀察結(jié)果序列分配標(biāo)簽。我們可以把 HMM 框架定義為包含以下組件：
狀態(tài)（如標(biāo)簽）：T=t_1, t_2, …, t_N
觀察結(jié)果（如單詞）：W=w_1, w_2, …, w_N
兩個特殊狀態(tài)：t_start 和 t_end，這兩個狀態(tài)與觀察結(jié)果無關(guān)
和狀態(tài)和觀察結(jié)果相關(guān)的概率：
初始概率：狀態(tài)的初始概率分布
最終概率：狀態(tài)的最終概率分布
轉(zhuǎn)移概率：從一個狀態(tài)到另一個狀態(tài)的概率矩陣 A
發(fā)射概率（emission probability）：從一個狀態(tài)生成的觀察結(jié)果的概率矩陣 B
一階隱馬爾科夫模型具備以下假設(shè)：
馬爾科夫假設(shè)：特定狀態(tài)的概率僅依賴于前一個狀態(tài)。形式：P(t_i∣t_1, …, t_i?1)=P(t_i∣t_i?1)
輸出的獨立性：輸出觀察結(jié)果 wi 的概率僅依賴于輸出觀察結(jié)果 ti 的狀態(tài)，而不是其他狀態(tài)或觀察結(jié)果。形式：P(w_i∣t_1…q_i, …, q_T, o_1, …, o_i, …, o_T)=P(o_i∣q_i)
注意：輸出假設(shè)和前述樸素貝葉斯分類器緊密相關(guān)。下圖便于理解該假設(shè)與樸素貝葉斯分類器之間的依賴性和關(guān)系：
HMM 中的轉(zhuǎn)移概率和發(fā)射概率。（圖源：維吉尼亞大學(xué) CS6501 課程）
現(xiàn)在我們可以定義兩個用 HMM 可以解決的問題。
學(xué)習(xí)和給定觀察序列相關(guān)的參數(shù)，即訓(xùn)練。例如，給定一個句子中的單詞和相關(guān)的詞性標(biāo)注，模型可以學(xué)到其潛在結(jié)構(gòu)（latent structure）。
將訓(xùn)練后的 HMM 用于觀察結(jié)果序列。例如，給定一個句子，使用 HMM 根據(jù)訓(xùn)練數(shù)據(jù)學(xué)得的潛在結(jié)構(gòu)預(yù)測每個單詞的詞性。
學(xué)習(xí)：估計轉(zhuǎn)移矩陣和發(fā)射矩陣（emission matrices）
給定一個觀察結(jié)果序列 W 和相關(guān)狀態(tài) T，我們?nèi)绾螌W(xué)習(xí) HMM 參數(shù)，即矩陣 A 和 B？
在 HHM 監(jiān)督場景下，可以使用最大似然估計原則來計算矩陣，從而完成參數(shù)學(xué)習(xí)。
過程為：計算每個事件在語料庫中出現(xiàn)的次數(shù)，然后將次數(shù)歸一化以形成適當(dāng)?shù)母怕史植?。我們需要對每個事件在語料庫中出現(xiàn)的次數(shù)計算 4 次：
其中，M 代表訓(xùn)練樣本的個數(shù)，N 代表序列長度，1 代表當(dāng)特定事件發(fā)生時指示函數(shù)的值為 1，0 代表特定事件未發(fā)生。該公式概覽了訓(xùn)練數(shù)據(jù)庫，計算每個事件出現(xiàn)的頻率。
然后將全部 4 次計算歸一化，以得出正確的概率分布：
這些公式將輸出轉(zhuǎn)移概率矩陣 A 和發(fā)射概率矩陣 B。
拉普拉斯平滑
訓(xùn)練過程中，該模型如何處理未見過的單詞？
當(dāng)未見過的單詞/觀察結(jié)果出現(xiàn)了，P(W_i∣T_i)=0，且預(yù)測過程中將會作出錯誤的序列決策。
有一種技術(shù)可以處理這種情況，即拉普拉斯平滑（Laplace smoothing）：每個狀態(tài)總有一個小發(fā)射概率要輸出未見單詞（可標(biāo)注為 UNK）。每次 HMM 遇到未知單詞，該模型將使用 P(UNK∣T_i) 的值作為發(fā)射概率。
解碼：為觀察序列尋找隱藏狀態(tài)序列
給定一個已訓(xùn)練的 HNN，即轉(zhuǎn)移矩陣 A 和 B 以及一個新的觀察序列 W=w_1,w_2,…,w_N，我們希望找到最佳的狀態(tài)序列 T=t_1,t_2,…,t_N 以解釋該觀察序列。
這一過程可以通過使用維特比算法（Viterbi algorithm）實現(xiàn)，該算法試圖找到總體上最佳的狀態(tài)序列 T=t_1,t_2,…,t_N。一般來說我們還可以使用另外一種后驗解碼的算法，該算法獨立地為序列中每個位置 i 選擇后驗概率最高的狀態(tài)。
維特比算法
維特比算法實際是用動態(tài)規(guī)劃解隱馬爾科夫模型的預(yù)測問題，即用動態(tài)規(guī)劃求概率最大的路徑，在 HMM 中，這些路徑對應(yīng)著一個狀態(tài)序列。根據(jù)動態(tài)規(guī)劃的原理，如果最優(yōu)狀態(tài)序列在時刻 i 通過結(jié)點 t_i，那么這一狀態(tài)序列從結(jié)點 t_i 到終點 t 的部分狀態(tài)序列，對于從 t_i 到 t 所有可能的部分狀態(tài)序列來說，必須是最優(yōu)的。因為如果不是最優(yōu)的，那么我們就能從 t_i 到 t 尋找一個更好的狀態(tài)序列以加大獲得觀察序列的概率。
定義在時刻 i 狀態(tài)為 t 的所有單個路徑中概率最大值為 δ，維特比算法可以通過使用馬爾科夫假設(shè)和如下定義的兩個函數(shù)計算上式單個路徑的最大值。
如下計算每一個狀態(tài)最可能的前面狀態(tài)：
維特比算法使用使用一個被稱之為 trellis 的 HMM 表征，它折疊了每一個位置的所有可能狀態(tài)，并作出了非常明確的獨立性假設(shè)：每一個位置僅依賴于前一個位置。
HMM 的 trellis 表示。
發(fā)射概率矩陣和狀態(tài)遷移概率矩陣。
通過使用維特比算法，轉(zhuǎn)移概率矩陣，我們可以將數(shù)據(jù)填充到 trellis 圖表中，并快速高效地找到維特比路徑。
將數(shù)據(jù)填入 trellis 表示中。
上圖是 Roger Levy 展示的維特比算法，完全的案例可參考：http://www.davidsbatista.net/assets/documents/posts/2017-11-12-hmm_viterbi_mini_example.pdf。
HMM 的重要觀察結(jié)果
本文的主要思想是看到樸素貝葉斯分類器和序列分類器 HMM 的聯(lián)系。
如果我們使 HMM 的隱藏狀態(tài)固定，則它就是樸素貝葉斯模型。
序列中每個單詞／觀察結(jié)果只有一個特征，即每個觀察結(jié)果的值。
每個狀態(tài)僅依賴于前一個狀態(tài)，即每個狀態(tài) t_i 都獨立于前面所有狀態(tài) t_1, t_2, …, t_i?2，除了緊挨著的前一個狀態(tài) t_i-1。
每一個觀察結(jié)果變量 w_i 僅依賴于當(dāng)前狀態(tài) t_i。
軟件包
seqlearn：適合 Python 的序列分類庫，包括隱馬爾科夫模型實現(xiàn)，它使用 sklearn API。
NLTK HMM：NLTK 也包括一個可以實現(xiàn)隱馬爾科夫模型框架的模塊。
lxmls-toolkit：在里斯本機器學(xué)習(xí)夏季課程中使用的自然語言處理工具包，也包括隱馬爾科夫模型實現(xiàn)。
聯(lián)系客服
