?

HMM的模型

???????圖1

????? 如上圖所示，白色那一行描述由一個(gè)隱藏的馬爾科夫鏈生成不可觀測(cè)的狀態(tài)隨機(jī)序列，藍(lán)紫色那一行是各個(gè)狀態(tài)生成可觀測(cè)的隨機(jī)序列

????? 話說，上面也是個(gè)貝葉斯網(wǎng)絡(luò)，而貝葉斯網(wǎng)絡(luò)中有這么一種，如下圖：

??????????

????? 代表：c確定時(shí)a和b獨(dú)立。(c為實(shí)心圓代表：c已經(jīng)被確定)

????? 這時(shí)，如果把z1看成a，x1看成b，z2看成c的話，則因?yàn)榈谝粋€(gè)圖的z1是不可觀測(cè)的(所以z1是空心圓)，也就是沒確定，則x1和z2就一定有聯(lián)系。

????? 進(jìn)一步，如果把z2、x2合在一起看成c的話，則x1和z2、x2就一定有聯(lián)系，則x1和x2有聯(lián)系(不獨(dú)立)。

????? 推廣之后：x2和x3不獨(dú)立，x1和x3也不獨(dú)立，于是xn們互相不獨(dú)立。

PS： LDA假定文章中的詞與詞之間互相獨(dú)立，而HMM中是所有的觀測(cè)互相均不獨(dú)立。 所以，對(duì)于一篇Machine Learn的文章，LDA會(huì)吧“機(jī)器”和“學(xué)習(xí)”分成兩個(gè)詞，而HMM會(huì)將其視為一個(gè)詞。

?

HMM的確定

?

初始概率分布

????? z1可能是狀態(tài)1，狀態(tài)2 ... 狀態(tài)n，于是z1就有個(gè)N點(diǎn)分布：

Z1	狀態(tài)1	狀態(tài)2	...	狀態(tài)n
概率	P1	P2	...	Pn

????? 即：Z1對(duì)應(yīng)個(gè)n維的向量。

??????上面這個(gè)n維的向量就是初始概率分布，記做π。

?

狀態(tài)轉(zhuǎn)移矩陣

????? 但Z2就不能簡(jiǎn)單的“同上”完事了，因?yàn)閆2和Z1不獨(dú)立，所以Z2是狀態(tài)1的概率有：Z1是狀態(tài)1時(shí)Z2是狀態(tài)1，Z1是狀態(tài)2時(shí)Z2是狀態(tài)1,..., Z1是狀態(tài)n時(shí)Z2是狀態(tài)1，于是就是下面的表

Z2 Z1	狀態(tài)1	狀態(tài)2	...	狀態(tài)n
狀態(tài)1	P11	P12	...	P1n
狀態(tài)2	P21	P22	...	P2n
...	...	...	...	...
狀態(tài)n	Pn1	Pn2	...	Pnn

???????即：Z1->Z2對(duì)應(yīng)個(gè)n*n的矩陣。

???????同理：Z_i?-> Z_i+1對(duì)應(yīng)個(gè)n*n的矩陣。

??????上面這些n*n的矩陣被稱為狀態(tài)轉(zhuǎn)移矩陣_，用A_n*n表示。

????? 當(dāng)然了，真要說的話，Z_i?-> Z_i+1的狀態(tài)轉(zhuǎn)移矩陣一定都不一樣，但在實(shí)際應(yīng)用中一般將這些狀態(tài)轉(zhuǎn)移矩陣定為同一個(gè)，即：只有一個(gè)狀態(tài)轉(zhuǎn)移矩陣。

??????圖1的第一行就搞定了，下面是第二行。

?

觀測(cè)矩陣

????? 如果對(duì)于zi有：狀態(tài)1, 狀態(tài)2, ..., 狀態(tài)n，那zi的每一個(gè)狀態(tài)都會(huì)從下面的m個(gè)觀測(cè)中產(chǎn)生一個(gè)：觀測(cè)1, 觀測(cè)2, ..., 觀測(cè)m，所以有如下矩陣：

X Z	觀測(cè)1	觀測(cè)2	...	觀測(cè)m
狀態(tài)1	P11	P12	...	P1m
狀態(tài)2	P21	P22	...	P2m
...	...	...	...	...
狀態(tài)n	Pn1	Pn2	...	Pnm

??????這可以用一個(gè)n*m的矩陣表示，也就是觀測(cè)矩陣，記做B_n*m。

?

????? 由于HMM用上面的π，A，B就可以描述了，于是我們就可以說：HMM由初始概率分布π、狀態(tài)轉(zhuǎn)移概率分布A以及觀測(cè)概率分布B確定，為了方便表達(dá)，把A, B, π 用 λ 表示，即：

????? ????? λ = (A, B, π)

例子

????? 假設(shè)我們相對(duì)如下這行話進(jìn)行分詞：

?????????? 歡迎來到我的博客

????? 再假設(shè)我們是這樣分的：找到“終止字”，然后根據(jù)終止字來分詞。即：對(duì)于這行字，“迎、到、我、的、客”是終止字，于是最終這么分詞：歡迎/來到/我/的/博客

