第十章 隐马尔科夫模型.pdf

袁春 清华大学深圳研究生院 李航 华为诺亚方舟实验室 目录 1. 隐马尔科夫模型的基本概念 2. 概率计算算法 3. 学习算法 4. 预测算法 一、隐马尔科夫模型的基本概念 隐马尔科夫模型的定义 观测序列的生成过程 应马尔科夫模型的3个基本问题 隐马尔科夫模型的定义 隐马尔可夫模型是关于时序的概率模型; 描述由一个隐藏的马尔可夫链随机生成不可观测的状态 随机序列(state sequence)，再由各个状态生成一个观测 而产生观测随机序列(observation sequence )的过程,序 列的每一个位置又可以看作是一个时刻。 隐马尔科夫模型 组成 初始概率分布 状态转移概率分布 观测概率分布 Q：所有可能状态的集合 V ：所有可能观测的集合 I: 长度为T 的状态序列 O：对应的观测序列 隐马尔科夫模型 组成 A ：状态转移概率矩阵 隐马尔科夫模型 组成 B：观测概率矩阵  ：初始状态概率向量 隐马尔科夫模型 三要素 两个基本假设 齐次马尔科夫性假设，隐马尔可分链t 的状态只和t-1状态 有关： 观测独立性假设，观测只和当前时刻状态有关； 例 ：盒子和球模型 盒子： 1 2 3 4 红球： 5 3 6 8 白球： 5 7 4 2 转移规则： 盒子1 下一个 盒子2 盒子2或3 下一个 0.4 左，0.6右 盒子4 下一个 0.5 自身，0.5盒子3 重复5次： O={ 红，红，白，白，红} 例 ：盒子和球模型 状态集合：Q={盒子1 ，盒子2 ，盒子3 ，盒子4}， N=4 观测集合：V={红球，白球} M=2 初始化概率分布： 状态转移矩阵： 观测矩阵： 观测序列的生成过程 隐马尔科夫模型的三个基本问题 1 、概率计算问题  给定：  计算： 2、学习问题  已知：  估计： ，使 最大 3 、预测问题 （解码）  已知：  求：使 最大的状态序列 概率计算方法 直接计算法 给定模型： 和观测概率： 计算： 最直接的方法： 列举所有可能的长度为T状态序列 ， 求各个状态序列I与观测序列 的联合概率 然后对所有可能的状态序列求和，得到 二、概率计算算法 直接计算法 前向算法 后向算法 一些概率与期望值的计算 概率计算方法 直接计算法 状态序列 概率： 对固定的状态序列I，观测序列O的概率： O和I 同时出现的联合概率为： 对所有可能的状态序列I求和，得到观测O的概率： 复杂度 前向算法 前向概率定义：给定隐马尔科夫模型λ ，定义到时刻t部分 观测序列为： ，且状态为qi 的概率为前向概率， 记作： 初值： 递推： 终止： 前向算法 因为： 所以： 递推： 复杂度 前向算法 减少计算量的原因在于每一次计算，直接