目錄
【數(shù)之道 29】"隱馬爾可夫模型"HMM是什么？了解它只需5分鐘！_嗶哩嗶哩_bilibili
這個(gè)視頻講的通俗易懂
- 實(shí)例帶入
- HMM解決的問(wèn)題
- HMM數(shù)學(xué)相關(guān)思想
3.1 知道所有狀態(tài)，計(jì)算特定結(jié)果概率
3.2 隱含狀態(tài)鏈
3.3 拓展思想 - 生活例子解釋
4.1 參數(shù)整理
4.2 Viterbi求解思路
1. 實(shí)例帶入
假設(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)鏈。
隱含狀態(tài)（骰子）之間存在轉(zhuǎn)換概率（transition probability），在我們這個(gè)例子里：
D6的下一個(gè)狀態(tài)是D4，D6，D8的概率都是1/3。
D4的下一個(gè)狀態(tài)是D4，D6，D8的概率都是1/3。
D8的下一個(gè)狀態(tài)是D4，D6，D8的轉(zhuǎn)換概率也都一樣是1/3。
我們其實(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ō)：
四面骰（D4）產(chǎn)生1，2，3，4的概率都是1/4。
六面骰（D6）產(chǎn)生1，2，3，4，5，6的概率都是1/6。
八面骰（D8）產(chǎn)生1，2，3，4，5，6，7，8的概率都是1/8。
我們同樣可以對(duì)輸出概率進(jìn)行其他定義。比如，我有一個(gè)被賭場(chǎng)動(dòng)過(guò)手腳的六面骰子，擲出來(lái)是1的概率更大，是1/2，擲出來(lái)是2，3，4，5，6的概率是1/10。
對(duì)于HMM來(lái)說(shuō)，如果提前知道所有隱含狀態(tài)之間的轉(zhuǎn)換概率、所有隱含狀態(tài)的序列和所有隱含狀態(tài)到所有可見(jiàn)狀態(tài)之間的輸出概率，做模擬是相當(dāng)容易的。
但是應(yīng)用HMM模型時(shí)候呢，往往是缺失了一部分信息的：
有時(shí)候你知道骰子有幾種，每種骰子是什么，但是不知道擲出來(lái)的骰子序列；
有時(shí)候你只是看到了很多次擲骰子的結(jié)果，剩下的什么都不知道。
如果應(yīng)用算法去估計(jì)這些缺失的信息，就成了一個(gè)很重要的問(wèn)題。
HMM解決的問(wèn)題
和HMM模型相關(guān)的算法主要分為三類，分別解決三種問(wèn)題：
知道骰子有幾種（隱含狀態(tài)數(shù)量），每種骰子是什么（輸出概率），根據(jù)擲骰子擲出的結(jié)果（可見(jiàn)狀態(tài)鏈），我想知道每次擲出來(lái)的都是哪種骰子（隱含狀態(tài)鏈）。
知道骰子有幾種（隱含狀態(tài)數(shù)量），每種骰子是什么（轉(zhuǎn)換概率），根據(jù)擲骰子擲出的結(jié)果（可見(jiàn)狀態(tài)鏈），我想知道擲出這個(gè)結(jié)果的概率。
知道骰子有幾種（隱含狀態(tài)數(shù)量），不知道每種骰子是什么（轉(zhuǎn)換概率），觀測(cè)到很多次擲骰子的結(jié)果（可見(jiàn)狀態(tài)鏈），我想反推出每種骰子是什么（轉(zhuǎn)換概率）。
HMM數(shù)學(xué)相關(guān)思想
3.1 知道所有狀態(tài)，計(jì)算特定結(jié)果概率
考慮到這里我們并不是真的要學(xué)會(huì)HMM背后的數(shù)學(xué)算法，所以這里我用一個(gè)最簡(jiǎn)單問(wèn)題來(lái)和大家一起思考這個(gè)過(guò)程：
知道骰子有幾種，每種骰子是什么，每次擲的都是什么骰子，根據(jù)擲骰子擲出的結(jié)果，求產(chǎn)生這個(gè)結(jié)果的概率。
解法無(wú)非就是概率相乘：
3.2 隱含狀態(tài)鏈
問(wèn)題：知道有三個(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。對(duì)應(yīng)的最大概率骰子序列就是D4，因?yàn)镈4產(chǎn)生1的概率是1/4，高于1/6和1/8。
把這個(gè)情況拓展，我們擲兩次骰子：
結(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。
所以最大概率骰子序列就是D4 D6 D4。
3.3 拓展思想
比如說(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)的骰子序列（馬爾可夫鏈）。
我們會(huì)應(yīng)用一個(gè)和前一個(gè)問(wèn)題類似的解法，只不過(guò)前一個(gè)問(wèn)題關(guān)心的是概率最大值，這個(gè)問(wèn)題關(guān)心的是概率之和。解決這個(gè)問(wèn)題的算法叫做前向算法（forward algorithm）。
首先，如果我們只擲一次骰子：
看到結(jié)果為1。產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算，總概率為0.18（13/72）：
把這個(gè)情況拓展，我們擲兩次骰子：
看到結(jié)果為1，6。產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算，總概率為0.02（91/5184）：
繼續(xù)拓展，我們擲三次骰子：
看到結(jié)果為1，6，3.產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算，總概率為0.003（1183/373248）：
同樣的，我們一步一步的算，有多長(zhǎng)算多長(zhǎng)，再長(zhǎng)的馬爾可夫鏈總能算出來(lái)的。用同樣的方法，也可以算出不正常的六面骰和另外兩個(gè)正常骰子擲出這段序列的概率，然后我們比較一下這兩個(gè)概率大小，就能知道你的骰子是不是被人換了。
4. 生活例子解釋
舉一個(gè)經(jīng)典的例子：一個(gè)東京的女孩每天根據(jù)天氣 {下雨，天晴} 決定當(dāng)天的活動(dòng) {公園散步,購(gòu)物,清理房間} 中的一種。
我們每天只能在twitter上看到她發(fā)的推特：“啊，我前天公園散步、昨天購(gòu)物、今天清理房間了！”。
那么我可以根據(jù)她發(fā)的推特推斷東京這三天的天氣。
4.1 參數(shù)整理
在這個(gè)例子里，顯狀態(tài)是活動(dòng)，隱狀態(tài)是天氣。
任何一個(gè)HMM都可以通過(guò)下列五元組來(lái)描述：
:param obs: 觀測(cè)序列
:param states: 隱狀態(tài)
:param start_p: 初始概率（隱狀態(tài)）
:param trans_p: 轉(zhuǎn)移概率（隱狀態(tài)）
:param emit_p: 發(fā)射概率 （隱狀態(tài)表現(xiàn)為顯狀態(tài)的概率）
這里設(shè)定下相關(guān)規(guī)則：
如果下雨，則公園散步概率=0.1，購(gòu)物概率=0.4，清理房間概率=0.5
如果天晴，則公園散步概率=0.6，購(gòu)物概率=0.3，清理房間概率=0.1
如果當(dāng)天天晴，則第二天天晴的概率=0.6，第二天下雨的概率=0.4
如果當(dāng)天下雨，則第二天天晴的概率=0.3，第二天下雨的概率=0.7
第一天天晴的概率為0.4，第一天下雨的概率為0.6
states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {
'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
}
emission_probability = {
'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}
4.2 Viterbi求解思路
她發(fā)的推特：“啊，我前天公園散步、昨天購(gòu)物、今天清理房間了！”
稍微講講思路：
定義V[時(shí)間][今天天氣] = 概率，注意今天天氣指的是，前幾天的天氣都確定下來(lái)了（概率最大）今天天氣是X的概率，這里的概率就是一個(gè)累乘的概率了。
因?yàn)榈谝惶煳业呐笥讶ド⒉搅?，所以?/p>
第一天下雨的概率V[第一天][下雨] = 0.6 * 0.1 = 0.06
第一天天晴的概率V[第一天][天晴] = 0.4 * 0.6 = 0.24。
從直覺(jué)上來(lái)看，因?yàn)榈谝惶炫笥殉鲩T了，她一般喜歡在天晴的時(shí)候散步，所以第一天天晴的概率比較大，數(shù)字與直覺(jué)統(tǒng)一了。
從第二天開(kāi)始，對(duì)于每種天氣Y，都有前一天天氣是X的概率 * X轉(zhuǎn)移到Y(jié)的概率 * Y天氣下朋友進(jìn)行這天這種活動(dòng)的概率。因?yàn)榍耙惶焯鞖釾有兩種可能，所以Y的概率有兩個(gè)，選取其中較大一個(gè)作為V[第二天][天氣Y]的概率，同時(shí)將今天的天氣加入到結(jié)果序列中。
比較V[最后一天][下雨]和[最后一天][天晴]的概率，找出較大的哪一個(gè)對(duì)應(yīng)的序列，就是最終結(jié)果。
運(yùn)行完成后根據(jù)Viterbi得到結(jié)果：
Sunny Rainy Rainy