????? 下面用上面的知識(shí)對(duì)這個(gè)例子建立HMM的A, B, π：

?????? 初始概率分布的確定：

?????????? 1，對(duì)于每個(gè)樣本，我們的目標(biāo)是確定其是不是“終止字”，因此對(duì)于每個(gè)樣本，其狀態(tài)只有n=2個(gè)：狀態(tài)1 -- 是、狀態(tài)2 -- 不是。

????? ????? 2，因此初始概率分布π為：

???????????????? π = {p1，p2}

????? ?????????? P1：整個(gè)句子中第一個(gè)字是非終止字的概率

????? ????? ????? P2：整個(gè)句子中第一個(gè)字是終止字的概率

??????狀態(tài)轉(zhuǎn)移矩陣的確定：

?????????? 剛才已經(jīng)知道狀態(tài)有n=2個(gè)，于是狀態(tài)轉(zhuǎn)移矩陣就立馬得出了，即狀態(tài)轉(zhuǎn)移矩陣是個(gè)n*n的矩陣，如下：

???????????????? A=

?????????? ????? p11：非終止字 -> 非終止字的概率。

????? ?????????? p12：非終止字 -> 終止字的概率。

????? ?????????? p21：終止字 -> 非終止字的概率。

????? ????? ????? p22：終止字 -> 終止字的概率。

?????? 觀測(cè)矩陣的確定：

?????????? 如果我們的目標(biāo)文字使用Unicode編碼，那么上面的任何一個(gè)字都是0~65535中的一個(gè)數(shù)，于是我們的觀測(cè)就會(huì)有m=65536個(gè)，于是觀測(cè)矩陣就是個(gè)n*m的矩陣，如下：

???????????????? B=

????? ?????????? p1,0：Unicode編碼中0對(duì)應(yīng)的漢字是非終止字的概率

????? ?????????? p1,65535：Unicode編碼中65535對(duì)應(yīng)的漢字是非終止字的概率

????? ?????????? p2,0：Unicode編碼中0對(duì)應(yīng)的漢字是終止字的概率

????? ?????????? p2,65535：Unicode編碼中65535對(duì)應(yīng)的漢字是終止字的概率

????? ????? PS：為什么x會(huì)有65535個(gè)觀測(cè)啊？“歡迎來到我的博客”這個(gè)明明只有8個(gè)字。原因是因?yàn)檎嬲腍MM面臨的情況，即：現(xiàn)有了 Z1=“非終止字”這個(gè)狀態(tài)，然后根據(jù)這個(gè)狀態(tài)從65535個(gè)字中選出x1=“歡”這個(gè)字，然后根據(jù)狀態(tài)轉(zhuǎn)移矩陣，下一次轉(zhuǎn)移到了Z2 =“終止字”，然后根據(jù)Z2從65535個(gè)字中選出了x2=“迎”這個(gè)字，這樣，最終生成了這句話。

?

HMM的兩個(gè)基本性質(zhì)

?齊次假設(shè)

????? 當(dāng)前狀態(tài)之和上一個(gè)狀態(tài)有關(guān)系，用公式表示的話就是：

?????????? P(z_t|z_t-1,x_t-1, z_t-2, x_t-2, ..., z₁, x₁)= P(z_t?| z_t-1)

?觀測(cè)獨(dú)立性假設(shè)

????? 所有的觀測(cè)之間是互相獨(dú)立的，某個(gè)觀測(cè)之和生成它的狀態(tài)有關(guān)系，即：

?????????? P(x_t|z_t,x_t, z_t-1, x_t-1, z_t-2, x_t-2,..., z₁, x₁) = P(x_t?| z_t)

?

PS：在一開始時(shí)說x1和z2、x2不獨(dú)立，怎么在這里又說x1和x2獨(dú)立呢？其實(shí)真嚴(yán)格追究的話x1和x2的確不互相獨(dú)立，因?yàn)閤1是被z1生成的，x2是被z2生成的， 但z2的形成受z1影響，所以x1和x2一定也會(huì)有聯(lián)系，但是為了研究和應(yīng)用的方便，就假設(shè)：生成x1的z1和生成x2的z2不獨(dú)立，但x1和x2獨(dú)立。

?

HMM的三個(gè)問題

????? 現(xiàn)在有幾個(gè)問題：

?????????? 1，知道HMM的參數(shù) λ = (A, B, π) 和觀測(cè)序列O = {o₁,o₂, ..., o_T} ，如何計(jì)算模型 λ 下觀測(cè)序列O出現(xiàn)的概率P(O | λ)。

?????????? 2，HMM的參數(shù)如何確定？

???????????????? 比如：對(duì)于剛才的中文分詞的小例子。

??????????????????????初始概率分布π好確定：是不是終結(jié)詞的概率各是0.5。

??????????????????????觀測(cè)矩陣B也好確定：1/65535嘛

???????????????? 但狀態(tài)轉(zhuǎn)移矩陣怎么確定？我怎么知道下個(gè)詞是終結(jié)詞的概率是多少？

