?詳解隱馬爾科夫模型?

作者：David S. Batista

選自：機器之心

本文首先簡要介紹樸素貝葉斯，再將其擴展到隱馬爾科夫模型。我們不僅會討論隱馬爾科夫模型的基本原理，同時還從樸素貝葉斯的角度討論它們間的關系與局限性。

隱馬爾科夫模型是用于標注問題的統計機器學習模型，是一種生成模型。隱馬爾科夫模型是關于時序的概率模型，它描述了由一個隱藏的馬爾科夫鏈隨機生成不可觀測的狀態隨機序列，再由各個狀態生成一個觀測而產生觀測隨機序列的過程。本文將重點介紹這種經典的機器學習模型。

簡介

機器學習一個經典的問題就是學習一個能區分兩個或多個類別的分類器，即在給定訓練樣本下能預測新樣本所屬的類別。機器學習分類器經常用于處理?NLP?任務，例如將郵件根據內容分類為垃圾郵件或正常郵件，將新聞按內容分為不同的主題等。但除了這種分類任務，NLP?還有很多都涉及到另一種與結構有關的預測，這種結構化預測一般可用概率圖表示。

NLP?中一個經典的案例就是詞性標注問題。在該任務中，x_i?表示一個個的單詞，y_i?表示對應?x_i?的詞性（如名詞、動詞和形容詞等）。對于這種任務來說，輸入的和輸出都是一個序列，即給定一個單詞序列，模型的輸出為對應單詞的標注序列，這種序列是與對應位置和上下文相關，所以是一種與結構相關的預測。

在這種序列預測問題中，數據由（x,?y）的序列組成，即一個樣本可描述為（x_1,?x_2,...,x_m，y_1,?y_2,?...,?y_m）。我們要學習的是在給定一個?x?的序列下，各種?y?序列的概率是多少，即：

在大多數問題中，這些序列具有順序相關性。即?x?近鄰的值與?y?近鄰的值具有相關性，或者也可以說?x_i?的近鄰決定了?y_i?的屬性。例如在英語中，介詞?to（x_i）后面所帶的單詞常常是動詞（y_i）。當然在機器學習中還有其它的任務涉及序列數據，例如在時序建模中，我們需要使用所有前面的觀測值?y?在?t+1?步時預測新的?y。在序列監督學習中，我們必須序列地預測所有?y?值。

隱馬爾科夫模型（HMM）是第一個針對序列分類所提出的算法。當然還有其它很多的序列模型，不過本文會從樸素貝葉斯模型開始逐步擴展到?HMM。

樸素貝葉斯分類器

樸素貝葉斯（分類器）是一種生成模型，它會基于訓練樣本對每個可能的類別建模。在預測中，樸素貝葉斯分類器在給定一個觀察樣本下，它會計算所有可能類別的概率并返回最可能由觀察樣本生成的類別。也就是說，樸素貝葉斯分類器會預測新樣本最可能生成的類別是什么。相比之下，如?Logistic?回歸那樣的判別模型會嘗試學習訓練樣本中的哪些特征最可能對區分類別起作用。

樸素貝葉斯模型在給定特征下最大化后驗概率而返回最可能的類別：

其中?y?為類別，x?arrow?為一個觀察樣本的特征向量。

NB?分類器是基于貝葉斯定理的，若我們將貝葉斯定理代入到上式，那么條件概率可以寫為：

在訓練中，對于一個給定的觀察樣本，我們可以用上式計算給定觀察樣本下是某個類別的概率，這樣迭代地可以計算所有類別的概率。又因為分母對所有項都是相同的，且不影響最大化概率的結果，上式可以簡寫為以下：

如果我們將向量按分量分解出來，那么原式可以寫為：

這個式子非常難以計算，因為它涉及到估計所有特征可能的組合。因此，我們可以根據樸素貝葉斯假設放寬各特征的條件。樸素貝葉斯定理假設：「給定一個類別，每一個特征都與其它特征條件獨立」。該假設可以表示為?p(x_i?|?y,?x_j)=p(x_i?|?y)，其中?i?不等于?j。在給定類別?y?的條件下，概率?p(x_i∣y)?是相互獨立的，因此也就能如下簡單地乘積表示聯合分布：?

將上式帶入后驗概率可得：

上式就是我們最終得到的樸素貝葉斯模型，我們根據樸素貝葉斯假設大大地簡化了計算。

訓練

