隐马尔可夫模型技术.ppt

第8章隐马尔可夫模型技术 HMM HiddenMarkovModelHMM的由来马尔可夫性和马尔可夫链HMM实例HMM的三个基本算法 HMM的由来 1870年 俄国有机化学家VladimirV Markovnikov第一次提出马尔科夫模型马尔可夫模型马尔可夫链隐马尔可夫模型 马尔可夫性 如果一个过程的 将来 仅依赖 现在 而不依赖 过去 则此过程具有马尔可夫性 或称此过程为马尔可夫过程 X t 1 f X t 马尔可夫链 时间和状态都离散的马尔可夫过程称为马尔可夫链记作 Xn X n n 0 1 2 在时间集T1 0 1 2 上对离散状态的过程相继观察的结果链的状态空间记做I a1 a2 ai R 条件概率Pij m m n P Xm n aj Xm ai 为马氏链在时刻m处于状态ai条件下 在时刻m n转移到状态aj的转移概率 转移概率矩阵 阴天 晴天 下雨 晴天阴天下雨晴天0 500 250 25阴天0 3750 250 375下雨0 250 1250 625 转移概率矩阵 续 由于链在时刻m从任何一个状态ai出发 到另一时刻m n 必然转移到a1 a2 诸状态中的某一个 所以有当Pij m m n 与m无关时 称马尔可夫链为齐次马尔可夫链 通常说的马尔可夫链都是指齐次马尔可夫链 s1 s2 s3 N 3t 0 q0 s3 有N个状态 S1 S2 SN 一阶离散马尔可夫模型 下一个时刻所处的状态是随机出现的 在每个时刻t 系统只能处于唯一一个状态qt 存在一个离散的时间序列t 0 t 1 当前状态 当前状态qt只与前面相邻的一个状态qt 1有关 与其他状态无关 s1 s2 s3 一阶离散马尔可夫模型 1 1 2 1 2 1 3 2 3 s1 s2 s3 一阶离散马尔可夫模型 1 1 2 1 2 1 3 2 3 aij 转移概率并且满足如下的标准随机约束条件 下雨 状态1多云 状态2晴天 状态3 一阶离散马尔可夫模型 问题 连续8天的天气状况为 晴天 晴天 晴天 下雨 下雨 晴天 多云 晴天 的概率是多少 一阶离散马尔可夫模型 晴天 晴天 晴天 下雨 下雨 晴天 多云 晴天 0 8 0 8 0 1 0 4 0 3 0 1 0 2 晴天 晴天 一阶离散马尔可夫链 晴天 下雨 下雨 t t 1 晴天 晴天 晴天 下雨 下雨 晴天 多云 晴天 晴天 多云 晴天 t 1 马尔可夫链 信号统计理论模型起源于60年代后期Baum和他的同事首先提出Baker CMU 和Jelinek IBM 在70年代早期实现在语音处理上的应用 隐马尔可夫链 HMM 理论 HMM实例 最后得到一个描述球的颜色的序列O1 O2 称为观察值序列O 设有N个缸 每个缸中装有很多彩球 球的颜色由一组概率分布描述 实验方式如下 根据初始概率分布 随机选择N个缸中的一个开始实验 根据缸中球颜色的概率分布 随机选择一个球 记球的颜色为O1 并把球放回缸中 根据描述缸的转移的概率分布 随机选择下一口缸 重复以上步骤 HMM实例 约束 在上述实验中 有几个要点需要注意 不能直接观察缸间的转移从缸中所选取的球的颜色和缸并不是一一对应的每次选取哪个缸由一组转移概率决定 什么是HMM 绿圈表示隐含状态 隐仅依赖于前一个状态 齐次给定当前状态 过去与将来无关 马尔可夫紫圈是输出观察序列的状态仅依赖于各自对应的隐状态 HMM模型 N M A B S s1 sN 隐状态的值 共有N种可能值K k1 kM 观察的值 共有M种可能值隐状态初始概率A aij 隐状态转移概率 N NB bjk 观察状态的概率 N M A B A A A B B S S S K K K S K S K HMM的基本要素 用模型五元组来描述HMM 或简写为 HMM组成 HMM是一个双重随机过程 两个组成部分 马尔可夫链 描述状态的转移 用转移概率描述 一般随机过程 描述状态与观察序列间的关系 用观察值概率描述 8 4HMM的三个基本问题 问题1 给定观察序列O O1 O2 OT 以及模型如何计算P O 概率计算 问题2 给定观察序列O O1 O2 OT以及模型 如何找出一个最佳状态序列 HMM识别 问题3 如何调整模型参数 使得P O 最大 估计问题 前后向算法 解码问题 Viterbi算法 训练问题 BaumWelch算法 7 4 2HMM基本算法 定义前向变量 表示模型下 在时刻t 观测事件为Ot 状态为i的概率 s1 s2 sN sj 时刻t t 1 a1j a2j aNj 估计问题 前向算法 估计问题 前向算法 递归求解 初始 递归 终止 2 1 2 2 2 3 2 N 3 1 估计问题 后向算法 定义后向变量 表示从终止时刻T到时刻t 1的观测事件序列是并且时刻t的状态是i的概率 s1 s2 sN si 时刻t t 1 ai1 ai2 aiN 估计问题 后向算法 递归求解 初始 递归 2 解码问题 Viterbi算法 找一个状态序列 这个状态序列在t时状态为i 并且状态i与前面t 1个状态构成的状态序列的概率值最大 s1 s2 sN sj 时刻t t 1 a1j a2j aNj 3 学习问题 Baum Welch算法 模型训练算法 算法步骤 1 初始模型 待训练模型 l0 2 基于l0以及观察值序列O 训练新模型l 3 如果logP X l log P X l0 Delta 说明训练已经达到预期效果 算法结束 4 否则 令l0 l 继续第2步工作 Baum Welch算法 续 参数估计 定义给定模型 和观察序列O 在时刻t处在状态i 时刻t 1处在状态j的概率 t i j 即 t i j P qt i qt 1 j O 使用统计意义上用频率近似概率的方法反复进行上面的过程 逐步改进模型参数 直到收敛 即不再明显增大 此时的就是HMM的最大相似性评估 Baum Welch算法 续 Baum Welch讨论 利用上述三个估算公式 计算得到一组新的模型参数 这组新的模型参数又可以作为一个新的估算过程的开始点 再次进行估算 如此反复进行 直到参数值收敛 Baum等人证明要么估算值 和估算前的参数值 相等 要么估算值 比估算前的参数值 更好的解释了观察序列O 参数最终的收敛点并不一定是一个全局最优值 但一定是一个局部最优值 Baum Welch算法是一类称为EM Estimation Maximisation 估计 最大化 算法的一个例子 这类算法均可保证收敛于一个局部最优值 1 前向后向算法计算P O 2 Baum Welch算法求出最优解 argmax P O 3 Viterbi算法解出最佳状态转移序列 4 根据最佳状态序列对应的 给出候选音节或声韵母5 通过语言模型形成词和句子 经典HMM语音识别一般过程 基于HMM的语音识别方案 判决规则 VITERBI计算 VQ 码本 训练 识别 X X 特征矢量的时间序列O 基于VQ的观察符号序列 HMM 3 HMM 2 HMM 1 O 声学参数分析 预处理 语音信号输入 基于HMM的观察符号序列的生成方式 当给定模型 A B 后 就可将该模型看成一个符号生成器 或称信号源 由它生成观察序列O o1o2 oT 其生成过程 也称HMM过程 是 1 初始状态概率分布 随机选择一个初始状态q1 Si 2 置t 1 3 按状态Si的符号概率分布bi k 随机产生一个输出符号ot Vk 4 按状态Si的状态转移概率分布aij 随机转移至一个新的状态qt 1 Sj 5 令t t 1 若t T 则返回步骤 3 否则结束过程 模型评估问题的解法 1 当给定模型 A B 以及观察序列O o1o2 oT时 计算模型 对观察序列O的P O 概率的思路是 穷举法 1 对长度为T的观察序列O 找出所有可能产生该观察序列O的状态转移序列Qj qj1qj2qj3 qjT j 1 2 J 2 分别计算Qj与观察序列O的联合概率P O Qj 2 取各联合概率P O Qj 的和 即 JP O P O Qj j 1 HMM模型的例子观察符号序列 abba所有可能的路径 1 S1 S1 S1 S2 S3 2 S1 S1 S2 S2 S3 3 S1 S1 S2 S3 S3 4 S1 S2 S2 S2 S3 5 S1 S2 S2 S3 S3 6 S1 S2 S3 S3 S3 模型评估问题的解法 2 P O 的一般解法 P O Qj P Qj P O Qj P Qj P qj1 P qj2 qj1 P qj3 qj2 P qjT 1 qjT aj0 1aj1 2aj2 3 ajT 1 TP O Qj P o1 qj1 P o2 qj2 P oT qjT b1j o1 b2j o2 b3j o3 bTj oT P O Qj aj0 1b1j o1 aj1 2b2j o2 ajT 1 TbTj oT JJTP O P O Qj ajt tbtj ot j 1j 1t 1 HMM模型的例子 模型评估问题的前向算法 采用前向算法求解P abba 概率的格型图 Q q1q2q3q4O abba t 最佳路径问题的解法 0 5x0 2 0 5x0 8 0 2x1 0 0 6x0 5 0 5x0 2 0 5x0 2 0 5x0 2 0 5x0 8 0 5x0 8 0 5x0 8 0 4x0 5 0 4x0 5 0 4x0 5 0 4x0 5 0 4x0 5 0 6x0 5 0 6x0 5 0 8x1 0 0 8x1 0 0 2x1 0 采用Viterbi算法求解产生观察序列abba最佳路径的格型图 Q q1q2q3q4O abba t 最佳路径 S1