隱馬爾可夫模型

1、隱馬爾可夫模型基本概念

隱馬爾可夫模型是關(guān)于時(shí)序的概率模型，描述由一個(gè)隱藏的馬爾科夫鏈隨機(jī)生成不可觀測(cè)的狀態(tài)隨機(jī)序列需五，再由各個(gè)狀態(tài)生成一個(gè)觀測(cè)從而產(chǎn)生觀測(cè)隨機(jī)序列的過(guò)程。

隱馬爾可夫模型的形式定義如下：

設(shè) $Q$ 是所有可能狀態(tài)的集合轧坎， $V$ 是所有可能觀測(cè)的集合：

$Q=\{q_1,q_2,\dots,q_N\}\quad V=\{v_1,v_2,\dots,v_M\}$

其中 $N$ 為可能狀態(tài)數(shù)宏邮， $M$ 為可能觀測(cè)數(shù)。

$I$ 是長(zhǎng)度為 $T$ 的狀態(tài)序列缸血， $O$ 是對(duì)應(yīng)的觀測(cè)序列：

$I=(i_1,i_2,\dots,i_T)\quad O=(o_1,o_2,\dots,o_T)$

$A$ 是狀態(tài)轉(zhuǎn)移概率矩陣：

$A=[a_{ij}]_{N\times N}$

其中：

$a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$

$B$ 是觀測(cè)概率矩陣：

$B=[b_j(k)]_{N\times M}$

其中：

$b_j(k)=P(o_t=v_k|i_t=q_j)$

$\pi$ 是初始狀態(tài)概率向量：

$\pi=(\pi_i)$

其中：

$\pi_i=P(i_1=q_i)$

隱馬爾可夫模型由初始狀態(tài)概率向量 $\pi$ 蜜氨、狀態(tài)轉(zhuǎn)移概率矩陣 $A$ 和觀測(cè)概率矩陣 $B$ 決定。因此隱馬爾可夫模型 $\lambda$ 可表示為：

$\lambda=(A,B,\pi)$

具體來(lái)說(shuō)捎泻，長(zhǎng)度為 $T$ 的觀測(cè)序列的生成過(guò)程如下：按照初始狀態(tài)分布 $\pi$ 產(chǎn)生狀態(tài) $i_1$ 记劝，按狀態(tài) $i_t$ 的觀測(cè)概率分布 $b_{i_t}(k)$ 生成 $o_t$ ，按狀態(tài) $i_t$ 的狀態(tài)轉(zhuǎn)移概率分布 $\{a_{i_t i_{t+1}} \}$ 產(chǎn)生狀態(tài) $i_{t+1}$ 族扰，依次遞推厌丑。

由定義可知隱馬爾可夫模型的兩個(gè)基本假設(shè)：

（1）齊次馬爾可夫性假設(shè)定欧，即隱藏的馬爾科夫鏈在任意時(shí)刻 $t$ 的狀態(tài)只依賴于其前一時(shí)刻的狀態(tài)，與其他時(shí)刻狀態(tài)及觀測(cè)無(wú)關(guān)怒竿，也與時(shí)刻 $t$ 無(wú)關(guān)砍鸠。

（2）觀測(cè)獨(dú)立性假設(shè)，即任意時(shí)刻的觀測(cè)只依賴于該時(shí)刻的馬爾科夫鏈狀態(tài)耕驰，與其它觀測(cè)狀態(tài)無(wú)關(guān)爷辱。

隱馬爾可夫模型的三個(gè)基本問(wèn)題如下：

（1）概率計(jì)算問(wèn)題：給定模型 $\lambda=(A,B,\pi)$ 和觀測(cè)序列 $O=(o_1,o_2,\dots,o_T)$ ，計(jì)算在模型 $\lambda$ 下序列 $O$ 出現(xiàn)的概率 $P(O|\lambda)$ 朦肘。

（2）學(xué)習(xí)問(wèn)題：已知觀測(cè)序列 $O=(o_1,o_2,\dots,o_T)$ 饭弓，估計(jì)模型 $\lambda=(A,B,\pi)$ 參數(shù)，使得在該模型下觀測(cè)序列 $P(O|\lambda)$ 最大媒抠。

