機(jī)器學(xué)習(xí)中的隱馬爾科夫模型（HMM）詳解

在之前介紹貝葉斯網(wǎng)絡(luò)的博文中，我們已經(jīng)討論過概率圖模型（PGM）的概念了。Russell等在文獻(xiàn)【1】中指出：“在統(tǒng)計(jì)學(xué)中，圖模型這個(gè)術(shù)語指包含貝葉斯網(wǎng)絡(luò)在內(nèi)的比較寬泛的一類數(shù)據(jù)結(jié)構(gòu)。” 維基百科中更準(zhǔn)確地給出了PGM的定義：“A graphical model or probabilistic graphical model is a probabilistic model for which a graph expresses the conditional dependence structure between random variables. ” 如果你已經(jīng)掌握了貝葉斯網(wǎng)絡(luò)，那么你一定不會(huì)對(duì)PGM的概念感到陌生。本文將要向你介紹另外一種類型的PGM，即隱馬爾可夫模型（HMM，Hidden Markov Model）。更準(zhǔn)確地說，HMM是一種特殊的貝葉斯網(wǎng)絡(luò)。

一些必備的數(shù)學(xué)知識(shí)

隨機(jī)過程（Stochastic Process）是一連串隨機(jī)事件動(dòng)態(tài)關(guān)系的定量描述。如果用更為嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)語言來描述，則有：設(shè)對(duì)每一個(gè) t∈T，X(t,w) 是一個(gè)隨機(jī)變量，稱隨機(jī)變量族 XT={X(t,w),t∈T} 為一隨機(jī)過程（或隨機(jī)函數(shù)），其中 T∈R 稱為指標(biāo)集，R 是實(shí)數(shù)集。w∈Ω，Ω為樣本空間。用映射來表示XT， 

即 X(?,?) 是定義在 T×Ω 上的二元單值函數(shù)。其中 T×Ω 表示 T 和 Ω 的笛卡爾積。

參數(shù) t∈T 一般表示時(shí)間。當(dāng) T 取可列集時(shí)，通常稱 XT 為隨機(jī)序列。XT (t∈T) 可能取值的全體集合稱為狀態(tài)空間，狀態(tài)空間中的元素稱為狀態(tài)。

馬爾科夫過程（Markov Process）是本文中我們所要關(guān)注的一種隨機(jī)過程。粗略地說，一個(gè)隨機(jī)過程，若已知現(xiàn)在的 t狀態(tài) Xt, 那么將來狀態(tài) Xu (u>t) 取值（或取某些狀態(tài)）的概率與過去的狀態(tài) Xs (s>t) 取值無關(guān)；或者更簡(jiǎn)單地說，已知現(xiàn)在、將來與過去無關(guān)（條件獨(dú)立），則稱此過程為馬爾科夫過程。

同樣，我們給出一個(gè)精確的數(shù)學(xué)定義如下：若隨機(jī)過程{Xt,t∈T}對(duì)任意 t1<t2<…<tn<t，xi，1≤i≤n 及 A 是 R的子集，總有 

則稱此過程為馬爾科夫過程。稱P(s,x;t,A)=P{Xt∈A|Xs=x}，s>t, 為轉(zhuǎn)移概率函數(shù)。Xt 的全體取值構(gòu)成集合 S 就是狀態(tài)空間。對(duì)于馬爾可夫過程 XT={Xt,t∈T}，當(dāng)S={1,2,3,?}為可列無限集或有限集時(shí)，通常稱為馬爾科夫鏈（Markov Chain）。

從時(shí)間角度考慮不確定性

在前面給出的貝葉斯網(wǎng)絡(luò)例子中，每一個(gè)隨機(jī)變量都有唯一的一個(gè)固定取值。當(dāng)我們觀察到一個(gè)結(jié)果或狀態(tài)時(shí)（例如Mary給你打電話），我們的任務(wù)是據(jù)此推斷此時(shí)發(fā)生地震的概率有多大。而在此過程中，Mary是否給你打過電話這個(gè)狀態(tài)并不會(huì)改變，而地震是否已經(jīng)發(fā)生也不會(huì)改變。這就說明，我們其實(shí)是在一個(gè)靜態(tài)的世界中來進(jìn)行推理的。

但是我們現(xiàn)在要研究的HMM，其本質(zhì)則是基于一種動(dòng)態(tài)的情況來進(jìn)行推理，或者說是根據(jù)歷史來進(jìn)行推理。假設(shè)要為一個(gè)高血壓病人提供治療方案，醫(yī)生每天為他量一次血壓，并根據(jù)這個(gè)血壓的測(cè)量值調(diào)配用藥的劑量。顯然，一個(gè)人當(dāng)前的血壓情況是跟他過去一段時(shí)間里的身體情況、治療方案，飲食起居等多種因素息息相關(guān)的，而當(dāng)前的血壓測(cè)量值相等于是對(duì)他當(dāng)時(shí)身體情況的一個(gè)“估計(jì)”，而醫(yī)生當(dāng)天開具的處方應(yīng)該是基于當(dāng)前血壓測(cè)量值及過往一段時(shí)間里病人的多種情況綜合考慮后的結(jié)果。為了根據(jù)歷史情況評(píng)價(jià)當(dāng)前狀態(tài)，并且預(yù)測(cè)治療方案的結(jié)果，我們就必須對(duì)這些動(dòng)態(tài)因素建立數(shù)學(xué)模型。

