馬爾可夫及隱馬爾可夫模型的應(yīng)用

黃崗

（西安體育學(xué)院 陜西 西安 710068）

馬爾可夫模型是由Andrei A Markov于1913年提出來(lái)的，作為一種統(tǒng)計(jì)模型，廣泛應(yīng)用在語(yǔ)音識(shí)別，詞性自動(dòng)標(biāo)注，音字轉(zhuǎn)換，概率文法等各個(gè)自然語(yǔ)言處理等應(yīng)用領(lǐng)域，到目前為止，它一直被認(rèn)為是實(shí)現(xiàn)快速精確的語(yǔ)音識(shí)別系統(tǒng)的最成功的方法[1]。而隱馬爾可夫模型是對(duì)馬爾可夫模型的一種擴(kuò)充，創(chuàng)立于20世紀(jì)60年代末70年代初。80年代得到了傳播和發(fā)展，成為信號(hào)處理的一個(gè)重要方向，同時(shí)開始應(yīng)用到生物序列尤其是DNA的分析中。從那時(shí)后起，在生物信息學(xué)領(lǐng)域HMM已經(jīng)變得無(wú)從不在。到了90年代，HMM還被引入計(jì)算機(jī)文字識(shí)別和移動(dòng)通信核心技術(shù)“多用戶的檢測(cè)”。20世紀(jì)90年代中期以后，隱馬爾可夫模型被引入到圖像處理和識(shí)別的研究中，并取得了一些初步的研究成果。HMM現(xiàn)已成功地用于語(yǔ)音識(shí)別，行為識(shí)別，文字識(shí)別以及故障診斷等領(lǐng)域[2]。目前的對(duì)于馬爾科夫和隱馬爾科夫模型的研究多為單一領(lǐng)域分析，尚不夠全面。本文通過(guò)整理分析馬爾科夫模型及隱馬爾可夫模型，主要針對(duì)兩個(gè)模型的應(yīng)用進(jìn)行分析，研究對(duì)比其在不同領(lǐng)域的應(yīng)用，分析其優(yōu)劣，進(jìn)一步提出了相關(guān)改進(jìn)建議和優(yōu)化措施。

1 馬爾可夫模型

馬爾可夫鏈?zhǔn)怯砂驳铝小ゑR爾可夫發(fā)現(xiàn)而得名的。在給定當(dāng)前知識(shí)或信息的情況下，過(guò)去（即當(dāng)期以前的歷史狀態(tài)）對(duì)于預(yù)測(cè)將來(lái)（即當(dāng)期以后的未來(lái)狀態(tài)）是無(wú)關(guān)的。一個(gè)簡(jiǎn)單?的例子，我們假設(shè)第二天的天氣狀況（晴天，陰天，雨天）只與今天的天氣狀況有關(guān)，與以前的狀況無(wú)關(guān)。并且，在今天天氣狀態(tài)已知的情況下，明天的天氣概率分布是確定的[3]。時(shí)間和狀態(tài)都是離散的馬爾可夫過(guò)程稱為馬爾可夫鏈，簡(jiǎn)記為Xn=X（n），n=0，1，2，…。馬爾可夫鏈?zhǔn)请S機(jī)變量X1，X2，X3…的一個(gè)數(shù)列。這些變量的范圍，即他們所有可能取值的集合，被稱為“狀態(tài)空間”，而Xn的值則是在時(shí)間n的狀態(tài)。如果Xn+1對(duì)于過(guò)去狀態(tài)的條件概率分布僅是Xn的一個(gè)函數(shù)，則P（Xn+1=x|X0，X1，X2，…，Xn|）=P（Xn+1=x|Xn）這 里x為 過(guò) 程 中 的 某 個(gè) 狀態(tài)。則這個(gè)恒等式可以被看作是馬爾可夫性質(zhì)。形式化地，我們可以認(rèn)為馬爾可夫鏈?zhǔn)菨M足下面兩個(gè)假設(shè)的一種隨機(jī)過(guò)程：

1）t+1時(shí)刻系統(tǒng)狀態(tài)的概率分布只與t時(shí)刻的狀態(tài)有關(guān)，與t時(shí)刻以前的狀態(tài)無(wú)關(guān)；

2）從t時(shí)刻到t+1時(shí)刻的狀態(tài)轉(zhuǎn)移與t的值無(wú)關(guān)。一個(gè)馬爾可夫鏈模型可表示為=（S，P，Q），其中各字母的含義如下：