（3）預(yù)測(cè)問(wèn)題：已知模型 $\lambda=(A,B,\pi)$ 和觀測(cè)序列 $O=(o_1,o_2,\dots,o_T)$ 弟断，求使得 $P(I|O)$ 最大的狀態(tài)序列 $I=(i_1,i_2,\dots,i_T)$ 。

接下來(lái)分別闡述這三個(gè)問(wèn)題的解決方法。

2、概率計(jì)算算法

2.1兔朦、直接計(jì)算法

狀態(tài) $I=(i_1,i_2,\dots,i_T)$ 的概率是：

$P(I|\lambda)=\pi_{i_1}a_{i_1 i_2}\dots,a_{i_{T-1}i_T}$

對(duì)固定的 $I=(i_1,i_2,\dots,i_T)$ 觀測(cè)序列 $O=(o_1,o_2,\dots,o_T)$ 的概率是：

$P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)\dots,b_{i_T}(o_T)$

$O,I$ 同時(shí)出現(xiàn)的聯(lián)合概率為：

$P(O,I|\lambda)=P(O|I,\lambda)P(I|\lambda)$

從而：

$P(O|\lambda)=\sum_{I}P(O,I|\lambda)=\sum_{I}P(O|I,\lambda)P(I|\lambda)$

可以看到奔坟，上式是對(duì)所有可能的 $I$ 序列求和，而長(zhǎng)度為 $T$ 的 $I$ 序列的數(shù)量是 $O(N^T)$ 數(shù)量級(jí)的，而 $P(O,I|\lambda)$ 的計(jì)算量是 $O(T)$ 級(jí)別的，因此計(jì)算量為 $O(TN^T)$ ，非常大叔汁，這種算法在實(shí)際中不可行。

2.2检碗、前向算法

首先定義前向概率：給定隱馬爾可夫模型 $\lambda$ 据块，定義到時(shí)刻 $t$ 部分觀測(cè)序列為 $o_1,o_2,\dots,o_t$ 且狀態(tài)為 $q_i$ 的概率為前向概率，記作：

$\alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_i|\lambda)$

觀測(cè)序列概率的前向算法如下：

（1）初值：

$\alpha_1(i)=\pi_i b_i(o_1),\quad i=1,2,\dots,N$

（2）遞推后裸，對(duì) $t=1,2,\dots,T-1$ ：

$\alpha_{t+1}(i)=\lbrack\sum_{j=1}^N \alpha_t(j) a_{ji}\rbrack b_i(o_{t+1}),\quad i=1,2,\dots,N$

（3）終止：

$P(O|\lambda)=\sum_{i=1}^N \alpha_T(i)$

前向算法高效的關(guān)鍵是局部計(jì)算前向概率，然后利用路徑結(jié)構(gòu)將前向概率遞推到全局微驶，得到 $P(O|\lambda)$ 浪谴。前向概率算法計(jì)算量是 $O(TN^2)$ 級(jí)別的。

2.3因苹、后向算法

首先定義后向概率：給定隱馬爾可夫模型 $\lambda$ 苟耻，定義在時(shí)刻 $t$ 狀態(tài)為 $q_i$ 的條件下，從 $t+1$ 到 $T$ 部分觀測(cè)序列為 $o_{t+1},o_{t+2},\dots,o_T$ 的概率為后向概率扶檐，記作：

$\beta_t(i)=P(o_{t+1},o_{t+2},\dots,o_T|i_t=q_i,\lambda)$

觀測(cè)序列概率的后向算法如下：

（1）初值：

$\beta_T(i)=1,\quad i=1,2,\dots,N$

（2）遞推凶杖，對(duì) $t=T-1,T-2,\dots,1$ ：

$\beta_t(i)=\sum_{j=1}^N a_{ij}b_j (o_{t+1})\beta_{t+1}(j)$

（3）終止：

$P(O|\lambda)=\sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i)$

3、學(xué)習(xí)算法

3.1款筑、監(jiān)督學(xué)習(xí)方法

若有 $S$ 個(gè)長(zhǎng)度相同觀測(cè)序列和對(duì)應(yīng)狀態(tài)序列 $\{(O_1,I_1),(O_2,I_2),\dots,(O_S,I_S) \}$ 則可利用極大似然估計(jì)得到隱馬爾可夫模型參數(shù)：

