隱馬爾柯夫模型的一種面向?qū)ο蟮某绦驅(qū)崿F(xiàn)框架

1、隱馬爾柯夫模型的一種面向?qū)ο蟮某绦驅(qū)崿F(xiàn)框架偉趙榮椿鄧摘要在以 C + + 語(yǔ)言作為程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)上, 提出了一種用面向?qū)ο蟮某绦蛟O(shè)計(jì)方法來(lái)實(shí)現(xiàn)隱馬爾柯夫模型的基本框架。 按照這一框架實(shí)現(xiàn)的隱馬爾柯夫 模型能夠很好地保護(hù)它自己不受未知的外部事件的影響, 從而使它的數(shù)據(jù)和功能免遭破壞; 而且對(duì)模型的改進(jìn)以及程序?qū)崿F(xiàn)上的變化也不會(huì)影響使用它的外部應(yīng)用程 序。 此外, 用這一方法編制的隱馬爾柯夫模型程序具有很好的重用性和繼承性。關(guān)鍵詞隱馬爾柯夫模型, 面向?qū)ο蟮某绦蛟O(shè)計(jì), 類(lèi),中圖分類(lèi)號(hào)T P 391T P 311引言隱馬爾柯夫模型, 作為一種主要的信號(hào)統(tǒng)計(jì)模型, 在信號(hào)處理、圖像處理、模式識(shí)別等

2、領(lǐng)域中有著廣泛的應(yīng)用。但是隱馬爾柯夫模型的數(shù)據(jù)元素眾多, 數(shù)學(xué)結(jié)構(gòu)豐富, 計(jì)算異常復(fù)雜, 因此 用傳統(tǒng)的程序設(shè)計(jì)方法通常不能很好地實(shí)現(xiàn)這一模型。 要高效、可靠地使用隱馬爾柯夫模型, 尤其是在大型應(yīng)用軟件系統(tǒng)中, 就要用一種嶄新的程序設(shè)計(jì)方法來(lái)實(shí)現(xiàn)它。面向?qū)ο蟮某绦蛟O(shè) 計(jì)方法是導(dǎo)致軟件構(gòu)造發(fā)生一場(chǎng)革命的新方法, 也是用來(lái)實(shí)現(xiàn)隱馬爾柯夫模型的一種新的程 序設(shè)計(jì)方法。 本文在以 C + + 語(yǔ)言作為程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)上, 提出了一種用面向?qū)ο蟮某绦?設(shè)計(jì)方法來(lái)實(shí)現(xiàn)隱馬爾柯夫模型的基本框架, 即把隱馬爾柯夫模型封裝在一個(gè)類(lèi)中。這個(gè)類(lèi)既 包含了表示模型特性的數(shù)據(jù)元素, 又包含了用于求解隱馬爾柯夫模型的三

3、個(gè)基本問(wèn)題的多個(gè) 函數(shù)。由于這個(gè)隱馬爾柯夫模型類(lèi)為使用它的各個(gè)應(yīng)用程序提供了統(tǒng)一的功能接口, 而實(shí)現(xiàn)這 些功能的數(shù)據(jù)成員和成員函數(shù)對(duì)于各個(gè)應(yīng)用程序是“不可見(jiàn)”的。隱馬爾柯夫模型類(lèi)的設(shè)計(jì)給出一個(gè)隱馬爾柯夫模型類(lèi)的 C + + 語(yǔ)言描述, 其中包括類(lèi)中數(shù)據(jù)成員的定義和成員函數(shù) 的定義, 以此作為隱馬爾柯夫模型的一種面向?qū)ο蟮某绦驅(qū)崿F(xiàn)框架。1. 1隱馬爾柯夫模型類(lèi)中數(shù)據(jù)成員的定義一個(gè)隱馬爾柯夫模型由 5 個(gè)數(shù)據(jù)元素唯一確定:1 西北工業(yè)大學(xué)博士生本文收到日期: 1998- 01- 16 西北工業(yè)大學(xué)教授© 1994-2013 China Academic Journal Electroni

4、c Publishing House. All rights reserved. ki.ne(1) 模型中所包含的狀態(tài)數(shù)目N 。 模型中所有的狀態(tài)組成集合S =S 1 , S 2 , S N 在時(shí)刻 t 的狀態(tài)可用 q t 來(lái)表示。(2)每個(gè)狀態(tài)所能產(chǎn)生的不同觀測(cè)符號(hào)的數(shù)目M 。所有的觀測(cè)符號(hào)組成集合V =v 1 , v 2 , vM (3)狀態(tài)轉(zhuǎn)移概率分布A = a ij , 式中a ij = P q t+ 1 = S j | q t = S i 1 i, j N觀測(cè)符號(hào)概率分布B =式中(4)bi j ,bij = P v j a t t| q t = S i 1 i N , 1 j M初

