1、第十章 隐马尔科夫模型 AndreyAndrey MarkovMarkov 中文名 马尔科夫 国 籍 俄国 出生地 梁赞 出生日期 1856年6月14日 逝世日期 1922年7月20日 主要成就 开创了随机过程这个新领域 HMM应用 人脸识别 语音识别 入侵检测 例： 隐马尔可夫模型是关于时序的概率模型; 描述由一个隐藏的马尔可夫链随机生成不可观测的 状态随机序列(state sequence)，再由各个状态生成一 个观测而产生观测随机序列(observation sequence ) 的过程,序列的每一个位置又可以看作是一个时刻。 隐马尔科夫模型的定义 组成 初始概率分布 状态转移概率分布
2、观测概率分布 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= 红，红，白，白
3、，红 例：盒子和球模型 状态集合：Q=盒子1，盒子2，盒子3，盒子4， N=4 观测集合：V=红球，白球 M=2 初始化概率分布： 状态转移矩阵： 观测矩阵： 例：盒子和球模型 观测序列的生成过程 1、概率计算问题 给定： 计算： 2、学习问题 已知： 估计： ，使 最大 3、预测问题（解码） 已知： 求：使 最大的状态序列 隐马尔科夫模型的三个基本问题 直接计算法 给定模型： 和观测概率： 计算： 最直接的方法： 列举所有可能的长度为T状态序列 ， 求各个状态序列I与观测序列 的联合概率 然后对所有可能的状态序列求和，得到 概率计算方法 直接计算法 状态序列 概率： 对固定的状态序列I，观测
4、序列O的概率： O和I同时出现的联合概率为： 对所有可能的状态序列I求和，得到观测O的概率： 复杂度 概率计算方法 前向概率定义：给定隐马尔科夫模型，定义到时刻t部 分观测序列为： ，且状态为qi的概率为前向概 率，记作： 初值： 递推： 终止： 前向算法 因为： 所以： 递推： 复杂度 前向算法 减少计算量的原因在于每一次计算，直接引用前一 个时刻的计算结果，避免重复计算。 复杂度 前向算法 例： 例： 例： 定义10.3 后向概率：给定隐马尔科夫模型，定 义在时刻t状态为qi的条件下，从t+1到T的部分 观测序列为： 的概率为后向概率， 记作： 后向算法 后向算法 前向后向统一写为：（ t
5、=1 和t=T-1分别对应） 后向算法 一些概率和期望值的计算 一些概率和期望值的计算 一些概率和期望值的计算 监督学习方法： 假设训练数据是包括观测序列O和对应的状态序列I 可以利用极大似然估计法来估计隐马尔可夫模型参数。 非监督学习方法： 假设训练数据只有S个长度为T的观测序O1,O2,Os, 采用Baum-Welch算法 学习算法 监督学习方法 已知： 1、转移概率aij的估计： 设样本中时刻t处于状态i，时刻t+1转移到状态j的频数为Aij，那么 状态转移概率aij的估计是： 监督学习方法 已知： 2、观测概率bj(k)的估计：设样本中状态为j并观测 为k的频数是Bj(k)，那么状态为
6、j观测为k的概率 3、初始状态概率 的估计 为S个样本中初始状 态为qi的频率。 往往人工标注数据很贵 假定训练数据只包括O1,O2,Os, 求模型参数=（A,B,) 实质上是有隐变量的概率模型：EM算法 1、确定完全数据的对数似然函数 完全数据 完全数据的对数似然函数 Baum-Welch算法 2、EM的E步 则： 对序列总长度T进行 Baum Welch算法 3、EM算法的M 步，极大化 求模型参数A,B, 第一项： 由约束条件： 利用拉格朗日乘子： 求偏导数，并结果为0 得： Baum Welch算法 3、EM算法的M 步，极大化 求A,B, 第二项可写成： 由约束条件 ，拉格朗日乘子法
7、： 得： 学习算法 Baum Welch算法 3、EM算法的M 步，极大化 求A,B, 第三项： 由约束条件： Baum Welch算法 将已上得到的概率分别用 表示： 学习算法 Baum Welch算法 学习算法 Baum Welch算法 近似算法 想法：在每个时刻t选择在该时刻最有可能出现的状态 ，从而得到 一个状态序列 ，将它作为预测的结果，在时刻t处于状态qi 的概率： 在每一时刻t最有可能的状态是： 从而得到状态序列： 得到的状态有可能实际不发生 预测算法 Viterbi 方法 用动态规划解概率最大路径，一个路径对应一个状态序列。 最优路径具有这样的特性：如果最优路径在时刻t通过结
8、点 ，那么这一路径从结点 到终点 的部分路径，对 于从 到 的所有可能的部分路径来说，必须是最优的。 只需从时刻t=1开始，递推地计算在时刻t状态为i的各条部分 路径的最大概率，直至得到时刻t=T状态为i的各条路径的最 大概率，时刻t=T的最大概率即为最优路径的概率P*，最优 路径的终结点 也同时得到。 之后，为了找出最优路径的各个结点，从终结点开始，由后 向前逐步求得结点 ，得到最优路径 维特比算法 导入两个变量和，定义在时刻t状态为i的所有单个路 径 中概率最大值为： 由定义可得变量的递推公式： 定义在时刻t状态为i的所有单个路径中概率最大的路径 的第t-1个结点为 维特比算法 Viter
9、bi 方法 Viterbi 方法 例 1、初始化：在t=1时，对每一个状态i，i=1,2,3，求状态i观测O1为 红的概率，记为： 代入实际数据： 例 例 2、在t=2时，对每一个状态i，i=1,2,3，求在t=1时状 态为j观测O1为红并在t=2时状态为i观测O2位白的路 径的最大概率，记为 同时，对每个状态i，记录概率最大路径的前一个状 态j 例 3、以P*表示最优路径的概率： 最优路径的终点是： 4、由最优路径的终点 ，逆向找到 于是求得最优路径，即最优状态序列： 例 人脸检测 人脸图像预处理 光线补偿 中值滤波 归一化处理 人脸检测 人脸识别 HMM训练步骤： 对每个人脸建立一个HMM
10、 1、人脸特征向量提取 2、建立公用的HMM模型 3、HMM初始参数确定 4、初始模型参数训练，主要是运用Viterbi算法训 练均匀分割得到参数，求得最佳分割点，然后重 新计算模型初始参数，直到模型收敛为止。 5、 人脸模型训练过程，将(1)中得到的观测向量代 入(4)中得到的模型参数进行训练，使用迭代方法 调整模型参数达到最优。 1、人脸特征向量提取： 基于奇异值分解的特征提取 离散余弦变换 多维尺度分析(MDS ) 人脸等密度线分析匹配方法、 弹性图匹配方法 。 人脸检测 SVD 稳定性：由于奇异值特征向量具有良好的稳定性，所以它对 图像噪音、图像光照条件引起的灰度变化具有不敏感的特性;
11、 转置不变性：A和A转置具有相同的奇异值; 旋转不变性：图像A和旋转后的图像有相同的特征向量; 唯一不变性：对矩阵A换两行或者两列仍然具有相同的特征 向量; 镜像变换不变形： 人脸检测 HMM模型 状态 人脸检测 人脸检测 人脸检测 3、初始参数确定： A矩阵： B矩阵：用混合高斯模型，则是将均匀分割后得到的五个部分中 的每个部分，使用K均值聚类，将每个状态聚成M类，然后分别计 算每一类的均值和方差，将这两个值分别赋给高斯模型。 初始模型 参数训练： 人脸检测 人脸检测 语音识别 语音识别 隐马尔科夫模型在入侵检测中的应用 隐马尔科夫模型在入侵检测中的应用 两种正常系统调用序列数据集。 Sen
12、dmail正常系统调用序列数据集 Sendmail的正常训练数据集是由1571583个系统调用构 成的序列,这些系统调用分属147个不同的进程(在本实 验中只考虑系统调用,不考虑进程)。 Sendmail正常系统调用序列中包含48个唯一系统调用, 这些系统调用的调用号为(按照序列中出现的顺 序):4,2,66, 138, 5,23,45,27,167, 85,59,105, 104, 106, 56, 19, 155, 83, 93, 94, 112, 100, 50, 128, 89, 121, 11, 1, 40,38,18, 78,101,102,88,95,6,108, 32,1, 8
13、,9, 14,17,3,124,41,61。 数据集 lpr的正常系统调用序列数据集 lpr的正常系统调用序列由2398个系统调用构成,分属9 个进程,长度大约是sendmail 正常系统调用序列的六百 五十五分之一。 Lpr正常系统调用序列包含包含37个唯一系统调用,系 统调用号分别为(按照序列中出现的顺序):4, 2, 66, 138, 5, 23, 45, 27, 105, 104, 106, 83, 59, 50, 88, 167, 17, 18, 155,19, 127, 93, 100, 112, 143, 128, 85, 89, 121, 3, 56, 7, 119, 32, 9, 8, 94。 数据集 END Q&R