?

?????????? 3，知道HMM的參數(shù) λ = (A, B, π) 和觀測(cè)序列O = {o₁,o₂, ..., o_T}，如何計(jì)算給定觀測(cè)序列條件概率P(I|O,? λ )最大的狀態(tài)序列I，即：

???????????????? 對(duì)于中文分詞，我想到底如何分的詞。

????? 上面三個(gè)問題：

???????????第一個(gè)問題被稱為：概率計(jì)算問題。

???????????????????? 解決辦法：前向-后向算法(一種動(dòng)態(tài)規(guī)劃算法)。

???????????第二個(gè)問題被稱為：學(xué)習(xí)問題。

???????????????????? 解決辦法：如果狀態(tài)序列已知，那用最大似然估計(jì)就好了，但HMM的狀態(tài)序列未知，即含有隱變量，所以要使用Baum-welch算法(其實(shí)其本質(zhì)就是EM算法)。

???????????第三個(gè)問題被稱為：預(yù)測(cè)問題/解碼問題。

???????????????????? 解決辦法：Viterbi算法(一種動(dòng)態(tài)規(guī)劃算法)。

概率計(jì)算問題

????? 該問題有兩種解決辦法：

?????????? 1，直接/暴力算法。

?????????? 2，前向算法/后向算法。

????? 而上面兩個(gè)算法中的“暴力方法”是實(shí)際應(yīng)用中絕不會(huì)被使用的。

????? Q：那為什么還說這玩意！（踹）

????? A：理解了直接/暴力算法可以幫助你推導(dǎo)Baum-welch算法。（回踹！）

?直接/暴力計(jì)算法

????? 問題：已知HMM的參數(shù) λ，和觀測(cè)序列O = {o₁, o₂, ...,o_T}，求P(O|λ)

????? 思想核心：大力出奇跡。

????? 思路：

?????????? 1，列舉所有可能的長(zhǎng)度為T的狀態(tài)序列I = {i₁, i₂, ..., i_T}；

?????????? 2，求各個(gè)狀態(tài)序列I與觀測(cè)序列 的聯(lián)合概率P(O,I|λ)；

?????????? 3，所有可能的狀態(tài)序列求和∑_I P(O,I|λ)得到P(O|λ)。

????? 步驟：

?????????? 1，最終目標(biāo)是求O和I同時(shí)出現(xiàn)的聯(lián)合概率，即：

???????????????? P(O,I|λ)= P(O|I, λ)P(I|λ)

?????????? 那就需要求出P(O|I, λ) 和 P(I|λ)。

?????????? 2，求P(I|λ) ，即狀態(tài)序列I = {i₁,i₂, ..., i_T} 的概率：

?????????? ????? 2.1，P(I|λ) = P(i₁,i₂, ..., i_T?|λ)

????????????????????? =P(i₁?|λ)P(i₂, i₃, ..., i_T?|λ)

????????????????????? =P(i₁?|λ)P(i₂?| i_1,?λ)P(i₃, i₄, ..., i_T?|λ)

????????????????????? =......

????????????????????? =P(i₁?|λ)P(i₂?| i_1,?λ)P(i₃?| i_2,?λ)...P(i_T?| i_T-1, λ)

???????????????? 而上面的P(i₁?|λ) 是初始為狀態(tài)i₁的概率，P(i₂?| i_1,?λ) 是從狀態(tài)i1轉(zhuǎn)移到i2的概率，其他同理，于是分別使用初始概率分布π 和狀態(tài)轉(zhuǎn)移矩陣A，就得到結(jié)果：

????????????????

???????????????? PS：上面的a_i1i2代表A的第i₁行第i₂列。

?

?????????? 3，P(O|I, λ)，即對(duì)固定的狀態(tài)序列I，觀測(cè)序列O的概率是：

????????????????

?????????? 4，代入第一步求出P(O,I|λ)。

?????????? 5，對(duì)所有可能的狀態(tài)序列I求和得到觀測(cè)序列O的概率P(O|λ)：

??????????

?

????? 時(shí)間復(fù)雜度：

?????????? 每個(gè)時(shí)刻有n個(gè)狀態(tài)，一共有t個(gè)時(shí)刻，而根據(jù)上面的第5步可以知道每個(gè)時(shí)刻需要乘2T-1次，所以時(shí)間復(fù)雜度是：O((2T-1)n^T)

?前向算法/后向算法

前向概率-后向概率

????? 如下圖所示：

????? 第一行是觀測(cè)不到的狀態(tài)序列，第二行是可以觀測(cè)到的觀測(cè)序列。

??????前向概率的定義是：當(dāng)?shù)趖個(gè)時(shí)刻的狀態(tài)為i時(shí)，前面的時(shí)刻分別觀測(cè)到y(tǒng)₁,y₂, ..., y_t的概率，即：

??????????

??????后向概率的定義是：當(dāng)?shù)趖個(gè)時(shí)刻的狀態(tài)為i時(shí)，后面的時(shí)刻分別觀測(cè)到y(tǒng)_t+1,y_t+2, ..., y_T的概率，即：

