隐马尔科夫模型(原理图解)ppt课件

山东大学高性能计算与大数据处理学科组HighPerformanceComputingandBigDataProcessingGroup 张庆科 隐马尔可夫模型原理图解 HiddenMarkovModels 提纲 HiddenMarkovModel 隐马尔科夫模型的三个问题 总结 1 3 2 HiddenMarkovModel 1马尔可夫模型 马尔可夫模型是数学中具有马尔可夫性质的离散时间随机过程 是用于描述随机过程统计特征的概率模型 t 1 t 2 t 3 t T 1 t T S1 S2 S3 SN S1 S2 S3 SN S1 S2 S3 SN S1 S2 S3 SN S1 S2 S3 SN 系统状态数目 N个 状态序列 观测序列 2 一阶马尔可夫模型概念 t 1 t 2 t 3 t 4 t 5 S1 S2 S3 S1 S2 S3 系统状态数目 N 3 一阶马尔可夫模型 MarkovModels S1 S2 S3 S1 S2 S3 S1 S2 S3 S1 S2 S3 a11 a12 a13 a22 a21 a23 a31 a33 a32 a11 a12 a22 a21 a23 a33 a32 a11 a12 a22 a21 a23 a33 a32 a11 a12 a22 a21 a23 a33 a32 下时期状态只取决于当前时期状态和转移概率 从某时刻状态到下时刻的状态按一定概率转移 t 1时刻 t时刻 qt 1 qt q1 q2 q3 t 1时刻 t时刻 晴 阴 雨 T 1 T 2 T 3 3 隐马尔可夫模型 t 1 t 2 t 3 t T 1 t T S1 S2 S3 SN S1 S2 S3 SN S1 S2 S3 SN S1 S2 S3 SN S1 S2 S3 SN S1 S2 S3 SN 隐藏状态 t 1 t 2 t 3 t T 1 t T 观测状态 隐藏状态序列 观察状态序列 HMM 状态序列 观测序列 一般随机过程 马儿科夫过程 t 1 t 2 t 3 t 4 t 5 S1 S2 S3 一阶隐马尔可夫模型 HiddenMarkovModels 图解 S1 S2 S3 S1 S2 S3 S1 S2 S3 S1 S2 S3 a11 a12 a13 a22 a21 a23 a31 a33 a32 a11 a12 a22 a21 a23 a33 a32 a11 a12 a22 a21 a23 a33 a32 a11 a12 a22 a21 a23 a33 a32 下时期状态只取决于当前时期状态和转移概率 从某时刻状态到下时刻的状态按一定概率转移 t 1时刻 t时刻 qt 1 qt 4 隐马尔可夫模型 HiddenMarkovModels HMM I 隐藏状态 转移概率 生成概率 b2 Q3 b3 Q4 b1 Q1 b1 Q1 b2 Q2 II 观察序列 q1 q2 q3 t 1时刻 t时刻 T 1 T 2 T 3 t 1 t 2 t 3 t T 1 t T S1 S2 S3 S1 S2 SN S1 S2 SN S1 S2 SN S1 S2 SN OT 1 5 隐马尔可夫模型 HiddenMarkovModels HMM HMM模型五元组表示 N M A B 用来描述HMM 或简写为 A B 一阶隐马尔可夫模型 HiddenMarkovModels 数学定义 OT N M 提纲 HiddenMarkovModel 隐马尔科夫模型的三个问题 总结 1 3 2 t 1 t 2 t 3 t T 1 t T S1 S2 S3 S1 S2 SN S1 S2 SN z S1 S2 SN S1 S2 SN a11 a12 a13 a22 a21 a23 aN1 aNN aN2 a11 a12 a22 a21 a23 a33 a32 a11 a12 a22 a21 a23 a33 a32 问题1 给定观察序列O O1 O2 OT 以及模型 A B 计算P O a01 a02 a0N 初始概率向量 1 隐马尔可夫模型 全概率计算 S2 问题本质 计算产生观测序列O的所有可能的状态序列对应的概率之和 共NT个可能路径 指数级计算 N 5 T 100 计算量10 72 t 1 t 2 t 3 B E t 4 a01 a02 a03 a04 a05 aT1 aT2 aT3 aT4 aT5 前向算法 后向算法 问题1 给定观察序列O O1 O2 OT 以及模型 A B 如何计算P O Sk Sk S1 SN S1 SN Sk S1 SN 0 t 1 t T 0 Sk S1 SN 1 初始化阶段 t 1 中间递归阶段 t 2 T 结束阶段 2 概率计算问题 前向算法 ForwardAlgorithm 前进 前进 N 5 T 100 计算量3000 Sk S1 SN Sk S1 SN 0 t T 0 Sk S1 SN 1 问题1 给定观察序列O O1 O2 OT 以及模型 A B 如何计算P O 3 概率计算问题 后向算法 ForwardAlgorithm Sk S1 SN t 1 后退 后退 初始化阶段 t T 中间递归阶段 t T 1 2 1 结束阶段 提纲 HiddenMarkovModel 隐马尔科夫模型的三个问题 总结 1 3 2 1 隐马尔可夫模型 路径预测 t 1 t 2 t 3 t T 1 t T S1 S2 SN S1 S2 SN S1 S2 SN z S1 S2 SN S1 S2 SN aN1 a01 a02 a0N 初始概率向量 S2 问题本质 计算产生观测序列O的最可能的一条隐藏状态序列Q 已知观察序列 解决方法 Viterbi算法 viterbi算法 t 1 t 2 t 3 B E t 4 a01 a02 a03 a04 a05 a1 0 a2 0 a3 0 a4 0 a5 0 2 隐马尔可夫状态路径预测 Viterbi算法 t 1 t 2 t 3 S1 S2 S1 S2 S1 S2 B E S4 S4 S4 S5 S5 S5 S3 S3 S3 t 4 S1 S2 S4 S5 S3 a01 a02 a03 a04 a05 a1 0 a2 0 a3 0 a4 0 a5 0 O1 O2 O3 O4 动画演示 由Viterbi算法计算产生观测序列O的最可能的一条隐藏状态序列Q Sk Sk S1 SN S1 SN Sk S1 SN 0 t 1时刻 t时刻 T时刻 0 Sk S1 SN 1时刻 初始化阶段 t 1 中间递归阶段 t 2 T 结束阶段 路径回溯 向量 3 预测隐马尔可夫状态路径 Viterbi算法 路径回溯 提纲 HiddenMarkovModel 隐马尔科夫模型的三个问题 总结 1 3 2 1 隐马尔可夫模型 参数训练问题 问题3 给定观察值序列O 如何调整模型参数 A B 使得P O 最大 t 1 t 2 t 3 t T 1 t T S1 S2 SN S1 S2 SN S1 S2 SN z S1 S2 SN S1 S2 SN aN1 a01 a02 a0N 初始概率向量 S2 问题本质 参数 A B 的估值问题 已知观察序列O 情形1 路径已知时的参数估计 监督学习方法 情形2 路径未知时的参数估计 非监督学习方法 问题3 给定观察值序列O 如何调整模型参数 A B 使得P O 最大 2 隐马尔可夫模型 参数训练问题 即 由最大似然估计法对HMM的参数进行估计 S2 S3 S1 S5 S2 S2 S3 S1 S5 Baum Welch算法 EM算法特例 对HMM参数估计 转移概率 生成概率 3 参数训练算法 Baum Welch算法基础 将乘积因子按定义展开 前向算法 后向算法 将分子中的 按其递归计算公式展开 前后向算法关系图 4 参数训练算法 Baum Welch算法 单观测序列 但在实际应用中 训练一个HMM用到的观测值序列往往不止一个 那么 对于多个观测值序列训练时 要对BW算法的重估公式进行修正 A转移概率矩阵 B生成概率矩阵 初始概率矩阵 A转移概率矩阵 B生成概率矩阵 0 初始概率矩阵 5 参数训练算法 Baum Welch算法 多观测序列 这种多观测序列正好适用于蛋白质家族序列中相关问题的解决 如多序列比对 情形1 路径已知时的参数估计 监督学