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

1、講一個(gè)故事

隱馬爾可夫模型（Hidden Markov Model，HMM）是統(tǒng)計(jì)模型昔驱，它用來描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過程。其難點(diǎn)是從可觀察的參數(shù)中確定該過程的隱含參數(shù)摔握。然后利用這些參數(shù)來作進(jìn)一步的分析糕韧，例如模式識(shí)別。

下面用一個(gè)簡(jiǎn)單的例子來闡述：
假設(shè)我手里有三個(gè)不同的骰子抽减。第一個(gè)骰子是我們平常見的骰子（稱這個(gè)骰子為D6）允青，6個(gè)面，每個(gè)面（1卵沉，2颠锉，3，4史汗，5琼掠，6）出現(xiàn)的概率是1/6。第二個(gè)骰子是個(gè)四面體（稱這個(gè)骰子為D4）停撞，每個(gè)面（1瓷蛙，2，3戈毒，4）出現(xiàn)的概率是1/4艰猬。第三個(gè)骰子有八個(gè)面（稱這個(gè)骰子為D8），每個(gè)面（1埋市，2冠桃，3，4道宅，5食听，6，7污茵，8）出現(xiàn)的概率是1/8樱报。

三個(gè)骰子

這串?dāng)?shù)字叫做可見狀態(tài)鏈。但是在隱馬爾可夫模型中泞当，我們不僅僅有這么一串可見狀態(tài)鏈迹蛤，還有一串隱含狀態(tài)鏈。在這個(gè)例子里笤受，這串隱含狀態(tài)鏈就是你用的骰子的序列穷缤。比如，隱含狀態(tài)鏈有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8

一般來說箩兽，HMM中說到的馬爾可夫鏈其實(shí)是指隱含狀態(tài)鏈津肛，因?yàn)殡[含狀態(tài)（骰子）之間存在轉(zhuǎn)換概率（transition probability）。在我們這個(gè)例子里汗贫，D6的下一個(gè)狀態(tài)是D4身坐，D6，D8的概率都是1/3落包。D4部蛇，D8的下一個(gè)狀態(tài)是D4，D6咐蝇，D8的轉(zhuǎn)換概率也都一樣是1/3涯鲁。這樣設(shè)定是為了最開始容易說清楚，但是我們其實(shí)是可以隨意設(shè)定轉(zhuǎn)換概率的有序。比如抹腿，我們可以這樣定義，D6后面不能接D4旭寿，D6后面是D6的概率是0.9警绩，是D8的概率是0.1。這樣就是一個(gè)新的HMM盅称。

同樣的肩祥，盡管可見狀態(tài)之間沒有轉(zhuǎn)換概率，但是隱含狀態(tài)和可見狀態(tài)之間有一個(gè)概率叫做輸出概率（emission probability）缩膝。就我們的例子來說混狠，六面骰（D6）產(chǎn)生1的輸出概率是1/6。產(chǎn)生2疾层，3将饺，4，5云芦，6的概率也都是1/6俯逾。我們同樣可以對(duì)輸出概率進(jìn)行其他定義贸桶。比如舅逸，我有一個(gè)被賭場(chǎng)動(dòng)過手腳的六面骰子，擲出來是1的概率更大皇筛，是1/2琉历，擲出來是2，3，4旗笔，5彪置，6的概率是1/10。

其實(shí)對(duì)于HMM來說蝇恶，如果提前知道所有隱含狀態(tài)之間的轉(zhuǎn)換概率和所有隱含狀態(tài)到所有可見狀態(tài)之間的輸出概率拳魁，做模擬是相當(dāng)容易的。但是應(yīng)用HMM模型時(shí)候呢撮弧，往往是缺失了一部分信息的潘懊，有時(shí)候你知道骰子有幾種，每種骰子是什么贿衍，但是不知道擲出來的骰子序列授舟；有時(shí)候你只是看到了很多次擲骰子的結(jié)果，剩下的什么都不知道贸辈。如果應(yīng)用算法去估計(jì)這些缺失的信息释树，就成了一個(gè)很重要的問題。這些算法我會(huì)在下面詳細(xì)講擎淤。

回到正題奢啥，和HMM模型相關(guān)的算法主要分為三類，分別解決三種問題：
1）知道骰子有幾種（隱含狀態(tài)數(shù)量）揉燃，每種骰子是什么（轉(zhuǎn)換概率）扫尺，根據(jù)擲骰子擲出的結(jié)果（可見狀態(tài)鏈），我想知道每次擲出來的都是哪種骰子（隱含狀態(tài)鏈）炊汤。
這個(gè)問題呢正驻，在語(yǔ)音識(shí)別領(lǐng)域呢，叫做解碼問題抢腐。這個(gè)問題其實(shí)有兩種解法姑曙，會(huì)給出兩個(gè)不同的答案。每個(gè)答案都對(duì)迈倍，只不過這些答案的意義不一樣伤靠。第一種解法求最大似然狀態(tài)路徑，說通俗點(diǎn)呢啼染，就是我求一串骰子序列，這串骰子序列產(chǎn)生觀測(cè)結(jié)果的概率最大。第二種解法呢该窗，就不是求一組骰子序列了规肴，而是求每次擲出的骰子分別是某種骰子的概率斩启。比如說我看到結(jié)果后，我可以求得第一次擲骰子是D4的概率是0.5，D6的概率是0.3翻擒，D8的概率是0.2.第一種解法我會(huì)在下面說到巩趁，但是第二種解法我就不寫在這里了草讶，如果大家有興趣颁督，我們另開一個(gè)問題繼續(xù)寫吧践啄。

2）還是知道骰子有幾種（隱含狀態(tài)數(shù)量），每種骰子是什么（轉(zhuǎn)換概率）沉御，根據(jù)擲骰子擲出的結(jié)果（可見狀態(tài)鏈）屿讽，我想知道擲出這個(gè)結(jié)果的概率吠裆。
看似這個(gè)問題意義不大伐谈，因?yàn)槟銛S出來的結(jié)果很多時(shí)候都對(duì)應(yīng)了一個(gè)比較大的概率。問這個(gè)問題的目的呢试疙，其實(shí)是檢測(cè)觀察到的結(jié)果和已知的模型是否吻合诵棵。如果很多次結(jié)果都對(duì)應(yīng)了比較小的概率，那么就說明我們已知的模型很有可能是錯(cuò)的祝旷，有人偷偷把我們的骰子給換了履澳。

