(15.1.1)--第15讲_隐马尔可夫模型.pdf
大数据机器学习第十五讲：隐马尔科夫模型和概率图模型目录1.隐马尔科夫模型的基本概念2.概率计算算法3.学习算法4.预测算法一、隐马尔科夫模型的基本概念 隐马尔科夫模型的定义 观测序列的生成过程 应马尔科夫模型的3个基本问题Andrey Markov 中文名 马尔科夫 国籍 俄国 出生地 梁赞 出生日期 1856年6月14日 逝世日期 1922年7月20日 主要成就 开创了随机过程这个新领域HMM应用 人脸识别 语音识别 入侵检测例：例：隐马尔可夫模型是关于时序的概率模型;描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列(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 初始化概率分布：状态转移矩阵：观测矩阵：例：盒子和球模型观测序列的生成过程 算法10.1(观测序列的生成）输入：隐马尔科夫模型=(A,B,),观测序列长度T；输出：观测序列O=(o1,o2,oT)1 按照初始状态分布产生状态i1 2 令t=1 3 按照状态it的观测概率分布bit(k)生成ot 4 按照状态it的状态转移概率分布产生状态 5 令t=t+1，如果tT,转 步骤3，否则，终止 1、概率计算问题给定：计算：2、学习问题已知：估计：，使最大 3、预测问题（解码）已知：求：使最大的状态序列隐马尔科夫模型的三个基本问题二、概率计算算法 直接计算法 前向算法 后向算法 一些概率与期望值的计算 直接计算法 给定模型：和观测序列：计算：最直接的方法(按概率公式直接计算)：列举所有可能的长度为T状态序列，求各个状态序列I与观测序列的联合概率 然后对所有可能的状态序列求和，得到概率计算方法 直接计算法 状态序列概率：对固定的状态序列I，观测序列O的概率：O和I同时出现的联合概率为：对所有可能的状态序列I求和，得到观测O的概率：概率计算方法复杂度 前向概率定义：给定隐马尔科夫模型，定义到时刻t部分观测序列为：，且状态为qi的概率为前向概率，记作：初值：递推：终止：前向算法 因为：所以：递推：前向算法复杂度 减少计算量的原因在于每一次计算，直接引用前一个时刻的计算结果，避免重复计算。前向算法复杂度例：例：例：定义：后向概率：给定隐马尔科夫模型，定义在时刻t状态为qi的条件下，从t+1到T的部分观测序列为：的概率为后向概率，记作：后向算法后向算法 前向后向统一写为：（t=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)，那么状态为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,得：对I 求和得到 代入原式：Baum Welch算法 3、EM算法的M 步，极大化求A,B,第二项可写成：由约束条件，拉格朗日乘子法：得：Baum Welch算法 3、EM算法的M 步，极大化求A,B,第三项：由约束条件：Baum Welch算法 将以上得到的概率分别用表示：学习算法 Baum Welch算法学习算法 Baum Welch算法四、预测算法 近似算法 维特比算法 想法：在每个时刻t选择在该时刻最有可能出现的状态，从而得到一个状态序列，将它作为预测的结果，在时刻t处于状态qi的概率：在每一时刻t最有可能的状态是：从而得到状态序列：得到的状态有可能实际不发生近似算法 Viterbi 方法 用动态规划解概率最大路径，一个路径对应一个状态序列。最优路径具有这样的特性：如果最优路径在时刻t通过结点，那么这一路径从结点到终点的部分路径，对于从到的所有可能的部分路径来说，必须是最优的。只需从时刻t=1开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，直至得到时刻t=T状态为i的各条路径的最大概率，时刻t=T的最大概率即为最优路径的概率P*，最优路径的终结点也同时得到。之后，为了找出最优路径的各个结点，从终结点开始，由后向前逐步求得结点，得到最优路径维特比算法 导入两个变量和，定义在时刻t状态为i的所有单个路径中概率最大值为：由定义可得变量的递推公式：定义在时刻t状态为i的所有单个路径中概率最大的路径的第t-1个结点为维特比算法维特比算法维特比算法例 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 1、人脸特征向量提取 2、建立公用的HMM模型 3、HMM初始参数确定 4、初始模型参数训练，主要是运用Viterbi算法训练均匀分割得到参数，求得最佳分割点，然后重新计算模型初始参数，直到模型收敛为止。5、人脸模型训练过程，将(1)中得到的观测向量代入(4)中得到的模型参数进行训练，使用迭代方法调整模型参数达到最优。人脸识别 HMM模型状态人脸识别人脸识别 3、初始参数确定：A矩阵：B矩阵：用混合高斯模型，则是将均匀分割后得到的五个部分中的每个部分，使用K均值聚类，将每个状态聚成M类，然后分别计算每一类的均值和方差，将这两个值分别赋给高斯模型。人脸检测 初始模型 参数训练：语音识别语音识别ENDQ&R
