隱馬爾可夫模型演算法

Ⅰ 02 隱馬爾可夫模型 - HMM的三個問題 - 概率計算問題

01 隱馬爾可夫模型 - 馬爾可夫鏈、HMM參數和性質

假設有三個盒子，編號為1,2,3；每個盒子都裝有黑白兩種顏色的小球，球的比例。如下：

按照下列規則的方式進行有放回的抽取小球，得到球顏色的觀測序列：
1、按照π的概率選擇一個盒子，從盒子中隨機抽取出一個球，記錄顏色後放回盒子中；
2、按照某種條件概率選擇新的盒子，重復該操作；
3、最終得到觀測序列：「白黑白白黑」

例如： 每次抽盒子按一定的概率來抽，也可以理解成隨機抽。
第1次抽了1號盒子①，第2次抽了3號盒子③，第3次抽了2號盒子②.... ； 最終如下：
①→③→②→②→③ 狀態值
白→黑→白→白→黑 觀測值

1、 狀態集合： S={盒子1，盒子2，盒子3}
2、 觀測集合： O={白，黑}
3、 狀態序列和觀測序列的長度 T=5 (我抽了5次)
4、 初始概率分布： π 表示初次抽時，抽到1盒子的概率是0.2，抽到2盒子的概率是0.5，抽到3盒子的概率是0.3。
5、 狀態轉移概率矩陣 A：a11=0.5 表示當前我抽到1盒子，下次還抽到1盒子的概率是0.5；
6、 觀測概率矩陣 - 混淆矩陣 - 為了不和之前的混淆矩陣概念沖突，可以稱之為發射矩陣，即從一個狀態發射到另一個狀態： B：如最初的圖，b11=第一個盒子抽到白球概率0.4，b12=第一個盒子抽到黑球概率0.6;

在給定參數π、A、B的時候，得到觀測序列為「白黑白白黑」的概率是多少?

這個時候，我們不知道隱含條件，即不知道狀態值：①→③→②→②→③ ；
我們如何根據π、A、B求出測序列為「白黑白白黑」的概率？
下面給出解決方案。

前向-後向演算法 給定模型λ=(A,B,π)和觀測序列Q={q1,q2,...,qT}，計算模型λ下觀測到序列Q出現的概率P(Q|λ)；

回顧上面的案例 ，λ=(A,B,π)已知。觀測到序列 Q=白→黑→白→白→黑，但我們不知道 狀態序列 I=①→③→②→②→③；我們要求解 P(Q|λ) ，即Q=白→黑→白→白→黑 這個觀測序列發生的概率。 可以用前向-後向演算法來實現 。

Baum-Welch演算法(狀態未知) 已知觀測序列Q={q1,q2,...,qT}，估計模型λ=(A,B,π)的參數，使得在該模型下觀測序列P(Q|λ)最大。

Baum-Welch演算法是EM演算法的一個特例，專門用來 求解 隱馬爾科夫中隱狀態參數 λ=(A,B,π) 。即：根據已知的 觀測到序列 Q=白→黑→白→白→黑，去尋找整個模型的一組隱狀態參數λ=(A,B,π)，使得在模型中 觀測序列 發生的可能性P(Q|λ)最大。

Viterbi演算法 給定模型λ=(A,B,π)和觀測序列Q={q1,q2,...,qT}，求給定觀測序列條件概率P(I|Q，λ)最大的狀態序列I。

已知 觀測到序列 Q=白→黑→白→白→黑，當我們得到λ=(A,B,π)後，我們用 Viterbi演算法 求出在哪一種 狀態序列 發生的可能性最大，即，求出 狀態序列 I=①→③→②→②→③；即，抽取什麼樣的盒子順序，更可能得到白→黑→白→白→黑這種結果。

1、直接計演算法(暴力演算法)
2、前向演算法
3、後向演算法

類似KNN計算最近鄰時候的演算法。《 01 KNN演算法 - 概述 》
也就是說， 暴力演算法 需要一個個遍歷所有的狀態去計算當前狀態發生的概率。

