劉功生，張春良，岳 夏，朱厚耀

（1.南華大學(xué)機(jī)械工程學(xué)院，湖南衡陽 421001；2.廣州大學(xué)機(jī)械與電氣工程學(xué)院，廣東廣州 510006）

基于HMM算法體系的逆維特比算法理論研究*

劉功生1，張春良2，岳 夏2，朱厚耀2

（1.南華大學(xué)機(jī)械工程學(xué)院，湖南衡陽 421001；2.廣州大學(xué)機(jī)械與電氣工程學(xué)院，廣東廣州 510006）

隱馬爾可夫模型（Hidden Markov Model，HMM）的基本算法體系主要包括Baum-Welch算法、前向-后向算法與Viterbi算法三大經(jīng)典算法，通過展開對HMM新問題及新算法的理論研究，引出逆維特比問題及逆維特比算法的理論體系，并提出將逆維特比算法引入HMM基本算法體系中構(gòu)建一種新的算法體系及一種新評估體系的構(gòu)想，最后對新算法體系的應(yīng)用進(jìn)行了展望。

隱馬爾科夫模型；逆維特比問題；逆維特比算法；評估體系

HMM本身是一個雙隨機(jī)過程，同時具有出色的動態(tài)過程建模能力[1]，因此HMM在語音識別、故障診斷及生物醫(yī)學(xué)等領(lǐng)域獲得了廣泛的應(yīng)用[2-4]。

在HMM經(jīng)典算法體系中，Baum-Welch算法雖然已發(fā)展得相當(dāng)成熟，但在實際應(yīng)用中仍存在訓(xùn)練過程局部收斂及訓(xùn)練結(jié)果魯棒性不足等缺點[5]。因此，尋求一種能對訓(xùn)練結(jié)果進(jìn)行有效評價的方法將越顯重要。在故障診斷領(lǐng)域中，HMM提供了一種以似然率大小作為訓(xùn)練模型性能好壞的評價標(biāo)準(zhǔn)的評估算法，但該評估方法存在似然率高時識別率不一定高的不足，即用似然率的高低來評價訓(xùn)練模型的性能好壞將會導(dǎo)致故障診斷結(jié)果存在一定的誤判風(fēng)險。因此進(jìn)行HMM新算法的研究并建立新的評估算法將具有很高的研究價值。本文中將以故障診斷作為HMM的應(yīng)用背景來展開對HMM新算法理論及新評估體系的研究。

1 HMM三大基本算法體系

1.1 HMM三大基本問題及算法

在HMM的基本理論框架中，HMM能用來求解的三大基本問題[6]為：學(xué)習(xí)問題、評估問題及解碼問題。該三大基本問題可簡單描述為：學(xué)習(xí)問題主要是獲取給定觀測值序列的HMM模型；評估問題主要是計算所獲得的HMM模型與輸入觀測值序列的似然率；解碼問題主要是在給定HMM模型情況下尋找對應(yīng)觀測值序列的最優(yōu)狀態(tài)序列。

在HMM的理論框架中同時也給出了求解以上三大基本問題的三大經(jīng)典算法[6]：訓(xùn)練問題的Baum-Welch算法、評估問題的前向或后向算法、解碼問題的Viterbi算法。此三大基本算法之間通過內(nèi)在的聯(lián)系構(gòu)成了經(jīng)典的HMM算法體系，如圖1所示。

圖1 HMM基本算法體系

圖1中，對于機(jī)械故障診斷過程，觀測序列1和觀測序列2均是由采集到的故障樣本通過特征提取獲得，其中，觀測序列1由用于訓(xùn)練的樣本獲得，觀測序列2由用于測試的樣本獲得。觀測序列1通過Baum-Welch訓(xùn)練算法可以獲得相應(yīng)狀態(tài)的HMM模型λ，但由于該訓(xùn)練算法在迭代過程中存在易陷入局部收斂的不足，難以保證訓(xùn)練結(jié)果為最優(yōu)。在設(shè)備狀態(tài)識別過程中，不良的訓(xùn)練結(jié)果將會導(dǎo)致識別率下降，因此訓(xùn)練的結(jié)果需要預(yù)先進(jìn)行模型性能的評估，性能較低的訓(xùn)練結(jié)果不能加入HMM模型庫。HMM算法體系中提供了前向——后向算法作為訓(xùn)練結(jié)果的評估算法，對于性能評估良好的模型才能作為Viterbi算法的輸入，用于進(jìn)行設(shè)備運行狀態(tài)的識別。

