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

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

簡介

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

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

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

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

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

樸素貝葉斯分類器

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

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

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

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

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

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

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

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

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

訓練

樸素貝葉斯的訓練主要由計算特征和類別的頻率而實現(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)生一個關于訓練樣本中所有類別特征的大型同現(xiàn)矩陣。

分類

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

上式可以分解為：

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

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

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

該模型包括兩個方面：

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

更常見的形式是：

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

隱馬爾科夫模型

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

和狀態(tài)和觀察結果相關的概率：

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

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

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

現(xiàn)在我們可以定義兩個用?HMM?可以解決的問題。

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

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

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

過程為：計算每個事件在語料庫中出現(xiàn)的次數(shù)，然后將次數(shù)歸一化以形成適當?shù)母怕史植?。我們需要對每個事件在語料庫中出現(xiàn)的次數(shù)計算?4?次：

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

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

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

拉普拉斯平滑

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

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

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

解碼：為觀察序列尋找隱藏狀態(tài)序列

給定一個已訓練的?HNN，即轉移矩陣?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ī)劃解隱馬爾科夫模型的預測問題，即用動態(tài)規(guī)劃求概率最大的路徑，在?HMM?中，這些路徑對應著一個狀態(tài)序列。根據(jù)動態(tài)規(guī)劃的原理，如果最優(yōu)狀態(tài)序列在時刻?i?通過結點?t_i，那么這一狀態(tài)序列從結點?t_i?到終點?t?的部分狀態(tài)序列，對于從?t_i?到?t?所有可能的部分狀態(tài)序列來說，必須是最優(yōu)的。因為如果不是最優(yōu)的，那么我們就能從?t_i?到?t?尋找一個更好的狀態(tài)序列以加大獲得觀察序列的概率。

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

如下計算每一個狀態(tài)最可能的前面狀態(tài)：

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

HMM?的?trellis?表示。

發(fā)射概率矩陣和狀態(tài)遷移概率矩陣。

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

將數(shù)據(jù)填入?trellis?表示中。

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

HMM?的重要觀察結果

軟件包

生成海報

免責聲明：本網(wǎng)站內容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準確性及可靠性，但不保證有關資料的準確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負責。本網(wǎng)站對有關資料所引致的錯誤、不確或遺漏，概不負任何法律責任。任何單位或個人認為本網(wǎng)站中的網(wǎng)頁或鏈接內容可能涉嫌侵犯其知識產(chǎn)權或存在不實內容時，應及時向本網(wǎng)站提出書面權利通知或不實情況說明，并提供身份證明、權屬證明及詳細侵權或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關文章源頭核實，溝通刪除相關內容或斷開相關鏈接。