1）S是系統(tǒng)所有可能的狀態(tài)所組成的非空的狀態(tài)集，有時(shí)也稱之為系統(tǒng)的狀態(tài)空間，它可以是有限的、可列的集合或任意非空集。文中假定S是可數(shù)集（即有限或可列）。用小寫字母i，j（或Si，Sj）等來(lái)表示狀態(tài)。

2）P=[Pij]n×n是系統(tǒng)的狀態(tài)轉(zhuǎn)移概率矩陣，其中Pij表示系統(tǒng)在時(shí)刻t處于狀態(tài)i，在下一時(shí)刻t+1處于狀態(tài)i的概率，N是系統(tǒng)所有可能的狀態(tài)的個(gè)數(shù)。對(duì)于任意i∈s，有3）Q＝[q1，q2…qn]是系統(tǒng)的初始概率分布，qi是系統(tǒng)在初始時(shí)刻處于狀態(tài)i的概率，滿足

為了更明晰地了解這個(gè)模型的意義，我們可以想一個(gè)有限狀態(tài)機(jī)，在不同狀態(tài)之間轉(zhuǎn)移有一個(gè)確定的概率分布。兩個(gè)狀態(tài)之間的概率就是在當(dāng)前狀態(tài)書籍的情況下，下一時(shí)間的狀態(tài)變?yōu)榱硪粋€(gè)節(jié)點(diǎn)狀態(tài)的概率。

2 隱馬爾可夫模型

馬爾可夫模型對(duì)日常的問(wèn)題有一個(gè)比較好的模型化描述。但是，這樣的模型研究?jī)r(jià)值并不大，因?yàn)樗袪顟B(tài)都已知了。另一方面，在很多情況下，我們對(duì)狀態(tài)是不能直接進(jìn)行觀測(cè)的，只能對(duì)狀態(tài)反應(yīng)出來(lái)的一部分性質(zhì)進(jìn)行觀測(cè)，這就導(dǎo)致了隱馬爾可夫模型（Hidden Markov Model）的提出。

隱馬爾可夫模型是馬爾可夫鏈的一種，它的狀態(tài)不能直接觀察到，但能通過(guò)觀測(cè)向量序列觀察到每個(gè)觀測(cè)向量都是通過(guò)某些概率密度分布表現(xiàn)為各種狀態(tài)，每一個(gè)觀測(cè)向量是由一個(gè)具有響應(yīng)概率密度分布的狀態(tài)序列產(chǎn)生[4]。它是一種用參數(shù)表示的用于描述隨機(jī)過(guò)程統(tǒng)計(jì)特性的概率模型，是一個(gè)雙重隨機(jī)過(guò)程，由兩個(gè)部分組成：馬爾可夫鏈和一般隨機(jī)過(guò)程。其中馬爾可夫鏈用來(lái)描述狀態(tài)的轉(zhuǎn)移，用轉(zhuǎn)移概率描述。一般隨機(jī)過(guò)程用來(lái)描述狀態(tài)與觀察序列間的關(guān)系，用觀察值概率描述[5]。

對(duì)于HMM模型，其的狀態(tài)轉(zhuǎn)換過(guò)程是不可觀察的，因而稱之為“隱”馬爾可夫模型。

HMM定義如下：

1）X代表一組狀態(tài)的集合，其中X＝{S1，S2，…，SN}，狀態(tài)數(shù)為N，并用qt來(lái)表示t時(shí)刻的狀態(tài)。雖然狀態(tài)是隱藏的，但對(duì)于很多應(yīng)用來(lái)說(shuō)，有一些物理的意義都和狀態(tài)或者狀態(tài)集相關(guān)。狀態(tài)內(nèi)部的聯(lián)系就是從一個(gè)狀態(tài)可以到其它狀態(tài)。

2）O代表一組可觀察符號(hào)的集合O＝{V1，V2，…，VM}，M是從每一狀態(tài)可能輸出的不同的觀察值的數(shù)目。

3）狀態(tài)轉(zhuǎn)移概率分布A＝{aij}，這里aij＝P{qi+1＝Sj|qt＝Si}，1＜i，j≤N。特殊情況下，每個(gè)狀態(tài)都可以一步到達(dá)其它任何狀態(tài)，這時(shí)對(duì)任意（i，j）有aij＞0。對(duì)于其他的HMM，可能有aij＝0（對(duì)于一對(duì)或多對(duì)i，j）。