??????????

前向算法

????? 如果令前向概率中的t=T，即：

?????????? α_i(T) = p(y₁,y₂, ..., y_T, q_T?= i | λ)

????? 那這就意味著，最后一個(gè)時(shí)刻位于第i號(hào)狀態(tài)時(shí)，觀測(cè)到y(tǒng)₁, y₂, ..., y_T的概率，這不就是“直接/暴力計(jì)算法”中第4步求出來的P(O,I|λ) 嘛。

????? 因此，如果對(duì) α_i(T) 的i求和，即：

?????????? α₁(T) +α₂(T) + ...+ α_n(T)??式1

????? 那就是觀測(cè)序列O的概率P(O|λ)。

????? 那么如何算α₁(T) +α₂(T) + ...+ α_n(T)？

????? 這樣想：

?????????? 嗯..如果能算出第T-1時(shí)刻的前向概率，即α₁(T-1) +α₂(T-1) + ... + α_n(T-1) 的話，那就能算出式1了(HMM的參數(shù)知道了，根據(jù)參數(shù)不就得了)。

?????????? 進(jìn)一步，如果能算出T-2時(shí)刻的前向概率，那就能得出T-1時(shí)刻的，進(jìn)而就得出時(shí)刻T的了。

?????????? 按照這個(gè)思路：啊！我只要算出1時(shí)刻的前向概率不就能算出結(jié)果了！

????? 剛才得到了有趣的結(jié)果，即：我求出第一個(gè)1時(shí)刻的前向概率 α_i(1) 后就等于求出最終結(jié)果了，那 α_i(1) 是啥？

????? 不就是第一個(gè)時(shí)刻狀態(tài)為第i號(hào)狀態(tài)時(shí)觀測(cè)到y(tǒng)₁的概率嗎，即：

?????????? α_i(1) = P(y₁,q₁=i | λ)

????? 而第一個(gè)時(shí)刻狀態(tài)為第i號(hào)狀態(tài)的概率是π_i，在第i號(hào)狀態(tài)時(shí)得到y(tǒng)1這個(gè)觀測(cè)的概率是B_iy1，于是：

???????????α_i(1) =π_i* B_iy1

????? PS：因?yàn)椴恢喇?dāng)前是幾號(hào)狀態(tài)，所以為了以后的步驟，這里需要將所有的狀態(tài)都算出來，即：計(jì)算出所有的 α₁(1)? ~? α_i(1)

????? 好了，第一個(gè)時(shí)刻已經(jīng)求出來了，我們就向后推。

????? 假設(shè)現(xiàn)在到第t個(gè)時(shí)刻了，而第t個(gè)時(shí)刻的狀態(tài)是狀態(tài)j，那我想求時(shí)刻t+1狀態(tài)為i的前向概率怎么求，這樣求：

?????? 時(shí)刻t+1的前向概率的 α_i(t+1) 的求法就是：t時(shí)刻的狀態(tài)轉(zhuǎn)移到t+1時(shí)刻的狀態(tài)的概率對(duì)所有狀態(tài)求和 * t時(shí)刻的狀態(tài)得到觀測(cè)的概率，換句話說就是：t時(shí)刻的前向概率對(duì)所有的狀態(tài)求和 * t時(shí)刻的狀態(tài)得到觀測(cè)的概率。

????? 即：

???????????a_i(t+1) = (∑_{_j}?a_j(t)a_ji)b_iy(t+1)

????? 解釋一下：

?????????? 首先，時(shí)刻t時(shí)狀態(tài)為j的前向概率是a_j(t)。

?????????? 現(xiàn)在時(shí)刻t狀態(tài)為j的概率知道了，那乘上狀態(tài)j轉(zhuǎn)移到狀態(tài)i的轉(zhuǎn)移概率就是時(shí)刻t+1時(shí)狀態(tài)為i的概率，即 a_j(t)a_ji?。

?????????? 但狀態(tài)是不可觀測(cè)的啊，所有我們要計(jì)算時(shí)刻t時(shí)所有狀態(tài)的情況，于是要對(duì)j求和，即：∑_{_j}?a_j(t) a_ji，這才是t時(shí)刻的狀態(tài)轉(zhuǎn)移到t+1時(shí)刻狀態(tài)的總概率。

?????????? 但這樣還沒完，因?yàn)檫€要由狀態(tài)得到觀測(cè)，所以還要在乘上狀態(tài)i得到觀測(cè)y_t+1的概率，于是就是上面的式子了。

????? 現(xiàn)在a_i(t+1) 知道怎么求了，那不就是所有的的前向概率都知道怎么求了，于是利用剛才的結(jié)論：P(O|λ) = α₁(T) +α₂(T) + ... + α_n(T)，不就求出觀測(cè)序列O的概率P(O|λ)了，即：

???????????P(O|λ) =∑_i α_i(T)

????? OK，前向算法說完了，下面總結(jié)下。

?

前向算法總結(jié)

