隱馬爾可夫模型三個基本問題以及相應的演算法

⑴ 隱馬爾可夫模型

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

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

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

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

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

是 狀態轉移概率矩陣 ：

其中：

是 觀測概率矩陣 ：

其中：

是 初始狀態概率向量 ：

其中：

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

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

（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的概率最大？

⑶ 隱馬爾可夫模型（基礎）

假設t時刻的狀態只與t-1時刻的狀態有關，與更早的時刻無關，這一假設稱為一階馬爾可夫假設。如果狀態有n種取值，在t時刻取任何一個值與t-1時刻取任何一個值的條件概率構成了一個n×n的矩陣A，稱為狀態轉移概率矩陣。無論t時刻的狀態值是什麼，在下一時刻一定會轉向n個狀態種一個，因此他們的轉移概率和必須為1。

在實際應用種，人們不能直接觀察到狀態的值，即狀態的值是隱含的，只能得到觀測的值。因此對模型進行擴充，得到隱馬模型。

觀測序列是能得到的值。

狀態序列是因，觀測序列是果，因為處於某種狀態才有了某一觀測值。

定義狀態觀測矩陣B，表示t時刻狀態值為s時的觀測值為v的概率

t時刻的狀態z=i的概率最大狀態序列中，t-1時刻的狀態值，有了這兩個變數，就可以得到維特比演算法。

訓練時給定一組樣本，確定狀態轉移矩陣和觀測矩陣，通過最大似然估計實現。如果已知訓練樣本集中每個觀測序列對應的狀態序列，給定初始狀態如：p0=[0.5, 0.2, 0.3], k步轉化過程為：p0=p0*pk。計算機程序需要利用迭代變數，藉助循環實現。經過多步轉化p0收斂於固定值(穩態)。可以通過最大似然估計得到模型參數。

狀態空間：隱狀態S的取值范圍

觀測空間：觀測狀態O的取值范圍

轉移概率：矩陣各元素都是用概率表示。其值非負，並且各行元素之和等於1。在一定條件下是互相轉移的，故稱為轉移概率矩陣。矩陣中的行數與列數可以相等，也可以不等。當它們相等時，矩陣就是一個方陣。由轉移概率組成的矩陣就是轉移概率矩陣。也就是說構成轉移概率矩陣的元素是一個個的轉移概率不同狀態之間的轉移概率，可以用轉移矩陣表示，記做a

發射概率：初始狀態的概率分布，在知道當前標簽的情況下，發射的概率，記做π

輸出概率：基於當前狀態，不同輸出的概率分布，記做b

模型參數λ = (a, b, π)

1、 齊次假設：即馬爾科夫假設

2、 觀測獨立性假設：觀測值只取決於對應的狀態值，與其他狀態無關

（1）首先, HMM模型表示為: lambda = HMM(A, B, pi), 其中A, B, pi都是模型的參數, 分別稱作: 轉移概率矩陣, 發射概率矩陣和初始概率矩陣.

（2）接著, 我們開始訓練HMM模型, 語料就是事先准備好的一定數量的觀測序列及其對應的隱含序列, 通過極大似然估計求得一組參數, 使由觀測序列到對應隱含序列的概率最大.

（3）在訓練過程中, 為了簡化計算, 馬爾可夫提出一種假設: 隱含序列中每個單元的可能性只與上一個單元有關. 這個假設就是著名的隱含假設.

（4）訓練後, 我們就得到了具備預測能力的新模型: lambda = HMM(A, B, pi), 其中的模型參數已經改變.

（5）之後給定輸入序列(x1, x2, ..., xn), 經過模型計算lambda(x1, x2, ..., xn)得到對應隱含序列的條件概率分布.

（6）最後, 使用維特比演算法從隱含序列的條件概率分布中找出概率最大的一條序列路徑就是我們需要的隱含序列: (y1, y2, ..., yn).

狀態轉移矩陣通過訓練樣本學習得到，採用最大似然估計。

初始狀態取每種值的概率Π，狀態轉移概率矩陣A，觀測概率矩陣B

隱馬爾可夫模型需要解決以下三個問題：

（1）估值問題（觀測序列出現的概率）。給定隱馬爾可夫模型的參數A和B，計算一個觀測序列x出現的概率值p（x）。前向後向演算法

（2）解碼問題（觀測序列最大化的隱含序列）。給定隱馬爾可夫模型的參數A和B以及一個觀測序列x，計算最有可能產生此觀測序列的狀態序列z。

已知一個觀測序列，尋找最有可能產生它的狀態序列。維特比演算法

（3）學習問題。給定隱馬爾可夫模型的結構，但參數未知，給定一組訓練樣本，確定隱馬爾可夫模型的參數A和B。

保姆韋爾奇演算法

隱馬爾可夫模型對條件概率p（x|z）建模，因此是一個生成式模型。