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

孫穎華，楊衛國

（江蘇大學理學院，江蘇 鎮江212013）

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

孫穎華，楊衛國

（江蘇大學理學院，江蘇 鎮江212013）

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

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

1 引言

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

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

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

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

2 定義

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

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

3 主要結果

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

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

定理3.1設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設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］.北京：化學工業出版社，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］史笑興，王太君，何振亞.二階隱馬爾科夫模型的學習算法及其與一階隱馬爾科夫模型的關系［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］葉飛.隱馬爾可夫模型算法基礎探析［J］.銅陵學院學報，2014，3：108-112.

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

［15］葉飛，王翼飛.高階隱馬氏模型研究進展［J］.數學進展，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