樸素貝葉斯的訓練主要由計算特征和類別的頻率而實現。以下描述的過程需要對每一個類別?y_i?都執行一次計算。為了計算先驗概率，我們簡單地通過計算所有樣本中類別?y_i?占的比率而估計類別出現的概率：

為了計算似然度估計，我們需要計算?x_i?和?y_i?一同出現的次數占?y_i?所出現次數的比率，來估計在?y_i?出現的情況下，x_i?出現的概率：

該計算式將產生一個關于訓練樣本中所有類別特征的大型同現矩陣。

分類

當我們給一個新的樣本進行分類，假設該樣本的特征為?x_1、w_3、w_5。那么對于每一個類別?y_i，我們需要計算：

上式可以分解為：

該式需要對每一個類別?y_i?都執行一次計算，因此我們可以選出在這些特征出現的情況下，最可能出現的類別是什么。

從樸素貝葉斯到隱馬爾科夫模型

前面展示的模型預測了在給定觀察樣本下最可能出現的類別。要想預測觀察序列?x=(x_1,?…,?x_n)?對應的類別序列?y=(y_1,?…,?y_n)，可以使用多個樸素貝葉斯模型的累乘而構建一個序列模型：

該模型包括兩個方面：

• 每個序列位置只有一個特征，即假設每個特征都以類?y_i?為基礎獨立生成時每個觀察結果對應的特征。
  

• 該模型不捕捉可觀察變量?x_i?之間的互動。
  

但是，假設在連續序列位置?y_i?上存在依賴項是合理的，還記得上文中關于詞性標注的示例嗎？這就是一階馬爾科夫模型，其引入了馬爾科夫假設：「特定狀態的概率僅依賴于前一個狀態」。

更常見的形式是：

其中?Y?代表所有可能的標簽序列?y?arrow?的集合。

隱馬爾科夫模型

隱馬爾科夫模型（HMM）是一個序列分類器。和其他的機器學習算法一樣，它可以被訓練，即給定觀察結果的標注序列，然后使用學得的參數給觀察結果序列分配標簽。我們可以把?HMM?框架定義為包含以下組件：

• 狀態（如標簽）：T=t_1,?t_2,?…,?t_N
  

• 觀察結果（如單詞）：W=w_1,?w_2,?…,?w_N
  

• 兩個特殊狀態：t_start?和?t_end，這兩個狀態與觀察結果無關
  

和狀態和觀察結果相關的概率：

• 初始概率：狀態的初始概率分布
  

• 最終概率：狀態的最終概率分布
  

• 轉移概率：從一個狀態到另一個狀態的概率矩陣?A
  

• 發射概率（emission?probability）：從一個狀態生成的觀察結果的概率矩陣?B
  

一階隱馬爾科夫模型具備以下假設：

• 馬爾科夫假設：特定狀態的概率僅依賴于前一個狀態。形式：P(t_i∣t_1,?…,?t_i?1)=P(t_i∣t_i?1)
  

• 輸出的獨立性：輸出觀察結果?wi?的概率僅依賴于輸出觀察結果?ti?的狀態，而不是其他狀態或觀察結果。形式：P(w_i∣t_1…q_i,?…,?q_T,?o_1,?…,?o_i,?…,?o_T)=P(o_i∣q_i)
  

注意：輸出假設和前述樸素貝葉斯分類器緊密相關。下圖便于理解該假設與樸素貝葉斯分類器之間的依賴性和關系：

HMM?中的轉移概率和發射概率。（圖源：維吉尼亞大學?CS6501?課程）

現在我們可以定義兩個用?HMM?可以解決的問題。

• 學習和給定觀察序列相關的參數，即訓練。例如，給定一個句子中的單詞和相關的詞性標注，模型可以學到其潛在結構（latent?structure）。
  

• 將訓練后的?HMM?用于觀察結果序列。例如，給定一個句子，使用?HMM?根據訓練數據學得的潛在結構預測每個單詞的詞性。
  

學習：估計轉移矩陣和發射矩陣（emission?matrices）

給定一個觀察結果序列?W?和相關狀態?T，我們如何學習?HMM?參數，即矩陣?A?和?B？

在?HHM?監督場景下，可以使用最大似然估計原則來計算矩陣，從而完成參數學習。

過程為：計算每個事件在語料庫中出現的次數，然后將次數歸一化以形成適當的概率分布。我們需要對每個事件在語料庫中出現的次數計算?4?次：