**3）知道骰子有幾種（隱含狀態(tài)數(shù)量），不知道每種骰子是什么（轉(zhuǎn)換概率）怀跛，觀測(cè)到很多次擲骰子的結(jié)果（可見狀態(tài)鏈）距贷，我想反推出每種骰子是什么（轉(zhuǎn)換概率）。 **
這個(gè)問題很重要吻谋，因?yàn)檫@是最常見的情況忠蝗。很多時(shí)候我們只有可見結(jié)果，不知道HMM模型里的參數(shù)漓拾，我們需要從可見結(jié)果估計(jì)出這些參數(shù)阁最，這是建模的一個(gè)必要步驟。

問題闡述完了骇两，下面就開始說解法闽撤，我們首先來看一個(gè)簡(jiǎn)單的問題：
知道骰子有幾種，每種骰子是什么脯颜，每次擲的都是什么骰子哟旗，根據(jù)擲骰子擲出的結(jié)果，求產(chǎn)生這個(gè)結(jié)果的概率栋操。

解法無非就是概率相乘：

接下來 闸餐，我們就開始解決上面提到的三個(gè)問題：
**1.看見不可見的，破解骰子序列 **
這里我說的是第一種解法矾芙，解最大似然路徑問題舍沙。
舉例來說，我知道我有三個(gè)骰子剔宪，六面骰拂铡，四面骰壹无，八面骰。我也知道我擲了十次的結(jié)果（1 6 3 5 2 7 3 5 2 4）感帅，我不知道每次用了那種骰子斗锭，我想知道最有可能的骰子序列。

其實(shí)最簡(jiǎn)單而暴力的方法就是窮舉所有可能的骰子序列失球，然后依照第零個(gè)問題的解法把每個(gè)序列對(duì)應(yīng)的概率算出來岖是。然后我們從里面把對(duì)應(yīng)最大概率的序列挑出來就行了。如果馬爾可夫鏈不長(zhǎng)实苞，當(dāng)然可行豺撑。如果長(zhǎng)的話，窮舉的數(shù)量太大黔牵，就很難完成了聪轿。
另外一種很有名的算法叫做Viterbi algorithm. 要理解這個(gè)算法，我們先看幾個(gè)簡(jiǎn)單的列子猾浦。
首先屹电，如果我們只擲一次骰子：

