二階離散隱馬爾科夫模型的嚴格定義及等價性質(zhì)

孫穎華，楊衛(wèi)國

（江蘇大學理學院，江蘇 鎮(zhèn)江212013）

二階離散隱馬爾科夫模型的嚴格定義及等價性質(zhì)

孫穎華，楊衛(wèi)國

（江蘇大學理學院，江蘇 鎮(zhèn)江212013）

隱馬氏模型作為一種具有雙重隨機過程的統(tǒng)計模型，具有可靠的概率統(tǒng)計理論基礎(chǔ)和強有力的數(shù)學結(jié)構(gòu)，已被廣泛應用于語音識別、生物序列分析、金融數(shù)據(jù)分析等領(lǐng)域.由于傳統(tǒng)的一階隱馬氏模型無法表示更遠狀態(tài)距離間的依賴關(guān)系，就可能會忽略很多有用的統(tǒng)計特征，故有人提出二階隱馬氏模型的概念，但此概念并不嚴格.本文給出二階離散隱馬爾科夫模型的嚴格定義，并研究了二階離散隱馬爾科夫模型的兩個等價性質(zhì).

二階隱馬爾科夫模型；觀測鏈；隱藏鏈

1 引言

在傳統(tǒng)的一階隱馬氏模型中存在兩個過程，分別是觀測過程和狀態(tài)過程.關(guān)于觀測過程，假設(shè)在給定當前狀態(tài)的前提下，將來符號的發(fā)出概率獨立于以前所有的狀態(tài)和發(fā)出的符號；關(guān)于狀態(tài)過程，假設(shè)在給定當前狀態(tài)的前提下，下一步狀態(tài)的轉(zhuǎn)移概率獨立于以前所有的狀態(tài)和發(fā)出的符號.起初一階隱馬氏模型被用于語音識別、模式識別和隨機信號方面［1-2］.近年來，研究者們又嘗試將其用于生物信息學研究中，如DNA建模、基因檢測［3］.2002年，文獻［4］對一階隱馬氏模型給出了系統(tǒng)總結(jié).但此類模型無法表示更遠狀態(tài)距離間的依賴關(guān)系，就可能會忽略很多有用的統(tǒng)計特征.例如：在文本信息抽取中，簡單的一階隱馬氏模型沒有考慮上下文特征等信息對抽取性能的作用，也未考慮狀態(tài)轉(zhuǎn)移概率和觀察值輸出概率與模型歷史狀態(tài)的關(guān)聯(lián)性；在研究語音信號時，假設(shè)各個分段內(nèi)的各幀語言信號是相互獨立的，就會忽略幀與幀之間的相關(guān)性；在對生物序列的研究中，待研究的生物序列的殘基之間也有很高的相關(guān)性，但在此類模型中未涉及.

為了克服一階隱馬氏模型的不足和缺陷，研究者們從不同角度做了改進，提出一些改進措施.其中之一就是考慮狀態(tài)轉(zhuǎn)移概率和符號發(fā)出概率與之前兩個狀態(tài)的依賴關(guān)系，提出了二階隱馬爾科夫模型.

文獻［5］基于一階隱馬氏模型的狀態(tài)序列獲得了一類二階隱馬氏模型解碼問題的Viterbi算法.文獻［6］研究了二階隱馬氏模型在語音識別中的應用，為語音識別中的狀態(tài)延續(xù)現(xiàn)象提供一個合理解釋，提高了識別效果.文獻［7］系統(tǒng)研究了二階隱馬氏模型三個基本問題算法，并研究了與一階隱馬氏模型之間的關(guān)系，并給出等價性定理.文獻［8］在傳統(tǒng)的隱馬氏模型的基礎(chǔ)上，研究改進了Baum-Welch算法，并導出了改進模型的參數(shù)估計公式.文獻［9］利用二階隱馬氏模型研究時空數(shù)據(jù)挖掘問題，表明二階隱馬氏模型對平穩(wěn)段定位具有非常好的性能.文獻［10］提出了基于二階隱馬氏模型的文本信息抽取算法，分析了其在文本信息抽取中的有效性，最終證得新算法提高了抽取精度.文獻［11］提出了基于二階隱馬爾可夫模型，表明新模型較傳統(tǒng)的模型有更高的詞性標注正確率和消歧率.文獻［12］研究了二階隱馬氏模型的基本算法，將二階隱馬氏模型（second-order hidden markov model，簡記為HMM2）應用到microRNA（miRNA）靶基因預測的后期過濾處理中，也取得較好效果.文獻［13］就高階隱馬爾可夫模型算法基礎(chǔ)中的EM算法（expectation-maximization algorithm）和動態(tài)規(guī)劃進行了一定梳理分析，從而促進高階隱馬氏模型在實際中的應用.

目前，二階隱馬爾科夫模型已被廣泛的應用，但還未發(fā)現(xiàn)其嚴格定義.在本文中，仿照文獻［4］中的一階隱馬氏模型的嚴格定義，給出二階離散隱馬氏模型的嚴格定義并研究了二階離散隱馬氏模型的兩個等價性質(zhì).

2 定義