其中，M?代表訓練樣本的個數，N?代表序列長度，1?代表當特定事件發生時指示函數的值為?1，0?代表特定事件未發生。該公式概覽了訓練數據庫，計算每個事件出現的頻率。

然后將全部?4?次計算歸一化，以得出正確的概率分布：

這些公式將輸出轉移概率矩陣?A?和發射概率矩陣?B。

拉普拉斯平滑

訓練過程中，該模型如何處理未見過的單詞？

當未見過的單詞/觀察結果出現了，P(W_i∣T_i)=0，且預測過程中將會作出錯誤的序列決策。

有一種技術可以處理這種情況，即拉普拉斯平滑（Laplace?smoothing）：每個狀態總有一個小發射概率要輸出未見單詞（可標注為?UNK）。每次?HMM?遇到未知單詞，該模型將使用?P(UNK∣T_i)?的值作為發射概率。

解碼：為觀察序列尋找隱藏狀態序列

給定一個已訓練的?HNN，即轉移矩陣?A?和?B?以及一個新的觀察序列?W=w_1,w_2,…,w_N，我們希望找到最佳的狀態序列?T=t_1,t_2,…,t_N?以解釋該觀察序列。

這一過程可以通過使用維特比算法（Viterbi?algorithm）實現，該算法試圖找到總體上最佳的狀態序列?T=t_1,t_2,…,t_N。一般來說我們還可以使用另外一種后驗解碼的算法，該算法獨立地為序列中每個位置?i?選擇后驗概率最高的狀態。

維特比算法

維特比算法實際是用動態規劃解隱馬爾科夫模型的預測問題，即用動態規劃求概率最大的路徑，在?HMM?中，這些路徑對應著一個狀態序列。根據動態規劃的原理，如果最優狀態序列在時刻?i?通過結點?t_i，那么這一狀態序列從結點?t_i?到終點?t?的部分狀態序列，對于從?t_i?到?t?所有可能的部分狀態序列來說，必須是最優的。因為如果不是最優的，那么我們就能從?t_i?到?t?尋找一個更好的狀態序列以加大獲得觀察序列的概率。

定義在時刻?i?狀態為?t?的所有單個路徑中概率最大值為?δ，維特比算法可以通過使用馬爾科夫假設和如下定義的兩個函數計算上式單個路徑的最大值。

如下計算每一個狀態最可能的前面狀態：

維特比算法使用使用一個被稱之為?trellis?的?HMM?表征，它折疊了每一個位置的所有可能狀態，并作出了非常明確的獨立性假設：每一個位置僅依賴于前一個位置。

HMM?的?trellis?表示。

發射概率矩陣和狀態遷移概率矩陣。

通過使用維特比算法，轉移概率矩陣，我們可以將數據填充到?trellis?圖表中，并快速高效地找到維特比路徑。

將數據填入?trellis?表示中。

上圖是?Roger?Levy?展示的維特比算法，完全的案例可參考：http://www.davidsbatista.net/assets/documents/posts/2017-11-12-hmm_viterbi_mini_example.pdf。

HMM?的重要觀察結果

• 本文的主要思想是看到樸素貝葉斯分類器和序列分類器?HMM?的聯系。
  

• 如果我們使?HMM?的隱藏狀態固定，則它就是樸素貝葉斯模型。
  

• 序列中每個單詞／觀察結果只有一個特征，即每個觀察結果的值。
  

• 每個狀態僅依賴于前一個狀態，即每個狀態?t_i?都獨立于前面所有狀態?t_1,?t_2,?…,?t_i?2，除了緊挨著的前一個狀態?t_i-1。
  

• 每一個觀察結果變量?w_i?僅依賴于當前狀態?t_i。
  

軟件包

• seqlearn：適合?Python?的序列分類庫，包括隱馬爾科夫模型實現，它使用?sklearn?API。
  

• NLTK?HMM：NLTK?也包括一個可以實現隱馬爾科夫模型框架的模塊。
  

• lxmls-toolkit：在里斯本機器學習夏季課程中使用的自然語言處理工具包，也包括隱馬爾科夫模型實現。

---

算法數學之美微信公眾號歡迎賜稿

稿件涉及數學、物理、算法、計算機、編程等相關領域。

稿件一經采用，我們將奉上稿酬。

投稿郵箱：math_alg@163.com。

總結

以上是生活随笔為你收集整理的【深度】从朴素贝叶斯到维特比算法：详解隐马尔科夫模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。