隱馬爾科夫模型演算法

㈠ 隱式馬爾科夫模型 及 Python + HMMlearn的使用

hmmlearn

隱式馬爾科夫模型Hidden Markov Models(HMMs) 是一種通用的概率模型。一個可觀測的變數X的序列被一個內部的隱藏狀態Z所生成。其中，隱藏狀態Z無法被直接觀測。在隱藏狀態之間的轉移被假設是通過 馬爾科夫鏈(Markov chain) 的形式。
模型可以表示為 起始概率向量 和轉移概率矩陣 . 一個觀測量生成的概率可以是關於 的任意分布， 基於當前的隱藏狀態。

HMMs的3個基本問題:

hmmlearn 是Python支持HMMs的包。原來是sklearn的一部分，後來由於介面不一致分成單獨的包了。不過使用起來和sklearn的其他模型類似。

構造HMM model:

初始化的參數主要有 n_components , covariance_type , n_iter 。每個參數的作用我還沒有研究。

通過 fit 方法。
輸入是一個矩陣，包含拼接的觀察序列concatenated sequences of observation (也就是samples)，和序列的長度。

EM演算法是背後擬合模型的演算法。基於梯度優化的方法。通常會卡到一個局部極優值上。通常用戶需要用不同的初始化跑多次 fit ，然後選擇分數最高的模型。

分數通過 score 方法計算。
推導出的最優的隱藏狀態可以調用 predict 方法獲得。 predict 方法可以指定解碼器演算法。當前支持的有 viterbi （Vierbi algorithm）和 map (posteriori estimation)。

㈡ 隱馬爾可夫模型

隱馬爾可夫模型是關於時序的概率模型，描述由一個隱藏的馬爾科夫鏈隨機生成不可觀測的狀態隨機序列，再由各個狀態生成一個觀測從而產生觀測隨機序列的過程。

隱馬爾可夫模型的形式定義如下：

設 是所有可能 狀態的集合 ， 是所有可能 觀測的集合 ：

其中 為可能狀態數， 為可能觀測數。

是長度為 的 狀態序列 ， 是對應的 觀測序列 ：

是 狀態轉移概率矩陣 ：

其中：

是 觀測概率矩陣 ：

其中：

是 初始狀態概率向量 ：

其中：

隱馬爾可夫模型由初始狀態概率向量 、狀態轉移概率矩陣 和觀測概率矩陣 決定。 因此隱馬爾可夫模型 可表示為：

具體來說，長度為 的觀測序列的生成過程如下：按照初始狀態分布 產生狀態 ，按狀態 的觀測概率分布 生成 ，按狀態 的狀態轉移概率分布 產生狀態 ，依次遞推。

（1） 齊次馬爾可夫性假設 ，即隱藏的馬爾科夫鏈在任意時刻 的狀態只依賴於其前一時刻的狀態，與其他時刻狀態及觀測無關，也與時刻 無關。

（2） 觀測獨立性假設 ，即任意時刻的觀測只依賴於該時刻的馬爾科夫鏈狀態，與其它觀測狀態無關。

（1） 概率計算問題 ：給定模型 和觀測序列 ，計算在模型 下序列 出現的概率 。

（2） 學習問題 ：已知觀測序列 ，估計模型 參數，使得在該模型下觀測序列 最大。

（3） 預測問題 ：已知模型 和觀測序列 ，求使得 最大的狀態序列 。

接下來分別闡述這三個問題的解決方法。

狀態 的概率是：

對固定的 觀測序列 的概率是：

同時出現的聯合概率為：

從而：

可以看到，上式是對所有可能的 序列求和，而長度為 的 序列的數量是 數量級的，而 的計算量是 級別的，因此計算量為 ，非常大， 這種演算法在實際中不可行 。

首先定義 前向概率 ：給定隱馬爾可夫模型 ，定義到時刻 部分觀測序列為 且狀態為 的概率為前向概率，記作：

觀測序列概率的前向演算法 如下：

（1）初值：

（2）遞推，對 ：

（3）終止：

前向演算法高效的關鍵是 局部計算前向概率，然後利用路徑結構將前向概率遞推到全局，得到 。前向概率演算法計算量是 級別的。

首先定義 後向概率 ：給定隱馬爾可夫模型 ，定義在時刻 狀態為 的條件下，從 到 部分觀測序列為 的概率為後向概率，記作：

觀測序列概率的後向演算法 如下：

（1）初值：

（2）遞推，對 ：

（3）終止：

若有 個長度相同觀測序列和對應狀態序列 則可利用極大似然估計得到隱馬爾可夫模型參數：

設樣本中時刻 處於狀態 時刻 轉移到狀態 的頻數為 ，那麼狀態轉移概率 的估計為：

設樣本中狀態為 觀測為 的頻數為 ，那麼觀測概率 的估計為：

初始狀態 的估計 為 個樣本中初始狀態為 的頻率。

假設給定訓練數據只包含 個長度為 的觀測序列 而沒有對應狀態序列，我們可以把狀態數據看作不可觀測的隱數據 ，則隱馬爾可夫模型事實上是一個含有隱變數的概率模型：

其參數可由EM演算法實現。

近似演算法的思想是，在每個時刻 選擇在該時刻最有可能出現的狀態 ，從而得到一個狀態序列 。