按照概率公式，列舉所有可能的長度為T的狀態序列I={i1,i2,...,iT}，求各個狀態序列I與觀測序列Q={q1,q2,...,qT}的聯合概率P(Q,I;λ)，然後對所有可能的狀態序列求和，從而得到最終的概率P(Q;λ)；

分析： 先思考這樣一個問題：生成「白-黑-白-白-黑」這樣的結果，是不是會有很多種盒子組合的序列來抽取，都會生成這樣一個結果？我把這些可能出現「白-黑-白-白-黑」結果的盒子序列的聯合概率求出來-P(Q,I;λ)，即∑P(Q,I) = P(Q) ，P(Q) 是我們觀測到「白-黑-白-白-黑」結果時，符合這個結果的所有狀態序列I出現的概率。

公式運用：

設狀態序列 I=③→②→①→①→②； T=5；
P(I;λ) = π 3 a 32 a 21 a 11 a 12

因為： 在給定狀態序列I後，Q中的每個觀測值都獨立。（貝葉斯網路原理） 貝葉斯網路
所以： P(Q|I;λ)可以用聯乘的方式表示 (獨立可以使用聯合概率)
I = ③→②→①→①→②
Q=白→黑→白→白→黑
P(Q|I;λ) = b 3白 b 2黑 b 1白 b 1白 b 2黑

P(Q,I;λ) = P(Q|I;λ) × P(I;λ)
= b 3白 b 2黑 b 1白 b 1白 b 2黑 × π 3 a 32 a 21 a 11 a 12

若：
I 1 = ③→②→①→①→②
I 2 = ①→②→③→①→②
...
I T = ②→②→①→③→②
都能得出：
Q = 白→黑→白→白→黑
因為我所有的盒子都能取出黑球和白球，所以T的值=3 5 ;

∑P(Q,I;λ) 計算的是 I 1 ~ I T 這些狀態序列情況下，求出的P(Q,I;λ)的和。

前向 和 後向 演算法是運用某種遞歸(遞推)的方式，幫助我們盡快得求解最終結果。

解析: 如果 t 這一時刻觀察到的狀態是 q t = 雨天；其中y={干，濕，濕... 濕}共t個狀態。
先不考慮λ。
α t 是 1時刻~t時刻 所有觀測值y1，y2，...yt ，qt 出現的聯合概率。
β t 是 t+1時刻~T時刻 所有觀測值y t+1 ，y t+2 ，...y T 出現的聯合概率。

前向概率-後向概率 指的其實是在一個觀測序列中，時刻t對應的狀態為si的概率值轉換過來的信息。

分析2~3步的推導： 因為q 1 ~ q t 這些條件對 q t+1 ~ q T 的產生沒有影響 (理由：貝葉斯網路)，所以這些條件可以去掉。

定義：給定λ，定義到時刻t部分觀測序列為q1,q2,...,qt且狀態為si的概率為 前向概率 。
記做：

在給定參數π、A、B的時候，得到觀測序列為「白黑白白黑」的概率是多少?

定義：給定λ，定義到時刻t狀態為si的前提下，從t+1到T部分觀測序列為qt+1,qt+2,...,qT的概率為 後向概率 。
記做：

分析上面的公式：
如果一共只有t個時間點，t+1的時刻不存在。那麼t+1以後發生的是必然事件。
所以 β t (i) = P(q t+1 ，q t+2 ，...，q T ) = 1;
如果實在不理解也沒關系，我們姑且認為認為定義了一個初始值，即 β T (i) = 1 ；

從T-1時刻，倒推到1時刻。
首先，β t+1 (j)是什麼？是t+1時刻，在狀態sj的前提下，下圖中圈起來這部分的聯合概率。

β t (j)是什麼？是t時刻，在狀態sj的前提下，下圖中圈起來這部分的聯合概率。

求給定模型λ和觀測序列Q的情況下，在時刻t處於狀態si的概率，記做：

