劉 輝

(上海電力大學 計算機科學與技術學院, 上海 200090)

隱馬爾可夫是可用于標準問題的統(tǒng)計學習模型,描述由隱藏的馬爾可夫鏈隨機生成觀測序列的過程,屬于生成模型[1]。其難點是從可觀察的參數(shù)中確定該過程的隱含參數(shù),然后利用這些參數(shù)來作進一步的分析,例如模式識別。藏于物理世界中的往往是表象,而真正的隱藏狀態(tài)是不可見的,需要通過觀察大量的表象來總結規(guī)律,從而確定事物的隱含狀態(tài),認識事物的本質。事物的隱含狀態(tài)與事物的表象存在著一定的關聯(lián)關系,可以通過統(tǒng)計的方法來確立它們之間的關聯(lián)。

1 隱馬爾可夫模型的建立

1.1 建立訓練數(shù)據(jù)集

在隱馬爾可夫模型的定義中,Q={q1,q2,q3,…,qN}是所有可能的狀態(tài)集合,V={v1,v2,v3,…,vM}是所有可能的觀測集合,I={i1,i2,i3,…,iT}是長度為T的狀態(tài)序列,O={o1,o2,o3,…,oT}是對應的觀測序列。

本文通過觀察海藻濕度的狀態(tài),確定是雨天還是晴天的例子來推導隱馬爾可夫模型的計算推理過程。海藻的濕度為可見狀態(tài),而天氣狀況為隱藏狀態(tài)(假設盲人能夠感知海藻濕度,卻無法觀察天氣)。在海藻模型中,觀測概率矩陣為

B=[bj(k)]N×M

(1)

式中:bj(k)——在時刻t處于狀態(tài)qj的條件下生成觀測vk的概率,bj(k)=P(ot=vk|it=qj),k=1,2,3,…,M;j=1,2,3,…,N;

M——觀測狀態(tài)總數(shù);

N——隱藏狀態(tài)總數(shù)。

觀測概率矩陣的定義考慮了時間t的因素,但在分析實際問題時做了簡化,即在任何時刻,觀測概率矩陣都不隨時間變化,因此在理解觀測概率矩陣時,可以把t去掉[2]。

通過觀察海藻的濕度來確定隱含狀態(tài),定義海藻濕度為“dry(干燥)”“dryish(稍干)”“damp(微濕)”“soggy(潮濕)”4個等級。不同的天氣狀況下觀測到的海藻濕度的概率是不同的,觀測數(shù)據(jù)如表1所示。

表1 不同天氣狀況下觀測到的海藻濕度概率

1.2 觀測概率矩陣

根據(jù)bj(k)的定義,表1所列出的概率其實就是觀測概率矩陣。因此,bj(k)中的變量可以理解為:j表示不同的天氣狀態(tài),k表示不同的海藻濕度等級。條件概率就是定義了在t時刻某個qj狀態(tài)下,某個vk狀態(tài)出現(xiàn)的概率。

由于觀測概率矩陣不考慮時間因素,所以bj(k)也不會隨著時間發(fā)生變化,寫成矩陣的形式為

1.3 狀態(tài)轉換概率矩陣

隱馬爾可夫模型中還定義了狀態(tài)轉換概率矩陣為

A=[aij]N×N

(2)

其中,aij=P(it+1=qj|it=qi)(i=1,2,3,…,N;j=1,2,3,…,N)是在時刻t處于狀態(tài)qi的條件下,在時刻t+1轉移到狀態(tài)qj的概率。

馬爾可夫鏈是隨機變量X1,X2,X3,…,XN的一個數(shù)列。這些變量的范圍,即它們所有可能取值的集合,被稱為“狀態(tài)空間”,而Xn的值則是在時間n的狀態(tài)。如果Xn+1對于過去狀態(tài)的條件概率分布僅是Xn的一個函數(shù),則

P(Xn+1|X0,…,Xn)=P(Xn+1|Xn)·

P(Xn|Xn-1)…P(X1|X0)

(3)

該式在理論上是完美的,但在實際運用過程中存在兩個問題:第一,假設要計算某個連續(xù)序列的概率,而這一概率會隨著序列長度的增加不斷減小,最后概率值將小到毫無意義;第二,每次計算都要記錄前n次的狀態(tài),當序列長度增大時,數(shù)據(jù)量將明顯增大,計算量也會變得相當大。因此,隱馬爾可夫模型做了最基本的假設:當前狀態(tài)只與前一個狀態(tài)有關,即