5、始狀態(tài)概率分布 i , 式中(5)i = P q1 = S i 1 i N這 5 個(gè)元素必須包含在隱馬爾柯夫模型類(lèi)中作為它的數(shù)據(jù)成員, 而且為了數(shù)據(jù)的安全性, 應(yīng)當(dāng)把這些數(shù)據(jù)元素定義為類(lèi)的私有數(shù)據(jù)成員。 為了使隱馬爾柯夫模型類(lèi)能夠成為模型的本質(zhì)的、抽象的描述, 同時(shí)為了盡可能減小類(lèi)的對(duì)象所占用的內(nèi)存空間, 在類(lèi)中除了定義用于表示這 5 個(gè)數(shù)據(jù)元素的數(shù)據(jù)成員以外, 不再定義用于存放中間計(jì)算結(jié)果的其它數(shù)據(jù)成員。 此外, 對(duì)于以上 3 個(gè)概率分布, 在類(lèi)中用 3 個(gè)指針變 量加以表示, 以便進(jìn)行動(dòng)態(tài)內(nèi)存分配, 這樣就可以根據(jù)實(shí)際應(yīng)用中所需要的模型大小恰當(dāng)?shù)厣?成模型。隱馬爾柯夫模型類(lèi)中數(shù)據(jù)成員的定義

6、:in t N ;in t M ;f lo a t 3 3A ;f lo a t 3 3B ;f lo a t 3 P I ;th e n um b e r o f sta te s in th e m o de lth e n um b e r o f d ist in c t o b se rva t io n sym bo ls p e r sta teth e sta te t ran sit io n p ro b ab ility d ist r ib u t io nth e o b se rva t io n sym bo l p ro b ab ility d ist r i

7、b u t io nth e in it ia l sta te p ro b ab ility d ist r ib u t io n隱馬爾柯夫模型類(lèi)中成員函數(shù)的定義在隱馬爾柯夫模型類(lèi)中定義的成員函數(shù)用于實(shí)現(xiàn)模型的功能, 即用于求解模型的 3 個(gè)基 本問(wèn)題。 隱馬爾柯夫模型的第一個(gè)基本問(wèn)題是通過(guò)前向反向過(guò)程來(lái)求解的。 前向變量的遞 推計(jì)算公式為21 ( i) = ibi (O 1 )1 i N(1)Nt ( i) a ijt+ 1 ( j ) =bj (O t+ 1 )1 t T - 1, 1 j N(2)i= 1前向變量的遞推計(jì)算過(guò)程結(jié)束以后, 就可以按以下公式計(jì)算概率 P (O | )N

8、P (O | ) = T ( i)(3)i= 1可以通過(guò)遞推公式計(jì)算反向變量T ( i) = 11 i N(4)Nt ( i) = a ij bj (O t+ 1 ) t+ 1 ( j )1 t T- 1, 1 i N(5)j = 1成員函數(shù), 這兩個(gè)成員函數(shù)的函數(shù)原型:vo id com p u te a lp h a (f lo a t 3cu r ren t a lp h a, f lo a t 3n ex t a lp h a, in t in dex )vo id com p u te b e ta (f lo a t 3 cu r ren t b e ta, f lo a t 3

9、p rev io u s b e ta , in t in dex )其中的參數(shù) cu r ren t a lp h a 和 cu r ren t b e ta 分別表示當(dāng)前時(shí)刻的前向變量和反向變量; 參數(shù)n ex t a lp h a 和 p rev io u s b e ta 分別表示計(jì)算所得的下一時(shí)刻的前向變量和上一時(shí)刻的反向變量。 在函數(shù) com p u te a lp h a 中參數(shù) in dex 表示下一時(shí)刻的觀測(cè)符號(hào)的標(biāo)號(hào), 而在函數(shù) com 2p u te b e ta 中參數(shù) in dex 表示當(dāng)前時(shí)刻的觀測(cè)符號(hào)的標(biāo)號(hào)。 由于前向變量和反向變量的遞推計(jì)算是隱馬爾柯夫模型的功能

