HMM(隱馬爾可夫模型)

目錄

【數(shù)之道 29】"隱馬爾可夫模型"HMM是什么膨疏?了解它只需5分鐘一睁!_嗶哩嗶哩_bilibili
這個(gè)視頻講的通俗易懂

  1. 實(shí)例帶入
  2. HMM解決的問題
  3. HMM數(shù)學(xué)相關(guān)思想
    3.1 知道所有狀態(tài),計(jì)算特定結(jié)果概率
    3.2 隱含狀態(tài)鏈
    3.3 拓展思想
  4. 生活例子解釋
    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。


image.png

假設(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皆刺。

image.png

對(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é)果的概率丈莺。


image.png

解法無非就是概率相乘:


image.png
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)單的列子。

如果我們只擲一次骰子:


image.png

看到結(jié)果為1碴倾。對(duì)應(yīng)的最大概率骰子序列就是D4逗噩,因?yàn)镈4產(chǎn)生1的概率是1/4,高于1/6和1/8跌榔。

把這個(gè)情況拓展异雁,我們擲兩次骰子:

image.png

結(jié)果為1,6僧须。這時(shí)問題變得復(fù)雜起來纲刀,我們要計(jì)算三個(gè)值,分別是第二個(gè)骰子是D6担平,D4示绊,D8的最大概率。

顯然暂论,要取到最大概率面褐,第一個(gè)骰子必須為D4。這時(shí)取胎,第二個(gè)骰子取到D6的最大概率是:


image.png

同樣的展哭,我們可以計(jì)算第二個(gè)骰子是D4或D8時(shí)的最大概率。

我們發(fā)現(xiàn)闻蛀,第二個(gè)骰子取到D6的概率最大匪傍。而使這個(gè)概率最大時(shí),第一個(gè)骰子為D4觉痛。

所以最大概率骰子序列就是D4 D6役衡。

繼續(xù)拓展,我們擲三次骰子:


image.png

同樣秧饮,我們計(jì)算第三個(gè)骰子分別是D6映挂,D4泽篮,D8的最大概率。我們?cè)俅伟l(fā)現(xiàn)柑船,要取到最大概率帽撑,第二個(gè)骰子必須為D6。這時(shí)鞍时,第三個(gè)骰子取到D4的最大概率是:


image.png

同上亏拉,我們可以計(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é)果是:


image.png

要算用正常的三個(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)距帅。

首先,如果我們只擲一次骰子:

image.png

看到結(jié)果為1括堤。產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算碌秸,總概率為0.18(13/72):


image.png

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


image.png

看到結(jié)果為1悄窃,6讥电。產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算,總概率為0.02(91/5184):
image.png

繼續(xù)拓展轧抗,我們擲三次骰子:
image.png

看到結(jié)果為1恩敌,6,3.產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算横媚,總概率為0.003(1183/373248):


image.png

同樣的潮剪,我們一步一步的算,有多長(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)的概率)
image.png

這里設(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
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末薪铜,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子梨州,更是在濱河造成了極大的恐慌痕囱,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,277評(píng)論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件暴匠,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡傻粘,警方通過查閱死者的電腦和手機(jī)每窖,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,689評(píng)論 3 393
  • 文/潘曉璐 我一進(jìn)店門帮掉,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人窒典,你說我怎么就攤上這事蟆炊。” “怎么了瀑志?”我有些...
    開封第一講書人閱讀 163,624評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵涩搓,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我劈猪,道長(zhǎng)昧甘,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,356評(píng)論 1 293
  • 正文 為了忘掉前任战得,我火速辦了婚禮充边,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘常侦。我一直安慰自己浇冰,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,402評(píng)論 6 392
  • 文/花漫 我一把揭開白布聋亡。 她就那樣靜靜地躺著肘习,像睡著了一般。 火紅的嫁衣襯著肌膚如雪坡倔。 梳的紋絲不亂的頭發(fā)上漂佩,一...
    開封第一講書人閱讀 51,292評(píng)論 1 301
  • 那天,我揣著相機(jī)與錄音致讥,去河邊找鬼仅仆。 笑死,一個(gè)胖子當(dāng)著我的面吹牛垢袱,可吹牛的內(nèi)容都是我干的墓拜。 我是一名探鬼主播,決...
    沈念sama閱讀 40,135評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼请契,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼咳榜!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起爽锥,我...
    開封第一講書人閱讀 38,992評(píng)論 0 275
  • 序言:老撾萬榮一對(duì)情侶失蹤涌韩,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后氯夷,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體臣樱,經(jīng)...
    沈念sama閱讀 45,429評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,636評(píng)論 3 334
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了雇毫。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片玄捕。...
    茶點(diǎn)故事閱讀 39,785評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖棚放,靈堂內(nèi)的尸體忽然破棺而出枚粘,到底是詐尸還是另有隱情,我是刑警寧澤飘蚯,帶...
    沈念sama閱讀 35,492評(píng)論 5 345
  • 正文 年R本政府宣布馍迄,位于F島的核電站,受9級(jí)特大地震影響局骤,放射性物質(zhì)發(fā)生泄漏攀圈。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,092評(píng)論 3 328
  • 文/蒙蒙 一庄涡、第九天 我趴在偏房一處隱蔽的房頂上張望量承。 院中可真熱鬧,春花似錦穴店、人聲如沸撕捍。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,723評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽忧风。三九已至,卻和暖如春球凰,著一層夾襖步出監(jiān)牢的瞬間狮腿,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,858評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工呕诉, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留缘厢,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,891評(píng)論 2 370
  • 正文 我出身青樓甩挫,卻偏偏與公主長(zhǎng)得像贴硫,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子伊者,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,713評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容