隐马尔柯夫模型的一种面向对象的程序实现框架

1、隐马尔柯夫模型的一种面向对象的程序实现框架伟赵荣椿邓摘要在以 C + + 语言作为程序设计语言的基础上, 提出了一种用面向对象的程序设计方法来实现隐马尔柯夫模型的基本框架。 按照这一框架实现的隐马尔柯夫 模型能够很好地保护它自己不受未知的外部事件的影响, 从而使它的数据和功能免遭破坏; 而且对模型的改进以及程序实现上的变化也不会影响使用它的外部应用程 序。 此外, 用这一方法编制的隐马尔柯夫模型程序具有很好的重用性和继承性。关键词隐马尔柯夫模型, 面向对象的程序设计, 类,中图分类号T P 391T P 311引言隐马尔柯夫模型, 作为一种主要的信号统计模型, 在信号处理、图像处理、模式识别等

2、领域中有着广泛的应用。但是隐马尔柯夫模型的数据元素众多, 数学结构丰富, 计算异常复杂, 因此 用传统的程序设计方法通常不能很好地实现这一模型。 要高效、可靠地使用隐马尔柯夫模型, 尤其是在大型应用软件系统中, 就要用一种崭新的程序设计方法来实现它。面向对象的程序设 计方法是导致软件构造发生一场革命的新方法, 也是用来实现隐马尔柯夫模型的一种新的程 序设计方法。 本文在以 C + + 语言作为程序设计语言的基础上, 提出了一种用面向对象的程序 设计方法来实现隐马尔柯夫模型的基本框架, 即把隐马尔柯夫模型封装在一个类中。这个类既 包含了表示模型特性的数据元素, 又包含了用于求解隐马尔柯夫模型的三

3、个基本问题的多个 函数。由于这个隐马尔柯夫模型类为使用它的各个应用程序提供了统一的功能接口, 而实现这 些功能的数据成员和成员函数对于各个应用程序是“不可见”的。隐马尔柯夫模型类的设计给出一个隐马尔柯夫模型类的 C + + 语言描述, 其中包括类中数据成员的定义和成员函数 的定义, 以此作为隐马尔柯夫模型的一种面向对象的程序实现框架。1. 1隐马尔柯夫模型类中数据成员的定义一个隐马尔柯夫模型由 5 个数据元素唯一确定:1 西北工业大学博士生本文收到日期: 1998- 01- 16 西北工业大学教授© 1994-2013 China Academic Journal Electroni

4、c Publishing House. All rights reserved. ki.ne(1) 模型中所包含的状态数目N 。 模型中所有的状态组成集合S =S 1 , S 2 , S N 在时刻 t 的状态可用 q t 来表示。(2)每个状态所能产生的不同观测符号的数目M 。所有的观测符号组成集合V =v 1 , v 2 , vM (3)状态转移概率分布A = a ij , 式中a ij = P q t+ 1 = S j | q t = S i 1 i, j N观测符号概率分布B =式中(4)bi j ,bij = P v j a t t| q t = S i 1 i N , 1 j M初

5、始状态概率分布 i , 式中(5)i = P q1 = S i 1 i N这 5 个元素必须包含在隐马尔柯夫模型类中作为它的数据成员, 而且为了数据的安全性, 应当把这些数据元素定义为类的私有数据成员。 为了使隐马尔柯夫模型类能够成为模型的本质的、抽象的描述, 同时为了尽可能减小类的对象所占用的内存空间, 在类中除了定义用于表示这 5 个数据元素的数据成员以外, 不再定义用于存放中间计算结果的其它数据成员。 此外, 对于以上 3 个概率分布, 在类中用 3 个指针变 量加以表示, 以便进行动态内存分配, 这样就可以根据实际应用中所需要的模型大小恰当地生 成模型。隐马尔柯夫模型类中数据成员的定义

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隐马尔柯夫模型类中成员函数的定义在隐马尔柯夫模型类中定义的成员函数用于实现模型的功能, 即用于求解模型的 3 个基 本问题。 隐马尔柯夫模型的第一个基本问题是通过前向反向过程来求解的。 前向变量的递 推计算公式为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前向变量的递推计算过程结束以后, 就可以按以下公式计算概率 P (O | )N