10、實(shí)現(xiàn)細(xì)節(jié), 因此在隱馬爾柯夫模型類(lèi)中應(yīng)當(dāng)把這兩個(gè)函數(shù)作為私有成員函數(shù)。有了實(shí)現(xiàn)前向變量一步遞推計(jì)算的成員函數(shù)作為基礎(chǔ), 就可以定義一個(gè)計(jì)算 P (O | ) 的 成員函數(shù)。在這個(gè)函數(shù)中首先求出第一個(gè)時(shí)刻的前向變量值作為初始值, 然后通過(guò)循環(huán)調(diào)用成 員函數(shù) com p u te a lp h a 從第二個(gè)時(shí)刻開(kāi)始遞推計(jì)算各個(gè)時(shí)刻的前向變量值直到最后一個(gè)時(shí)刻, 將最后時(shí)刻的各個(gè)狀態(tài)的前向變量值相加即可得到 P (O | ) 。下面給出這個(gè)成員函數(shù)的函數(shù)原型:f lo a t com p u te P ( in t len g th o f o b se rva t io n sequ en ce,

11、 in t 3 o b se rva t io n sequ en ce)函數(shù)的兩個(gè)參數(shù)分別表示觀測(cè)序列的長(zhǎng)度和觀測(cè)序列。函數(shù)返回計(jì)算所得的概率。函數(shù) com 2p u te P 是模型功能調(diào)用的一個(gè)接口, 應(yīng)當(dāng)把它作為類(lèi)的公有成員函數(shù)。隱馬爾柯夫模型的第二個(gè)基本問(wèn)題通常用V ite rb i 算法來(lái)求解, 算法的計(jì)算過(guò)程:(1)計(jì)算初始值1 ( i) =1 ( i) =ibi (O 1 )01 i N1 i N(6)(7)(2)遞推計(jì)算t ( j ) = m ax t- 1 ( i) a ij bj (O t )1 i Nt ( j ) = a rg m ax t- 1 ( i) a ij

12、1 i N計(jì)算最大值2 t T , 1 2 t T , 1 j Nj N(8)(9)(3)p 3m ax T ( i) 1 i N(10)(11)=q3=a rg m ax T ( i) 1 i NT(4)路徑回溯q33= t+ 1 (q t+ 1 )(12)t = T - 1, T- 2, 1t以上算法的計(jì)算過(guò)程與前向變量的遞推計(jì)算過(guò)程極為相似。因此, 為了實(shí)現(xiàn)V ite rb i 算法同樣需要定義如下的成員函數(shù)以實(shí)現(xiàn) t ( j ) 的一步遞推計(jì)算:vo id com p u te de lta (f lo a t 3 cu r ren t de lta, f lo a t 3 n ex

13、t de lta , in t 3 n ex t p si, in t in dex )其中參數(shù) cu r ren t de lta 表示當(dāng)前時(shí)刻的 值, 參數(shù) n ex t de lta 和 nex t p si 分別表示下一時(shí)刻的 值和 值, 參數(shù) in dex 表示下一時(shí)刻的觀測(cè)符號(hào)的標(biāo)號(hào)。同樣道理, 應(yīng)當(dāng)把這個(gè)函數(shù)作為類(lèi)的私有成員函數(shù)。有了成員函數(shù) com p u te de lta, 就可以在此基礎(chǔ)上定義以下成員函數(shù)來(lái)實(shí)現(xiàn)V ite rb i 算法:vo id f in d SS ( in t len g th o f o b se rva t io n sequ en ce, in

14、 t 3 o b se rva t io n sequ en ce,© 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. ki.nein t 3 sta te sequ en ce)其中前兩個(gè)參數(shù)分別表示觀測(cè)序列的長(zhǎng)度和觀測(cè)序列, 最后一個(gè)參數(shù)表示求得的最佳狀態(tài)序列。 除了要進(jìn)行回溯以外, 函數(shù) f in d SS 的計(jì)算過(guò)程與函數(shù) com p u te P 的計(jì)算過(guò)程完全相同。 同樣, 函數(shù) f in d SS 必須作為類(lèi)的公有成員以便外部應(yīng)用程序能夠調(diào)用它來(lái)求解模型

15、的基本問(wèn)題。隱馬爾柯夫模型的第三個(gè)基本問(wèn)題可以用B aum 2W e lch 算法迭代求解, 算法的迭代公式i =1( i)1 i N(13)T - 1t ( i, j )a t= 1 ij =1 i N , 1 j N(14)T - 1t ( i)t= 1Tt ( i)t= 1s. t. O t= v jb1 i N , 1 j N(15)i j =Tt ( i)t= 1其中 t ( i) 和 t ( i, j ) 可以按以下公式由前向變量和反向變量計(jì)算得到 t ( i) t ( i) t ( i) =1 t T , 1 i N(16)Nt ( i) t ( i)i= 1 t ( i) a

16、i j bj (O t+ 1 ) t+ 1 ( j ) t ( i, j ) =1 t T- 1, 1 i, j N(17)NNt ( i) a ij bj (O t+ 1 ) t+ 1 ( j )i= 1 j = 1為了實(shí)現(xiàn)B aum 2W e lch 算法需要定義以下兩個(gè)計(jì)算給定時(shí)刻的 值和 值的成員函數(shù):vo id com p u te gamm a ( in t len g th o f o b se rva t io n sequ en ce, in t 3 o b se rva t io n sequ en ce, in t t im e t, f lo a t 3 gamm a)