4）狀態(tài)j的觀察概率分布B＝{bj（k）}，表示狀態(tài)j輸出相應(yīng)觀察值的概率，其中bj（k）＝P{Ot＝Vk|qt＝Sj}，1≤j≤N，1≤k≤M。

5）初始化狀態(tài)分布π＝{πi}，πi＝P{q1＝Si}，1≤i≤N。

由上，HMM可以定義為一個(gè)五元組λ：

λ＝（X，O，π，A，B）

或簡(jiǎn)寫為

λ＝（π，A，B）

上面所述HMM的3個(gè)關(guān)鍵元素實(shí)際可以分成兩部分，其一為Markov鏈，由π、A描述，另一部分是一個(gè)隨機(jī)過(guò)程，由B描述。

利用隱馬爾可夫模型，一般可以解決以下幾類經(jīng)典的問(wèn)題。

1）估值問(wèn)題。

給定觀察序列O＝O1O2…OT和模型λ＝（A，B，π），計(jì)算P（O|λ）。即給定模型和輸出觀察序列，如何計(jì)算從模型生成觀察序列的概率?？梢园阉醋魇窃u(píng)估一個(gè)模型和給定觀察輸出序列的匹配程度，由此可以用來(lái)在一系列候選對(duì)象中選取最佳的匹配。例如我們要預(yù)測(cè)未來(lái)足球比賽的勝負(fù)，我們會(huì)收集現(xiàn)在的信息，并找出以后一系列比賽最可能的結(jié)果。隱馬爾可夫模型可以給出每種可能結(jié)果出現(xiàn)的概率。

2）解碼問(wèn)題。

給定觀察序列O＝O1O2…OT和模型λ＝（A，B，π），求在某種有意義的情況下最優(yōu)的相關(guān)狀態(tài)序列Q＝q1q2…qT。該可以理解為對(duì)輸出觀察的最佳“解釋”，它試圖揭示模型的隱藏部分，比如說(shuō)查找“正確”的狀態(tài)序列，在應(yīng)用中，通常都使用一個(gè)優(yōu)化策略來(lái)最大可能的解決這個(gè)問(wèn)題。在智能電網(wǎng)的監(jiān)控中，我們想知道每個(gè)用電器的使用情況，但又不能對(duì)每一個(gè)用電器都安裝一個(gè)傳感器，成本太高，而且有的地方不適合安裝傳感器。因此只能壓縮采樣。這里采集的數(shù)據(jù)就可以看作實(shí)際情況——用電器開關(guān)狀態(tài)的一個(gè)性質(zhì)反應(yīng)。如果傳感器數(shù)量多，我們就可以利用馬爾可夫模型，以較高的精確度恢復(fù)用電器開關(guān)情況這一原始狀態(tài)。

3）學(xué)習(xí)問(wèn)題。

如何調(diào)整模型參數(shù)λ＝（A，B，π），對(duì)于一個(gè)給定的觀察序列O＝O1O2…OT，使得P（O|λ）最大。它試圖優(yōu)化模型的參數(shù)來(lái)最佳的描述一個(gè)給定的觀察序列是如何得來(lái)的。這里，我們有了所有的數(shù)據(jù)，但是想要一個(gè)馬爾可夫模型來(lái)簡(jiǎn)單地描述它。就需要求出相應(yīng)的參數(shù)。當(dāng)然，我們可以用這個(gè)模型來(lái)匹配已有的數(shù)據(jù)，來(lái)看它是否合理地?cái)M合了現(xiàn)在有數(shù)據(jù)。一般情況下，我們會(huì)用一部分?jǐn)?shù)據(jù)訓(xùn)練，用一部分?jǐn)?shù)據(jù)來(lái)測(cè)試，防止一些簡(jiǎn)單的高次擬合產(chǎn)生。

3 隱馬爾可夫模型的應(yīng)用

隱馬爾可夫模型有以下特點(diǎn)：

1）HMM具有強(qiáng)有力的時(shí)間序列建模能力，在應(yīng)用與模式識(shí)別時(shí)具有一些獨(dú)特的優(yōu)勢(shì)，主要體現(xiàn)在整體和局部都具備平移不變性。HMM的核心是有限狀態(tài)自動(dòng)機(jī)，這賦予了它解決局部平移問(wèn)題的能力[6]。