因此，三大經(jīng)典算法通過其內(nèi)在的聯(lián)系聯(lián)結(jié)在一起，構(gòu)成了HMM的基本算法體系，并為故障診斷提供一種有效的算法模型。

1.2 維特比算法的實現(xiàn)過程

由于維特比問題的目的是要尋找給定模型λ和觀測序列O的最優(yōu)狀態(tài)序列Q*，對應(yīng)的viterbi算法[7-8]實現(xiàn)過程如下：

（1）首先定義兩個變量：

（2）初始化定義的兩個變量：

（3）變量的迭代計算過程：

（4）終結(jié)迭代過程

（5）回溯最優(yōu)路徑

由Viterbi過程總結(jié)出兩大約束條件：

（1）最優(yōu)路徑條件需保證T時刻滿足：

（2）最優(yōu)路徑回溯條件應(yīng)滿足：

2 逆維特比算法理論框架構(gòu)建

2.1 逆維特（Inv-Viterbi）比問題的提出

根據(jù)維特比問題的定義可以相應(yīng)地把逆維特比問題[9]描述為：對于給定的HMM模型λ及一狀態(tài)序列Q，如何確定一觀測值序列O，使得所給的狀態(tài)序列為所求觀測值序列的最優(yōu)狀態(tài)序列。

2.2 逆維特比算法實現(xiàn)過程

逆維特比問題的提出后，最關(guān)鍵的就是要建立某種算法來實現(xiàn)它，用于解決逆維特比問題的算法稱為逆維特比算法。逆維特比算法實現(xiàn)過程是通過對維特比算法實現(xiàn)過程添加某種約束條件及觀測值的挑選規(guī)則而推導(dǎo)出來的。推導(dǎo)過程定義如下。

（1）定義一個變量Mt(i)，表示的是所給定的最優(yōu)狀態(tài)路徑上到達(dá)t時刻狀態(tài)為Si的前續(xù)路徑累積概率，其初始化值定義為：

迭代過程定義為：

上式中的πi為狀態(tài)i的初始狀態(tài)概率，aij表示為狀態(tài)轉(zhuǎn)移概率，bi(Ot-1)表示的是t-1時刻在狀態(tài)i觀測到觀測值Ot-1的概率。

（2）定義約束條件

約束條件一：

約束條件二：

上式中，qt表示的是已經(jīng)給定了的狀態(tài)路徑Q=q1,q2,…,qT中t時刻的狀態(tài)。其中不等式（5）和（6）中的約束條件是通過對Viterbi過程的約束條件（1）和（2）分析得來。通過引入這兩個約束條件可以確保選取的觀測值序列能滿足最優(yōu)路徑的要求。由于任意時刻t的觀測值Ot都是從觀測值空間Vt={v1,v2,…,vM}中選取，為了壓縮可能的觀測序列搜索空間，提高觀測值選取效率，需要進(jìn)一步提出觀測值序列的選擇規(guī)則。

（3）建立觀測值的選擇規(guī)則

1）篩選規(guī)則1：任意時刻t選取的觀測值Ot必須要滿足約束條件一，若不滿足該約束條件的則應(yīng)該將其從觀測值空間中除去，可以進(jìn)行初步壓縮搜索空間；

2）篩選規(guī)則2：若在任意時刻t中應(yīng)用完篩選規(guī)則1后觀測值空間中剩余的觀測值數(shù)量還多于一個，則選取剩余觀測值中的任意兩個觀測值v和v?，如果選取v?為t時刻觀測值時，對于t+1時刻任意狀態(tài)i≠qt+1，由Mt+1(qt+1)-Mt+1(i)所求得的N-1維向量 μ的各個分量均比選取v為t時刻的觀測值大或相等時，從觀測值空間中去除v，進(jìn)一步壓縮搜索空間。

則逆維特比算法的實現(xiàn)流程如下：