?????? 初值：α_i(1) =π_i* B_iy1

?????? 遞推：對(duì)于t = 1, 2, …,T-1

a_i(t+1) = (∑_{_j}?a_j(t)a_ji)b_iy(t+1)

?????? 最終：P(O|λ) =∑_i α_i(T)

???????PS：這里的 α_i(t) 中i表示第i號(hào)狀態(tài)，t表示第t時(shí)刻。有的教程中會(huì)把i和t位置調(diào)換一下，變成 α_t(i)，其實(shí)都一樣。

?

前向算法例子

????? 假設(shè)有3個(gè)盒子，編號(hào)為1,2,3，每個(gè)盒子都裝有紅白兩種顏色的小球，數(shù)目如下：

??????????

盒子號(hào)	1	2	3
紅球數(shù)	5	4	7
白球數(shù)	5	6	3

????? 然后按照下面的方法抽取小球，來得到球顏色的觀測(cè)序列：

?????????? 1，按照 π=(0.2, 0.4, 0.4) 的概率選擇1個(gè)盒子，從盒子隨機(jī)抽出

1個(gè)球，記錄顏色后放回盒子；

2，按照下圖A選擇新的盒子，按照下圖B抽取球，重復(fù)上述過程；

PS：

A的第i行是選擇到第i號(hào)盒子，第j列是轉(zhuǎn)移到j(luò)號(hào)盒子，如：第一行第二列的0.2代表：上一次選擇1號(hào)盒子后這次選擇2號(hào)盒子的概率是0.2。

B的第i行是選擇到第i號(hào)盒子，第j列是抽取到j(luò)號(hào)球，如：第二行第一列的0.4代表：選擇了2號(hào)盒子后抽取紅球的概率是0.4。

?????? 求：得到觀測(cè)序列“紅白紅”的概率是多少？

?????? 解：

1，明確已知：HMM模型的參數(shù)已經(jīng)如上圖所示了，那我們就需要再明確兩件事：HMM中那“看不見的狀態(tài)”和“可見的觀測(cè)”分別是什么。

?????????? “可見的觀測(cè)”根據(jù)題目可知是：y =“紅白紅”， “看不見的狀態(tài)”就是這三次分別選擇了什么盒子，且一共有3個(gè)狀態(tài)：選中1號(hào)盒子、選中2號(hào)盒子、選中3號(hào)盒子。

?????????? 2，根據(jù)前向算法，第一步計(jì)算 α_i(1)，這很簡(jiǎn)單：

???????????????? α_{i =1}?(t=1) 即時(shí)刻1時(shí)位于狀態(tài)“選中1號(hào)盒子”的前向概率，所以：α₁(1) =“選中1號(hào)盒子”*“選中紅球” = π₀* B₁₀= 0.2*0.5 = 0.1

???????????????? 同理：α₂(1) =0.4*0.4 = 0.16，α₃(1) = 0.4*0.7 = 0.28。

?????????? 3，計(jì)算 α_i(2)：

???????????????? 根據(jù)公式：

α₁(2) = (∑_j α₁(2)α_j1) b_1y2

= (0.1*0.5 + 0.16*0.3 + 0.28*0.2) * 0.5

=0.077

α₂(2) = 0.1104

α₃(2) = 0.0606

?????????? 4，同α_i(2)，計(jì)算α_i(3)：

???????????????? α₁(3) =0.04187

???????????????? α₂(3) =0.03551

???????????????? α₃(3) =0.05284

?????????? 5，最終

P(O|λ) = ∑_i α_i(3)

= 0.04187 + 0.03551 + 0.05284

= 0.13022

后向算法

????? 有了前向算法的基礎(chǔ)，后向算法就好說了，因?yàn)榫褪乔跋蛩惴ǖ姆催^來：先計(jì)算最后一個(gè)然后推到第一個(gè)，于是詳細(xì)說明就不在給了，直接上結(jié)論：

?????

后向算法總結(jié)

?????? 初值：β_T(i) = 1

????? PS：概率為1的原因是 -- 本來還需要看看時(shí)刻T后面有什么東西，但因?yàn)樽詈笠粋€(gè)時(shí)刻T 后面已經(jīng)沒有時(shí)刻，即不需要再觀測(cè)某個(gè)東西，所以你隨便給個(gè)什么都行，我不在乎。

?????? 遞推：對(duì)于t = T-1, T-2,…, 1

β_i(t) = (∑_{_j}?a_ijb_jy(t+1)β_j(t+1))

???????PS：這一步是根據(jù)t+1的后向概率算t時(shí)刻的后向概率β_i(t)，因此：

?????????? β_i(t) = 第t時(shí)刻位于第i號(hào)狀態(tài)轉(zhuǎn)移到第t+1時(shí)刻位于第j號(hào)狀態(tài)的概率a_ij?*? ?第t+1時(shí)刻第j號(hào)狀態(tài)給出y(t+1) 觀測(cè)的概率b_jy(t+1)?* 第t+1時(shí)刻的后驗(yàn)概率。