定義2.1設(shè)S=｛1，2，···，N｝，L=｛1，2，···，M｝為兩有限狀態(tài)空間，X=｛Xn，n≥0｝，Y=｛Yn，n≥0｝是分別在S與L上取值的隨機變量序列.如果X=｛Xn，n≥0｝為二階隱馬氏鏈，其二維初始分布與二階轉(zhuǎn)移矩陣分別為：

則稱｛X，Y｝=｛Xn，Yn，n≥0｝是二階隱馬爾科夫模型.X=｛Xn，n≥0｝被稱為二階隱馬氏模型的隱藏鏈，Y=｛Yn，n≥0｝被稱為二階隱馬氏模型的觀測鏈.

3 主要結(jié)果

在給出二階離散隱馬爾科夫模型的嚴格定義后，本節(jié)研究二階離散隱馬氏模型的兩個等價性質(zhì).

引理3.1設(shè)X=｛Xn，n≥0｝與Y=｛Yn，n≥0｝是分別在S與L上取值的隨機變量序列，則（3）式成立的充要條件是：對任意n≥1，有

定理3.1設(shè)X=｛Xn，n≥0｝，Y=｛Yn，n≥0｝如前定義，則｛X，Y｝=｛Xn，Yn，n≥0｝為由定義1.1定義的二階隱馬爾科夫模型的充要條件是：?n≥1，

證明 由引理及二階馬氏鏈的等價性，可得本定理成立.

注3.1由公式（12）可得到文獻［15］中公式（6）.

定理3.2設(shè)X=｛Xn，n≥0｝，Y=｛Yn，n≥0｝如前定義，則｛X，Y｝=｛Xn，Yn，n≥0｝為由定義1.1定義的二階隱馬爾科夫模型的充要條件是：?n≥2，

注3.2公式（13）與公式（14）即為文獻［15］中公式（5）與公式（4）在m=2，n=2時的情形.

［1］Levinson S E.Structual methods in automatic speech recognition［J］.Proceeding of the IEEE，1985，73：1625-1650.

［2］Rabiner L R.A tutorial on hidden markov models and selected applications in speech recognition［J］. Proceeding of the IEEE，1989，77（2）：257-286.

［3］王翼飛，史定華.生物信息學-智能化算法及其應用［M］.北京：化學工業(yè)出版社，2006.

［4］Ephraim Y，Merhav N.Hidden Markov process［J］.IEEE Transactions on Information Theory，2002，48（6）：1518-1569.

［5］He Y.Extended Viterbi algorithm for second order hidden Markov process［J］.IEEE 9th International Conference on Pattern Recognition，1988，2：718-720.

［6］Mari J F，Haton J P，Kriouile A.Automatic word recognition based on second-order hidden Markov models［J］.IEEE Trans.Speech Audio Processing，1997，5（1）：22-25.

［7］史笑興，王太君，何振亞.二階隱馬爾科夫模型的學習算法及其與一階隱馬爾科夫模型的關(guān)系［J］.應用科學學報，2001，19（1）：29-32.

［8］杜世平，李海.二階隱馬爾可夫模型及其在計算語言學中的應用［J］.四川大學學報，2004，41（2）：284-289.

［9］Mari J F，Le Ber F.Temporal and spatial data mining with second-order hidden Markov models［J］.Soft Computing，2006，10（5）：406-414.

［10］周順先，林亞平，王耀南，等.基于二階隱馬爾可夫模型的文本信息抽取［J］.電子學報，2007，35（11）：2226-2231.

［11］劉潔彬，宋茂強，趙方，等.基于上下文的二階隱馬爾可夫模型［J］.計算機工程，2010，36（10）：231-235.

［12］高松，秦殿剛，馮鐵男，等.二階HMM算法改進及在miRNA靶基因預測中的應用［J］.應用科學學報，2010，28（3）：307-312.

［13］葉飛.隱馬爾可夫模型算法基礎(chǔ)探析［J］.銅陵學院學報，2014，3：108-112.

［14］Chung K L.A Course in Probability Theory［M］.London：Academic Press，2010.

［15］葉飛，王翼飛.高階隱馬氏模型研究進展［J］.數(shù)學進展，2014，43（2）：219-231.

The strict definition of second-order discrete hidden Markov model and its equivalent nature

Sun Yinghua，Yang Weiguo

（Faculty of Science，Jiangsu University，Zhenjiang212013，China）

Hidden Markov model，as a statistical model of doubly stochastic process，has a reliable theoretical foundation in probability and statistics and strong mathematical structure.It has been widely used in speech recognition，biological sequence analysis，financial data analysis，etc.As the conventional first-order hidden Markov model can not express the dependency relationship between the further distance，many useful statistical characteristic were ignored in many works.Therefore，the concept of second-order hidden Markov model was put forward，but this concept is not strict.In this paper，we give the strict definition of second-order discrete hidden Markov model and study two equivalent properties of the second-order discrete hidden Markov model.

second-order hidden Markov model，observation chain，hidden chain

O211.62

A

1008-5513（2015）04-0380-07

10.3969/j.issn.1008-5513.2015.04.007

2015-04-07.

國家自然科學基金（11071104）.

孫穎華（1991-），碩士生，研究方向：隱馬爾科夫模型.

2010 MSC:60J05