1）初始化初始觀測值為O0=ε,ε為一常量；

2）令t=1;

3）應(yīng)用篩選規(guī)則1對t時刻可能取得的觀測值進(jìn)行初步篩選，獲得長度為t的觀測值序列組Ot=Ot-1Ot，其中Ot（為粗體，表示的是序列）是有t時刻之前的長度為t-1的序列Ot-1增加t時刻的觀測值Ot構(gòu)成的觀測值序列，其可能包含多個滿足條件的觀測值序列；

4）應(yīng)用篩選規(guī)則2對步驟3中剩余的多個觀測值序列進(jìn)行深度篩選，壓縮觀測值序列組Ot的中觀測序列的數(shù)量；

5）令t=t+1，若t＜T（T為所給狀態(tài)序列長度），返回步驟3繼續(xù)執(zhí)行，否則往下執(zhí)行步驟6；

6）運用約束條件二對前面步驟剩下的觀測值序列組Ot進(jìn)行最終的篩選，最后剩下的觀測值序列則為逆維特比算法所要求得觀測值序列。

3 HMM新評估體系構(gòu)建

本研究中把逆維特比算法的理論引入到HMM基本算法體系中與維特比算法有效結(jié)合，構(gòu)造一種新的HMM評估體系，如圖2所示。

圖2 逆維特比閉環(huán)評估體系

圖2中，通過計算逆維特比算法的輸出觀測值序列3與維特比算法的輸入觀測值序列2的相似度來作為HMM模型λ性能的評估標(biāo)準(zhǔn)。

圖3 模型與序列關(guān)系圖

從理論上來說，序列3與序列2應(yīng)該是相同的序列，但從圖3中可以看出，HMM模型參數(shù)λ與維特比算法及逆維特比算法的輸入及輸出序列是密切相關(guān)的，因此HMM模型λ性能的好壞將會影響到逆維特比算法的最終輸出結(jié)果。而在實際的應(yīng)用中，由于HMM的訓(xùn)練算法自身的不足，最終將會影響其訓(xùn)練結(jié)果的可靠性，使訓(xùn)練出來的模型λ難以獲得最優(yōu)性能。因此序列3一般情況下并不是與序列2完全相同的，而且很多時候相差較大，但模型的性能與兩觀測序列的相似程度存在某種內(nèi)在的聯(lián)系，因此可以通過計算兩個序列的相似度大小來作為模型性能好壞的量度，而相似度可通過相關(guān)系數(shù)來衡量。

相關(guān)系數(shù)的計算式為：

式中，x與y表示的是兩個長度為N的序列，xˉ與yˉ分別表示的是兩序列的算術(shù)平均值。相關(guān)系數(shù)的取值范圍為0≤|ρxy|≤1，相關(guān)系數(shù)值越大表明模型性能就越好，反之則性能就越低。

通過引入相似程度的計算，與逆維特比算法及維特比算法一起建立一種HMM模型性能的新評估體系，且這種評估體系為一種閉環(huán)的評估體系，對于將評估結(jié)果作為訓(xùn)練算法的反饋建立一種閉環(huán)訓(xùn)練體系具有一定的指導(dǎo)意義。

4 展望

HMM新評估體系建立后不僅是HMM算法體系的一個補充，而且將對HMM體系的進(jìn)一步研究提供了新的思路。

（1）HMM循環(huán)訓(xùn)練體系。通過新建立的閉環(huán)評估體系與HMM訓(xùn)練算法結(jié)合，同時引入K-means聚類算法，在模型訓(xùn)練中根據(jù)評估結(jié)果來評判模型性能的好壞。若訓(xùn)練結(jié)果不理想，則通過聚類算法重新優(yōu)化模型初始值，進(jìn)入下一次的訓(xùn)練及評估過程，如此，通過訓(xùn)練——評估——再訓(xùn)練——再評估過程建立起一種HMM閉環(huán)訓(xùn)練體系。