看到結(jié)果為1.對(duì)應(yīng)的最大概率骰子序列就是D4，因?yàn)镈4產(chǎn)生1的概率是1/4跃巡，高于1/6和1/8.
把這個(gè)情況拓展危号，我們擲兩次骰子：

同樣，我們計(jì)算第三個(gè)骰子分別是D6厕鹃，D4兢仰，D8的最大概率乍丈。我們?cè)俅伟l(fā)現(xiàn)，要取到最大概率把将，第二個(gè)骰子必須為D6轻专。這時(shí)，第三個(gè)骰子取到D4的最大概率是

同上秸弛，我們可以計(jì)算第三個(gè)骰子是D6或D8時(shí)的最大概率。我們發(fā)現(xiàn)洪碳，第三個(gè)骰子取到D4的概率最大递览。而使這個(gè)概率最大時(shí)，第二個(gè)骰子為D6瞳腌，第一個(gè)骰子為D4绞铃。所以最大概率骰子序列就是D4 D6 D4。

寫到這里嫂侍，大家應(yīng)該看出點(diǎn)規(guī)律了儿捧。既然擲骰子一二三次可以算，擲多少次都可以以此類推挑宠。我們發(fā)現(xiàn)菲盾，我們要求最大概率骰子序列時(shí)要做這么幾件事情。首先各淀，不管序列多長(zhǎng)懒鉴，要從序列長(zhǎng)度為1算起，算序列長(zhǎng)度為1時(shí)取到每個(gè)骰子的最大概率碎浇。然后临谱，逐漸增加長(zhǎng)度，每增加一次長(zhǎng)度奴璃，重新算一遍在這個(gè)長(zhǎng)度下最后一個(gè)位置取到每個(gè)骰子的最大概率悉默。因?yàn)樯弦粋€(gè)長(zhǎng)度下的取到每個(gè)骰子的最大概率都算過了，重新計(jì)算的話其實(shí)不難苟穆。當(dāng)我們算到最后一位時(shí)抄课，就知道最后一位是哪個(gè)骰子的概率最大了。然后雳旅，我們要把對(duì)應(yīng)這個(gè)最大概率的序列從后往前推出來剖膳。

2.誰動(dòng)了我的骰子？
比如說你懷疑自己的六面骰被賭場(chǎng)動(dòng)過手腳了岭辣，有可能被換成另一種六面骰吱晒，這種六面骰擲出來是1的概率更大，是1/2沦童，擲出來是2仑濒，3叹话，4，5墩瞳，6的概率是1/10驼壶。你怎么辦么？答案很簡(jiǎn)單喉酌，算一算正常的三個(gè)骰子擲出一段序列的概率热凹，再算一算不正常的六面骰和另外兩個(gè)正常骰子擲出這段序列的概率。如果前者比后者小泪电，你就要小心了般妙。
比如說擲骰子的結(jié)果是：

要算用正常的三個(gè)骰子擲出這個(gè)結(jié)果的概率，其實(shí)就是將所有可能情況的概率進(jìn)行加和計(jì)算相速。同樣碟渺，簡(jiǎn)單而暴力的方法就是把窮舉所有的骰子序列，還是計(jì)算每個(gè)骰子序列對(duì)應(yīng)的概率突诬，但是這回苫拍，我們不挑最大值了，而是把所有算出來的概率相加旺隙，得到的總概率就是我們要求的結(jié)果绒极。這個(gè)方法依然不能應(yīng)用于太長(zhǎng)的骰子序列（馬爾可夫鏈）。
我們會(huì)應(yīng)用一個(gè)和前一個(gè)問題類似的解法蔬捷，只不過前一個(gè)問題關(guān)心的是概率最大值集峦，這個(gè)問題關(guān)心的是概率之和。解決這個(gè)問題的算法叫做前向算法（forward algorithm）抠刺。

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

同樣的塔淤，我們一步一步的算，有多長(zhǎng)算多長(zhǎng)速妖，再長(zhǎng)的馬爾可夫鏈總能算出來的高蜂。用同樣的方法，也可以算出不正常的六面骰和另外兩個(gè)正常骰子擲出這段序列的概率罕容，然后我們比較一下這兩個(gè)概率大小备恤，就能知道你的骰子是不是被人換了。