基于隱馬爾可夫模型的雙鏈馬爾可夫模型

陳 琦，吾拉木江·艾則孜，申建新，胡錫健

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，烏魯木齊 830046)

隱馬爾可夫模型(HMM)作為一種統(tǒng)計(jì)分析模型，最初是在20世紀(jì)60年代后半期由Leonard E.Baum和其他一些作者提出的，經(jīng)過近半個(gè)世紀(jì)的發(fā)展，現(xiàn)已成功應(yīng)用到語音識別、生物信息科學(xué)、故障診斷等領(lǐng)域。HMM要求模型的輸出之間是條件獨(dú)立的，然而這種假設(shè)在實(shí)際應(yīng)用中有時(shí)并不合理。A.Berchtold［1］提出了雙鏈馬爾可夫模型(DCMM)。DCMM可以看成是對HMM的擴(kuò)展，其模型的輸出之間具有直接關(guān)系。DCMM雖然已提出10多年，但國內(nèi)學(xué)者對其研究很少。本文對DCMM的概念、發(fā)展及其基本問題進(jìn)行介紹，并利用其與HMM之間的區(qū)別，通過本文所提出的推導(dǎo)條件，從與HMM基本問題有關(guān)的一套概念及算法推導(dǎo)出DCMM的一套概念及算法。

1 隱馬爾可夫模型

1.1 HMM符號化

定義 {Ut:t=1，2，…，T}是觀察序列;{St:t=1，2，…，T}是隱狀態(tài)序列。用(t)和(t)分別表示{Ut，1≤t≤t}和{St，1≤t≤t}，那么，可以通過以下2個(gè)公式來描述一個(gè)隱馬爾可夫模型［2］:

也可以將一個(gè)離散HMM用一個(gè)5元組表示:λ =(M，N，π，A，B)，其中:M 表示隱狀態(tài)的數(shù)目;N表示可觀測狀態(tài)數(shù)目;π表示初始狀態(tài)的概率分布，π ={πi}，πi=P(S1=i)，1≤i≤M;A 表示隱狀態(tài)轉(zhuǎn)移概率矩陣 A={ai，j}，ai，j=P{St+1=j|St=i}，1≤i，j≤M;B表示給定狀態(tài)下的觀察概率分布，B={bjk}，bjk=bj(k)=p(Ut=k|St=j)，1≤k≤N，1≤j≤M。還可以將上述5元組簡寫成一個(gè)3元組:λ=(π，A，B)。由于此馬爾可夫鏈有M個(gè)隱狀態(tài)，因此可稱其為一個(gè)M狀態(tài)馬爾可夫模型。注意，本文所討論的是離散HMM，連續(xù)的情況可以類似推出。

1.2 與HMM問題有關(guān)的概念及算法

1.2.1 觀察序列的聯(lián)合概率［2］

1.2.2 向前向后概率［3］

對 t=1，2，…，T，定義如下行向量:

同樣可以定義向后概率向量:

由向前概率與向后概率的定義可以得到

1.2.3 Lk(t)和 Hk，l(t)的定義［3］

在一組給定的參數(shù)集下，定義:

不加證明地給出以下結(jié)論:

1.2.4 HMM學(xué)習(xí)問題的EM算法［4］

EM算法步驟如下:

3)用計(jì)算得到的 Lk(t)、Hk，l(t)更新參數(shù):

1.2.5 HMM解碼問題的Viterbi算法［5］

定義 δt(i)=maxP(s1，s2，…，st-1，st=i，u1，u2，…，ut|λ)，即求 T 時(shí)刻最大的 δT(i)所代表的狀態(tài)序列。

算法步驟:

1)初始化:δ1(i)= πibi(u1)，φ1(i)=0，1≤i≤M;

2)遞歸:δt(j)=max［δt-1(i)ai，j］bj(ui)，2≤

2 雙鏈馬爾可夫模型

2.1 模型簡介

DCMM是一個(gè)未知(隱)模型和一個(gè)已知(明)模型的特性的某種組合，之所以稱其為雙鏈，是因?yàn)樗梢员豢醋?個(gè)馬爾可夫鏈的疊加。其中的隱鏈控制一個(gè)未觀察到的變量的狀態(tài)之間的關(guān)系，明鏈控制一個(gè)觀察到的變量的輸出之間的關(guān)系。DCMM是為非齊次時(shí)間序列建模而設(shè)計(jì)的。Berchtold［6］提出:如果一個(gè)時(shí)間序列可被分解成一個(gè)有限的轉(zhuǎn)移矩陣的集合，那么DCMM可以用來控制這些矩陣的轉(zhuǎn)移過程。模型的結(jié)構(gòu)可以用圖1描述。

圖1 雙鏈馬爾可夫模型結(jié)構(gòu)

可以看到:DCMM使一個(gè)HMM的輸出之間具有了某種關(guān)系，而一個(gè)HMM的輸出之間不存在任何關(guān)系。之前也有一些學(xué)者按照類似的想法(使一個(gè)HMM的輸出之間具有某種關(guān)系)，提出過一些模型。Poritz、Kenny［7-9］提出一種將 HMM 與自回歸模型結(jié)合的方法，Wellekens和 Paliwal［10-11］先后提出了一種類似的DCMM模型，前者針對連續(xù)HMM情況，后者針對離散HMM情況。

2.2 模型符號化

本文研究的是輸出為離散的情況。一個(gè)雙鏈隱馬爾可夫模型包含2個(gè)隨機(jī)變量:St和Ut。St，Ut表示含義和HMM模型相同，即St表示隱狀態(tài)，Ut表示觀察序列。那么一個(gè)DCMM模型可以用一個(gè)3 元組表示:κ(π，A，C)［1］。