2）HMM體現(xiàn)了類似結(jié)構(gòu)方法的一些特點(diǎn)，從而可能具備結(jié)構(gòu)方法的部分優(yōu)點(diǎn)。作為一種統(tǒng)計(jì)模型，隱馬爾可夫模型仍然是基于特征以及貝葉斯決策進(jìn)行判別，但是與一般統(tǒng)計(jì)方法和模型不同，它需要根據(jù)先驗(yàn)知識(shí)和對(duì)隨機(jī)信號(hào)結(jié)構(gòu)的分析構(gòu)造一個(gè)合適的有限狀態(tài)自動(dòng)機(jī)作為其隱含層的拓?fù)浣Y(jié)構(gòu)，這種有限狀態(tài)自動(dòng)機(jī)實(shí)際上描述了信號(hào)的發(fā)生機(jī)制，因此，它的拓?fù)浣Y(jié)構(gòu)包含了信號(hào)的部分結(jié)構(gòu)信息。

因此，它在許多領(lǐng)域，多括模式識(shí)別，天氣預(yù)測(cè)，文字識(shí)別，語(yǔ)言翻譯等領(lǐng)域有廣泛的用途[7]。幾個(gè)典型的應(yīng)用如下：

1）語(yǔ)音識(shí)別

已知標(biāo)準(zhǔn)語(yǔ)音序列w1，w2，…，wn，求待測(cè)序列c1，c2，…，cn的含義

HMM模型：將每句話為理解為狀態(tài)；將輸入的待測(cè)樣本為理解為觀測(cè)值。

訓(xùn)練：統(tǒng)計(jì)狀態(tài)轉(zhuǎn)移矩陣和語(yǔ)言序列到觀測(cè)序列的輸出矩陣。

求解：采用Viterbi算法

步驟：聲音采樣——傅立葉到頻域——頻域特征向量提取——輸入樣本——構(gòu)造HMM——輸入聲音——求解模型

2）疾病分析

已知疾病序列w1，w2，…，wn，求表征序列c1，c2，…，cn對(duì)應(yīng)狀態(tài)轉(zhuǎn)移過(guò)程。

HMM模型：將每種疾病為理解為狀態(tài)；將輸入的表征現(xiàn)象為理解為觀測(cè)值。

訓(xùn)練：統(tǒng)計(jì)從一種疾病轉(zhuǎn)變到另一種疾病的概率轉(zhuǎn)移矩陣和某一疾病呈現(xiàn)出某一癥狀的概率矩陣。

求解：采用Viterbi算法。

3）詞性標(biāo)注

已知單詞序列w1，w2，…，wn，求詞性序列c1，c2，…，cn。

HMM模型：將詞性為理解為狀態(tài)；將單詞為理解為輸出值。

訓(xùn)練：統(tǒng)計(jì)詞性轉(zhuǎn)移矩陣和詞性到單詞的輸出矩陣。

求解：Viterbi算法。

4 結(jié)束語(yǔ)

馬爾可夫模型還是有很多局限性的。它的一些假設(shè)忽略了實(shí)際的細(xì)節(jié)。具體來(lái)說(shuō)，以下幾個(gè)方面：

1）HMM在默認(rèn)的情況下僅指一階隱馬爾可夫模型，一階隱馬爾可夫模型中有3個(gè)重要假設(shè)：①狀態(tài)轉(zhuǎn)移的Markov假設(shè)：系統(tǒng)在當(dāng)前時(shí)刻的狀態(tài)向下一時(shí)刻所處的狀態(tài)轉(zhuǎn)移的狀態(tài)轉(zhuǎn)移概率僅僅與當(dāng)前時(shí)刻的狀態(tài)有關(guān)，而與以前的歷史無(wú)關(guān)。②不動(dòng)性假設(shè)，即狀態(tài)與具體時(shí)間無(wú)關(guān)。③輸出值的Markov假設(shè)：系統(tǒng)在當(dāng)前時(shí)刻輸出觀測(cè)值的概率，只取決于當(dāng)前時(shí)刻的狀態(tài)而與當(dāng)前時(shí)刻以前的時(shí)刻所處的狀態(tài)無(wú)關(guān)。而在實(shí)際應(yīng)用中，這樣假設(shè)并不十分合理，因?yàn)槿我粫r(shí)刻出現(xiàn)的觀測(cè)值的概率不僅僅依賴于系統(tǒng)當(dāng)前所處的狀態(tài)，也可能依賴于系統(tǒng)在之前時(shí)刻所處的狀態(tài)[8]。

