（概率论与数理统计专业论文）隐马尔可夫模型的原理及其应用.pdf

y 6 5 4 1 7 5 隐马尔可夫模型的原理及其应用 概率论与数理统计专业 研究生 杜世平指导老师 马 洪 隐马尔可夫模型( h i d d e n ma r k o v m o d e l s : h m m) 是由 两个随机变量序列组 成 ， 其 中 一 个 是 不 可 释 漆 的( 即 隐 藏) 变 化 状 态 序 列 ， 另 一 个 是 由 不 可 观 察 的 状 态 序列 所 产 生 枷翩漆符号 序 列. 在过 去几 十年 里. 关 于h m m的 许 多 研究 工作 主 要 集中 在 一 阶 系 统 上， 即 一阶 跪 马 尔可 夫 模型( f ir s t- o r d e r h m m : h m m i ) 上， h m m i 作了 两个重要假设: ( i ) 状态转移的m a r k o v 假设:系统在当前时刻的 状态向 下一时刻所处的 状 态 转 移 的 状 态 转 移 概 率 仅仅 与当 前 时 刻 的 状 态 有 关 ， 而 与 以 前 的 历 史 无 关 . ( 2 ) 输出 值的m a r k o v 假设:系统在当前时刻输出 观测值的概率. 只取决 于当 前时 刻的 状态而与当前时刻以 前的时刻所处的 状态无关。 而在实际应用中， 这样假设并不十分合理。 为此， 本文对h mm i 中的两个 假设条 件作了 改 进。首先介绍了在观测嗓声和马尔可夫链不相互独立的条件下 改 进的隐马尔可夫模型( 二阶隐马尔可夫模型: s e c o n d - o r d e r h m, 简记为11 02 ) 的结构. 其次， 在传统的隐马尔可夫模型的基础上， 研究了 改进的模型的前向 - 后向算法和b a u m - w e l c h 算法， 并导出了改进的模型的参数估计公式。 最后举例 说明了改进的模型在计算语言学中的应用。 关键词，一阶隐马尔可夫模型，二阶隐马可夫模型， 参数估计， 前向 一后 向算法，b a u m - we l c h 算法， 乘子，计算语言学。 t h e o r y o f h i d d e n m a r k o v mo d e l s a n d i t s a p p l i c a t i o n s ma j o r : p r o b a b i l i t y a n d s t a t i s t i c s g r a d u a t e s t u d e n t s h i p i n g d u i n s t r u c t o r h o n g ma a h id 七 l m a k o v p ro c e ss is a d o u b le st o c h a sti c p ro ce s s : a n u n cl e劝 魄p ro c e s s v n 山is h id 白r fr o m 由 e a v a fi m列 a n o b e a v a b le p ro o p ro o m s w h ic h is 由 te u n u re d 勿th e u n 另 一 个 是 可以 观 察到的 随机 序 列 o , 2 0 1 . 4 r 2 0 称 为 马尔可夫 链，( o ? 0 ) 称为 其观察链。 隐马尔可夫模型己在语音识别中得到了广泛的应用， 8 0 年代末开始应用于 计算生物学。目前，隐马尔可夫模型在人类基因组研究的许多方面都有广泛的 应用。 如， d n a序列的比 对 ( a l i g n m e n t ) 、 基因发 现 ( g e n e b n d i n g ) 、 作基因 图 ( g e n e t i c m a p p i n g ) 、 作物理图 ( p h y s i c a l m a p p i n g ) 及蛋白 质二 级结构的 预 测等。在过去几十年里关于隐马尔可夫模型的许多研究工作主要集中在一阶隐 马尔可夫模型 ( h m m 1 )，而一阶隐马尔可夫模型作了 两个重要的假设: 四川大学硕士学位论文 ( 1 ) 状态转移的m a r k o v 假设: 在t 时刻 ( 前一时刻) 处于状态s ; ，而在 t + 1 时 刻( 当 前时 刻) 进 入 状态s i 的 状 态 转 移 概率 只 取决 于 前 一时 刻 所处的 状 态，而与前一时刻以前的历史无关。 ( 2 )输出值的ma r k o v 假设:输出观察值的概率同样具有ma r k o v 性，即 只取决于当前时刻所处的状态，而与以前的历史无关。 事实上，这种假设并不十分合理，这是因为在一些实际际问题中，任一时 刻的状态向下一时刻的状态的转移概率，以及某一状态出现某观察值的概率， 不仅依赖于系统当前所处的状态，而且依赖于系统前一时刻所处的状态，为了 弥补这一缺陷， 本文进行了一些研究，对一阶隐马尔可夫模型的两个假设条件 作了改进。首先介绍了在观测噪声和马尔可夫链不相互独立的条件下改进的隐 马尔可夫模型 ( 二阶隐马尔可夫模型:s e c o n d - o r d e r h m m ， 简记为 h m m 2 )的结 构。 其次， 在传统的隐马尔可夫模型的基础上， 研究了改进的模型的前向 一 后向 算法和b a u m - w e l c h 算法， 并导出了改进的模型的参数估计公式。 最后举例说明 了改进的模型在计算语言学中的应用 为了对上述问题进行更好的研究，本文首先介绍了一阶隐马尔可夫模型的 基本结构，引出了 将隐马尔可夫模型应用到实际问 题中所要解决的三个基本问 题以及相应的 三种算法: 前向 一后向 算法、 v i t e r b i 算法、 b a u m - we l c h算法尸 着重讨论了第一个问 题和第三个问 题的解决。其次，介绍了隐马尔可夫模型在 生物信息学中，主要介绍在 d n a序列比 对以 及基因发现中的应用。最后讨论 了改进的隐马尔可夫模型 ( 二阶隐马尔可夫模型)的结构及其在计算语言学中 的应用。 2 一阶隐马尔可夫模型 2 . 1 h m m 的基本元素 四川大学硕士学位论文 h mm一个清晰的极好描述是由r a b i n e : 给出，根据 ( r a b i n e r 1 9 8 9 ) h mm由以下几种元素组成: ( i )隐藏的状态集合 s = ss z , ， 二 ， s , ) ， 并记t 时 的 状态 为q , , q , e ( s i , s 2 , . . .s x ) ( 2 )观察符号集合 v = y , ， v 2 ， . . . i v m ) ,m表 示 每 一 个 状 态的 不同 符号 数 ( 3 ) 状 态 转 移 概 率 分 布 a = ( a , ) ，其 中 a li = p ( q ,. i = s ; i q 二 s , ) 1 - i ,j - n ( 2 . 1 . 1 ) ( 4 ) 状态i 中 可见 符号的 概率分布b = b , ( k ) ) ， 其中 b , ( k ) = p ( o , = v k i q , = s ; ) 1 - k - m , 1 - i - n , ( 2 . 1 . 2 ) 其中o , 表 示 在t 时 状 态 为s ; 的 观 察 值 ( 5 ) 初 始 状 态 分 布 ， 二 = t , 其 中 ; r , = p ( q , = s , ) l - i - n ( 2 . 1 .3 ) 一个h mm完全由a . b . ;r 所确定，为了 方便， 简记为.t 二 ( a , b , ; r ) 2 . 2 h m m 模式识别技术关键 给定h mm，将其应用到实际中须解决以下三个基本问题: 问 题1己 知 观察 序 列o 二 口 . 刀 2 ， ， ， 】 ， 口 : 和模 型a = ( a , b , z ) 如 何 有 效 地计 算 在给定模型又 条件下产生观察序列。 的条件概率即p( 0 1 元 ) 问 题2 己 知 观 察 序 列o 二 0 , 0 z , . . . ， o , 和 模型a 二 ( a , b , 哟如何 选 择相 应的 四川人学顾 卜 学位论文 在某种意义上最佳 ( 能最好解释观察序列)的状态序列。 问题3 如何调整模型参数a = ( a , b , )r ) ，以 使条 件概率p( o i a) 最大。 对应于h mm三个问题的求解，产生 h mm在应用中的三个算法:前向一 后向算法 问题为例 v i t e r b i 算法、b a u m - we lc h算法，下面主要以第一个问题和第二个 予以详细讨论。 2 . 3 前向 一后向算法 前向 一后向算法是对第一个问题的求解，计算给定模型又 产生观察序列o 的 概率， 即 求p ( 0 1 a ) 。 给定 模 型a 产生 某 一 状态 序列q 二 9 1 , 4 2 , . . . , 9 ; 的 概 率: p ( q i a ) = 二 。 a v ,v, 4 y =v , ， 二 a v r_ ,v ! - v i“ 二 _.。 ( 2 . 3 . 1 ) 式 中 9 . 是 初 始 状 态 ， n ,: 是 初 始 状 态 为 9 。 的 概 率 ， 气 v , 是 从 初 始 状 态 9 : 转 移 到t- 2 时 的 状态9 : 的 概 率， 以 此 类推， t 是 观 察 序 列 长 度。 在该状态序列q = 4 1 , 9 2 , , 9 : 条件下 模型已 给定)， 产生 观察序列 o = 0 , 1 0 2 ， 二 ， o f 的 概率为 p ( o i q ,a ) 一 b y . ( o ) b , , ( 0 2 ) . . . b w , ( o 7.) 一 f1b , ( o , ) ( 2 . 3 . 2 ) 式 中 气 ( 0 , ) 是 状 态 9 产 生 观 察 o , 的 概 率 ， 气 ( o , ) = p ( o , 1 9 z ) 状态序列o 和观察序列o同时发生的概率( 联合概率) 为上二式概率之积， p ( o , q i a ) = p ( o q , a ) p ( qi ) ) ( 2 . 3 . 3 ) 四川大学硕 l : 学位论文 将所有可能状态序列所对应的上式联合概率求和，便得到给定模型又 条件 下产生观察序列o的概率，即 p ( o i a ) 一 艺p ( o , q i a ) 一 艺 ,r , .b ,. ( o . ) a , , b v , ( o , ) * . . a , ,_., , b , ( o , ) ( 2 .3 .4 ) 0， . ， 卜。 . 4 r 不难 看出， 技 照定 义 来计 算p ( o i 幻需 要( 2 t - 1 ) n t 次 乘 法 和n t - 1 次 加 法。这样，即使在n和t都很小的情况下， 其运算量也是非常大的。因此，为 使问题 1 的求解变成现实，必须寻求更简捷的办法，前向一后向算法就是这样 一种高效算法 定义前向变量: a , ( i ) = p ( o , , o ， ， ， o9 , = s ; a ,) ( 2 . 3 . 5 ) 这就是说， 前向 变量a , ( i ) 是指在给定 模 型r 的 条 件下， 产生t 以 前的 部分 观 察 序列 0 1 , 0 2, . . . , 0 , ， 且t 时又 处 于 状态s ; 的 概 率， 前向 变 量a , ( f ) 可 按下 列步 骤进行迭代计算: ( 1 )初始化 a , ( i ) = ) t i执 ( o , ) 1 - p ( o i .z ) ( 2 . 4 . 2 ) 性质2 a 是p ( o j z ) 的临界点当 且仅当a 是 q ( a , 刀 ( ( q ( a a ) 作为x 的函 四川人学硕士学位论文 数)的临界点。 由上面的讨论可知， 我们可以 借助辅助函数q ( a , i ) ， 应用b a u m - w e l c h 算 法选择a = ( a , b , ;r ) ， 使p ( o i a ) 局部最大。为此引入下面两个变量: 给定模型a 和观察序列o的条件下，t 时位于状态s 。 的概率 r , ( i ) = p ( q , = s , o , a ) = p ( q , = s , o , a ) p ( o i a ) 1 _ t _t ( 2 . 4 . 3 ) 给 定 模型a 和 观察 序 列o 的 条 件下， t 时 在状态s ; , t + 1 时 在状态s ; 的 概 率， 1 , ( i , 1 ) = p ( q , = 5 ， ， 叮 ，+ ， = s j i o , a ) = a , ( i ) a y b ; ( o ,. , ) q ,+ , ( .j ) 尸 ( 0 之 ) a , ( i) a , b , ( o ,. , ) 戏 . , u ) =万 不n - ey a , ( i ) a b f ( o ,+ , ) ,6 ,+ , ( .1 ) 1 _r _t一1( 2 . 4 . 4 ) , _ ,了 司 下面的讨论只考虑输出 观察值的概率分布是离散的情形 ( 连续情形也可类 似得到)。假设每一 个状态可观察到的不同 符号为vv z , , 、共 m个， o , 。 v ， v 2 1 * . . v . 若o , - v k ,则 b ,( o , ) = p ( o , = 、 q , = s ) 由式 ( 2 . 3 . 1 )、 辅助函数 ( 2 .3 .2 )、 ( 2 .3 .3 )可得 q ( a , .1 ) = 艺 lo g p ( 0 , t , qi a ) p ( o , qi a ) = y, lo g ( jf b , ( 0 . ) l l a a ,- :， , ( o , ) ) p ( o , q i a ) 一 艺lo g iry p ( o , q i a )十 d 乞 lo g j v,_w ,)p (o ,q i; ) + y (之 lo g bq, (o ,)p (o ,q i a ) 口: 二 zq , . , ( 2 . 4 . 5 ) 四川大学硕士学位论文 z ; 的重估计 由上式可得 q ( a j ) = 艺lo g ir y . p ( o , q i a ) + v , = 艺 lo g jf rp ( o , 4 , = s , i a ) 十 (p )( 2 . 4 . 6 ) 又 因 为 )r , 满 足 约 束 条 件艺 n , 二 1 所以根据拉格朗日乘子法，由 n - 、.12 艺 lo g ic ; p ( 0 , 。 一s ; i a ) + rp , + r ( i 一 艺 f ) 可得: 风 = p ( o , 9 . = s , .1 ) = a ,q )an 些= 。 (。 艺 a , ( i) a ( i) 1 5i _n p ( o i a ) ( 2 . 4 . 7 ) 其中r 是la g r a n g e 乘 子，9 1是与 元无 关的 其 余 所 有 项 之 和。 a的 重 估 计， 由 式( 2 .4 .5 ) 可 得: w ( a a一 艺 艺lo g o p ( o ,4 ,- , = s ;,r , 一 s ; i a ) 十 (0 2 其 中 iv z 是d e 无 关 的 其 余 所 有 项 之 和 ( 2 . 4 . 8 ) 又 因 为 a 满 足 约 束 条 件 艺 a , 二 i 1 . 1 所以 由】 a g r a n g e 乘子 法 可 得a s 的 重估 公 式: 四川大学硕 卜 学位论文 p ( 0 , q ,- i = s ， ， ， = s , i r )y- , ( i , j ) : 二 一 r 艺 p ( 0 , q ,- , = s ; r ) 创齐，一 一1 _ i , j _ n ( 2 .4 .9 ) 艺r , ( t ) 艺间 b , ( k ) 的重估计 由式( 2 . 4 . 5 ) 可得 q ( a , 1 ) = 叉艺lo g b ; ( k )p ( o , q , = s i i a ) + (p 3 ( 2 . 4 . 1 0 ) , = 1 , _, 其中(p 3 是 b ; ( k ) 无 关的 其 余 所 有 项 之 和 又 因 为 b , ( k ) 满 足 约 束 条 件 : 艺 b ; ( k ) = 1 b ; ( k ) = y p ( o , q , = s ; i a ) s ，、 ， = ._ d o g ., =i已 一一 一 -一( 2 .4 . 1 1 ) 艺p ( o , q , = s i r )艺r ( i ) 其 中 .5, = , .i 1当 。 ， _ v k 0当 。 # v k 2 . 5 h m m 的各种结构类型 我们一般情况下，考虑的是遍历或全通h m m 这个特殊情况，即模型中的任 一个状态可由任一个其它状态到达 ( 一步之内) ( 严格地讲，遍历模型的性质 是:任一个状态可由任一个其它状态在有限步内到达)，此类模型具有性质: 每 个a ;， 系 数 都 是 正 的 。 在某些应用中，己 发现应用其它类型的h m m 说明被模拟的信号性质比用标 准遍历好。给出一种新的模型称为左一右模型或b a k i s 模型。因为同模型相关 四川大学b p i 士学位论文 联的基本状态序列有性质:当时间增加时，状态标号也增加 ( 或保持相同)， 即状态从左向右转移。显然，左一右模型的h m m 具有的性质可用来模拟随时间 变化的语音信号。 所以 左 一右 模 型的h m m 都 具 有 基 本 性 质: a , = 0 , j i + a ( 2 . 5 . 3 ) 给定一个 值，即不允许跳过 个状态，对于左一右模型的最后状态， 状态转 移系数是确定的，a m , = 1 , a m = 0 , i n ( 2 . 5 . 4 ) 虽然己 把h m m 分为遍历的和左一右模型，还有很多可能的变化和联合。例 如，我们可以 将两个平行的左一右h m m 交叉连接.严格地说，这是左一右模型 ( 它 满足 所 有a , 的 约 束) ， 比 严 格 的 左 一 右 模 型 灵 活 强加 在左 一右 模型上的 约束 对重估过程没 有本质的 影响， 这是由 于 任何初 始值为零的h m m 参数在整个重估过程中将保持为零。 以上我们所讨论的h m m 都属于状态产生输出型，即根据每个时刻所到达的 状态来决定输出的概率分布。 对于转移弧产生输出型，每个输出不是与到达状 态相联系，而是与转移弧相联系，因而输出的概率分布与弧两端的状态有关。 在转移弧输出型h m m 系统中再加增加一种 “ 零转移弧”可以 使系统具有更大的 灵活性。零转移弧是指从一个状态到另一个状态转移时具有描述其它转移弧同 样的转移概率，但是没有观察值，因为它不产生输出，从而也不占用时间。 h m m 中许多地方都采用了零转移弧 ( 一般在虚线上标记巾 表示零转移弧) 。 例如: ( 1 )在左一右模型中，小 表示两个平稳段之间不存在过渡段。 ( 2 )在 四川大学顽 i - 学位论文 一个词的生成模型中， 其中中 表示在说同 一个词时有人将其中某些部分省略掉。 ( 3 ) 在一个连接数字串的发音模型中， 其中中 表示由一个数字的结尾直接转移 到另一个数字的起始端。 h m m 结构的另一个有意义的变形是约束参数， 基本思想是在不同状态的h m m 参数间建立等价关系。此时，模型中独立参数的个数减少，并且对参数的估值 有某种程度的简化。 当观察密度在2 个或更多状态上相同时， 可应用约束参数。 语音发音时经常发生这种情况。当没有足够的训练数据用来估计大量的模型参 数时， 这种思想很合适。 此时可用约束参数来减少参数的个数( 即模型的大小) ， 目 的是简化参数估计问题。 隐马尔可夫模型在生物信息学中的应用 引言 2 0 世纪9 0 年代以来，伴随着各种基因 组测序计划 ( 人类基因组计划和各 勺刁. 互3. 种模式生物测序计划) 的展开和分子结构测定技术的突破以 及i n t e rn e t 的普及， 海量的生 物序列数据如雨后春笋般迅速出 现。 如何处理、 存储和分析这些数据? 这已 不是生物学家本身可以 解决的问题，需要其他学科的介入，由此催生了一 门新的学科生物信息学 ( b i o i n f o r m a t i c s )，它是多种学科交叉、渗透的产 物， 涉及生物学、 数学、统计学、物理学、 化学、 信息以 及计算机科学等诸多 学科的知识。 生物序列分析是生物信息学的主要研究领域， 其主要工作是从浩瀚的原始 生物序列数据中发掘和提取信息， 探索和揭示生命的奥秘，生物序列分析包罗 万象，但大致可归纳为序列同源性搜寻，多重比 对和亲缘树的构建、蛋白 质结 构预测、基因组序列分析和基因发现以及快速搜索 ( 序列) 数据库技术等主要 方面。 四川大学硕士学位论文 依据分子生物学的知识，各种数学工具己被广泛地应用于生物序列的数学 建模和分析，并取得了一系列重要结果， 有力地推动了生命科学的发展，近 1 0 年来，隐马尔可夫模型应用于生物序列分析已取得令人瞩目 的成果，隐马尔可 夫模型是一类智能化算法，首先在语音识别上崭露头角，尔后又在生物序列分 析方面屡建功勋，展现了强大的生命力，由于隐马尔可夫模型具有牢固的统计 学基础和有效的训练算法，因此能用于各种问题。下面将从 d n a序列的比对 ( a l i g n m e n t ) 、 基因 发 现 ( g e n e f i n d i n g ) 两 个方面 来介 绍 模型的 结构 和此模型 在生物序列分析中的应用。 3 . 2 d n a 序列的比对 3 . 2 . 1 d n a 序列多 重比 对的隐马尔可夫模型 生命最重要的物质基础是核酸 ( d n a与r n a ) 和蛋白 质。 d n a分子中的核昔 酸碱基分别是腺嗓吟 ( a )、鸟嗓吟 ( g )、胸腺啼健 ( t )、胞嘀咤 ( c )， 因 此 我 们 一 般 将d n a分 子 看 成 是 由 字 母 表 。 = a , g , c , t 中 的 元 素 组 成 的 字母序列， 而一切物种的蛋白 质都是由2 0 种氨基酸构成的， 所以 蛋白 质序列也 可以 用2 0 钟氨基酸的单个字母表示。 所谓序列的比 对， 是指两个或多个序列按 字母比 较，尽可能确切地反映它们之间的相似和相异性。比 较的目的在于阐明 序列之间的同 源关系，以及从己知序列预测新序列的结构和功能，下面以 “ 多 个d n a序列的比 对问题” 为例子说明如何在d n a 序列上建立隐马尔可夫模型， 设有k个d n a 序列: o (k ) = 0 .(k ) ， o 2 (k ) ， .， . o : ， (k )0 , i , z t , k k ( 3 . 2 . 1 . 1 ) 其 中 司 二 a , c , g , t ) ， 以 上是k 个 需 要 进 行比 对 的d n a 序 列 . 在d n a 序 列的 比对中，隐马尔可夫模型可如下建立 ( 如下图所示):隐马尔可夫链取值为m 四川大学硕 i - 学位论文 ( 配对)，i( 插入) 及d ( 删除) 3 个状态 ( 通常还要设置开始状态和结束 状态)，可观察的序列取值为a , g , c , t。 图1 隐马尔可夫模型 隐马可夫链可以看成在d n a 序列上运动，从一个起始状态开始，以某概率 进入配对、插入、删除状态之间的某一个，其中配对和插入状态将产生一个新 的碱基， 删除状态从原始d n a 序列中去掉一个特定的碱基。 每个状态结束之后， 模型转换到下一个状态，同样，在新的状态，又可以进入配对、插入和删除状 态。 于是当隐马尔可夫链经历了从起始状态到结束状态时， 便可得到两个序列， 一是状态序列 ( 观察不到)， 二是a , c , g , t 组成的字母序列 ( 可观察到)。 此 时， 初始状态的分布已 不重要， h m m 可简记为a = ( a , b ) o h m m 应于分析生物序列的原理是分析由 它产生不同 序列的概率，多 序列比 对 问 题 的 研 究 ， 就 是 寻 找 无 使 得 np ( o (x )乃 最 大 ， 其 中 0 (0 ， p cz)， 一 o (x ， 是 要进行比对的序列 ( 这里假设各个序列是相互独立的)。对于与模型相符合的 序列，能以 较大的概率产生该序列;若不与该模型符合的序列，则按此模型产 生该序列的概率会较小。 3 . 2 . 2 d n a 序列观察 概率的 计算: 前向 一后向算法 四川大学硕_ l 学位论文 设0 = 0 ; , 0 2 , . . . 1 0 : 是 一 个 观 察 序 列( d n a序 列) ， 记t 时 刻的 状态 为q , ， 9 o = g o = b e g i n , q t + i = s t + i = e n d 。 前 向 变 量a , ( i ) 与 后向 变 量戊( i ) 的 定 义 如 式 ( 2 . 3 . 5 )与式 ( 2 . 3 . 8 )所示。 前向 变量a , ( i ) 可按 下列步 骤 进 行迭代计算: 1 )初始化 a , ( ! ) = a . , b ; ( o , ) 1 i _ n ( 3 . 2 . 2 . 1 ) 2 ) 迭代计算 a , ( j ) = 艺a , ( i ) a y ) b , ( o , ) t = 1 ,2 , . . . , t 一 1 n ( 3 . 2 . 2 . 2 ) 后向算法可按下步骤进行迭代计算: 初始化 八( i ) = a ,. . , 1 _i _n 2 ) 迭代计算 1 5 .1 ,1 1 5i ( 3 . 2 . 2 . 3 ) a ( i) = 艺a . b ; ( o ,. ,),6 ,. i( j ) t = t一 i , t一 z , . . . _ 0 1 s i, j _ n ( 4 . 2 . 1 ) 同样假设任一时刻出现的观察矢量的概率不仅依赖于系统当前时刻所处的 状态，而且依赖于系统前一时刻所处的状态，即 气 ( 1 ) = p ( o , = v , i q , = s . , q ,- , = s , ) 1 - i . j - n 1 - 1 _ 0 ( 4 . 2 . 3 ) 状 态 转 移 概 率 分 布 a , = ( a , ) a x = a j k 其 中 a 1 = p ( q z = s j 。 一s , )艺a 4 = 1 a 0 1 _i _ 。 1 : i , l 、 n ( 4 . 2 . 5 ) 观 察 值 的 概 率 分 布 : b , = ( b ; ( 1 ) ) b z = 气 ( 1 ) 其 中 b ; ( 1 ) = p ( o , = v , q , = s ; ) 1 f n 1 i m ( 4 .2 .6 ) b 1 ( 1 ) = p ( o , = y r i q , = s ; , q ,- 1 = s , ) 1 ij n 1 - i - m ( 4 .2 .7 ) 因此，该改进的 h m m ( 二阶隐马尔可夫模型)的参数集合可简记为 it 二 份 , aa z , 尽 , b , ) ， 研 究b a u m - w e lc h 算 法 需 要 借 助 前 向 一 后 向 算 法 ， 下 面 先 介绍改进h mm ( 二阶隐马尔可夫模型)的前向 一 后向 算法。 4 . 3 4 . 3 . 1 推广的前向 一 后向算法 前向算法 定义前向变量 a , ( i , j ) = p ( o , 1 0 2 ， ， o , , q ,- , = s , , q , = s . a ) ( 4 . 3 . 1 . 1 ) 前向 变量a , ( i , .1 ) 是指在给定 模型a 的 条件下， 产生 t 以 前部分观察序列 0 1 ， o z ， . . ， 。 ， ， 且 在t - 1 时 状 态 为s t 时 状 态 为s i 的 概 率 。 前向 变量a , ( j , j ) 可按如下步骤进行迭代计算 四川大学硕 l 学位论文 1 )初始化 a 2 ( i , j ) = ;r ; b , ( o ) a , b , ( 0 2 ) i i ,j n ( 4 3. 1 . 2 ) 2 )迭代计算 a ,. , ( j , k ) = 艺 a , ( i, j ) a ,k b rk (0 ,. , ) 2 t t - 1 1 有k n ( 4 .3 .1 .3 ) 4 . 3 . 2 后向算法 与前向算法相类似，定义后向变量 1 , ( i , j ) = p ( 0 1. 1 1 0 ,1 2 ， 二 ， o t i q ,- , = s , q , = s , , a ) ( 4 .3 .2 . 1 ) 即 在 给 定 模 型a 和t- 1 时 状 态为s ; , t 时 状 态 为s i 的 条 件 下， 从t + l 时 到 最 后部分观察序列的概率，可按如下步骤进行迭代计算: 1 )初始化 几( i , j ) = 1 1 i , j 1 ) = 艺 a ,k 气 ( 0 ,. , ) q ,. , ( j , k ) r- t - 1 ,t -2 ,. . .,2 1 簇i j 成n ( 4 .3 .2 .3 ) 4 . 3 . 3 观测序列概率的计算 由( 4 .3 . 1 . 1 ) 、( 4 .3 . 2 . 1 ) 式可得， 在给定模型a 条 件下， 产生观察序列o 的概率 p ( o j z ) = p ( o ! ， 0 2 ， . . . , o t i a ) 一 艺 艺 p ( 0 : ， 0 2 ， . 二 ，0 0 ,十 : ， 一o t ,q 卜 ， 二 s ;, q ， 一 s , i 之 ) 四川大学硕 i _ 学位论文 二 艺 艺 a , ( i , j ) a ( i , 1 ) 2 t $ ,+ i = s k o , a ( 4 .4 . 1 . 1 ) 则: 1 ) , ( i , i , k ) a , ( l , i ) q j k b i k ( o ,+ , ) 戏 + i ( j , k ) 二 二 . . . ， 川 ， ， ， ， ， ， ， ， ， ， ， 刀n n 2 t t - 1 ( 4 .4 . 1 .2 ) ， 艺 艺 艺 a , ( i, j ) q k b jk ( o ,+ i ) ,8 ,+ i ( 1 , k ) 佃 ij 一 k 司 2 )给 定 观 察 序 列o 和 模型x 的 条 件下， t - 1 时 为 状态s i , t 时 为 状 态si 的 概率: r ( i, 1 ) = p ( $ ,- i = s ，。 ， = s j i o ,a ) = 艺 , ( i ,.1 , k ) a , y , j ) 戏( i , j ) = 一- ( 4 .4 . 1 . 3 ) 艺 艺 a ,( i, j ) a ( i,j ) , . i j . 证明:1 )由式 ( 4 .2 . 5 )、 ( 4 .2 .7 )、 ( 4 .3 . 1 . 1 )与式 ( 4 .3 .2 . 1 )可得: , ( j , j , k ) “ p ( 9 ,- = s , 9 , = s , 9 ,* 一s a. 1 0 , a ) 四川大学硕 i s 学位论文 - p ( 9 ,- 1 = s4 , = s ; , 9 , . , = s , , 0 1 a ) / p ( oi a ) p ( 9 , - i ， s , , 9 , = s , , o , , ， 一 ， o o a ) - p ( 9 ,+ 一s k 1 0 1. 1 1 . . . ， o t 4 (- 1 = s 9 , = s j , a ) p ( o i r ) a , ( 1 , j ) a k b j k ( 0 ,. , ) 戊 , 1 ( j , k ) 2 ) 艺 艺艺 a , ( i, l ) a k b jk ( a , ) a , ( j , k ) i - i j - 1 k - 1 r , ( t , j ) = p ( 9 ,- i = s 9 , “ s , i 0 , a ) = e p ( 9 ,- 1 = s , ,9 , = s j , 4 ,. , = s k 1 0 , a ) 2 i t - 1 ( 4 . 4 . 1 . 4 ) ( 4 . 4 . 1 . 5 ) 由式 ( 4 .4 . 1 . 1 )、 ( 4 .4 . 1 .2 )与式 ( 4 .3 . 2 .3 )即可得证。 定理1 设 , ( i , j , k ) 如式( 4 .4 . 1 . 1 ) 所定 义， 则改 进的h m m的 各 个参数的 重估公式为: n n 万 ， 二 y y, , z ( i, j , k ) 1 i n( 4 . 4 . 1 . 6 ) j - 1 k - 1 :7) 艺 z ( i, j , k ) a ， 二 k - in n 艺艺 2 ( i, j , k ) 了 - i k = 1 1 i,j n ( 4 . 4 . 1 a 必 艺 , ( l, j , k ) = 抽 z_ _ 艺艺 4 , ( i, j , k ) 1 ij , k n ( 4 . 4 . 1 n n 艺艺 , ( i, .l , k ) .8 而 = j . 1 k - in a 1 -i -n 1 ! m( 4 .4 . 1 . 9 ) 艺艺 7 2 ( i, j , k ) 1 = 1 k = 1 四川大学硕士学位论文 , ( i , j , k ) 氏.屿 n艺kcl 闪艺1-2 b ;, ( 1 ) = l . 7, , ( i, j , k ) 1 -i j -n 1 -1 -m ( 4 .4 . 其中 当。 = v ， 时， 氏, = 1 ， 否 则 么、 = 。 。 下 面 出 给出 a iik 的 重 估 公 式 的 推 导 其 余 参 数 的 重 估 公 式 的 推 导 与a p k 1 . 1 0 ) 的重 估公式的推导方法类似，这里不再重复。 证明: 在给定模型a 的 条件下， 观察 序列0 与 状 态 序列q 同时发 生的 概率 p ( o , q i a ) = 7r 4, b . , ( 0 , ) a , , b g iqx ( 0 2 ) na v,-.a,v,., b ,., ( 0 ,a ) ( 4 .4 . 1 . 1 1 ) 由上式可知，辅助函数 q ( a , a ) 一 y- lo g (p (0 ,q ia )p (o , q ia ) 才 一 1_ ! 艺艺lo g a a,-, , 一 p ( o , q i a ) + ,p q口 . 2 其 中 ， 是 与 待 估 参 数 a ， 无 关 的 其 余 所 有 项 孕 又 因 为 : ， 满 足 约 束 条 件 : n _i a ， 一 ， 所以，根据l a g r a n g e 乘子法，由 n n n了- 1 a s j k 艺 艺 艺艺lo g a yk .p ( o , 9 ,一s 9 , = s ; , 9 ,+ , = s k a ) + rp + r ( 1 , - i i - i k - i , = 2 nn-、 、。 l , a yk 1k.1少 = ” 可得 艺p ( o , 9 ,- i = s ， 。 ， = s j , 9 ,. ， 二 s k a ) a g k = 1= 2 一 艺p ( o , 9 ,- i = s ， 。 ， = s 1 a ) 四川大学, i0 i : 学位论文 ( i , j , k ) 吞 闪艺间 , ( i , j , k ) 工 r, ( i, j )艺艺 , ( i, j , k ) 1 - p s ， 即 词 串“ t h e g r e e n b a n a n a ” 比“ t h e g r e e n t i m e 更具可能性， 此结论符合我们的认识。 在随机上下文无关语法中加进了隐马尔可 夫模型产生的语言模型要比单纯用随机上下文无关语法好，因为此方法考虑了 具体词汇信息对句子结构的影响。 结论: 本文对传统的隐马尔可夫模型( h m m 1 ) 的两个假设条件作了 改 进。首先讨 四川大学硕士学位论文 论了 在观测噪声和马尔可夫链不相互独立的条件下改进的隐马尔可夫模型 二 阶隐马尔可夫模型:s e c o n d - o r d e r h m m , 简记为 h m m 2 )的结构。其次，在传统 的隐马尔可夫模型的基础上，研究了改进的模型的前向一 后向算法和 b a u m - w e l c h 算法， 并导出了 改进的 模型的参数估计公式。 最后举例说明了改进 的模型在计算语言学中的应用。 参考文献: fl 钱 敏 平， 龚 光 鲁从 数 学 的 角 度 看 计 算 智 能 j .科 学 通 报 ， 1 9 9 8 ,8 .4 3 ( 6 ) : 1 6 8 1 - 1 6 9 5 ( 2 1 j e a n - f r a n c o i s m a r i , j e a n - p a u l h a t o n , a b d e l a z i z k r i o u i l e . a u t o m a t ic w o r d r e c o g n i t i o n b a s e d o n s e c o n d - o r d e r h i d d e n m a r k o v m o d e l s j . i e e e t r a n s a c t i o n s . o n s p e e c h a n d a u d i o p r o c e s s i n g v o l . 5 , n o . , j a n u a ry 1 9 9 7 3 m a r i . j . f , f o h r . d , j u n q u j . c . a s e c o n d - o r d e r h m m f o r h i g h p e r f o r m a n c e w o r k a n d p h o n e m e - b a s e d c o n t i n u o u s s p e e c h r e c o g n i t i o n . i n p r o c . i e e e - i c a s s p a t l a n t a 1 9 9 6 ( 4 1 x i a l i n l i . , m a r c p a r i z e a u a n d r e j e a n p l a m o n d o n .t r a i n i n g h i d d e n m a r k o v m o d e l s w i t h mu l t i p l e o b s e r v a t i o n -a c o m b i n a t