（2）新型HMM訓(xùn)練算法。逆維特比算法的實現(xiàn)將對HMM其它新算法及理論的研究提供一定的參考價值與指導(dǎo)意義。由圖3可知，HMM模型λ是觀測值序O與狀態(tài)序列Q的連接橋梁，通過Viterbi算法可以實現(xiàn)以觀值序列O及HMM模型λ作為輸入最終獲得狀態(tài)序列Q，而通過逆維特比算法又可以通過輸入狀態(tài)序列Q及HMM模型λ而獲得觀測值序列O，那么理論上來說也可以參考維特比及逆維特比算法的實現(xiàn)過程來建立另外一種新的問題和算法來實現(xiàn)輸入觀測值序列O及狀態(tài)序列Q最終輸出HMM模型λ，從而實現(xiàn)一種新的HMM訓(xùn)練算法。

［1］騰格爾，賀昌政，蔣曉毅.隱馬爾可夫模型研究進(jìn)展及其管理領(lǐng)域應(yīng)用［J］.軟科學(xué)，2012，26（2）：122-126.

［2］朱明，郭春生.隱馬爾可夫模型及其最新應(yīng)用與發(fā)展［J］.計算機(jī)系統(tǒng)應(yīng)用，2010，19（7）：255-259.

［3］ Bengio S.Multimodal speech processing using asyn?chron-ous hidden markov models［J］.Information Fu?sion，2004，5（2）：81-89.

［4］Lee J M，Kim S J，Hwang Y，et al.Diagnosis of me?chanical fault signals using continuous hidden Markov model［J］.Journal of Sound and Vibration，2004，276（3）：1065-1080.

［5］張春良，岳夏，朱厚耀.基于自評估HMM的離心泵狀態(tài)識別方法研究［J］.廣州大學(xué)學(xué)報：自然科學(xué)版，2010（4）：13-17.

［6］Rabiner L.A tutorial on hidden Markov models and se?lect-ed applications in speech recognition［J］.Proceed?ings of the IEEE，1989，77（2）：257-286.

［7］Viterbi A.Error bounds for convolutional codes and an as?ymptotically optimum decoding algorithm［J］.Infor?ma-tion Theory， IEEE Transactions on， 1967， 13（2）：260-269.

［8］Forney Jr G D.The viterbi algorithm［C］.Proceedings of the IEEE，1973，61（3）：268-278.

［9］Schnall-Levin M，Chindelevitch L，Berger B.Inverting the Viterbi algorithm：an abstract framework for struc?ture de-sign［C］.//Proceedings of the 25th internation?al conferen-ce on Machine learning.ACM， 2008：904-911.

Research on theory of Inv-Viterbi Algorithm Based on the Basic Algorithm System of HMM

LIU Gong-sheng1，ZHANG Chun-liang2，YUE Xia2，ZHU Hou-yao2
（1.School of Mechanical Engineering University of South China，Hengyang421001，China；2.Shool of Mechanical and Electrical Engineering，Guangzhou University，Guangzhou510006，China）

The system of the basic Hidden Markov Model（HMM）algorithm includes the three important algorithms of Baum-Welch algorithm，F(xiàn)orward-Backward algorithm and Viterbi algorithm.The Inv-viterbi problem and its corresponding algorithm is put forward in the paper after the research of the new HMM problem and algorithm.Then a new algorithm system and a new evaluation system are built by introducing the Inv-viterbi algorithm into the HMM basic algorithm system.Finally we give a prospect on the application of the new algorithm system.

Hidden Markov Model；Inv-Viterbi problem；Inv-Viterbi algorithm；evaluation system

TP301.6

：A

：1009－9492(2014)11－0007－04

10.3969/j.issn.1009-9492.2014.11.002

劉功生，男，廣西玉林人，碩士研究生。研究領(lǐng)域：信號檢測與故障診斷。

張春良，男，1964年生，教授，博士生導(dǎo)師。研究領(lǐng)域：設(shè)備狀態(tài)監(jiān)測與故障診斷、制造過程自動化、微制造技術(shù)、激光加工技術(shù)和數(shù)控技術(shù)等。

(編輯：阮 毅)

*國家自然科學(xué)基金（編號：51275099）；廣東省自然科學(xué)基金（編號：S2012010009505）；廣州市羊城學(xué)者首席科學(xué)家項目（編號：12A006S）；廣州市機(jī)電設(shè)備狀態(tài)監(jiān)測與控制重點實驗室建設(shè)項目（編號：2060402）

2014－05－24