近似演算法的優點是計算簡單，缺點是不能保證預測的狀態序列整體是最有可能的狀態序列，因為預測的狀態序列可能有實際不發生的部分，比如存在轉移概率為0的相鄰狀態。盡管如此，近似演算法還是有用的。

維特比演算法實際上是用動態規劃解隱馬爾可夫模型預測問題，即用動態規劃求概率最大路徑（最優路徑），此路徑對應一個狀態序列。

定義 在時刻 狀態為 的所有單個路徑 中概率最大值 為：

由定義得遞推式：

定義 在時刻 狀態為 的所有單個路徑 中概率最大路徑的第 個結點 為：

維特比演算法 如下：

（1）初始化：

（2）遞推，對 :

（3）終止：

（4）回溯，對 ：

最優路徑為

㈢ 隱馬爾可夫模型的基本問題

1. 評估問題。
給定觀測序列 O=O1O2O3…Ot和模型參數λ=(A,B,π)，怎樣有效計算某一觀測序列的概率，進而可對該HMM做出相關評估。例如，已有一些模型參數各異的HMM，給定觀測序列O=O1O2O3…Ot，我們想知道哪個HMM模型最可能生成該觀測序列。通常我們利用forward演算法分別計算每個HMM產生給定觀測序列O的概率，然後從中選出最優的HMM模型。
這類評估的問題的一個經典例子是語音識別。在描述語言識別的隱馬爾科夫模型中，每個單詞生成一個對應的HMM，每個觀測序列由一個單詞的語音構成，單詞的識別是通過評估進而選出最有可能產生觀測序列所代表的讀音的HMM而實現的。
2.解碼問題
給定觀測序列 O=O1O2O3…Ot 和模型參數λ=(A,B,π)，怎樣尋找某種意義上最優的隱狀態序列。在這類問題中，我們感興趣的是馬爾科夫模型中隱含狀態，這些狀態不能直接觀測但卻更具有價值，通常利用Viterbi演算法來尋找。
這類問題的一個實際例子是中文分詞，即把一個句子如何劃分其構成才合適。例如，句子「發展中國家」是劃分成「發展-中-國家」，還是「發展-中國-家」。這個問題可以用隱馬爾科夫模型來解決。句子的分詞方法可以看成是隱含狀態，而句子則可以看成是給定的可觀測狀態，從而通過建HMM來尋找出最可能正確的分詞方法。
3. 學習問題。
即HMM的模型參數λ=(A,B,π)未知，如何調整這些參數以使觀測序列O=O1O2O3…Ot的概率盡可能的大。通常使用Baum-Welch演算法以及Reversed Viterbi演算法解決。
怎樣調整模型參數λ=(A,B,π)，使觀測序列 O=O1O2O3…Ot的概率最大？

㈣ 條件隨機場和隱馬爾科夫模型最大區別在哪裡

隱馬爾可夫模型（Hidden Markov Model，HMM），最大熵馬爾可夫模型（Maximum Entropy Markov Model，MEMM）以及條件隨機場（Conditional Random Field，CRF）是序列標注中最常用也是最基本的三個模型。HMM首先出現，MEMM其次，CRF最後。三個演算法主要思想如下：HMM模型是對轉移概率和表現概率直接建模，統計共現概率。MEMM模型是對轉移概率和表現概率建立聯合概率，統計時統計的是條件概率，但MEMM容易陷入局部最優，是因為MEMM只在局部做歸一化。CRF模型中，統計了全局概率，在 做歸一化時，考慮了數據在全局的分布，而不是僅僅在局部歸一化，這樣就解決了MEMM中的標記偏置（label bias）的問題。舉個例子，對於一個標注任務，「我愛北京天安門「， 標注為」 s s b e b c e」對於HMM的話，其判斷這個標注成立的概率為 P= P(s轉移到s)*P(『我』表現為s)* P(s轉移到b)*P(『愛』表現為s)* …*P().訓練時，要統計狀態轉移概率矩陣和表現矩 陣。對於MEMM的話，其判斷這個標注成立的概率為 P= P(s轉移到s|』我』表現為s)*P(『我』表現為s)* P(s轉移到b|』愛』表現為s)*P(『愛』表現為s)*..訓練時，要統計條件狀態轉移概率矩陣和表現矩陣。對於CRF的話，其判斷這個標注成立的概率為 P= F(s轉移到s,』我』表現為s)….F為一個函數，是在全局范圍統計歸一化的概率而不是像MEMM在局部統計歸一化的概率。當前，最後出現的CRF在多項任務上達到了統治級的表現，所以如果重頭搞應用的話，大家可以首選CRF。

本質上，CRF有以下三個優點：

CRF沒有HMM那樣嚴格的獨立性假設條件，因而可以容納任意的上下文信息。特徵設計靈活（與ME一樣） ————與HMM比較

同時，由於CRF計算全局最優輸出節點的條件概率，它還克服了最大熵馬爾可夫模型標記偏置（Label-bias）的缺點。 ­­————與MEMM比較

CRF是在給定需要標記的觀察序列的條件下，計算整個標記序列的聯合概率分布，而不是在給定當前狀態條件下，定義下一個狀態的狀態分布。

凡事都有兩面，正由於這些優點，CRF需要訓練的參數更多，與MEMM和HMM相比，它存在訓練代價大、復雜度高的缺點。