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

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

(新疆大學數學與系統科學學院，烏魯木齊 830046)

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

1 隱馬爾可夫模型

1.1 HMM符號化

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

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

1.2 與HMM問題有關的概念及算法

1.2.1 觀察序列的聯合概率［2］

1.2.2 向前向后概率［3］

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

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

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

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

在一組給定的參數集下，定義:

不加證明地給出以下結論:

1.2.4 HMM學習問題的EM算法［4］

EM算法步驟如下:

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

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

定義 δt(i)=maxP(s1，s2，…，st-1，st=i，u1，u2，…，ut|λ)，即求 T 時刻最大的 δ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是一個未知(隱)模型和一個已知(明)模型的特性的某種組合，之所以稱其為雙鏈，是因為它可以被看作2個馬爾可夫鏈的疊加。其中的隱鏈控制一個未觀察到的變量的狀態之間的關系，明鏈控制一個觀察到的變量的輸出之間的關系。DCMM是為非齊次時間序列建模而設計的。Berchtold［6］提出:如果一個時間序列可被分解成一個有限的轉移矩陣的集合，那么DCMM可以用來控制這些矩陣的轉移過程。模型的結構可以用圖1描述。

圖1 雙鏈馬爾可夫模型結構

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

2.2 模型符號化

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

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

一個DCMM是馬爾可夫鏈和HMM的結合。當只有一個隱狀態(M=1)時，DCMM變成一個轉移矩陣為C(1)的齊次馬爾可夫鏈;當隱狀態數M＞1時，每個矩陣C(k)有相同的行，DCMM變成一個HMM。

2.3 DCMM的基本問題

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

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

3)在給定模型和一個輸出序列的情況下隱狀態序列的最優估計。

3 HMM到DCMM的推導

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

由HMM導出DCMM學習問題的EM算法，前兩步同HMM學習問題的EM算法，只需將第3步中的利用條件變為

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

根據文獻［1］，上述推導結果所得結論與文［1］中的結果相同，從而簡化了DCMM模型的參數估計算法推導過程。即經過適當的變化，可以將HMM的一套估計算法理論用到DCMM模型中。觀察序列u0，u1，…，uT的似然函數的估計，可以利用式(13)及DCMM向前概率、向后概率得到。給定觀察序列u0，u1，…，uT時，模型參數 π、A、C的估計問題可以利用EM算法解決。在給定模型和一個輸出序列的情況下，隱狀態序列的最優估計問題可以利用Viterbi算法解決。

4 推導條件分析

5 結束語

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

［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.