單個狀態概率的意義主要是用於判斷在每個時刻最可能存在的狀態，從而可以得到一個狀態序列作為最終的預測結果。

求給定模型λ和觀測序列Q的情況下，在時刻t處於狀態si並時刻t+1處於狀態sj概率，記做：

03 隱馬爾可夫模型 - HMM的三個問題 - 學習問題

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

隱馬爾可夫模型（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相比，它存在訓練代價大、復雜度高的缺點。

Ⅲ 從馬爾可夫模型到隱馬爾可夫模型

馬爾可夫模型個人認為這個概念應該是從 隨機過程 裡面提出來的，由馬爾可夫過程過來的概念。實際上掌握了隨機過程裡面對馬爾可夫過程的特殊情況：離散參數離散狀態的馬爾可夫鏈的數學運算的話。就能夠很好解決馬爾可夫模型上面的計算問題，包括隱馬爾科夫模型。講馬爾可夫模型以及過程重點在於其滿足的性質-馬爾可夫性。

隨機過程：
現實中時常出現，某個事物滿足一定的隨機分布，但是其隨機分布會隨著時間的變化而變化。我們假設其在時刻 符合隨機分布 並且用隨機變數 來表示。假設 。但是在時間 的時候就符合隨機分布 並且用隨機變數 來表示。假設 。也就是說某個事物的某個特徵會隨著時間的變化其對應的分布也會發生變化。這樣一個總體的過程，稱之為 隨機過程。

具體例子：
燈泡壽命問題，燈泡其實在每個時間點上都有一定的可能性會損壞，在這個時間點上損壞的可能性符合一個具體的正態分布（其 是確定的），而隨著時間的久遠，燈泡損壞的可能性就變大了。所以在之後的某個時間點上燈泡損壞的可能性可能就符合另外一個具體的正態分布（其 就和先前不一樣了，會有變壞的趨勢）。燈泡損壞在傳統的概率論中也是一個經典例子，可能傳統的概率論會認為燈泡的壽命長短符合一個隨機分布，並且用一個隨機變數來表示，我們研究這個分布的特徵。這里和傳統的概率論中不一樣，可以發現的是，引入了隨機過程，可以對隨機現象更加深入徹底地描述和研究。

定義隨機過程中的一些量。
參數：也就是上述的時間，如果是和時間有關，往往叫做時間序列。但是很多的現象研究不是和時間相關的。

狀態：也就是上述的隨著時間變化的隨機變數。

馬爾可夫過程：滿足馬爾科夫性的隨機過程。

以後再解釋
馬爾可夫性：
馬爾可夫鏈：

馬爾可夫模型和上述的關系。

具體講一下 隱馬爾可夫模型。

和普通的馬爾可夫不一樣，馬爾可夫模型是可以確定狀態序列的。也就是說序列上的每個項的分布是怎麼樣的是已知的。而隱馬爾可夫模型是連序列上的每個項的是什麼分布都不能夠知道，都是隨機的。

對於這樣的一個隨機模型。
經常要解決三個基本問題：
1). 給定 和 ，求解 。 又叫作 計算問題。
2). 給定 和 ，求解一個狀態轉換序列 ，使得最優可能產生上面的序列。又叫做估計問題。
3). 在模型參數（A或者B）未知或者參數不準確的情況下，由 來調整參數。又叫做訓練問題。

狀態一定是按著產生了部分觀察序列來的。考慮前綴。 表示處理到了n,觀察序列到n為止都是答案的概率。但是不好轉移，轉移的時候要枚舉前後隱藏狀態，考慮把隱藏狀態也表示出來。 表示處理到了n，並且第n個狀態為j的概率。
范圍：
結果：
初始化：
轉移：

知道 和 ，求Q，狀態序列，使得產生 的可能性最大。

定義：

這個函數的含義是：
模型在時刻t處於狀態i，觀察到 的最佳狀態轉換序列的概率。
從而有了轉移方程：