而隱馬爾科夫模型就是解決這類問題時(shí)最常用的一種數(shù)學(xué)模型，簡(jiǎn)單來說，HMM是用單一離散隨機(jī)變量描述過程狀態(tài)的時(shí)序概率模型。HMM的基本模型可用下圖來表示，其中涂有陰影的圓圈 yt?2,yt?1,yt 相當(dāng)于是觀測(cè)變量，空白圓圈 xt?2,xt?1,xt 相當(dāng)于是隱變量?；氐絼倓偺峒暗母哐獕褐委煹睦?，你所觀測(cè)到的狀態(tài)（例如血壓計(jì)的讀數(shù)）相當(dāng)于是對(duì)其真實(shí)狀態(tài)（即病人的身體情況）的一種估計(jì)（因?yàn)橛^測(cè)的過程中必然存在噪聲），用數(shù)學(xué)語言來表述就是P(yt|xt)，這就是模型中的測(cè)量模型或測(cè)量概率（Measurement Probability）。另外一方面，當(dāng)前的（真實(shí)）狀態(tài)（即病人的實(shí)際身體狀況）應(yīng)該與其上一個(gè)觀測(cè)狀態(tài)相關(guān)，即存在這樣的一個(gè)分布P(xt|xt?1)，這就是模型中的轉(zhuǎn)移模型或轉(zhuǎn)移概率（Transition Probability）。當(dāng)然，HMM中隱變量必須都是離散的，觀測(cè)變量并無特殊要求。 

注意這里我們其實(shí)使用了馬爾科夫假設(shè)：即當(dāng)前狀態(tài)只依賴于過去的有限的已出現(xiàn)的歷史。我們前面所采用的描述是：“已知現(xiàn)在的 t 狀態(tài) Xt, 那么將來狀態(tài) Xu(u>t) 取值（或取某些狀態(tài)）的概率與過去的狀態(tài) Xs(s>t) 取值無關(guān)”。兩種表述略有差異，但顯然本質(zhì)上是一致的。而且更準(zhǔn)確的說，在HMM中，我們認(rèn)為當(dāng)前狀態(tài)緊跟上一個(gè)時(shí)刻的狀態(tài)有關(guān)，即前面所謂的“有限的已出現(xiàn)的歷史”就是指上一個(gè)狀態(tài)。用數(shù)學(xué)語言來表述就是 

如果讀者已經(jīng)閱讀過本文最開始列出的兩篇文章，那么你應(yīng)該已經(jīng)意識(shí)到，這其實(shí)是PGM三種基本的結(jié)構(gòu)單元中的最后一種情況，即條件獨(dú)立型的結(jié)構(gòu)單元。

再結(jié)合HMM的基本圖模型（即上圖），我們就會(huì)得出HMM模型中的兩個(gè)重要概率的表達(dá)式：

離散的轉(zhuǎn)移概率（Transition Probability）“

連續(xù)（或離散）的測(cè)量概率（Measurement Probability） 

一個(gè)簡(jiǎn)單的例子

現(xiàn)在我們已經(jīng)了解了HMM的基本結(jié)構(gòu)，接下來不妨通過一個(gè)實(shí)際的例子來考察一下，HMM的轉(zhuǎn)移概率和測(cè)量概率到底是什么樣的。下圖給出了一個(gè)用于表示股市動(dòng)態(tài)的概率圖模型，更具體的說這是一個(gè)馬爾科夫模型（Markov Model），因?yàn)樵搱D并未涉及隱狀態(tài)信息。根據(jù)之前（以貝葉斯網(wǎng)絡(luò)為例的）PGM學(xué)習(xí)，讀者應(yīng)該可以看懂改圖所要展示的信息。例如，標(biāo)記為 1 的圓圈表示的是當(dāng)前股市正處于牛市，由此出發(fā)引出一條指向自身，權(quán)值為0.6的箭頭，這表示股市（下一時(shí)刻）繼續(xù)為牛市的概率為0.6；由標(biāo)記為 1 的圓圈引出的一條指向標(biāo)記為 2 的圓圈的箭頭，其權(quán)值為0.2，這表示股市（下一時(shí)刻）轉(zhuǎn)入熊市的概率是0.2；最后，由標(biāo)記為 1 的圓圈引出的一條指向標(biāo)記為 3 的圓圈的箭頭，其權(quán)值為0.2，這表示股市（下一時(shí)刻）保持不變的概率是0.2。顯然，從同一狀態(tài)引出的所有概率之和必須等于1。

所以馬爾科夫模型中的各個(gè)箭頭代表的就是狀態(tài)之間相互轉(zhuǎn)化的概率。而且，通常我們會(huì)把馬爾科夫模型中所有的轉(zhuǎn)移概率寫成一個(gè)矩陣的形式，例如針對(duì)本題而已，則有 