?????? 最終：P(O|λ) =∑_i π_ib_iy1β_i(1)

????? PS：同第二步，只不過這里是第1時(shí)刻。

?

前后向概率的關(guān)系

????? 具體推倒就不給出了，總之：

????? 擁有所有觀測(cè)時(shí)，第t時(shí)刻有第i個(gè)狀態(tài)的概率 = t時(shí)刻的前向概率 * t時(shí)刻的后向概率，即：

?????????? P(i_t?= q_i, Y | λ ) ?= α_i(t) * β_i(t)

?

單個(gè)狀態(tài)的概率

????? 這里的單個(gè)狀態(tài)是什么呢？就是給定觀測(cè)O和HMM的參數(shù) λ 時(shí)，在時(shí)刻t時(shí)位于隱狀態(tài)i的概率，記為：

?????????? γ_t(i) = P(i_t= q_i?| O, λ)

????? PS：這里的O是所有觀測(cè)的合集，即：O = {y₁?= o₁, y₂?= o₂, …,y_T?= o_T}

?????? 這個(gè)就很強(qiáng)啦，因?yàn)槲覀兛梢怨烙?jì)在t時(shí)刻的隱狀態(tài)，進(jìn)而求出隱狀態(tài)序列！

????? PS：這個(gè)的確是求隱狀態(tài)序列的一種方式，但這種有個(gè)問題 -- 求出的隱狀態(tài)之間互相獨(dú)立，即：沒有考慮到第t+1時(shí)刻的隱狀態(tài)是由第t時(shí)刻的隱狀態(tài)轉(zhuǎn)移過來的情況。換言之：這樣求得的隱狀態(tài)是“每個(gè)隱狀態(tài)都是僅在當(dāng)前時(shí)刻最優(yōu)，可每個(gè)隱狀態(tài)都沒考慮到全局情況”。

????? 而它的求解也很簡(jiǎn)單，如下：

兩個(gè)狀態(tài)的聯(lián)合概率

????? 剛才“單個(gè)狀態(tài)的概率”求得的t時(shí)刻的隱狀態(tài)沒有考慮到“上下文”，那就考慮下上下文，即：時(shí)刻t位于隱狀態(tài)i時(shí)，t+1時(shí)刻位于隱狀態(tài)j，記為：

?????????? ξ_t(i, j) =P(i_t?= q_i, i_t+1?= q_j?| O, λ)

????? 求解推導(dǎo)：

?

一些期望

??????????

學(xué)習(xí)問題

????? 學(xué)習(xí)問題分兩種：

1，????????觀測(cè)序列和隱狀態(tài)序列都給出，求HMM。

PS：這種學(xué)習(xí)是監(jiān)督學(xué)習(xí)。

2，????????給出觀測(cè)序列，但沒給出隱狀態(tài)序列，求HMM。

PS：這種學(xué)習(xí)是非監(jiān)督學(xué)習(xí)，利用Baum-Welch算法。

觀測(cè)序列和隱狀態(tài)序列都給出

????? 這種其實(shí)求法超簡(jiǎn)單：用大數(shù)定理用頻率來估算HMM的三種概率就OK了。

??????????

?????? 解釋：

?????????? 還是用最開始的分詞的例子。

????????????? 初始概率：

i = 0：第一個(gè)文字是終止字的次數(shù) / (第一個(gè)文字是終止字的次數(shù) + 不是終止字的次數(shù))

i = 1：第一個(gè)文字不是終止字的次數(shù) / (第一個(gè)文字是終止字的次數(shù) + 不是終止字的次數(shù))

????????????? 轉(zhuǎn)移概率：

???????????????? i=0,j=0：第t個(gè)字是終止字，第t+1個(gè)字是終止字的次數(shù) / (第t個(gè)字是終止字，第t+1個(gè)字是終止字的次數(shù) + 第t個(gè)字是終止字，第t+1個(gè)字不是終止字的次數(shù) + 第t個(gè)字不是終止字，第t+1個(gè)字是終止字的次數(shù) + 第t個(gè)字不是終止字，第t+1個(gè)字不是終止字的次數(shù))

???????????????? i=0,j=1、i=1, j=0、i=1, j=1同理。

????????????? 觀測(cè)概率：

???????????????? i=0,k=0：Unicode編碼中編碼為0的字是終止字的次數(shù) / (Unicode編碼中編碼為0的字是終止字的次數(shù) + Unicode編碼中編碼為0的字不是終止字的次數(shù))

???????????????? i=1,k=0：Unicode編碼中編碼為0的字不是終止字的次數(shù) / (Unicode編碼中編碼為0的字是終止字的次數(shù) + Unicode編碼中編碼為0的字不是終止字的次數(shù))

???????????????? 其他k=j同理。

?

Baum-Welch算法

????? 其實(shí)該算法的本質(zhì)就是EM算法，因?yàn)樗鉀Q的問題就是：有了觀測(cè)值X，而觀測(cè)值有個(gè)隱變量Z時(shí)，求在HMM參數(shù) λ下的聯(lián)合概率P(X, Z | λ) 。

