隐马尔科夫模型PPT.ppt
《隐马尔科夫模型PPT.ppt》由会员分享,可在线阅读,更多相关《隐马尔科夫模型PPT.ppt(40页珍藏版)》请在三一文库上搜索。
1、隐马尔科夫模型(HMM),Table of Contents,马尔科夫模型 隐马尔科夫模型 HMM基本问题 3.1 HMM评估问题 3.2 HMM解码问题 3.3 HMM学习问题 HMM应用背景 4.1 自动文本分类 4.2 汉语词性标注 4.3 汉语自动分词 4.4 文本信息抽取 4.5 其他应用领域,1.马尔科夫模型,马尔科夫(Markov)模型是由俄罗斯数学家Andrei AMarkov于20世纪初提出的一个统计模型。,有限状态的离散时间Markov链是一个长度为T的随机变量序列 , 的取值范围是有限状态集 。,假定它满足以下两个条件:(1)任一时刻的随机变量只依赖于前一时刻的随机变量:
2、,(2)时间无关性(马尔科夫性):,则显然有:,以上随机过程可以称为可观测Markov模型,因为此过程的输出在每一个时间点是一个状态,并且每一个状态对应一个可观测事件。,上述模型称为一阶Markov模型。,如把条件(1)适当放松,任一时刻的随机变量只依赖于前两(三,k)个时刻的随机变量,则此模型为两(三,k)阶Markov模型。,Markov模型,2.隐马尔科夫模型,一个HMM是不确定的、随机的有限状态自动机,由不可观测的状态转移过程(一个Markov链)和可观测的观察生成过程组成。按观测值是离散还是连续的,HMM可分为离散型和连续型。我们这里主要介绍离散HMM。,一阶离散HMM是一个五元组:
3、 ,可以简写为 ,其中N是Markov链状态数;M是状态可能生成的观察值数; 表示初始状态概率向量,其中,A为状态转换概率分布矩阵,表示i状态向j状态转换的概率: ,其中:,B为观察值概率分布矩阵,表示在j状态输出观察值k的概率: ,其中:,隐马尔可夫模型(HMM)是一种在Markov链的基础上发展起来的统计信号模型,能够利用收集的训练样本进行自适应学习。,隐马尔科夫模型,HMM拓扑结构,左右型的HMM,全连通的HMM,含并行结构的HMM,含间隔跳转的HMM,3.HHM基本问题,HMM理论有3个基本问题:,(2)解码问题 给定一个HHM的模型 和观测序列 ,如何选择对应最佳的状态序列,使它在某
4、种状态下最优(出现的概率最大),以较好地解释观测值,(1)评估问题 给定一个HHM的模型 和观测序列 ,如何高效的计算此模型产生的观测序列的概率,(3)学习问题(训练问题) 给定观测序列 ,如何调整模型参数 ,以使得观察序列出现的概率 最大化,3.1评估问题,解决HHM评估问题的典型算法有穷举搜索直接计算法、前向算法和后向算法:,一、穷举搜索直接计算,1、算法思想 列举长度为T的所有可能的状态序列 ,分别求解各个状态序列与观测序列的联合概率 ,最后求和得到,2、算法过程,(1)状态序列 出现的概率为:,(2)对于其中一种状态序列,观测序列的概率为: 依据贝叶斯公式:,(3)求和:,3、算法评价
5、,由于每一时刻点所到达的状态有N种可能,所以总的不同的状态序列有 种。其中每一个状态序列需要2T-1次乘法运算。所以总的运算量为 次乘法运算(此外还需要 次加法运算)。,穷举算法的时间复杂度为 ,在求解 的过程中存在大量的重复计算,不适用于大的模型和较长的序列。,二、前向算法,1、算法思想,到达某网格节点的概率可以用前一时刻N个节点的概率表示出来。 前向算法通过已经保存了的子路径来计算新路径的概率。,HHM网状结构,(3)终止,在时刻T所有隐状态(对应观测值 )的概率求和:,(2)递归,计算t+1时刻处于各隐状态(对应观测值为 )的概率:,2、算法过程,定义到时刻t,部分观测序列为 ,状态 的
6、前向概率为:,(1)初始化,计算t=1时处于各隐状态(对应观测值为 )的概率:,t时刻前向概率的递归关系,3、算法评价,由以上算法过程可知,计算 总共需要 次乘法运算和 次加法运算。,前向算法的复杂度为 ,相比于穷举法计算,复杂度降低了几个数量级,减少了重复计算。,2后向算法,(1)初始化,最终时刻的所有状态的概率规定为:,定义从时刻t+1到时刻T,部分观测序列为 ,状态 的后向概率为:,1、算法思想 和前向算法基本一致,唯一的区别是选择的局部状态不同。,2、算法过程,(2)递归,计算t时刻处于各隐状态(对应观测值为 )的概率:,(3)终止:,3、算法评价,t时刻后向概率的递归关系,由以上算法
7、过程可知,计算 总共需要 次 乘法运算和 次加法运算。,后向算法的复杂度与前向算法相等,都是 。,3.2解码问题,1、算法思想,解答解码问题,即寻求对于给定观测序列的最优状态序列。有好几种标准可用于定义最优状态序列。比如,其中一个可能的优化标准是分别选择每个时刻各自最可能的状态。 但是每个时刻最可能的状态的叠加不一定能得到最可能的状态序列。可能这种得到的最优序列根本是“不合法”的。这种算法仅简单地考虑了每一个时刻点各自最可能的状态,而没有考虑到状态序列发生的概率。,定义优化标准为:寻求单一最佳状态序列,以最大化 ,运用贝叶斯原理,也即最大化,对于上述问题的一个可行的解决方案就是修改优化标准。于
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 隐马尔科夫 模型 PPT
链接地址:https://www.31doc.com/p-9180063.html