HMM（隱馬爾可夫模型）

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

是在被建模的系統(tǒng)被認(rèn)為是一個(gè)馬爾可夫過(guò)程與未觀測(cè)到的（隱藏的）的狀態(tài)的統(tǒng)計(jì)馬爾可夫模型。

下面用一個(gè)簡(jiǎn)單的例子來(lái)闡述：

假設(shè)我手里有三個(gè)不同的骰子。第一個(gè)骰子是我們平常見(jiàn)的骰子（稱這個(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。

假設(shè)我們開(kāi)始擲骰子，我們先從三個(gè)骰子里挑一個(gè)，挑到每一個(gè)骰子的概率都是1/3。然后我們擲骰子，得到一個(gè)數(shù)字，1，2，3，4，5，6，7，8中的一個(gè)。不停的重復(fù)上述過(guò)程，我們會(huì)得到一串?dāng)?shù)字，每個(gè)數(shù)字都是1，2，3，4，5，6，7，8中的一個(gè)。例如我們可能得到這么一串?dāng)?shù)字（擲骰子10次）：1 6 3 5 2 7 3 5 2 4

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

一般來(lái)說(shuō)，HMM中說(shuō)到的馬爾可夫鏈其實(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è)定是為了最開(kāi)始容易說(shuō)清楚，但是我們其實(shí)是可以隨意設(shè)定轉(zhuǎn)換概率的。比如，我們可以這樣定義，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。這樣就是一個(gè)新的HMM。

同樣的，盡管可見(jiàn)狀態(tài)之間沒(méi)有轉(zhuǎn)換概率，但是隱含狀態(tài)和可見(jiàn)狀態(tài)之間有一個(gè)概率叫做輸出概率（emission probability）。就我們的例子來(lái)說(shuō)，六面骰（D6）產(chǎn)生1的輸出概率是1/6。產(chǎn)生2，3，4，5，6的概率也都是1/6。我們同樣可以對(duì)輸出概率進(jìn)行其他定義。比如，我有一個(gè)被賭場(chǎng)動(dòng)過(guò)手腳的六面骰子，擲出來(lái)是1的概率更大，是1/2，擲出來(lái)是2，3，4，5，6的概率是1/10。

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

      如果你只想看一個(gè)簡(jiǎn)單易懂的例子，就不需要往下看了。 

說(shuō)兩句廢話，答主認(rèn)為呢，要了解一個(gè)算法，要做到以下兩點(diǎn)：會(huì)其意，知其形。答主回答的，其實(shí)主要是第一點(diǎn)。但是這一點(diǎn)呢，恰恰是最重要，而且很多書上不會(huì)講的。正如你在追一個(gè)姑娘，姑娘對(duì)你說(shuō)“你什么都沒(méi)做錯(cuò)！”你要是只看姑娘的表達(dá)形式呢，認(rèn)為自己什么都沒(méi)做錯(cuò)，顯然就理解錯(cuò)了。你要理會(huì)姑娘的意思，“你趕緊給我道歉！”這樣當(dāng)你看到對(duì)應(yīng)的表達(dá)形式呢，趕緊認(rèn)錯(cuò)，跪地求饒就對(duì)了。數(shù)學(xué)也是一樣，你要是不理解意思，光看公式，往往一頭霧水。不過(guò)呢，數(shù)學(xué)的表達(dá)頂多也就是晦澀了點(diǎn)，姑娘的表達(dá)呢，有的時(shí)候就完全和本意相反。所以答主一直認(rèn)為理解姑娘比理解數(shù)學(xué)難多了。

回到正題，和HMM模型相關(guān)的算法主要分為三類，分別解決三種問(wèn)題： 

1）知道骰子有幾種（隱含狀態(tài)數(shù)量），每種骰子是什么（轉(zhuǎn)換概率），根據(jù)擲骰子擲出的結(jié)果（可見(jiàn)狀態(tài)鏈），我想知道每次擲出來(lái)的都是哪種骰子（隱含狀態(tài)鏈）。 

這個(gè)問(wèn)題呢，在語(yǔ)音識(shí)別領(lǐng)域呢，叫做解碼問(wèn)題。這個(gè)問(wèn)題其實(shí)有兩種解法，會(huì)給出兩個(gè)不同的答案。每個(gè)答案都對(duì)，只不過(guò)這些答案的意義不一樣。第一種解法求最大似然狀態(tài)路徑，說(shuō)通俗點(diǎn)呢，就是我求一串骰子序列，這串骰子序列產(chǎn)生觀測(cè)結(jié)果的概率最大。第二種解法呢，就不是求一組骰子序列了，而是求每次擲出的骰子分別是某種骰子的概率。比如說(shuō)我看到結(jié)果后，我可以求得第一次擲骰子是D4的概率是0.5，D6的概率是0.3，D8的概率是0.2.第一種解法我會(huì)在下面說(shuō)到，但是第二種解法我就不寫在這里了，如果大家有興趣，我們另開(kāi)一個(gè)問(wèn)題繼續(xù)寫吧。

2）還是知道骰子有幾種（隱含狀態(tài)數(shù)量），每種骰子是什么（轉(zhuǎn)換概率），根據(jù)擲骰子擲出的結(jié)果（可見(jiàn)狀態(tài)鏈），我想知道擲出這個(gè)結(jié)果的概率。 

看似這個(gè)問(wèn)題意義不大，因?yàn)槟銛S出來(lái)的結(jié)果很多時(shí)候都對(duì)應(yīng)了一個(gè)比較大的概率。問(wèn)這個(gè)問(wèn)題的目的呢，其實(shí)是檢測(cè)觀察到的結(jié)果和已知的模型是否吻合。如果很多次結(jié)果都對(duì)應(yīng)了比較小的概率，那么就說(shuō)明我們已知的模型很有可能是錯(cuò)的，有人偷偷把我們的骰子給換了。