P(Xn+1|X0,…,Xn)=P(Xn+1|Xn)

(4)

針對本文案例來說,今天的天氣狀態(tài)只受昨天天氣狀態(tài)的影響。但還需考慮時間段不同狀態(tài)轉移矩陣是否相同的問題。

按實際情況來說,萬年前晴天轉雨天的概率顯然與如今晴天轉雨天的概率是不同的,因此隱馬爾可夫模型又做了一個不動性假設(狀態(tài)概率轉移矩陣與時間無關),即

P(Xi+1|Xi)=P(Xj+1|Xj),?i,j

(5)

此處的i和j在海藻模型中分別表示地球時間第i天和第j天。

基于時間不動性假設,就可以統(tǒng)計狀態(tài)轉移的概率。假設歷史上只出現(xiàn)了“sunny”“cloudy”“rainy”3種天氣狀態(tài) ,那么就可以統(tǒng)計出某個時間段內(nèi),從一個狀態(tài)轉移至另一狀態(tài)的頻率(這里的頻率可以理解為概率),如表2所示。

表2 狀態(tài)轉移概率

aij的定義正好與表2中從行到列的概率相對應。因此,狀態(tài)轉換概率矩陣為

1.4 初始狀態(tài)概率矩陣

設置一個初始狀態(tài)概率向量π為

π=(πi)i=1,2,3,…,N

(6)

其中,πi=P(i1=qi)是時刻t=1時狀態(tài)qi出現(xiàn)的概率。

在海藻模型中,本文給出π=(0.6,0.2,0.2)。

1.5 隱馬爾可夫模型的創(chuàng)建

一個完整的隱馬爾可夫模型是由初始狀態(tài)概率向量π、狀態(tài)轉移概率矩陣A和觀測概率矩陣B所決定的,π和A決定狀態(tài)序列,B決定觀測序列。因此,隱馬爾可夫模型λ可以用三元符號表示,即λ=(A,B,π),A,B,π稱為隱馬爾可夫模型的三要素。

隱馬爾可夫模型是關于時序的概率模型,描述由一個隱藏的馬爾可夫鏈隨機生成不可觀測的狀態(tài)序列,再由各個狀態(tài)生成一個觀測結果而產(chǎn)生觀測序列的過程。序列的每一個位置可以看作是一個時刻。

在海藻模型中,盲人每天第一件事情便是感知海藻的濕度,即每天記錄海藻的狀態(tài)。假設盲人連續(xù)記錄了3天,海藻的觀測序列為O=(dry,damp,soggy),則由隱馬爾可夫模型可知,第1天海藻狀態(tài)為dry,可能最佳隱藏狀態(tài)為sunny;第2天海藻狀態(tài)為damp,可能最佳隱藏狀態(tài)為cloudy;第3天海藻狀態(tài)為soggy可能最佳隱藏狀態(tài)為rainy。由此得到天氣的隱藏狀態(tài)序列為I=(sunny,cloudy,rainy)。

2 隱馬爾可夫模型的3個基本問題

2.1 概率計算問題

海藻模型中提出了在已知模型λ=(A,B,π)中求解P(O|λ)的問題。

在海藻模型中,根據(jù)觀察序列尋找到一個隱藏序列,該概率可以表示為P(O|I,λ)。顯然I序列的個數(shù)不只一個,3種天氣狀態(tài)對應3個序列,I的總數(shù)為3×3×3=27個,假設有N種狀態(tài),對應T個觀察序列,那么I的總數(shù)為NT個。

將27個序列一一列舉出來,分別進行計算。對固定的狀態(tài)序列I={i1,i2,i3,…,iT},觀測序列O={o1,o2,o3,…,oT}的概率為

P(O|I,λ)=bi1(o1)bi2(o2)·

bi3(o3)…biT(oT)

(7)

由于上述概率P(O|I,λ)是條件概率,即假定每個隱藏序列是已知的,故觀測到的海藻狀態(tài)與狀態(tài)轉移矩陣沒有關系,只與其觀測概率分布有關。如,已知3天的天氣狀態(tài)均為sunny,那么P(O={dry,damp,soggy}|I={sunny,sunny,sunny},λ)=b1(1)b1(3)b1(4)=0.60×0.15×0.05=0.004 5。