設(shè)樣本中時(shí)刻 $t$ 處于狀態(tài) $i$ 時(shí)刻 $t+1$ 轉(zhuǎn)移到狀態(tài) $j$ 的頻數(shù)為 $A_{ij}$ 智蝠，那么狀態(tài)轉(zhuǎn)移概率 $a_{ij}$ 的估計(jì)為：

$\hat{a}_{ij}=\frac{A_{ij}}{\sum_{j=1}^N A_{ij}}$

設(shè)樣本中狀態(tài)為 $j$ 觀測(cè)為 $k$ 的頻數(shù)為 $B_{jk}$ 腾么，那么觀測(cè)概率 $b_j(k)$ 的估計(jì)為：

$\hat_j(k)=\frac{B_{jk}}{\sum_{k=1}^M B_{jk}}$

初始狀態(tài) $\pi_i$ 的估計(jì) $\hat{\pi}_i$ 為 $S$ 個(gè)樣本中初始狀態(tài)為 $q_i$ 的頻率杈湾。

3.2解虱、無(wú)監(jiān)督學(xué)習(xí)方法（Baum-Welch算法）

假設(shè)給定訓(xùn)練數(shù)據(jù)只包含 $S$ 個(gè)長(zhǎng)度為 $T$ 的觀測(cè)序列 $\{O_1,O_2,\dots,O_S \}$ 而沒有對(duì)應(yīng)狀態(tài)序列，我們可以把狀態(tài)數(shù)據(jù)看作不可觀測(cè)的隱數(shù)據(jù) $I$ 漆撞，則隱馬爾可夫模型事實(shí)上是一個(gè)含有隱變量的概率模型：

$P(O|\lambda)=\sum_I P(O|I,\lambda)P(I|\lambda)$

其參數(shù)可由EM算法實(shí)現(xiàn)殴泰。

4、預(yù)測(cè)算法

4.1浮驳、近似算法

近似算法的思想是悍汛，在每個(gè)時(shí)刻 $t$ 選擇在該時(shí)刻最有可能出現(xiàn)的狀態(tài) $i_t^*$ ，從而得到一個(gè)狀態(tài)序列 $I^*=(i_1^*,i_2^*,\dots,i_T^*)$ 至会。

近似算法的優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單离咐，缺點(diǎn)是不能保證預(yù)測(cè)的狀態(tài)序列整體是最有可能的狀態(tài)序列，因?yàn)轭A(yù)測(cè)的狀態(tài)序列可能有實(shí)際不發(fā)生的部分奋献，比如存在轉(zhuǎn)移概率為0的相鄰狀態(tài)健霹。盡管如此旺上，近似算法還是有用的瓶蚂。

4.2、維特比算法

維特比算法實(shí)際上是用動(dòng)態(tài)規(guī)劃解隱馬爾可夫模型預(yù)測(cè)問(wèn)題宣吱，即用動(dòng)態(tài)規(guī)劃求概率最大路徑（最優(yōu)路徑）窃这，此路徑對(duì)應(yīng)一個(gè)狀態(tài)序列。

定義在時(shí)刻 $t$ 狀態(tài)為 $i$ 的所有單個(gè)路徑 $(i_1,i_2,\dots,i_t)$ 中概率最大值為：

$\delta_t(i)=\max_{i_1,i_2,\dots,i_{t-1}}P(i_t=i,i_{t-1},\dots,i_1,o_t,o_{t-1},\dots,o_1|\lambda),\quad i=1,2,\dots,N$

由定義得遞推式：

$\begin{aligned} \delta_{t+1}(i)&=\max_{i_1,i_2,\dots,i_{t-1}}P(i_{t+1}=i,i_{t-1},\dots,i_1,o_t,o_{t-1},\dots,o_1|\lambda)\\ &=\max_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1}) \end{aligned}$

定義在時(shí)刻 $t$ 狀態(tài)為 $i$ 的所有單個(gè)路徑 $(i_1,i_2,\dots,i_{t-1},i)$ 中概率最大路徑的第 $t-1$ 個(gè)結(jié)點(diǎn)為：

