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

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

（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)典算法，通過展開對(duì)HMM新問題及新算法的理論研究，引出逆維特比問題及逆維特比算法的理論體系，并提出將逆維特比算法引入HMM基本算法體系中構(gòu)建一種新的算法體系及一種新評(píng)估體系的構(gòu)想，最后對(duì)新算法體系的應(yīng)用進(jìn)行了展望。

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

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

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

1 HMM三大基本算法體系

1.1 HMM三大基本問題及算法

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

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

圖1 HMM基本算法體系

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

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

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

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

（1）首先定義兩個(gè)變量：

（2）初始化定義的兩個(gè)變量：

（3）變量的迭代計(jì)算過程：

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

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

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

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

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

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

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

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

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

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

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

迭代過程定義為：

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

（2）定義約束條件

約束條件一：

約束條件二：

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

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

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

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

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

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

2）令t=1;

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

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

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

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

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

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

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

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

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

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

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

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

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

4 展望

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

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

（2）新型HMM訓(xùn)練算法。逆維特比算法的實(shí)現(xiàn)將對(duì)HMM其它新算法及理論的研究提供一定的參考價(jià)值與指導(dǎo)意義。由圖3可知，HMM模型λ是觀測(cè)值序O與狀態(tài)序列Q的連接橋梁，通過Viterbi算法可以實(shí)現(xiàn)以觀值序列O及HMM模型λ作為輸入最終獲得狀態(tài)序列Q，而通過逆維特比算法又可以通過輸入狀態(tài)序列Q及HMM模型λ而獲得觀測(cè)值序列O，那么理論上來說也可以參考維特比及逆維特比算法的實(shí)現(xiàn)過程來建立另外一種新的問題和算法來實(shí)現(xiàn)輸入觀測(cè)值序列O及狀態(tài)序列Q最終輸出HMM模型λ，從而實(shí)現(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ì)算機(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］張春良，岳夏，朱厚耀.基于自評(píng)估HMM的離心泵狀態(tài)識(shí)別方法研究［J］.廣州大學(xué)學(xué)報(bào)：自然科學(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)域：信號(hào)檢測(cè)與故障診斷。

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

(編輯：阮 毅)

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

2014－05－24