PS：我總結(jié)的EM算法地址如下：

http://blog.csdn.net/xueyingxue001/article/details/52020673

????? 這里在貼一下EM算法的步驟：

????? 上面的步驟寫成統(tǒng)一的式子就是：

因此EM算法對(duì)應(yīng)到HMM的學(xué)習(xí)問題就是：

? 所有觀測(cè)數(shù)據(jù)寫成O=(o₁, o_2?…o_T)，所有隱數(shù)據(jù)寫成I=(i₁, i₂?…i_T)，完全數(shù)據(jù)是(O, I)=(o₁, o₂?…o_T? ,i₁,i₂?… i_T)，完全數(shù)據(jù)的對(duì)數(shù)似然函數(shù)是lnP(O, I | λ)

于是：

就有如下推導(dǎo)：

?????? 解釋：

?????????? 第一行：EM的Q函數(shù)。

?????????? 第二行：條件概率公式。

?????????? 第三行：

第一：第二行分母代表“上一次求出的參數(shù)與觀測(cè)集合的聯(lián)合概率”，對(duì)本次的估計(jì)沒幫助，所以可以舍去。

第二：第三行那個(gè)是正比符號(hào)，即使沒有上一個(gè)解釋可是可以保證第二行與第三行是成正比的。

????? 話說，P(O, I | λ) 在“HMM概率計(jì)算問題”的“直接/暴力計(jì)算法”中已經(jīng)解出了，這里再貼下截圖：

?????

????? 于是上面可以進(jìn)一步做如下推導(dǎo)：

?????

????? 對(duì)于上式，除了HMM的參數(shù) λ = (A, B, π) 外都是已知的了。

????? 話說上圖將最后一個(gè)等號(hào)寫在3行是為了表述一點(diǎn)：這三行的每一行僅包含HMM的一個(gè)參數(shù)，而我們的目標(biāo)是求Q函數(shù)的最大，于是只要求最后三行的最大就好了。為了方便說明，我將上圖最后三行的三個(gè)式子從上向下依次命名為：π式，α式，β式。

求 π 式

????? π 式有個(gè)約束：所有π_i的和為1。

????? 于是對(duì)于有約束的求極值為題就拉格朗日乘子法的伺候！

????? 1，拉格朗日函數(shù)

?????

????? 2，上式對(duì) π_i?求偏導(dǎo)

?????

????? 3，上式對(duì)i求和后 π_i?的和為1就把 π 約掉了，從而求出拉格朗日參數(shù)

?????

????? 4，將上式帶入第二步的式子就求出了π：

?????

????? 而上式的 γ 就是“HMM概率計(jì)算問題”中“單個(gè)狀態(tài)的概率”中的 γ(PS：不是拉格朗日參數(shù))，于是 π 就求出來了！

?

求 α 式

????? α 式可以寫成

????? 仍然使用拉格朗日乘子法，得到

?????

?????

????? 上式的 γ 是“HMM概率計(jì)算問題”中“單個(gè)狀態(tài)的概率”中的 γ，上式的 ξ 是“HMM概率計(jì)算問題”中“兩個(gè)狀態(tài)的聯(lián)合概率”中的 ξ。

?

求 β 式

????? 同理，得到：

?????

????? 上式的 γ 是“HMM概率計(jì)算問題”中“單個(gè)狀態(tài)的概率”中的 γ。

?

預(yù)測(cè)問題

????? 預(yù)測(cè)問題有兩種解決辦法：

1，????????近似算法。其實(shí)就是“HMM概率計(jì)算問題”中“單個(gè)狀態(tài)的概率”的解法。

2，????????Viterbi 算法。下面講解這個(gè)。

VIterbi算法

????? 在介紹維特比算法之前，我先用通俗的語言描述下它。

????? 假設(shè)我們遇到了這么個(gè)問題：

?????????? 大學(xué)時(shí)你讓室友幫你帶飯(如果你上過大學(xué)，別告訴我你沒干過這事....)，然后你室友問你想吃啥？你回答：“你吃啥我吃啥，不過回來時(shí)幫忙帶瓶雪碧，謝啦”。于是有趣的事就發(fā)生了：你室友給你帶回了飯和雪碧并興高采烈的說：“我去，食堂換大廚了，那個(gè)小賣部的收銀員換成了個(gè)漂亮妹子！！”然后你問他：“你去的哪個(gè)食堂和小賣部？”，他想了想回答：“你猜。”

?????????? 好了，你猜吧~

?????????? 我猜你妹啊(╯‵□′)╯︵┻━┻

????? 嘛，先別慌掀桌，不管如何你室友幫你帶了飯，所以咱們就滿足下他那小小的惡作劇，就當(dāng)做是給他跑腿的辛苦費(fèi)好了。

????? PS：假設(shè)你學(xué)校有2個(gè)小賣部和2個(gè)食堂。

????? 于是，mission start！

????? 首先，問他：你先去得小賣部？他回答：是的。

????? OK，買東西的先后順序搞定了，如下圖：

?????