一個(gè)隱狀態(tài)的集合為G(S)={1，…，M}，一個(gè)可能輸出的集合為G(U)={1，…，N}，隱狀態(tài)的初始分布為π ={πi}，πi=P(S1=i)，1≤i≤M，隱狀態(tài)間的轉(zhuǎn)移概率矩陣為A={ai，j}，ai，j=P{St+1=j|St=i}，1≤i，j≤M。給定隱狀態(tài) St時(shí)連續(xù)輸出ut之間的轉(zhuǎn)移矩陣集合用C={C(k)}表示，其中C(k)=)i，j∈G(U)，k∈G(S)。

一個(gè)DCMM是馬爾可夫鏈和HMM的結(jié)合。當(dāng)只有一個(gè)隱狀態(tài)(M=1)時(shí)，DCMM變成一個(gè)轉(zhuǎn)移矩陣為C(1)的齊次馬爾可夫鏈;當(dāng)隱狀態(tài)數(shù)M＞1時(shí)，每個(gè)矩陣C(k)有相同的行，DCMM變成一個(gè)HMM。

2.3 DCMM的基本問題

1)模型給定時(shí)觀察序列u0，u1，…，uT的似然函數(shù)的估計(jì)。

2)給定觀察序列 u0，u1，…，uT時(shí)模型參數(shù)π、A、C 的估計(jì)。

3)在給定模型和一個(gè)輸出序列的情況下隱狀態(tài)序列的最優(yōu)估計(jì)。

3 HMM到DCMM的推導(dǎo)

在DCMM中向前、向后概率及Lk(t)、Hk，l(t)與在HMM中定義一樣，只做如下變換(t)中:

由HMM導(dǎo)出DCMM學(xué)習(xí)問題的EM算法，前兩步同HMM學(xué)習(xí)問題的EM算法，只需將第3步中的利用條件變?yōu)?/p>

由HMM導(dǎo)出的DCMM解碼問題的Viterbi算法:定義 δt(i)=maxP(s1，s2，…，st-1，st=i，u1，u2，…，ut|κ)，即求T時(shí)刻最大的δT(i)所代表的狀態(tài)序列。在解決HMM問題的Viterbi算法中做以下變換可得 解 決DCMM解碼問題的Viterbi算法。

根據(jù)文獻(xiàn)［1］，上述推導(dǎo)結(jié)果所得結(jié)論與文［1］中的結(jié)果相同，從而簡化了DCMM模型的參數(shù)估計(jì)算法推導(dǎo)過程。即經(jīng)過適當(dāng)?shù)淖兓梢詫MM的一套估計(jì)算法理論用到DCMM模型中。觀察序列u0，u1，…，uT的似然函數(shù)的估計(jì)，可以利用式(13)及DCMM向前概率、向后概率得到。給定觀察序列u0，u1，…，uT時(shí)，模型參數(shù) π、A、C的估計(jì)問題可以利用EM算法解決。在給定模型和一個(gè)輸出序列的情況下，隱狀態(tài)序列的最優(yōu)估計(jì)問題可以利用Viterbi算法解決。

4 推導(dǎo)條件分析

5 結(jié)束語

本文分別對HMM及DCMM進(jìn)行了介紹，發(fā)現(xiàn)并利用2種模型之間的關(guān)系，提出了從HMM到DCMM的推導(dǎo)條件，從而由HMM一套估計(jì)算法推導(dǎo)出了DCMM的一套估計(jì)算法，并分析驗(yàn)證了這種推導(dǎo)的可行性，從而完成了基于比較熟悉的HMM到不太熟悉的DCMM的研究，為算法創(chuàng)新提供了新的思路。

［1］Berchtold A.The Double Chain Markov Model［J］.Communications in Statistics-Theory and Methods，1999，28(11):1-8.

［2］Zucchini R W，Donald I M.Hidden Markov Models for Time Series An Introduction Using in R［M］.Boca RatonFL:Chapman ＆ Hall/CRC，2009.

［3］Li J.Hidden Markov Model-Penn State Department of Statistics［EB/OL］.［2002-08-22］.sites.stat.psu.edu/～jiali/course/stat597e/notes2/hmm.pdf.

［4］Olivier Cappé，Eric Moulines，Tobias Rydén.Inference in Hidden Markov Models［M］.New York:Springer，2005.

［5］Forney G D.The Viterbi Algorithm［J］.Proceedings of the IEEE，1973，61:268-278.

［6］Berchtold A.Learning in Markov Chains［C］//Apprentissage，des principes naturels aux methodes artificielles.Ritschard，Berchtold.Paris:HERMEZ，1998.

［7］Poritz A B.Linear predictive hidden Markov models and the speech signal［J］.Proceedings ICASSP，1982:1291-1294.

［8］Poritz A B.Hidden Markov models:A guided tour［J］.Proceedings ICASSP，1998，1:7-13.

［9］Kemeny P，Lennig M，Mermelstein P.A linear predictive HMM for vectorvalued observations with applications to speech recognition［J］.IEEE Transactions on Accoustics，Speech，and Signal Processing，1990，38(2):220-225.

［10］Wellekens C J.Explicit time correlation in Hidden Markov Models for speech recognition［J］.Proceedings ICASSP，1987:384-486.

［11］Paliwal K K.Use of temporal correlation between successive frames in a hidden Markov model based speech recognizer［J］.Proceedings ICASSP，1993，2:215-218.