目錄
【數(shù)之道 29】"隱馬爾可夫模型"HMM是什么膨疏?了解它只需5分鐘一睁!_嗶哩嗶哩_bilibili
這個(gè)視頻講的通俗易懂
- 實(shí)例帶入
- HMM解決的問題
- 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è)骰子是我們平常見的骰子(稱這個(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è)我們開始擲骰子芯义,我們先從三個(gè)骰子里挑一個(gè)哈垢,挑到每一個(gè)骰子的概率都是1/3。
然后我們擲骰子扛拨,得到一個(gè)數(shù)字耘分,1,2绑警,3求泰,4,5计盒,6渴频,7,8中的一個(gè)章郁。
不停的重復(fù)上述過程枉氮,我們會(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ù)字叫做可見狀態(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)鏈。
隱含狀態(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榴嗅。
同樣的妄呕,盡管可見狀態(tài)之間沒有轉(zhuǎn)換概率,但是隱含狀態(tài)和可見狀態(tài)之間有一個(gè)概率叫做輸出概率(emission probability)嗽测。就我們的例子來說:
四面骰(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)過手腳的六面骰子情屹,擲出來是1的概率更大坪仇,是1/2,擲出來是2垃你,3椅文,4喂很,5,6的概率是1/10皆刺。
對(duì)于HMM來說少辣,如果提前知道所有隱含狀態(tài)之間的轉(zhuǎn)換概率、所有隱含狀態(tài)的序列和所有隱含狀態(tài)到所有可見狀態(tài)之間的輸出概率羡蛾,做模擬是相當(dāng)容易的漓帅。
但是應(yīng)用HMM模型時(shí)候呢,往往是缺失了一部分信息的:
有時(shí)候你知道骰子有幾種痴怨,每種骰子是什么忙干,但是不知道擲出來的骰子序列;
有時(shí)候你只是看到了很多次擲骰子的結(jié)果浪藻,剩下的什么都不知道捐迫。
如果應(yīng)用算法去估計(jì)這些缺失的信息,就成了一個(gè)很重要的問題爱葵。
HMM解決的問題
和HMM模型相關(guān)的算法主要分為三類施戴,分別解決三種問題:
知道骰子有幾種(隱含狀態(tài)數(shù)量),每種骰子是什么(輸出概率)萌丈,根據(jù)擲骰子擲出的結(jié)果(可見狀態(tài)鏈)赞哗,我想知道每次擲出來的都是哪種骰子(隱含狀態(tài)鏈)。
知道骰子有幾種(隱含狀態(tài)數(shù)量)浓瞪,每種骰子是什么(轉(zhuǎn)換概率)懈玻,根據(jù)擲骰子擲出的結(jié)果(可見狀態(tài)鏈)巧婶,我想知道擲出這個(gè)結(jié)果的概率乾颁。
知道骰子有幾種(隱含狀態(tài)數(shù)量),不知道每種骰子是什么(轉(zhuǎn)換概率)艺栈,觀測(cè)到很多次擲骰子的結(jié)果(可見狀態(tài)鏈)英岭,我想反推出每種骰子是什么(轉(zhuǎn)換概率)。
HMM數(shù)學(xué)相關(guān)思想
3.1 知道所有狀態(tài)湿右,計(jì)算特定結(jié)果概率
考慮到這里我們并不是真的要學(xué)會(huì)HMM背后的數(shù)學(xué)算法诅妹,所以這里我用一個(gè)最簡(jiǎn)單問題來和大家一起思考這個(gè)過程:
知道骰子有幾種,每種骰子是什么毅人,每次擲的都是什么骰子吭狡,根據(jù)擲骰子擲出的結(jié)果,求產(chǎn)生這個(gè)結(jié)果的概率丈莺。
解法無非就是概率相乘:
3.2 隱含狀態(tài)鏈
問題:知道有三個(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è)情況拓展异雁,我們擲兩次骰子:
結(jié)果為1,6僧须。這時(shí)問題變得復(fù)雜起來纲刀,我們要計(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 拓展思想
比如說你懷疑自己的六面骰被賭場(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)距帅。
首先,如果我們只擲一次骰子:
看到結(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)的馬爾可夫鏈總能算出來的抗碰。用同樣的方法,也可以算出不正常的六面骰和另外兩個(gè)正常骰子擲出這段序列的概率绽乔,然后我們比較一下這兩個(gè)概率大小叁征,就能知道你的骰子是不是被人換了。
4. 生活例子解釋
舉一個(gè)經(jīng)典的例子:一個(gè)東京的女孩每天根據(jù)天氣 {下雨应役,天晴} 決定當(dāng)天的活動(dòng) {公園散步,購物,清理房間} 中的一種诊胞。
我們每天只能在twitter上看到她發(fā)的推特:“啊,我前天公園散步睦授、昨天購物两芳、今天清理房間了!”去枷。
那么我可以根據(jù)她發(fā)的推特推斷東京這三天的天氣怖辆。
4.1 參數(shù)整理
在這個(gè)例子里,顯狀態(tài)是活動(dòng)删顶,隱狀態(tài)是天氣竖螃。
任何一個(gè)HMM都可以通過下列五元組來描述:
: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逗余,購物概率=0.4特咆,清理房間概率=0.5
如果天晴,則公園散步概率=0.6录粱,購物概率=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ā)的推特:“啊些楣,我前天公園散步脂凶、昨天購物、今天清理房間了愁茁!”
稍微講講思路:
定義V[時(shí)間][今天天氣] = 概率蚕钦,注意今天天氣指的是,前幾天的天氣都確定下來了(概率最大)今天天氣是X的概率鹅很,這里的概率就是一個(gè)累乘的概率了嘶居。
因?yàn)榈谝惶煳业呐笥讶ド⒉搅耍裕?/p>
第一天下雨的概率V[第一天][下雨] = 0.6 * 0.1 = 0.06
第一天天晴的概率V[第一天][天晴] = 0.4 * 0.6 = 0.24促煮。
從直覺上來看邮屁,因?yàn)榈谝惶炫笥殉鲩T了,她一般喜歡在天晴的時(shí)候散步菠齿,所以第一天天晴的概率比較大佑吝,數(shù)字與直覺統(tǒng)一了。
從第二天開始绳匀,對(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