如果馬爾科夫模型中有 k 個(gè)狀態(tài)，那么對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移矩陣的大小就是 k×k。其中第 m 行，第 n 列所給出的值就是 P(xt=n|xt?1=m)。也就給定狀態(tài) m 的情況下，下一時(shí)刻轉(zhuǎn)換到狀態(tài) n 的概率。例如，第2行，第1列的值為 0.5，它的意思就是如果當(dāng)前狀態(tài)是標(biāo)記為 2 的圓圈（熊市），那么下一時(shí)刻轉(zhuǎn)向標(biāo)記為 1 的圓圈（牛市）的概率是 0.5。而且，矩陣中，每一行的所有值之和必須等于1。

至此，我們已經(jīng)知道可以用一個(gè)矩陣 A 來代表 P(xt|xt?1)，那又該如何表示 P(yt|xt) 呢？當(dāng)然，由于P(yt|xt) 可能是連續(xù)的，也可能是離散的，所以不能一言以蔽之。為了簡(jiǎn)化，我們當(dāng)前先僅考慮離散的情況。當(dāng)引入 P(yt|xt) 之后，我們才真正得到了一個(gè)隱馬爾科夫模型，上面我們所說的標(biāo)記為1、2 和 3 的（分別代表牛市、熊市和平穩(wěn)）三個(gè)狀態(tài)現(xiàn)在就變成了隱狀態(tài)。當(dāng)隱狀態(tài)給定后，股市的表現(xiàn)可能有 l=3 種情況，即當(dāng)前股市只能處于“上漲”，“下跌”，或者“不變”三種狀態(tài)之一。完整的HMM如下圖所示。 

易知，（當(dāng)測(cè)量概率是離散的情況下），HMM中的P(yt|xt) 也可以用一個(gè)矩陣 B 來表示。并且B 的大小是 k×l。對(duì)于當(dāng)前這個(gè)例子而言，我們有 

其中第 1 行，第 1 列，就表示 P(yt=1 | xt=1) ，也就是我們已知當(dāng)前正處于牛市，股票上升的概率為0.7； 同理，第 1 行，第 2 列，就表示 P(yt=2 | xt=1) ，也就是我們已知當(dāng)前正處于牛市，股票下跌的概率為0.1。

再次強(qiáng)調(diào)，只有當(dāng)測(cè)量概率是離散的情況下，我們才能用一個(gè)矩陣來表示P(yt|xt) 。對(duì)于連續(xù)的情況，比如我們認(rèn)為觀測(cè)變量的取值符合高斯分布，也即是概率 P(yt|xt) 的分布符合高斯分布，那么應(yīng)該有多少個(gè)高斯分布呢？顯然有多少個(gè)隱狀態(tài)（例如 k 個(gè)），就應(yīng)該有多少個(gè)高斯分布。那么矩陣 B 就應(yīng)該變成了由 k 個(gè)高斯分布的參數(shù)，即 σ1,μ1,σ2,μ2,?,σk,μk，組成的一個(gè)集合。

之前的文章里我們談過，人類學(xué)習(xí)的任務(wù)是從資料中獲得知識(shí)，而機(jī)器學(xué)習(xí)的任務(wù)是讓計(jì)算機(jī)從數(shù)據(jù)中獲得模型。那模型又是什么呢？回想一下機(jī)器學(xué)習(xí)中比較基礎(chǔ)的線性回歸模型 y=∑iwixi，我們最終是希望計(jì)算機(jī)能夠從已有的數(shù)據(jù)中或者一組最合適的參數(shù) wi，因?yàn)橐坏?nbsp;wi 被確定，那么線性回歸的模型也就確定了。同樣，面對(duì)HMM，我們最終的目的也是要獲得能夠用來確定（數(shù)學(xué)）模型的各個(gè)參數(shù)。通過前面的討論，我們也知道了定義一個(gè)HMM，應(yīng)該包括矩陣 A和 矩陣 B （如果測(cè)量概率是離散情況的話），那只有這些參數(shù)能夠足以定義個(gè)HMM呢？

要回答這個(gè)問題，我們不妨來思考一下這樣一個(gè)問題。假如我們現(xiàn)在已經(jīng)得到了 矩陣 A 和 矩陣 B ，那么我們能否求出下面這個(gè)序列的概率 P(y1=上漲,y2=上漲,y3=下跌)。注意對(duì)于這樣一個(gè)序列，我們并不知道隱狀態(tài)的情況，所以采用貝葉斯網(wǎng)絡(luò)中曾經(jīng)用過的方法，設(shè)法把隱狀態(tài)加進(jìn)去，在通過積分的方法將未知的隱狀態(tài)積分積掉。于是有

這里就可以運(yùn)用馬爾科夫假設(shè)進(jìn)行簡(jiǎn)化，所以上式就變成了 

到這里，我們就很容易發(fā)現(xiàn)，上面這個(gè)式子中，還有一個(gè)未知量，那就是PGM的初始狀態(tài)，我們將其記為 π 。

于是我們知道，要確定一個(gè)HMM模型，我們需要知道三個(gè)參數(shù)，我們將其記作 λ(A, B, π)。