在狀態(tài)轉移矩陣中,只要知道初始狀態(tài)概率向量π,就能夠從某個時刻推斷一連串隱藏狀態(tài)序列的概率

P(I|λ)=πi1ai1i2ai2i3…aiT-1iT

(8)

式(8)對馬爾可夫鏈的一階假設進行了很好的簡化。比如,第1天天氣狀態(tài)為sunny的概率為初始概率,已知;第2天為sunny的概率只與第1天的狀態(tài)有關,也就是狀態(tài)轉移矩陣中sunny→sunny的概率;第3天仍為sunny的概率也只與前一天相關,即sunny→sunny的概率。因此,隱藏狀態(tài)從一個狀態(tài)轉移至另一個狀態(tài),每次只要乘以狀態(tài)轉移矩陣中的某個值即可。

根據(jù)I出現(xiàn)的概率,以及在I出現(xiàn)的條件下O出現(xiàn)的概率,可以求得聯(lián)合概率為

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

πibi1(o1)ai1i2bi2(o2)…aiT-1iTbiT(oT)

(9)

然后,對所有可能的狀態(tài)序列I求和,得到觀測序列O的概率P(O|λ),即

P(O|λ)=ΣIP(O|I,λ)P(I|λ)=

Σi1,i2…iTπibi1(o1)ai1i2bi2(o2)…

aiT-1iTbiT(oT)

(10)

上述算法不記憶先前的計算結果,算法傳播到第3個狀態(tài)后,一切推倒,重新計算。因此,這種算法在數(shù)據(jù)量大的情況下是不可行的。

在程序中有用空間換時間的思想,其實在數(shù)學公式中也是通用的。采用中間變量來記錄結果,并利用該中間變量來計算后續(xù)節(jié)點,那么很明顯可以極大地簡化計算次數(shù)[3],減少計算量。

2.2 預測問題

根據(jù)給定的模型參數(shù)λ計算出P(O|λ)的值,給定一連串輸入序列。對每個單詞進行標注,從而使得整個隱藏序列對于觀測序列來說概率最大[4],即P(I|O)最大。維特比算法是用動態(tài)規(guī)劃解隱馬爾可夫模型預測問題,即用動態(tài)規(guī)劃求解概率最大路徑(最優(yōu)路徑),這時一條路徑對應著一個狀態(tài)序列。

在t=1時刻,對于每一個狀態(tài)i(i=1,2,3),求狀態(tài)i下觀測o1是sunny的概率δ1(i)為

δ1(i)=πibi(o1)=πibi(sunny),

i=1,2,3

(11)

代入實際數(shù)據(jù)后,可得δ1(1)=0.10,δ1(2)=0.16,δ1(3)=0.28。

對于t=1時刻,每個隱藏狀態(tài)i可能出現(xiàn)sunny的概率與初始狀態(tài)有關,與轉移概率無關。在t=2時刻,對于不同的隱藏狀態(tài),有3條路徑同時到達,此時不再計算3條路徑的概率和,而是取其中概率最大的1條,代表從t時刻轉移至t+1時刻,某一隱藏狀態(tài)序列it,it+1出現(xiàn)ot,ot+1的概率最大。用公式表示為

(12)

計算可得:δ2(1)=0.028,δ2(2)=0.050 4,δ2(3)=0.042。同理,在t=3時刻,有

(13)

可得,δ3(1)=0.007 56,δ3(2)=0.010 08,δ3(3)=0.014 7。

用P*表示最優(yōu)路徑的概率,則

(14)

那么最優(yōu)路徑的終點

(15)

記錄路徑經(jīng)過節(jié)點的變量定義為

i=1,2,3,…,N

(16)

3 結 語

隱馬爾可夫模型參數(shù)的估計問題是一個隱藏變量的極大似然估計。對隱馬爾可夫預測模型求偏導,得到極大似然函數(shù)的極值,再計算聯(lián)合概率,而聯(lián)合概率的計算巧妙地使用了節(jié)點圖的各種性質,用中間變量降低了節(jié)點計算的復雜度,導出了對計算有幫助的定義,方便了參數(shù)求解。