而 就是
因此 的轉移過程構成了一個圖，而Q就是上面的最優路徑。

利用 觀察數據進行對模型參數 或者 或者 進行預測和修正，訓練問題，又可以叫做預測問題。

並且這個問題其實是帶有隱變數的最大似乎估計，也就是EM演算法。
直接講EM,用數學角度來引入 或者 用遞歸式來求解含有隱變數的參數估計 都是可以的，後者會比較清楚。
但是課上老師給出了另外一種比較好的解釋：
考慮第三個問題，實際上應該分兩種情況。
1：帶指導的參數學習。
給出的數據是這樣的：
狀態/觀察數據。
硬幣中的例子就是
H/1 H/1 T/1 T/2 H/3 T/3 T/2 H/1 T/2 H/3 H/3 H/1
其實當擁有了數據 狀態/觀察數據 是可以直接對參數進行估計的。
假設是齊次的（一般也是齊次的，概率只和狀態有關，和時間關系不大，放在詞句中就是詞語所在的句子的部位關系不是很大，而是上下文內容關系比較大。），

考慮aij 指的是在狀態i和狀態j的轉移概率。
可以直接對上面2個2個統計進行參數估計。
考慮bi(o_j)也就是狀態為i輸出為o_j的。
一個一個枚舉來即可。
考慮pi_i。也就是初始狀態。
一個一個枚舉狀態即可。

帶有指導的是有缺點的：
數據上不可行，狀態這樣的數據其實都是人工標注的。
數據量要求比較大。

但是在NLP中這個方法是很重要的。因為效果比較好。

2：不帶指導的參數學習
數據上只給出了 觀察序列，沒有狀態序列。

實際上1中就出了答案。沒有狀態序列，我們就枚舉狀態序列。
比如上述。如果觀察出來了
1 2 2
那麼我們就考慮以下
1 2 2
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT
所有情況。
所以就產生了
H/1 H/2 H/2
H/1 H/2 T/2
....
然後分組進行統計參數估計即可。

但是這里有兩個問題：
1：狀態太多了。N^T。
2：給每個狀態的權重是一樣的。不是很科學。（實際上還行，如果使用熵最大原理。）
那麼怎麼辦？解決2考慮給不同狀態加權重，那麼要有一個先驗的的知識：
咱們先給出先驗的 模型參數。
那麼就可以計算P(Q|O,人)P（Q,O|人）這樣的東西了。
明顯可以用P(Q|O,人)作為一個路徑序列的權重。
但是這樣計算的時候，路徑序列很長。並且轉移路徑還是N^T條。
不可行。

避開對路徑的考慮。考慮參數abt最多隻有涉及兩個時間點的。
我們如果只關注兩個時間點之間的狀態。那麼就可以變成二維的。
使Q不是一個路徑的。而是只是兩個時間點之間的狀態。
q_t = i q_t+1 = j 。把這個概率計算出來的話。就能直接對aij這樣的進行估計了。
（實際上只是換了一種計數方式，就減少了問題規模，因為咱們關注的也只是路徑上兩個點兩個點之間的。）

由此引出Baum_Welch演算法：

定義以下：

這樣就能對參數們進行評估了。有以下：

這樣只要挑一個滿足條件的初始值，然後迭代求解即可。

Ⅳ 隱馬爾可夫模型（二）-骰子的故事

整理自： http://www.cnblogs.com/skyme/p/4651331.html

隱馬爾可夫模型（Hidden Markov Model，HMM）是統計模型，它用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數。然後利用這些參數來作進一步的分析，例如模式識別。

下面用一個簡單的例子來闡述：
假設我手裡有三個不同的骰子。第一個骰子是我們平常見的骰子（稱這個骰子為D6），6個面，每個面（1，2，3，4，5，6）出現的概率是1/6。第二個骰子是個四面體（稱這個骰子為D4），每個面（1，2，3，4）出現的概率是1/4。第三個骰子有八個面（稱這個骰子為D8），每個面（1，2，3，4，5，6，7，8）出現的概率是1/8。