3）知道骰子有幾種（隱含狀態(tài)數(shù)量），不知道每種骰子是什么（轉(zhuǎn)換概率），觀測(cè)到很多次擲骰子的結(jié)果（可見(jiàn)狀態(tài)鏈），我想反推出每種骰子是什么（轉(zhuǎn)換概率）。 

這個(gè)問(wèn)題很重要，因?yàn)檫@是最常見(jiàn)的情況。很多時(shí)候我們只有可見(jiàn)結(jié)果，不知道HMM模型里的參數(shù)，我們需要從可見(jiàn)結(jié)果估計(jì)出這些參數(shù)，這是建模的一個(gè)必要步驟。

問(wèn)題闡述完了，下面就開(kāi)始說(shuō)解法。（0號(hào)問(wèn)題在上面沒(méi)有提，只是作為解決上述問(wèn)題的一個(gè)輔助） 

0.一個(gè)簡(jiǎn)單問(wèn)題 

其實(shí)這個(gè)問(wèn)題實(shí)用價(jià)值不高。由于對(duì)下面較難的問(wèn)題有幫助，所以先在這里提一下。 
知道骰子有幾種，每種骰子是什么，每次擲的都是什么骰子，根據(jù)擲骰子擲出的結(jié)果，求產(chǎn)生這個(gè)結(jié)果的概率。

解法無(wú)非就是概率相乘： 

1.看見(jiàn)不可見(jiàn)的，破解骰子序列 

這里我說(shuō)的是第一種解法，解最大似然路徑問(wèn)題。 

舉例來(lái)說(shuō)，我知道我有三個(gè)骰子，六面骰，四面骰，八面骰。我也知道我擲了十次的結(jié)果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那種骰子，我想知道最有可能的骰子序列。

其實(shí)最簡(jiǎn)單而暴力的方法就是窮舉所有可能的骰子序列，然后依照第零個(gè)問(wèn)題的解法把每個(gè)序列對(duì)應(yīng)的概率算出來(lái)。然后我們從里面把對(duì)應(yīng)最大概率的序列挑出來(lái)就行了。如果馬爾可夫鏈不長(zhǎng)，當(dāng)然可行。如果長(zhǎng)的話，窮舉的數(shù)量太大，就很難完成了。 

另外一種很有名的算法叫做Viterbi algorithm. 要理解這個(gè)算法，我們先看幾個(gè)簡(jiǎn)單的列子。 

首先，如果我們只擲一次骰子：

結(jié)果為1，6.這時(shí)問(wèn)題變得復(fù)雜起來(lái)，我們要計(jì)算三個(gè)值，分別是第二個(gè)骰子是D6，D4，D8的最大概率。顯然，要取到最大概率，第一個(gè)骰子必須為D4。這時(shí)，第二個(gè)骰子取到D6的最大概率是 

同樣的，我們可以計(jì)算第二個(gè)骰子是d4或d8時(shí)的最大概率。我們發(fā)現(xiàn)，第二個(gè)骰子取到d6的概率最大。而使這個(gè)概率最大時(shí)，第一個(gè)骰子為d4。所以最大概率骰子序列就是d4=>d6。 
繼續(xù)拓展，我們擲三次骰子： 同樣，我們計(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。所以最大概率骰子序列就是

寫到這里，大家應(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è)骰子的最大概率都算過(guò)了，重新計(jì)算的話其實(shí)不難。當(dāng)我們算到最后一位時(shí)，就知道最后一位是哪個(gè)骰子的概率最大了。然后，我們要把對(duì)應(yīng)這個(gè)最大概率的序列從后往前推出來(lái)。 

2.誰(shuí)動(dòng)了我的骰子？ 

比如說(shuō)你懷疑自己的六面骰被賭場(chǎng)動(dòng)過(guò)手腳了，有可能被換成另一種六面骰，這種六面骰擲出來(lái)是1的概率更大，是1> 2，擲出來(lái)是2，3，4，5，6的概率是1> 10。你怎么辦么？答案很簡(jiǎn)單，算一算正常的三個(gè)骰子擲出一段序列的概率，再算一算不正常的六面骰和另外兩個(gè)正常骰子擲出這段序列的概率。如果前者比后者小，你就要小心了。 

>

比如說(shuō)擲骰子的結(jié)果是： 
要算用正常的三個(gè)骰子擲出這個(gè)結(jié)果的概率，其實(shí)就是將所有可能情況的概率進(jìn)行加和計(jì)算。同樣，簡(jiǎn)單而暴力的方法就是把窮舉所有的骰子序列，還是計(jì)算每個(gè)骰子序列對(duì)應(yīng)的概率，但是這回，我們不挑最大值了，而是把所有算出來(lái)的概率相加，得到的總概率就是我們要求的結(jié)果。這個(gè)方法依然不能應(yīng)用于太長(zhǎng)的骰子序列（馬爾可夫鏈）。 < p>我們會(huì)應(yīng)用一個(gè)和前一個(gè)問(wèn)題類似的解法，只不過(guò)前一個(gè)問(wèn)題關(guān)心的是概率最大值，這個(gè)問(wèn)題關(guān)心的是概率之和。解決這個(gè)問(wèn)題的算法叫做前向算法（forward=" " algorithm）。 
首先，如果我們只擲一次骰子：

把這個(gè)情況拓展，我們擲兩次骰子：

看到結(jié)果為1，6.產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算，總概率為0.05：

繼續(xù)拓展，我們擲三次骰子：

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