$\psi_t(i)=arg\max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}],\quad i=1,2,\dots,N$

維特比算法如下：

（1）初始化：

$\delta_1(i)=\pi_i b_i(o_1),\quad i=1,2,\dots,N$

$\psi_1(i)=0,\quad i=1,2,\dots,N$

（2）遞推征候，對(duì) $t=2,3,\dots,T$ :

$\delta_{t}(i)=\max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]b_i(o_t),\quad i=1,2,\dots,N$

$\psi_t(i)=arg\max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}],\quad i=1,2,\dots,N$

（3）終止：

$P^*=\max_{1\leq i\leq N}\delta_T(i)$

$i_T^*=arg\max_{1\leq i\leq N}[\delta_T(i)]$

（4）回溯杭攻，對(duì) $t=T-1,T-2,\dots,1$ ：

$i_t^*=\psi_{t+1}(i_{t+1}^*)$

最優(yōu)路徑為 $I^*=(i_1^*,i_2^*,\dots,i_T^*)$

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市疤坝，隨后出現(xiàn)的幾起案子兆解，更是在濱河造成了極大的恐慌，老刑警劉巖跑揉，帶你破解...
沈念sama閱讀 218,941評(píng)論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件锅睛，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡历谍，警方通過(guò)查閱死者的電腦和手機(jī)现拒，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,397評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)望侈，“玉大人印蔬，你說(shuō)我怎么就攤上這事⊥蜒茫” “怎么了侥猬？”我有些...
開封第一講書人閱讀 165,345評(píng)論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵例驹，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我退唠，道長(zhǎng)眠饮，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,851評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任铜邮，我火速辦了婚禮仪召，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘松蒜。我一直安慰自己扔茅，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,868評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布秸苗。她就那樣靜靜地躺著召娜，像睡著了一般。火紅的嫁衣襯著肌膚如雪惊楼。梳的紋絲不亂的頭發(fā)上玖瘸，一...
開封第一講書人閱讀 51,688評(píng)論 1贊 305
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音檀咙，去河邊找鬼雅倒。笑死，一個(gè)胖子當(dāng)著我的面吹牛弧可，可吹牛的內(nèi)容都是我干的蔑匣。我是一名探鬼主播，決...
沈念sama閱讀 40,414評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼棕诵，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼裁良！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起校套，我...
開封第一講書人閱讀 39,319評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤价脾，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后笛匙，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體侨把，經(jīng)...
沈念sama閱讀 45,775評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,945評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年膳算，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了座硕。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,096評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡涕蜂，死狀恐怖华匾，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情，我是刑警寧澤蜘拉，帶...
沈念sama閱讀 35,789評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布萨西，位于F島的核電站，受9級(jí)特大地震影響旭旭，放射性物質(zhì)發(fā)生泄漏谎脯。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,437評(píng)論 3贊 331
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一持寄、第九天我趴在偏房一處隱蔽的房頂上張望源梭。院中可真熱鬧，春花似錦稍味、人聲如沸废麻。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,993評(píng)論 0贊 22
一樁弒父案模庐，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)烛愧。三九已至，卻和暖如春掂碱，著一層夾襖步出監(jiān)牢的瞬間怜姿，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,107評(píng)論 1贊 271
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工疼燥，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留沧卢，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,308評(píng)論 3贊 372
代替公主和親
正文我出身青樓悴了，卻偏偏與公主長(zhǎng)得像搏恤，于是被迫代替她去往敵國(guó)和親违寿。傳聞我的和親對(duì)象是個(gè)殘疾皇子湃交，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,037評(píng)論 2贊 355

隱馬爾可夫模型

1、隱馬爾可夫模型基本概念

2、概率計(jì)算算法

2.1兔朦、直接計(jì)算法

2.2检碗、前向算法

2.3因苹、后向算法

3、學(xué)習(xí)算法

3.1款筑、監(jiān)督學(xué)習(xí)方法

3.2解虱、無(wú)監(jiān)督學(xué)習(xí)方法（Baum-Welch算法）

4、預(yù)測(cè)算法

4.1浮驳、近似算法

4.2、維特比算法

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