這串數字叫做可見狀態鏈。但是在隱馬爾可夫模型中，我們不僅僅有這么一串可見狀態鏈，還有一串隱含狀態鏈。在這個例子里，這串隱含狀態鏈就是你用的骰子的序列。比如，隱含狀態鏈有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8

一般來說，HMM中說到的馬爾可夫鏈其實是指隱含狀態鏈，因為隱含狀態（骰子）之間存在轉換概率（transition probability）。在我們這個例子里，D6的下一個狀態是D4，D6，D8的概率都是1/3。D4，D8的下一個狀態是D4，D6，D8的轉換概率也都一樣是1/3。這樣設定是為了最開始容易說清楚，但是我們其實是可以隨意設定轉換概率的。比如，我們可以這樣定義，D6後面不能接D4，D6後面是D6的概率是0.9，是D8的概率是0.1。這樣就是一個新的HMM。

同樣的，盡管可見狀態之間沒有轉換概率，但是隱含狀態和可見狀態之間有一個概率叫做輸出概率（emission probability）。就我們的例子來說，六面骰（D6）產生1的輸出概率是1/6。產生2，3，4，5，6的概率也都是1/6。我們同樣可以對輸出概率進行其他定義。比如，我有一個被賭場動過手腳的六面骰子，擲出來是1的概率更大，是1/2，擲出來是2，3，4，5，6的概率是1/10。

其實對於HMM來說，如果提前知道所有隱含狀態之間的轉換概率和所有隱含狀態到所有可見狀態之間的輸出概率，做模擬是相當容易的。但是應用HMM模型時候呢，往往是缺失了一部分信息的，有時候你知道骰子有幾種，每種骰子是什麼，但是不知道擲出來的骰子序列；有時候你只是看到了很多次擲骰子的結果，剩下的什麼都不知道。如果應用演算法去估計這些缺失的信息，就成了一個很重要的問題。這些演算法我會在下面詳細講。

回到正題，和HMM模型相關的演算法主要分為三類，分別解決三種問題：
1）知道骰子有幾種（隱含狀態數量），每種骰子是什麼（轉換概率），根據擲骰子擲出的結果（可見狀態鏈），我想知道每次擲出來的都是哪種骰子（隱含狀態鏈）。
這個問題呢，在語音識別領域呢，叫做解碼問題。這個問題其實有兩種解法，會給出兩個不同的答案。每個答案都對，只不過這些答案的意義不一樣。第一種解法求最大似然狀態路徑，說通俗點呢，就是我求一串骰子序列，這串骰子序列產生觀測結果的概率最大。第二種解法呢，就不是求一組骰子序列了，而是求每次擲出的骰子分別是某種骰子的概率。比如說我看到結果後，我可以求得第一次擲骰子是D4的概率是0.5，D6的概率是0.3，D8的概率是0.2.第一種解法我會在下面說到，但是第二種解法我就不寫在這里了，如果大家有興趣，我們另開一個問題繼續寫吧。

2）還是知道骰子有幾種（隱含狀態數量），每種骰子是什麼（轉換概率），根據擲骰子擲出的結果（可見狀態鏈），我想知道擲出這個結果的概率。
看似這個問題意義不大，因為你擲出來的結果很多時候都對應了一個比較大的概率。問這個問題的目的呢，其實是檢測觀察到的結果和已知的模型是否吻合。如果很多次結果都對應了比較小的概率，那麼就說明我們已知的模型很有可能是錯的，有人偷偷把我們的骰子給換了。

**3）知道骰子有幾種（隱含狀態數量），不知道每種骰子是什麼（轉換概率），觀測到很多次擲骰子的結果（可見狀態鏈），我想反推出每種骰子是什麼（轉換概率）。 **
這個問題很重要，因為這是最常見的情況。很多時候我們只有可見結果，不知道HMM模型里的參數，我們需要從可見結果估計出這些參數，這是建模的一個必要步驟。

