（数学专业论文）拓展的隐马氏模型和贝叶斯网络.pdf

国防科学技术大学研究生院硕十学位论文 摘要 隐马氏模型 h i d d e nm a r k o vm o d e l s 简称为h m m 是一类统计模型 它包括 一个隐状态过程和一个与之相关的可观测过程 其经典理论是由l e b a u m 等在2 0 世纪6 0 年代末7 0 年代初所给出的 随后这一模型于2 0 世纪7 0 年代中期由j e n i k 等应用到语音识别领域 逐步发展成为语音识别领域中最瞩目 最有效的技术之 一 目前 它在生物统计 基因识别 文字识别和图像处理等方面都有广泛应用 贝 叶斯网络 b a y e s i a nn e t w o r k 简称为8 n 是2 0 世纪8 0 年代发展起来的 最早由 j u d e ap e a r l 于1 9 8 6 年提出 当时主要用于处理人工智能中的不确定性信息 随后 它逐步成为处理不确定性信息技术的主流 并且在工业控制 医疗诊断等领域的 许多智能系统中得到应用 本文主要从隐马氏模型的拓展着手 首先定义了广义隐马氏模型 g e n e r a l i z e d h i d d e nm a r k o vm o d e l 简称为g h m m 推导出了g h m m 的三个问题的解决方 法 得出了类似于隐马氏模型的前后向算法 v i t e r b i 算法以及学习算法 并通过 仿真试验验证了算法的可行性 同时考虑小波具有很强的去噪功能 我们把小波 加入到隐马氏模型中来 并推导了小波变换在隐马氏模型非参数估计中的应用 然 后从维数拓展上研究讨论了2 维隐马氏模型 通过对离散2 维隐马氏模型 2 d h i d d e nm a r k o vm o d e l s 简称为2 dh m m 三个问题的推导 结合模糊聚类 推 导了f u z z y 2 d h m m s 算法 证明了算法的收敛性 同时定义了连续2 维隐马氏模 型 并简单推导出了连续2 维隐马氏模型三个问题的解决方法 最后从考虑更一 般的隐马氏模型角度研究了贝叶斯网络 总结了动态贝叶斯网络和隐马氏模型之 间的联系 通过转换为隐马氏模型对几类离散d b n 进行了推导 关键词 隐马氏模型广义隐马氏模型2 维隐马氏模型 贝叶斯网络小波变换f c m 算法 第i j 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t t h eh i d d e nm a r k o vm o d e l sw h i c hc o n s i s to fah i d d e nm a r k o vp r o c e s sa n da n o b s e r v a t i o np r o c e s sa r es t a t i s t i c a lm o d e l s a n dt h es h o r tf o r mi sh m m t h e yw e r e b r o u g h tf o r w a r db yb a u ma n dh i sc o l l e a g u e si nt h el a t es i x t i e sa n de a r l ys e v e n t i e s i n 1 9 7 0 s t h e yw e r ea p p l i e di n t os p e e c hr e c o g n i t i o nb yj e n i ka n ds o m eo t h e rp e o p l e t h e y h a v eb e e nd e v e l o p e dt ob eo n eo ft h em o s te f f i c i e n tt e c h n i q u e s n o w t h e yh a v eb e e n w i d e l yu s e d i n b i o s t a t i s t i c s g e n er e c o g n i t i o n c h a r a c t e rr e c o g n i t i o n a n di m a g e p r o c e s s i n ge t c b a y e s i a nn e t w o r kw a sd e v e l o p e di nt h el a t ee i g h t i e s w h i c hw a s b r o u g h tb yj u d e ap e a r la n dh i sc o l l e a g u e si n 19 8 6 i th a sb e e nm a i n l ya p p l i e dt o u n c e r t a i ni n f o r m a t i o no fa r t i f i c i a li n t e l l i g e n c ea tf i r s t g r a d u a l l yi th a sb e e nd e v e l o p e d t ob et h eb a s i ct e c h n i q u e so fu n c e r t a i ni n f o r m a t i o n a n di th a sb e e nw i d e l yu s e di nt h e i n t e l l i g e n c es y s t e mo fi n d u s t r yc o n t r o l m e d i c a ld i a g n o s ee t c i nt h i sa r t i c l e w es t a r t e dw i t he x t e n s i o no fh m m f i r s t l y w ep r o p o s e dan e w g e n e r a l i z e dm a r k o vm o d e lg h m ma n dw es t u d i e dt h r e eb a s i cp r o b l e m so ft h e g h m m s e v e r a ln e wa n a l y t i cf o r m u l a ew h i c ha r es i m i l a rt of o r w a r d b a c k w a r d a l g o r i t h m v i t e r b ia l g o r i t h ma n ds t u d y i n ga l g o r i t h mo fh m m f o rs o l v i n gt h r e eb a s i c p r o b l e m s w e r e t h e o r e t i c a l l y d e r i v e da n df u r t h e rd e m o n s t r a t e d b yc o m p u t e r s i m u l a t i o n c o n s i d e r i n gt h eb e s td e n o i s i n gf u n c t i o n w ei n t r o d u c e dt h ew a v e l e ti n t o h m ma n di n t r o d u c e dw a v e l e tt r a n s f o r m a t i o nf o r n o n p a r a m e t r i c e s t i m a t i o no f h m m n e nw ed i s c u s s e d2 d h m mb yc o n s i d e r i n gt h ed i m e n s i o n a le x t e n s i o no f h m m c o m b i n e dw i t hf u z z yc l u s t e r i n gf u z z y 一2 d h m m sa l g o r i t h mw a sp r o p o s e da n d c o n v e r g e n c eo ft h ea l g o r i t h mw a sa n a l y s e dt h r o u g hs o l v i n gt h et h r e eb a s i cp r o b l e m so f 2 一dh m m w ep r o p o s e dt h ec o n t i n u o u s2 dh m ma n ds i m p l yi n f e r r e dt h et h r e eb a s i c p r o b l e m s o fc o n t i n u o u s2 dh m m f i n a l l y w es t u d i e db a y e s i a nn e t w o r kb y c o n s i d e r i n gam o r eg e n e r a lh m m t h er e l a t i o nb e t w e e nh m ma n dd b nh a db e e n s u m m a r i z e d t h e nw es o l v e dt h er e a s o n i n gp r o b l e mo fs e v e r a lk i n d so fs e p a r a t e dd b n k e yw o r d s h m mg h m m 2 dh m m b a y e s i a nn e t w o r k w a v e l e tt r a n s f o r m a t i o nf c ma l g o r i t h m 第i j i 页 国防科学技术人学研究生院硕十学位论文 图表目录 表2 1 f 加 a b 的数值 1 2 表2 2 一f 岳 一a 百 的数值 1 3 表3 1 初始模型参数 2 4 表3 2 重估的新模型参数 2 4 第l l l 页 国防科学技术大学研究生院硕十学位论文 图4 1 图4 2 图4 3 图4 4 图4 5 图目录 变量消元法示例 3 5 d b n 表示图 4 2 特殊d b n 表示图 4 5 因子h m m 表示图 4 5 耦合h m m 表示图 4 7 第i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已 经发表和撰写过的研究成果 也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目 垣匮鲍随墨匮搓型塑丛生堑圉签 学位论文作者签名 日期 删年 月 彦日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留 使用学位论文的规定 本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档 允 许诊之淡查阅和借阅 可以将学位论文的全部或部分内容编入有关数据库进行检索 可以呆用影印 缩印或扫描等复制手段保存 汇编学位论文 保密学位论文在解密后适用本授权书 学位论文题目 垣匮鲍随墨匮送型塑丞生堑圜签 学位论文作者签名 作者指导教师签名 垃立绐 垒 日期 脯i 月谚日 日期 多卯扩年i 1 月加日 国防科学技术大学研究生院硕十学位论文 第一章绪论弟一早三百y 匕 隐马氏模型 h i d d e nm a r k o vm o d e l s 简称为h m m 作为一种统计模型 在生态学 密码分析 基因识别 目标跟踪 图象处理和信号处理等等各个领域 中获得了广泛的应用 1 9 6 6 年 b a u m 和p e t r i e 在文献 1 l 2 q h 最早完整地提出了 隐马氏模型 当时称之为马尔可夫链的概率函数 随后在2 0 世纪7 0 年代中期由 j e n i k 等应用到语音识别中p i t 4 1 逐步发展成为语音识别中最瞩目 最有效的技术 之一 由于贝尔实验室的r a b i n e r 等人在2 0 世纪8 0 年代中期对隐马氏模型理论深 入浅出的介绍1 5 1 1 6 i 才逐渐使隐马氏模型为世界各国从事语音处理的研究人员所了 解和熟悉 进而成为公认的一个研究热点 1 1 隐马氏模型的研究现状 近年来 人们尝试将隐马氏模型应用于移动通信中的多用户检测和生物信息 学中的d n a 序列对比 但是影响模式识别系统识别率的重要因素是输入信号的不 规范 在手写体文字识别中 由于写字者的不同 手写文字与标准文字之间的差 异 都造成了识别系统输入信号的不规范 在语音识别中 不同说话人音调 语 速的变化 以及各种实时环境中的噪声等等 更会导致系统识别率的降低 因此 研究人员考虑把具有很强的滤波去噪功能的小波变换引入隐马氏模型 得到了一 种对输入模式信号自适应 抗干扰的隐马氏模型 隐马氏模型在语音识别 字符识别 金融数据分析和图像处理等领域的研究 中已经获得了广泛的应用1 1 4 2 1 由于它只能直接对序列数据建模 因此可以被看 作是1 维的 如果要用1 维隐马氏模型来处理矩阵数据 比如图像数据 就必须选 择由 些特征构成的序列数据来表达矩阵数据 而这常常会损失掉矩阵数据中所 蕴含的某些重要信息 因为矩阵数据在本质上是2 维的 它们和序列数据相比在 拓扑结构上通常都存在着本质上的区别 因而科研工作者开展了对1 维隐马氏模 型进行2 维的推广工作 比如a g a z z i 和k u o 提出的 伪2 维隐马氏模型1 2 3 1 1 2 4 1 但 其本质卜是两个1 维隐马氏模型的嵌套 不是真 f 的2 维隐马氏模型 真正的2 维隐马氏模型最先由d e v i j v e r 提出并应用于图像分割1 2 5 1 通常又被称为隐马氏网 格随机场 2 维隐马氏模型的三个基本问题可以利用确定松弛算法和l j 向算法 心6 1 2 7j 近似求解 但是一直没有得到很好的解决 文献 2 8 通过把2 维隐马氏模型 斜对角线卜的状态序列看作一个状态可变的1 维马氏模型 利用l 维隐马氏模型 下的前向后向算法和v i t e r b i 算法讨论了2 维隐马氏模型的分析解 但是 现有 的算法并不是很完美 随着新问题的不断出现 就要求寻找更有效的解决方法 因 第1 页 国防科学技术大学研究生院硕十学位论文 此 现在和以后的 段时f h j 内将仍然足一个活跃的研究方向 贝叶斯网络 3 s 加 是一种帮助人们将概率统计应用于复杂领域 进行不确定性 推理和数据分析的工具 它起源于人工智能领域的研究并且在工业控制 医疗诊 断等领域的许多智能系统中得到应用 研究贝叶斯网络需要解决两个问题 推理 问题和学习问题 静态贝叶斯网络的推理问题现在有很多方法可以解决 效果还 比较好 学习问题是个n p 问题 而且针对不同的条件有不同的解决方法 研究是 没有止境的 现在和以后的一段时间内将仍然是一个活跃的研究方向 动念贝叶 斯网络由于节点太多 它的推理和学习都是很困难的 目前还有很多问题需要解 决 动态贝叶斯网络1 4 1 1 是目前研究的一个热点 1 2 本文的主要工作 本文在第二章介绍了隐马氏模型的三个基本问题 并且讨论了连续隐马氏模 型的三个基本问题的解决 经典的隐马氏模型首先要求隐状态过程为单步齐次平 稳马氏链 在实际中当噪声比较复杂或者噪声影响较大时就无法满足 其次在经 典隐马氏模型中我们假设观测值只与最近的状态有关 但是在实际问题中观测值 往往受到前面观测值的影响 为了解决这些问题我们放宽了隐马氏模犁的假设提 出了广义隐马氏模型 经典隐马氏模型和广义隐马氏模型最大的差别在于广义隐 马氏模型中只有一个马氏过程 同时介绍了小波变换在隐马氏模型非参数估计中 的运用 本文第三章从维数拓展上研究讨论了2 维隐马氏模型 给出了离散2 维隐马 氏模型的定义 并类似给出了连续2 维隐马氏模型的定义 文献f 2 8 指出2 维隐马 氏模型行或者列上的状态序列也具有马氏模型的特征 通过这点讨论了2 维隐马 氏模型的分析解 得到解决三个基本问题的算法 模糊c 均值 f c m 算法是一 种基于模糊划分的模糊聚类分析方法 它通过对目标函数进行p i c a r d 迭代来实现 极小化 d a tt r a n 和m i c h a e lw a g n e r 等人将f c m 算法和e m 算法相结合 提出了 模糊e m 算法 并将它应用到了离散隐马氏模型 d h m m 的参数训练中 在此 基础上又结合了模糊熵 f e 聚类算法 提出了一种新的目标函数 最终给出了 f c m f e h m m s 算法 我们把这个思想应用到2 维隐马氏模型上束 得出了 f u z z y 2 d h m m s 算法 得到了更广泛的学习算法 第四章在考虑进一步拓展隐马氏模型的基础上联系到贝叶斯网络 介绍了贝 叶斯网络的摹本内容 把隐马氏模型和动态贝叶斯网络对比 得出 e f f j 的联系 同 时通过对比隐马氏模型与动态贝叶斯网络 发现隐马氏模型是动态贝叶斯网络的 一类特例 可以把离散的动态贝叶斯网络转换为隐马氏模型 由此推导了几类离 散动念贝叶斯网络的推理和学习问题 第2 页 国防科学技术大学研究生院硕士学位论文 第二章隐马氏模型基础知识及拓展 本章第一节第二节介绍了离散h m m 和连续h m m 的定义 讨论了隐马氏模 型三大问题中的学习问题 第三节针对经典隐马氏模型中观测值只与最近的状态 有关 但是在实际问题中观测值往往受到前面观测值的影响这个问题我们提出了 广义隐马氏模型 最后讨论了小波变换在隐马氏模型非参数估计中的应用 简单 推导了小波变换在隐马氏模型非参数估计中的应用 2 1 隐马氏模型定义 隐马氏模型的定义是马氏链定义的延伸 对于马氏链 所描述的系统的每一 个状态都与一个可观测的 物理 事件相对应 但是这个限制太严格 在许多实 际问题中不能应用这样的模型 因此 我们把该模型的概念延伸到如下情况 状 态过程无法直接观测 而只能通过观测来问接了解 从而引入了隐马氏模型 因此 我们定义隐马氏模型为一个双重的随机过程 它具有一个不可观测的隐状态随机 过程 该过程是一个马氏链 该过程只能通过另一个可观测的随机过程来进行 了解 观测过程概率地依赖于隐状态过程 马氏链可以作为隐马氏模型的一个特 例 观测过程正好等于隐状态过程 此时观测过程概率地依赖于隐过程就变成了 一种确定性的依赖了 我们先给出经典的离散隐马氏模型 d h m m 和连续隐马 氏模型 c h m m 的定义 定义2 1 1 离散h m m 由两个定义在概率空间 q f p 上的随机过程似 y 组成 其中x 置 te t 为不可观测单步齐次马氏链 状态空间为s 住2 y t 丁 是一个可以观测到的与状态链相关的离散时间有限状态过程 状态空 间为v 一他2 m 分别称之为隐状态过程和观测过程 这样 一个离散h m m 的概率参数为a 似 a b 其中初始概率万 杌k 尸 x o i 转移概率 a 一 k p x j i x f 观测特征的条件分布 b p f 七 b j 足 p k l j f j 它们分别满足 nnm 善巧2 1 荟 1 1 2 1 定义1 1 2 在定义2 1 1 中 如果观测空间y 变成连续空间 隐状态链x x 和观测链y y 的相关性由如下的一族观测概率密度函数来表达 b 2 b j y y y k 2 第3 页 国防科学技术大学研究牛院硕士学位论文 其中 y p x 阢 yi 表示在x 的条件卜 k 的条 f l 概率密度 它满足 c 6 y d y 1 我们称此模型为连续h m m 不同形式的6 y 是由不同的参数来描述的 而估计这种参数的e m 公式也是 不一样的 目前使用比较广泛的是高斯型即6 y 具有下面的形式 k f f b s y c j k y 乒l j k 业 其中n y j c l 弦 肛 为d 维高斯密度函数 业为均值矢量 肚为方差矩阵 k j 为 x ln 组成6 的混合概密个数 c j k 为组合系数 满足 c 弦 1 连续h m m 参数仍可记为a 缸 a b 其中的b 不再是一个矩阵 而是一组 概率密度函数族 在本章中 如果没有特殊交待 连续h m m 均为混合高斯型 2 2 隐马氏模型的三个问题 隐马氏模型需要解决三个基本问题 识别问题 给定一个观察序列y y l 一 y r 和某个模型a 0 a b 计算y 在a 下的概率p y y l a 解码问题 给定观察序列y 一 y l 一 y r 和模型a 怎样选择另一个隐状态序 列x 五 x t 使它在某种意义下是最优的 学习问题 对于给定的观察序列y y l 一 y r 怎样调整模型参数a 从而找 到一组最适合样本集的参数a 伍 a b 对离散h m m 三个问题的解决 可分别用前向 后向算法 v i t e r b i 算法和e m 算法得到解决 很多资料上f 5 l i 8 i 都有具体的理论推导 连续h m m 三个问题的解 决也相似的用这三种算法来解决 我们主要在连续h m m 下对三种算法做简要的 讨论 2 2 1 识别问题 已知观测序列y y l 一 y r 和模型a 何 彳 b 记状态过程及相应的状态 值分别为x x 1 一 x r x 记观测过程y k 匕 匕 识别问 题的关键是计算概率尸 y 引a 其中y 多是指 sy n es y n n ksy t 在本文中都采用这种记法 那么我们定义如下几个变量 第4 页 国防科学技术大学研究生院硕十学位论文 p 附一协 坐坠警华型艘 础 型鼍羔 型 删 塑盟攀芷冬型尘业 o y f 吵丁 很容易得到连续h m m 的前后向算法 i 初始化 口 乃包 y 1 墨fs n 屏 i l 1 i n i i 迭代 a 一a t j a j i b i y 1s fs 丁一1 1sis 尼 i 乏屈 t j a i j b y t 1 1 墨f s z 一1 1s fs i i i 结果 p y 1 一 y r 2 善 f 2 荟展 j 包 y 2 著q f 肛 f 要求得p y 引a 只需再对p y 1 一 y r 多重积分即可 2 2 2 解码问题 给定一个观测序列y y y r 和一个h m m 的参数a 我们需要知道观测 链所对应的隐状态序列是什么 这一问题的问答取决于对模型状态物理意义的理 解 对于同一个观测序列y y l 一 y r 根据不同的优化原则 可以得到不同的 状态序列 我们普遍采用路径最优原则 这是基于整体性考虑的方法 令 6 f m a x 塑堕堕 型i 生墨兰坚竖蔓兰业 f l 乓一t 妙1 妙 则我们很容易得到 4 o 包 m m a x 6 口 f 它的实际计算程序可以用如下的v i t e r b i 算法 i 初始化 6 l f 刀f b i y 1 第5 页 国防科学技术大学研究牛院硕十学位论文 妒1u 0 i i 迭代 4 6 y m a x 6 o a u 妒 a r g m a x 6 f i i i 结束 p 一m 璺x 辞 f 砖 a r gm a x r 训 i v 路径回溯 即最佳状态链的确定 彳 妒 t 2 2 3 学习问题 学习的目的是通过对学习样本集的统计计算 调整模型的参数a 协 a b 以 使概率p y 引a 最大 即是使得p m y r 最大 从而对每个模式找到一组最 适合样本集的参数 这是三个问题中最困难的一个问题 实际上 给定任何有限 观测序列 没有一种最佳方法能估计模型参数 但是可以利用迭代处理方法来选 择a p a b 以使概率p y 引a 局部最大 我们主要讨论e m 算法 设模型的 初始参数为a 协 a b 且读入样本的观测序列y y l 夕 y r 我们记 y 匕 k 类似离散的情况我们定义如下变量 邑 塑坠娑乓巫型 埔 一 以啦 塑 字 拨h m m 的定义很答易得出 酏j 必挲出巡 q i f l t n f 盟 q j 屈 第6 页 比七 盟x 李业盟 善q j 肛 薹c 谴n y 心 故 上式中 q f 屈 f 分别为前向变量和后向变量 茧 f 表示在f 时刻发生状 态转移 i 呻歹 的概率 相应的n i 为t 时刻状念为i 的概率 以 i 为整个观测 序列中从状态f 出发的概率 茧 f 为整个观测序列中状态转移 f 一 的频 率 由极大似然原理得到离散h m m 重估公式 岛 一酗 胴 互 o 弓 亨j 一 c 业一 弓 一 泓 f 以 r 扣1 r 扣1 2 2 1 1 一善以 j k y 一 以 歹 七 y 一u j k 只一i r 业 上弓 一 z 肚 昌 星 亍 一 以 胴 以 j 七 我们可以类似地给出连续h m m 参数估计的严格证明 首先 我们仿照离散证明定义下面的目标函数 q a 万 p 伍 x m 一优 y y l a i o g p x 毡m 优 y 多l 万 其中x x m m 和y y 分别表示x l 葺 x r 坼 m l m r 坼和 x y l 一 耳 y r p x x m m y 多恤 o r p x x m m y y l a 根据模型的定义我们很容易得到 p z 咄m 毗y 讷2 氏珥 幽珥 y r 其中吃 y 表示p m m y 量y i 置 x t a 根据上式对目标函数分解 我们得到 q a d q l a a 一 q 2 a 万 q 3 a 万 其中 q l a 万 l g 曩p x f y 歹i 万 q 2 a 万 iv i v 1l g p 置 f 置 1 市 第7 页 国防科学技术大学研究生院硕士学位论文 g z 乃 i v l i 11 0 9 y p x i m y 多f j 17 t 1 f i 对q 1 a 石 和g z 万 进行优化我们可以得到 珥 p x r i y 两 p 鼍乩置 1 j r e yx j i p 五吐y e x 因 只 q n y u 甜 故我们有q 3 a 万 0 3 a 万 q 3 a 万 q 3 q 万 2 善善善1 g c f p 置if m f r i x q 3 z q 万 2 荟荟善l o g n y r 玎泗 x r f m r z r i x 对g a 万 优化很容易得到 2 3 2 4 p 置吐m f r y l x 2 旦1 2 5 p 置 f y e x q 3 a 两 誊砉耄 一罢 g h 一j 1 g i i j 1 y 一 厂 i 1 1 m 一 卜 置 z m y 歹l 万 分另 令皇半 旦紫 得至o f 甜以善t p 置一f m 一z y 多i 万 y t u i l 匿tp 置吐m 吐y 歹瞅 甜一 y n i t y u i t n o 2 甜 p 置乩m f y yx y p 一屯m 吐y e yx z p x f m z y 多l 万 只一比 只一甜 r tp 置屯m y 砸 显然 2 3 2 7 式与 2 2 式是等价的 从而证明了重估公式 2 6 2 7 第8 页 国防科学技术大学研究生院硕士学位论文 2 3 广义隐马氏模型 隐马氏模型在基因关联分析和基因识别 文字识别 语音识别 图象处理等 方面都有广泛应用 但美中不足的是它首先要求隐状态过程为单步齐次平稳马氏 链 在实际中当噪声比较复杂或者噪声影响较大时就无法满足1 3 5 3 7 1 其次在经典 隐马氏模型中我们假设观测值只与最近的状态有关 但是在实际问题中观测值往 往受到前面观测值的影响 为了解决这些问题我们提出了广义隐马氏模型 经典 隐马氏模型和广义隐马氏模型最大的差别在于广义隐马氏模型中只有一个马氏过 程 2 3 1 广义隐马氏模型定义 定义2 3 1 广义隐马氏模型 g e n e r a l i z e dh i d d e nm a r k o vm o d e l 简称为 g h m m 由两个定义在概率空问 q f j p 上的随机过程僻 y 组成 其中 x 一 置 t e t 为不可观测的离散时间有限状态过程 状态空间s 1 2 y 似 t e t 是一个可观测到的与状态链相关的离散时间有限状态过程 状态空间 为vz 1 2 m 分别称之为隐状态过程和观测过程 若z x y 为单步齐 次马氏链 且将来的状态和观测只与最近的状态和观测有关 那么我们就称模型 为广义隐马氏模型 这样 一个g h m m 的概率参数为f 缸 a b 各个参数的 定义如下 i 概率分布万 乃k p x 吐i e s i i 转移概率a 0 膻 呦删 删i 口坎 j 1 p x j f y ix t f y 七 i i i 特征条件分布 b p f u 村i b j u p y i x f j e s k ze v v f 1 2 t 一1 它们满足 著嘎21 荟6 1 善善 7 1 1 sfs 1s 七sm 2 8 一般对每个模式建立一个广义隐马氏参数模型 而要识别一个样本就是给出 样本的观测过程y 佤 匕 找出此样本出自那一个模型r 这就需要解决三 个问题 识别问题 解码问题和学习l u j 题 2 3 2 广义隐马氏模型的求解 1 识别问题 在给定一个观测序列y y y y r 和模型r 的条件下计算观测序列的概率 第9 页 p y yir 记状态过程的状念值石 o 工 x t 状态过程和观测过程的值 z z 1 乙 刁 其中z f 只 易知 p y 2 ylr 2 荟p z zi t 荟如 口x 熊 一s r x b 1 士 对x 的所有可能情形求和就能得到结果 但其计算量是指数级 当 较大时 很难实现 因而我们考虑前向算法和后向算法 把模型的前向变量口 f 和后向变 量屈 f m 定义为 o t p x y y 置 i r 2 9 屈 i y r p 只m 匕一y rlz f f y r 2 1 0 q 和f l i 咒 可以递归计算如下 i 初始化 口 o p x 1 一f x y l r 曩岛 y i e s 2 1 1 屏o 蜥 暑1 v i e s 渺r y 2 1 2 i i 迭代 o f t 1 f 2 一 q 弦j y r i 帅y i e s v t e 1 2 t 1 2 1 3 f l t i 苁 2 口 以 i y 诡 y v i e s v t e 1 2 t 一1 2 1 4 i i i 结果 p y 2 yl f 2 著 o 2 喜展 l y p z 1 f lr 产 o t t i f l t i 只 2 1 5 我们以p y yir 作为衡量在不同模型下的相似度 并按照b a y e s 统计原则 取f 一a r g m a x p y yi 一 为识别结果 认为样本y 出自模型r 2 解码问题 给定观测量序列y y ly y 丁 我们需要知道观测链对应的隐状态 根据 不同的优化原则我们可以得到不同的状态序列 单点最优 即在每一个时刻求最可能的状态 我们定义变量 n i p 置 i l r y r 由定义我们很容易得到计算公式 肿卜错2 篇溉 仁峋 因而我们可以求得在每个时刻的最可能状态 第1 0 页 国防科学技术人学研究生院硕十学位论文 a r g m a x 以 f t 1 2 丁 e 5 但是这种原则没有考虑前后状态的制约关系 我们一般考虑路径最优的原则 路径最优 在给定y y 1 y r 和模型r 的条件下 使整个状态序列最优 即 x a r g m a x p x xi y y r 我们定义变量 6 m a xe z 1 一 y z 2 0 2 2 z y i r 因此得到相应的v i t e r b i 算法 i 初始化 6 f p x 1 一f k y if 嘎b i y f 0 i i 迭代 v t 2 z 1 2 4 i m a x 6 j 口肌 i y q t i a r gm a x 6 一 加 舳 i y l s s v i i i 结束 p m 瑚a x 6 r x r a r gm a x 6 r f i v 路径回溯 一仍 l z 二1 t 1 2 t 一1 2 1 7 2 1 8 2 1 9 2 2 0 2 2 1 2 2 2 2 2 3 3 学习问题 学 3 的目的是通过对样本集的统计计算 调整模型的参数 对每一个模型在 极大似然意义下找到一组最适合样本的参数 设观测样本为y y ly y r 我 们定义变量 缶o p 置 i 置 i y y f 由条件概率定义我们很容易得到计算公式 骢加竖一2 专等 由极大似然原理可以得到模型参数重估公式为 嘎一y 1 f 2 2 4 第1 1 页 国防科学技术大学研究生院硕十学位论文 色o j 6 y v k 6 y 巾 n 擅 j f 旦l 1 百 一 n f 6 y k n o 6 y 吨 包 七 旦 f 一 以 f t 1 2 2 5 2 2 6 其中6 是一个特征函数 在本文后面章节中如无特殊交待均为特征函数 定义如下 毗 任黧 上述重估公式的收敛性证明可以借助e m 算法的基本思想 参照经典h m m 的 参数估计公式的推导过程 1 3 l 来完成 我们先给定某个初始参数r 0 在当前状态下 按 2 2 4 1 广 2 2 6 式重新估计参数r 然后在新得到的参数下重估模型的参数 直至 某个收敛条件满足为止 最终得到的模型使p y yir 达到局部极大值 2 3 3 仿真示例 构造一个广义隐马氏模型的计算实例对上面的几个算法的实现和运行作进一 步说明 取n 2 m 3 f 协 a b 的具体数值见表2 1 表2 1f 一缸 a 口 的数值 r 的参数 i 1f 2 石 0 4o 6 a l l z 0 2 0o 1 5o 2 0o 1 7 o 1 50 2 0 o 1 0o 1 50 2 0o 1 3o 1 5o 2 0 a i 2 z 0 1 5o 1 50 1 5o 1 5o 2 00 1 5 0 1 50 2 00 2 00 1 5o 1 50 2 0 a i 3 z o 2 00 1 5o 1 50 2 00 2 00 1 5 o 1 50 1 50 2 0o 1 5o 1 50 1 5 6 f 尼 o 2 0 0 4 00 4 0o 3 0 0 4 00 3 0 p y yir 1 8 0 11 e 一0 2 5 随机生成一个观测样本 那么利用前后向算法计算p r yir 一1 8 0 1l e 一0 2 5 再由v i t e r b i 算法得到最优状态过程x 此外如果以模型r 的数据作为初始参数 第1 2 页 国防科学技术大学研究生院硕 学位论文 通过学爿算法训练模型 直到收敛 那么得到新的模型参数f 协 a 曰 见表2 2 冉 利用前后向算法计算e r yir 我们发现此时尸 y yir 达到了局部最大值 模型达到了最优 表2 2f 缸 a 曰 的数值 r 的参数 f 一1f 2 o 6 1 1 20 3 8 8 8 巧 a i l f 0 1 4 2 0o 2 3 6 50 1 7 9 80 1 3 0 8o 2 3 8 80 1 8 2 6 0 0 6 8 80 2 2 9 4o 1 4 3 40 0 6 4 80 2 2 5 80 1 5 7 7 a i 2 z 0 2 1 3 20 0 5 7 50 1 8 2 80 2 1 5 60 0 5 6 80 1 8 5 7 o 2 18 10 0 7 9 80 2 4 8 50 2 2 7 10 0 5 7 30 2 5 6 9 a i 3 z 0 1 3 2 50 1 9 3 00 1 7 1 30 1 2 1 30 2 0 9 50 1 7 6 4 0 1 0 5 50 1 8 6 20 2 1 1 50 0 7 6 60 2 4 1 20 1 7 9 3 包 七 0 3 2 3 50 3 2 6 40 3 5 0 10 2 6 4 20 3 4 0 40 3 9 5 4 p 一yir 9 4 314 e 一0 2 4 2 4 小波变换在隐马氏模型的应用 自2 0 世纪8 0 年代以来 隐马氏模型尤其是连续h m m 被成功应用于语音识 别和文字识别 近年来 人们又尝试将其应用于移动通信中的多用户检测和生物 信息学中的d n a 序列对比 但是影响模式识别系统识别率的重要因素是输入信号 的不规范 在手写体文字识别中 由于写字者的不同 手写文字与标准文字之间 的差异 都造成了识别系统输入信号的不规范 在语音识别中 不同说话人音调 语速的变化 以及各种实时环境中的噪声等等 更会导致系统识别率的降低 因 此我们需要构造一种对输入模式信号自适应 抗干扰的隐马氏模型 由于小波变 换具有很强的滤波去噪功能 一个自然的想法是在隐马氏模型识别系统前串连一 个小波滤波器 但是当输入的信号进行了小波变换后 隐马氏模型的参数也相应 发生了改变 就需要重新估计参数 计算很繁琐 我们给出一种方法通过给定变 换后的小波系数来修改隐马氏模型模型参数的值 避免了繁琐复杂的计算过程 连续h m m 参数为a 如 a b 其中初始概率万 仉i r r i p x o f 转移概 率a 口 f k 尸 一 i x f 观测特征的条件分布 rk 1 b b j y 罗c j k n y l t j k 肚 ye v 1 2 i t i t n 我们假设变换后的向量序列可 l 镯 j 以表示为如下形式 第1 3 页 国防科学技术入学研究生院硕十学位论文 z l 儿 其中z t 代表t 时刻小波滤波器的输出 伪 j 1 2 j 表示小波滤波器的脉冲 响应 一 代表t 一 时刻隐马氏模型的观测值 对每一个 f k 和0 s s j 我们定义变量妒讲o 一 o 一 缈趾 f j e h j y 一 矗 l y 一 一1 h j y l 一 i m 一 k f 一 c o v h y 一 办 1 y 一1 0 y 一 i 一 f m 一 一k 我们记经小波滤波器变换后的模型参数为a 一 7 a b7 其中由参数定义我 们易得玎7 a c 肛7 不变 我们记变化后的b c 肛 心 让 由妒址o j f 一 定义 我们得到心7 妒政 f 诸 o 且妒地o n o 一 有如下迭代公式 妒龌 f 一 一h j e y 卜 i 五一 f m j k 荟荟嘶t 只 j 1 h j y i x 广啦m 七 j 1m t m t j l 七7 p 心手l f 7 m 手1 川誓一 f m 一 k 荟磊 妒 o j 一1 锄 2 2 7 0 一 h j 2c o v y 卜 x t j i m 足 荟z c o v j l l m 只十 h j y i x j f m 州 七 十1 f m 叫一1 七7 p j l f m 一 一1 k7 i t 一i m 一 k 2 2 玻 荟荟m f j 嘲触 2 2 8 而缈诸 f j 口m 心 f j 口m2 政因而得到小波变换后的参数重估算法 i 初始化 对i 1 2 n 和k 1 2 l 有 妒膻o 一 口 政 i t j a m 2 踣 i i 迭代 对j 一j 一1 o o0 逐次使用 2 2 7 式 2 2 8 式计算妒膻o j o j j i i 结果 7 妒汝o 披 驴浊o 第1 4 页 国防科学技术大学研究牛院硕七学位论文 第三章2 维隐马氏模型 本章第一节我们研究了2 维隐马氏模型的定义以及三个基本问题 给出了解 决这三个基本问题的算法 并通过计算机仿真对算法的实现和运行作了进一步的 说明 第二节结合了模糊熵 f e 聚类算法 得出了f u z z y 2 d h m m s 算法 可 以发现学习算法是f u z z y 一2 d h m m s 算法的一种特殊情况 同时定义了连续2 维隐 马氏模型 并推导出了三个问题的解决方法 3 12 维隐马氏模型理论 隐马氏模型自从b a u m 等人在2 0 世纪6 0 年提出以来 1 4 就在语音识别 字 符识别 金融数据分析和图像处理等领域的研究中已经获得了广泛的应用 1 4 2 1 1 由 于它只能直接对序列数据建模 因此可以被看作是1 维的 如果要用1 维隐马氏 模型来处理矩阵数据 比如图像数据 就必须选择由一些特征构成的序列数据来表 达矩阵数据 而这常常会损失掉矩阵数据中所蕴含的某些重要信息 因为矩阵数 据在本质上是2 维的 它们和序列数据相比在拓扑结构上通常都存在着本质上的 区别 为了更好地利用隐马氏模型的思想对矩阵数据建模 对1 维隐马氏模型进 行2 维推广很有意义 文献 2 8 指出2 维隐马氏模型行或者列上的状态序列也具 有马氏模型的特征 通过把2 维隐马氏模型斜对角线上的状态序列看作一个状态 可变的1 维马氏模型 利用l 维隐马氏模型下的前向后向算法和v i t e r b i 算法讨论 了2 维隐马氏模型的分析解 3 1 12 维隐马氏模型定义 设k 沏 1 i1 msm 1s ls 是一个大小为m n 的整数网格 对于 k 中任意两个格点 m n7 和 m 以 若m7 m 或者m m 且 l7 n 那么称格点 m7 n7 在格点仰 1 之前 用 m n m z 表示 我们记格子点上的状态为x 其取值空间为s s s s s l 记格子点上的观测状态为匕 其取值空间记为 v 似 砭 吆 若我们记死 优 n l m n l n l 3 1 p x 一 一i x 一1 一 q m 一1 m l n 1 7 i p x 如一i x 一1 川 m 2 l n l 一般我们假设随机过程满足时齐性 即 3 1 式不随格子点变化而变化 这样 一个 离散2 维隐马氏模型的概率参数为a 一缸 a v a a b 各个参数的定义如下 i 初始概率石 饥k e x l 一f 1s is i i 第一列状态转移概率分布a y a y 体瞄 p 以 l j ix 剃 l 置f 1 墨f s 厶1s 聊sm i i i 第一行状态转移概率分布a a 口 i 口孑一p x 一一j lx 川 f 1 f j sl 1 s ls n i v 2 阶状态转移a a 口耻i 口 七 p l i kix 一l 一 f x m 一一l 1s f ksl 1s lsm 1s 以 v 观测特征的条件分布b b p 尼 工 xp j p y 一一kl x m 一 j 1s k k 1sj sl 1sm g m 1s 霉s 这样我们定义了2 维隐马氏模型 直接对它进行讨论很困难 我们需要把它 转换成经典隐马氏模型来处理 我们得到如下定理 本章中我们记状态集及其取值分别为x x x 一 x m 一 如 i 记观测集及其取值分别为k k 一 y y 1 y 2 i y 肘 定理3 1 1 一个2 维隐马氏模型a 缸 a v a h a b 则 以 就构成一个单 步齐次平稳马氏链 证明 e x 一 i 以一 1 x 1 五 e x l 一一 x 2