8、P (O | ) = T ( i)(3)i= 1可以通过递推公式计算反向变量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成员函数, 这两个成员函数的函数原型: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 )其中的参数 cu r ren t a lp h a 和 cu r ren t b e ta 分别表示当前时刻的前向变量和反向变量; 参数n ex t a lp h a 和 p rev io u s b e ta 分别表示计算所得的下一时刻的前向变量和上一时刻的反向变量。 在函数 com p u te a lp h a 中参数 in dex 表示下一时刻的观测符号的标号, 而在函数 com 2p u te b e ta 中参数 in dex 表示当前时刻的观测符号的标号。 由于前向变量和反向变量的递推计算是隐马尔柯夫模型的功能

10、实现细节, 因此在隐马尔柯夫模型类中应当把这两个函数作为私有成员函数。有了实现前向变量一步递推计算的成员函数作为基础, 就可以定义一个计算 P (O | ) 的 成员函数。在这个函数中首先求出第一个时刻的前向变量值作为初始值, 然后通过循环调用成 员函数 com p u te a lp h a 从第二个时刻开始递推计算各个时刻的前向变量值直到最后一个时刻, 将最后时刻的各个状态的前向变量值相加即可得到 P (O | ) 。下面给出这个成员函数的函数原型: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)函数的两个参数分别表示观测序列的长度和观测序列。函数返回计算所得的概率。函数 com 2p u te P 是模型功能调用的一个接口, 应当把它作为类的公有成员函数。隐马尔柯夫模型的第二个基本问题通常用V ite rb i 算法来求解, 算法的计算过程:(1)计算初始值1 ( i) =1 ( i) =ibi (O 1 )01 i N1 i N(6)(7)(2)递推计算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计算最大值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以上算法的计算过程与前向变量的递推计算过程极为相似。因此, 为了实现V ite rb i 算法同样需要定义如下的成员函数以实现 t ( 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 )其中参数 cu r ren t de lta 表示当前时刻的 值, 参数 n ex t de lta 和 nex t p si 分别表示下一时刻的 值和 值, 参数 in dex 表示下一时刻的观测符号的标号。同样道理, 应当把这个函数作为类的私有成员函数。有了成员函数 com p u te de lta, 就可以在此基础上定义以下成员函数来实现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)其中前两个参数分别表示观测序列的长度和观测序列, 最后一个参数表示求得的最佳状态序列。 除了要进行回溯以外, 函数 f in d SS 的计算过程与函数 com p u te P 的计算过程完全相同。 同样, 函数 f in d SS 必须作为类的公有成员以便外部应用程序能够调用它来求解模型

15、的基本问题。隐马尔柯夫模型的第三个基本问题可以用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 ) 可以按以下公式由前向变量和反向变量计算得到 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为了实现B aum 2W e lch 算法需要定义以下两个计算给定时刻的 值和 值的成员函数: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)这两个函数的前三个参数表示观测序列的长度、观测序列和给定时刻, 最后一个参数分别表示计算所得的给定时刻的 值和 值。在这两个函数中首先计算前向变量和反向变量的初始值,然后调用函数 com p u te a lp h a 和 com p u te b e ta 递推计算前向变量和反向变量直到给定时刻或给定时刻的下一时刻,

18、最后根据公式(16)、(17) 算出给定时刻的 值和 值。 同样应当把以上两个成员函数的访问权限设置成私有的。有了这两个函数, 就可以定义实现B aum 2W e lch 算 法的成员函数: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)函数的两个参数分别表示观测序列的长度和观测序列。在该成员函数中, 用当前的模型参数通过调用函数 com p u te gamm a 和 com p u te x i 计算各个时刻的 值和 值, 然后根

19、据公式(13) (15) 计算出一个新的模型参数, 并对这两个模型加以比较以确定模型参数的重估过程是否继续进行。 为了使得外部应用程序能够调用函数 ad ju st M P , 应当把它的访问权限设置成公有的。结论3本文提出的这一框架所实现的隐马尔柯夫模型是最为基本的。 隐马尔柯夫模型的变化很多, 在这一程序实现框架中并没有考虑模型本身的诸多变化因素。但是由于程序实现方法的优 越性, 在这一框架中实现隐马尔柯夫模型的多种变化是极为容易的, 而且并不影响使用它的外 部应用程序。参考文献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 面向对象程序设计 1 北京: 北京大学出版社,

21、 1992张国锋 1C + + 语言及其程序设计教程 1 北京: 电子工业出版社, 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