????? 接下來開始思考：

?????????? 第一步：從宿舍到小賣部A和B的距離都差不多，不好判斷，即從宿舍到小賣部A的概率 = 從宿舍到小賣部B的概率，如下圖；

??????????

?????????? 第二步：從小賣部A、B到食堂1、2有四種路線(A1, A2, B1, B2)，然后這四種路線中到食堂1最短的是A1，到食堂2最短的是B2，然后這貨絕對(duì)那個(gè)近選哪個(gè)，所以如果去食堂1，則他會(huì)選擇A1，如果去食堂2，則他會(huì)選擇B2，如下圖：

??????????

?????????? 第三步：看看他給帶來的飯，嗯....這個(gè)飯我記得食堂1有賣，食堂2不知道，就當(dāng)沒有吧，那就假設(shè)他去的是食堂1，如下圖：

??????????

?????????? 第四步：OK，終點(diǎn)已經(jīng)確定，接下來反推回去，就好了，即：他絕壁選個(gè)最近的小賣部，所以他會(huì)選擇距離食堂1最近的小賣部A，如下圖：

??????????

?????????? 第五步：對(duì)他說：“你先去小賣部A然后去食堂1對(duì)吧”，他說：“我次奧，你咋知道的”。

?

????? OK，例子舉完了，我們來看看維特比算法，其實(shí)維特比算法就是上面的過程：?? ????? 1，先從前向后推出一步步路徑的最大可能，最終會(huì)得到一個(gè)從起點(diǎn)連接每一個(gè)終點(diǎn)的m條路徑(假設(shè)有m個(gè)終點(diǎn))。

????? ????? 2，確定終點(diǎn)之后在反過來選擇前面的路徑。

????? ????? 3，確定最優(yōu)路徑。

????? 下面看看Viterbi算法的定義。

Viterbi 算法的定義

????? 定義變量δt(i)：表示時(shí)刻t狀態(tài)為i的所有路徑中的概率最大值，公式如下：

??????????

????? 過程：

??????????

????? 上面的符號(hào)之前都已經(jīng)見過，這里不再解釋，下面為了更好地理解這幾步，我們來舉個(gè)例子。

例子

????? 還是盒子球模型。

????? 盒子和球模型λ= (A, B,π)，狀態(tài)集合Q={1, 2, 3}，觀測(cè)集合V={紅, 白}，

??????????

????? 已知觀測(cè)序列O=(紅，白，紅)，試求最優(yōu)狀態(tài)序列，即最優(yōu)路徑I*= (i₁^*, i₂^*, i₃^*)。

??????解：

?????????? 如下圖所示(圖中的數(shù)字在之后的步驟中會(huì)一一推導(dǎo)出來)

????????????????

?????????? 要在所有可能的路徑中選擇一條最優(yōu)路徑，按照以下步驟出來。

????????????? 1，初始化

??????????????t=1時(shí)，對(duì)每個(gè)狀態(tài)i, i=1, 2, 3，求狀態(tài)為i觀測(cè)o₁為紅的概率，記此概率為δ₁(i)，則：

???????????????? δ₁(i) = π_ib_i(o₁)=π_ib_i(紅)， i = 1, 2, 3

?????????? 代入實(shí)際數(shù)據(jù)

???????????????? δ₁(1) = 0.10，δ₁(2) =0.16，δ₁(3) = 0.28

?????????? 記ψ₁(i) = 0，i = 1, 2, 3。

???????????2，在t=n時(shí)

?????????? t=2時(shí)，對(duì)每個(gè)狀態(tài)i，求在t=1時(shí)狀態(tài)為j觀測(cè)為紅并且在t=2時(shí)狀態(tài)為i觀測(cè)為白的路徑的最大概率，記概率為δ₂(t)，則根據(jù)：

????????????????

?????????? 同時(shí)，對(duì)每個(gè)狀態(tài)i, i = 1, 2, 3，記錄概率最大路徑的前一個(gè)狀態(tài)j：

?????????? ?????

?????????? 計(jì)算：

????????????????

?????????? 同樣，在t=3時(shí)

? ? ? ? ? ? ? ??????????????????

???????????3，求最優(yōu)路徑的終點(diǎn)

??????????????以P*表示最優(yōu)路徑的概率，則

????????????????

?????????? 最優(yōu)路徑的終點(diǎn)是i₃^*:

????????????????

???????????4，逆向找i₂^*,i₁^*：

???????????????? 在t=2時(shí)，i₂^*?= ψ₃(i₃^*) =ψ₃(3) = 3

???????????????? 在t=2時(shí)，i₁^*?= ψ₂(i₂^*) =ψ₂(3) = 3

?????????? 于是求得最優(yōu)路徑，即最有狀態(tài)序列I* = (i₁^*,i₂^*, i₃^*) = (3, 3, 3)。

轉(zhuǎn)載于:https://www.cnblogs.com/sddai/p/8475424.html

總結(jié)

以上是生活随笔為你收集整理的隐马尔可夫(HMM)、前/后向算法、Viterbi算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。