問題闡述完了，下面就開始說解法，我們首先來看一個簡單的問題：
知道骰子有幾種，每種骰子是什麼，每次擲的都是什麼骰子，根據擲骰子擲出的結果，求產生這個結果的概率。

解法無非就是概率相乘：

接下來 ，我們就開始解決上面提到的三個問題：
**1.看見不可見的，破解骰子序列 **
這里我說的是第一種解法，解最大似然路徑問題。
舉例來說，我知道我有三個骰子，六面骰，四面骰，八面骰。我也知道我擲了十次的結果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那種骰子，我想知道最有可能的骰子序列。

其實最簡單而暴力的方法就是窮舉所有可能的骰子序列，然後依照第零個問題的解法把每個序列對應的概率算出來。然後我們從裡面把對應最大概率的序列挑出來就行了。如果馬爾可夫鏈不長，當然可行。如果長的話，窮舉的數量太大，就很難完成了。
另外一種很有名的演算法叫做Viterbi algorithm. 要理解這個演算法，我們先看幾個簡單的列子。
首先，如果我們只擲一次骰子：

看到結果為1.對應的最大概率骰子序列就是D4，因為D4產生1的概率是1/4，高於1/6和1/8.
把這個情況拓展，我們擲兩次骰子：

同樣，我們計算第三個骰子分別是D6，D4，D8的最大概率。我們再次發現，要取到最大概率，第二個骰子必須為D6。這時，第三個骰子取到D4的最大概率是

同上，我們可以計算第三個骰子是D6或D8時的最大概率。我們發現，第三個骰子取到D4的概率最大。而使這個概率最大時，第二個骰子為D6，第一個骰子為D4。所以最大概率骰子序列就是D4 D6 D4。

寫到這里，大家應該看出點規律了。既然擲骰子一二三次可以算，擲多少次都可以以此類推。我們發現，我們要求最大概率骰子序列時要做這么幾件事情。首先，不管序列多長，要從序列長度為1算起，算序列長度為1時取到每個骰子的最大概率。然後，逐漸增加長度，每增加一次長度，重新算一遍在這個長度下最後一個位置取到每個骰子的最大概率。因為上一個長度下的取到每個骰子的最大概率都算過了，重新計算的話其實不難。當我們算到最後一位時，就知道最後一位是哪個骰子的概率最大了。然後，我們要把對應這個最大概率的序列從後往前推出來。

2.誰動了我的骰子？
比如說你懷疑自己的六面骰被賭場動過手腳了，有可能被換成另一種六面骰，這種六面骰擲出來是1的概率更大，是1/2，擲出來是2，3，4，5，6的概率是1/10。你怎麼辦么？答案很簡單，算一算正常的三個骰子擲出一段序列的概率，再算一算不正常的六面骰和另外兩個正常骰子擲出這段序列的概率。如果前者比後者小，你就要小心了。
比如說擲骰子的結果是：

要算用正常的三個骰子擲出這個結果的概率，其實就是將所有可能情況的概率進行加和計算。同樣，簡單而暴力的方法就是把窮舉所有的骰子序列，還是計算每個骰子序列對應的概率，但是這回，我們不挑最大值了，而是把所有算出來的概率相加，得到的總概率就是我們要求的結果。這個方法依然不能應用於太長的骰子序列（馬爾可夫鏈）。
我們會應用一個和前一個問題類似的解法，只不過前一個問題關心的是概率最大值，這個問題關心的是概率之和。解決這個問題的演算法叫做前向演算法（forward algorithm）。

所以我們根據下表計算出得到該序列的概率：

同樣的，我們一步一步的算，有多長算多長，再長的馬爾可夫鏈總能算出來的。用同樣的方法，也可以算出不正常的六面骰和另外兩個正常骰子擲出這段序列的概率，然後我們比較一下這兩個概率大小，就能知道你的骰子是不是被人換了。

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

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）建模，因此是一個生成式模型。