2）經(jīng)典隱馬爾可夫模型理論具有狀態(tài)集固定的缺陷，這種缺陷影響了隱馬爾可夫模型對(duì)隨機(jī)信號(hào)建模的能力，并限制了基于隱馬爾可夫模型的分類器的性能。利用隱馬爾可夫模型對(duì)任何信號(hào)建模都存在這樣的問(wèn)題，被建模的信號(hào)比較簡(jiǎn)單或者包含信息量比較一致（如語(yǔ)音），基于先驗(yàn)知識(shí)預(yù)先定義狀態(tài)集或者通過(guò)多次實(shí)驗(yàn)選擇一種比較合適的固定狀態(tài)集基本上就能描述所有的模式。而圖像則不同，圖像包含的信息量非常豐富，這就導(dǎo)致不同圖像之間的信息量差距相應(yīng)的不可避免的要大，因此這個(gè)問(wèn)題在圖像處理中就暴露得比較明顯。因此，在實(shí)際應(yīng)用中，隱馬爾可夫模型有很多的改進(jìn)模型，使其能更了的匹配實(shí)際狀態(tài)。例如，在用電器監(jiān)測(cè)中，我們假設(shè)同一時(shí)間開關(guān)的用電器數(shù)目有一個(gè)上界，那么許多狀態(tài)轉(zhuǎn)移是不可能發(fā)生的。又如，我們對(duì)一個(gè)用電器的開關(guān)時(shí)間長(zhǎng)短作一個(gè)簡(jiǎn)單的統(tǒng)計(jì)，那么在某一狀態(tài)的概率中，我們還要考慮這一狀態(tài)中用電器開關(guān)時(shí)間的概率，可以對(duì)這一狀態(tài)的發(fā)生概率作一次修正。這是傳統(tǒng)的的馬爾可夫模型所不能做到的。

[1]李相勇，張南，蔣葛夫.道路交通事故灰色馬爾可夫預(yù)測(cè)模型[J].公路交通科技，2003，20（4）：98－100.LI Xiang-yong，ZHANG Nan，JIANG Ge-fu.Grey-markov model for forecasting road accidents[J].Journal of Highway and Transportation Research and Development，2003，20（4）：98－100.

[2]劉克.實(shí)用馬爾可夫決策過(guò)程[M].清華大學(xué)出版社，2004.

[3]施程，桑廣書.基于加權(quán)馬爾可夫鏈的杭州市年降水量預(yù)測(cè)[J].浙江水利科技，2012（15）：21－23，44.SHI Cheng，SANG Guang-shu.An annual precipitation prediction based on weighted markov Chain in hangzhou[J].Zhejiang Hydrotechnics，2012（15）：21－23，44.

[4]羅宇，杜利民.基于隱馬爾可夫模型局部最優(yōu)狀態(tài)路徑的數(shù)據(jù)重建算法[J].電子與信息學(xué)報(bào)，2004（5）：722－726.LUO Yu，DU Li-min.HMM local optimal state path-based data imputation[J].Journal of Electronics and Information Technology，2004（5）：722－726.

[5]何彥斌，楊志義，馬薈，等.一種基于HMM的場(chǎng)景識(shí)別方法[J].計(jì)算機(jī)科學(xué)，2011（4）：254－256.HE Yan-bin，YANG Zhi-yi，MA Hui，et al.Method of situation recognition based on hidden markov model[J].Computer Science，2011（4）：254－256.

[6]潘奇明，程詠梅.基于隱馬爾可夫模型的運(yùn)動(dòng)目標(biāo)軌跡識(shí)別[J].計(jì)算機(jī)應(yīng)用研究，2008（7）：1988－1991.PAN Qi-ming，CHENG Yong-mei.Trajectory recognition of moving objects basedon hidden Markov model[J].Application Research of Computers，2008（7）：1988－1991.

[7]李楠，姬光榮.基于不同隱馬爾科夫模型的圖像識(shí)別方法[J].現(xiàn)代電子技術(shù)，2012（8）：54－56，60.LI Nan，JI Guang-rong.Image recognition algorithms based on different hidden Markov models[J].Modern Electronics Technique，2012（8）：54－56，60.

[8]劉云中，林亞平，陳治平.基于隱馬爾可夫模型的文本信息抽取[J].系統(tǒng)仿真學(xué)報(bào)，2004（3）：507－510.LIU Yun-zhong，LIN Ya-ping，CHEN Zhi-ping.Text information extraction based on hidden markov model[J].Acta Simulata Systematica Sinica，2004（3）：507－510.