17、vo id com p u te x i ( in t len g th o f o b se rva t io n sequ en ce, in t 3 o b se rva t io n sequ en ce,in t t im e t, f lo a t 3 3 x i)這兩個(gè)函數(shù)的前三個(gè)參數(shù)表示觀測(cè)序列的長(zhǎng)度、觀測(cè)序列和給定時(shí)刻, 最后一個(gè)參數(shù)分別表示計(jì)算所得的給定時(shí)刻的 值和 值。在這兩個(gè)函數(shù)中首先計(jì)算前向變量和反向變量的初始值,然后調(diào)用函數(shù) com p u te a lp h a 和 com p u te b e ta 遞推計(jì)算前向變量和反向變量直到給定時(shí)刻或給定時(shí)刻的下一時(shí)刻,

18、最后根據(jù)公式(16)、(17) 算出給定時(shí)刻的 值和 值。 同樣應(yīng)當(dāng)把以上兩個(gè)成員函數(shù)的訪問(wèn)權(quán)限設(shè)置成私有的。有了這兩個(gè)函數(shù), 就可以定義實(shí)現(xiàn)B aum 2W e lch 算 法的成員函數(shù):vo id ad ju st M P ( in t len g th o f o b se rva t io n sequ en ce, in t 3 o b se rva t io n sequ en ce)函數(shù)的兩個(gè)參數(shù)分別表示觀測(cè)序列的長(zhǎng)度和觀測(cè)序列。在該成員函數(shù)中, 用當(dāng)前的模型參數(shù)通過(guò)調(diào)用函數(shù) com p u te gamm a 和 com p u te x i 計(jì)算各個(gè)時(shí)刻的 值和 值, 然后根

19、據(jù)公式(13) (15) 計(jì)算出一個(gè)新的模型參數(shù), 并對(duì)這兩個(gè)模型加以比較以確定模型參數(shù)的重估過(guò)程是否繼續(xù)進(jìn)行。 為了使得外部應(yīng)用程序能夠調(diào)用函數(shù) ad ju st M P , 應(yīng)當(dāng)把它的訪問(wèn)權(quán)限設(shè)置成公有的。結(jié)論3本文提出的這一框架所實(shí)現(xiàn)的隱馬爾柯夫模型是最為基本的。 隱馬爾柯夫模型的變化很多, 在這一程序?qū)崿F(xiàn)框架中并沒(méi)有考慮模型本身的諸多變化因素。但是由于程序?qū)崿F(xiàn)方法的優(yōu) 越性, 在這一框架中實(shí)現(xiàn)隱馬爾柯夫模型的多種變化是極為容易的, 而且并不影響使用它的外 部應(yīng)用程序。參考文獻(xiàn)R ab ine r L R. A T u to r ia l o n H idden M a rko v M

20、o de ls and Se lec ted A pp lica t io n s in Sp eech R eco gn it io n. P ro c o f th e IE E E , 1989, 77 (2) : 257 286R um baugh J , B lah a M , P rem e r lan i W , e t a l. O b jec t2O r ien ted M o de ling and D e sign. E ng lew oo d C liff s:12P ren t ice2H a ll,1991楊芙清等 1 面向?qū)ο蟪绦蛟O(shè)計(jì) 1 北京: 北京大學(xué)出版社,

21、 1992張國(guó)鋒 1C + + 語(yǔ)言及其程序設(shè)計(jì)教程 1 北京: 電子工業(yè)出版社, 199234A n O b jec t2O r ien ted P ro g ramm in g A pp ro ach toIm p lem en t H idden M a rko v M o de lD en g W e iZ h a o R on g ch u nD ep a r tm en t o f Com p u te r Sc ien ce an d E n g in ee r in gN o r thw e ste rn Po ly tech n ica l U n ive r sity, X

22、 ian 710072H idden M a rko v m o de l (HM M ) is an im po r tan t sto ch a st ic m o de l o f sign a l an d h a s a w ideran ge o f app lica t io n s. B u t HM M is too com p lica ted to b e im p lem en ted eff ic ien t ly b y co n ven2 t io n a l p ro g ramm in g m e tho d s. H e re w e p re sen t

23、an o b jec t2o r ien ted p ro g ramm in g (OO P ) ap 2 p ro ach to im p lem en t HM M b y en cap su la t in g it in a c la ss u sin g C + + a s th e p ro g ramm in g lan2 gu age. Su ch an app ro ach , to o u r b e st k now ledge, h a s no t b een repo r ted in th e op en lite ra2 tu re s.1,In Sec t io nHM M .w e def in e f ive da ta typ e s in th e c la ss rep re sen t in g th e f ive e lem en t s o fIn Sec t io n 2, w e f ir st em p lo y fo rw a rd2b ackw a rd a lgo r ithm (eq s. 1 th ro u gh 5) , V ite rb ia lgo r ithm ( eq s