隐马尔可夫模型课件

Ch04.参数模型Ch04.参数模型Part1隐马尔可夫模型Part1隐马尔可夫模型马尔可夫链状态t时刻的状态长度为T的离散时间上的状态序列例如：转移概率（矩阵）

为从状态到的转移概率马尔可夫链状态马尔可夫链状态转移图

马尔可夫链状态转移图马尔可夫链j-阶马尔可夫过程下一时刻为某个状态的概率仅与最近的j个状态有关一阶马尔可夫过程任一时刻为某状态的概率仅与上一时刻的状态相关仅与最近的j个状态有关仅与上一个状态有关马尔可夫链j-阶马尔可夫过程仅与最近的j个状态有关仅与上一个隐马尔可夫模型隐马尔可夫模型（HiddenMarkovModel，缩写为HMM）状态不可见在t时刻，隐藏的状态以一定的概率激发出可见的符号，其取值表示为长度为T的离散时间上的可见符号序列例如：观察到可见符号的概率隐马尔可夫模型隐马尔可夫模型（HiddenMarkovM隐马尔可夫模型状态转移图隐马尔可夫模型状态转移图一个例子盒子编号不可见每次从任一盒子中取出一个小球隐藏状态：盒子编号可见符号：小球盒子i中取出各种小球的概率得到某个特定小球序列的概率？一个例子离散HMM的符号表示隐藏状态集可见符号集状态序列观察序列状态转移概率观察到可见符号的概率初始状态概率完整的HMM参数向量离散HMM的符号表示隐藏状态集完整的HMM参数向量HMM三大核心问题估值问题已知观察到特定符号序列XHMM模型参数向量求似然函数解码问题已知观察到特定符号序列XHMM模型参数向量求最有可能产生X的隐状态序列HMM三大核心问题估值问题HMM三大核心问题学习（或参数估计）问题已知观察到特定符号序列X求模型参数向量的估计值例如：ML估计HMM三大核心问题学习（或参数估计）问题估值问题直接计算HMM模型产生可见长度为T的符号序列X的概率其中，表示状态的初始概率假设HMM中有c个隐状态，则计算复杂度为！例如：c=10，T=20，基本运算1021次！估值问题直接计算HMM模型产生可见长度为T的符号序列X的概率估值问题解决方案递归计算t时刻的计算仅涉及上一步的结果，以及，，和HMM向前算法HMM向后算法估值问题解决方案估值问题HMM向前算法定义：t时刻在状态i，并且已观察到x(1)，x(2)，……x(t)的概率初始化对每一个隐状态i，计算递归fort=2toT对每一个隐状态j，计算end最后

计算复杂度估值问题HMM向前算法计算复杂度估值问题HMM向前算法估值问题HMM向前算法估值问题HMM向后算法（向前算法的时间反演版本）定义：t时刻在状态i，并且已逆向观察到x(T)，x(T-1)，……x(t)的概率初始化对每一个隐状态i，计算（假设T时刻每个状态的概率相同）递归fort=T-1to1对每一个隐状态i，计算end最后

计算复杂度估值问题HMM向后算法（向前算法的时间反演版本）计算复杂度例子HMM为：吸收状态，即序列结束时的必然状态。该状态产生唯一的特殊可见符号v0，表示HMM过程结束例子HMM为例子已知t=0时状态为，即现观测到的序列为计算HMM产生这个特定观测序列的概率？例子已知t=0时状态为，即例子解例子解HMM用于分类为每一个类别建立一个HMM每个HMM有自己的参数向量，该参数向量可以从属于类别i的样本中学习（估计）得到。贝叶斯决策决策结果HMM用于分类为每一个类别建立一个HMMHMM用于语音识别“从左到右”（left-to-right）HMM为每个单词发音建立一个HMM，其参数为用向前算法计算发音序列X的类条件概率取决于语言本身和上下文语义用贝叶斯公式计算X的后验概率最大后验概率指示语音内容发音“viterbi”的“从左到右”HMMHMM用于语音识别“从左到右”（left-to-right）解码问题已知一个观察序列XT，寻找最可能的隐状态序列穷举法把所有可能的隐状态序列的概率都计算一遍计算复杂度解码问题已知一个观察序列XT，寻找最可能的隐状态序列解码问题Viterbi算法初始化对每个隐状态i，计算递归fort=2toT:对每一个隐状态j，计算end最后fort=T-1to1（路径回溯）:end计算复杂度解码问题Viterbi算法计算复杂度例子HMM为例子HMM为例子已知t=0时状态为，即现观测到的序列为计算最可能的隐状态序列？例子已知t=0时状态为，即例子解.0027练习：把此图填写完整，并回溯最佳状态路径例子解.0027练习：把此图填写完整，并回溯最佳状态路径解码问题对于较长的序列，Viterbi算法可能导致计算机下溢出改进：基于对数的Viterbi算法优点变乘为加避免下溢出结果与Viterbi算法一样解码问题对于较长的序列，Viterbi算法可能导致计算机下溢解码问题对数Viterbi算法初始化对每个隐状态i，计算递归fort=2toT:对每一个隐状态j，计算end最后fort=T-1to1（路径回溯）:end解码问题对数Viterbi算法学习问题从一组训练样本D={X1,X2,…,Xn}中，学习HMM的参数向量不存在根据训练集确定HMM最优参数的算法常用算法向前向后算法（forward-backwardalgorithm）又称Baum-Welch重估计算法（Baum-Welchre-estimationalgorithm）核心思想通过递归方式更新HMM中的参数，以得到能够最好解释训练样本的HMM参数学习问题从一组训练样本D={X1,X2,…,Xn}中，学习问题Baum-Welch重估计公式已知X和的情况下，t时刻为状态i，t+1时刻为状态j的后验概率向前向后学习问题Baum-Welch重估计公式向前向后学习问题向前向后算法初始化repeat基于和X，利用Baum-Welch重估计公式计算

until

收敛返回参数估计结果学习问题向前向后算法Part2贝叶斯置信网Part2贝叶斯置信网特征相关性某些情况下，关于分布的先验知识并非直接是概率分布的形式，而是有关各个特征分量之间的统计相关性（或独立性）关系x1和x3统计独立，而其他特征对不独立特征相关性某些情况下，关于分布的先验知识并非直接是概率分布的相关性例子汽车的状态发动机温度油温油压轮胎内气压相关性油压与轮胎内气压相互独立油温与发动机温度相关相关性例子汽车的状态贝叶斯置信网用图的形式来表示特征之间的因果依赖性贝叶斯置信网（Bayesianbeliefnet）因果网（causalnetwork）置信网（beliefnet）有向无环图节点间的连线具有方向性图中无循环路径仅讨论离散情况贝叶斯置信网用图的形式来表示特征之间的因果依赖性贝叶斯置信网每个节点A,B,C,…代表一个系统变量（特征）每个节点可能的离散取值A的值：a1,a2,a3,…例如A表示灯的状态a1=开，a2=关，P(a1)=0.7，P(a2)=0.3节点之间的有向连接表示变量之间的依赖关系从A到C的连接表示，或任意节点的状态可通过与其相连的节点的状态推断贝叶斯置信网每个节点A,B,C,…代表一个系统变量（特征联合概率线性链联合概率线性链联合概率简单回路联合概率简单回路任意节点取特定值的概率线性链任意节点取特定值的概率线性链任意节点取特定值的概率简单回路任意节点取特定值的概率简单回路例子1鱼分类置信网0.60.20.20.20.30.5例子1鱼分类置信网0.60.20.20.20.30.5例子1求“一条夏天在北大西洋捕获的鱼为光泽暗淡宽度窄的鲈鱼”的概率0.60.20.20.20.30.5例子1求“一条夏天在北大西洋捕获的鱼为光泽暗淡宽度窄的鲈鱼”例子1求“一条夏天在北大西洋捕获的鱼为光泽暗淡宽度窄的鲈鱼”的概率夏天：北大西洋：光泽暗淡：宽度窄：鲈鱼：例子1求“一条夏天在北大西洋捕获的鱼为光泽暗淡宽度窄的鲈鱼”例子1冬天在南大西洋捕获到鲑鱼的概率在南大西洋捕获光亮度高的鲈鱼的概率夏天在北大西洋捕获一条宽的并且光亮度高的鱼的概率0.60.20.20.20.30.5例子1冬天在南大西洋捕获到鲑鱼的概率0.60.20.20.2给定除目标变量X之外的变量的取值情况，确定其它变量的概率证据

，其中表示变量i的取值情况例如，鱼分类置信网已有证据：已知冬季：渔民更喜欢南大西洋：鱼的光泽较亮：由于遮挡，无法测出宽度证据注意的位置！给定除目标变量X之外的变量的取值情况，确定其它变量的概率证据置信度考虑某个节点XX之前的节点集合称为X的父节点P，X之后的节点集合称为X的子节点C例子：X的父节点：{A，B}X的子节点：{C，D}估计X的概率时，需区别对待X的父节点和子节点证据e：除X以外各节点的变量取值情况在给定e的情况下，命题x=(x1,x2,…)的置信度（belief）必须进行归一化，使得x所有取值的概率之和为1置信度考虑某个节点X估计X的概率时，需区别对待X的父节点和子置信度对X的子节点假设子节点之间无连接例如：置信度对X的子节点例如：置信度对X的父节点假设父节点之间无连接表示父节点处于状态n时的取值忽略除了X的父节点和子节点之外的节点相互依赖性，简化上式置信度对X的父节点表示父节点处置信度命题x的置信度节点X取某个特定值的概率等于两个因子的乘积第一个取决于子节点第二个取决于父节点置信度命题x的置信度证据简单情况直接表示变量i的取值置信度对固定的e，为常数证据简单情况例子1鱼分类置信网0.60.20.20.20.30.5例子1鱼分类置信网0.60.20.20.20.30.5例子1南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？0.60.20.20.20.30.5例子1南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？0.60.例子1南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？a未知b2=南大西洋c1=光亮d未知先求x1=鲑鱼的概率e:例子1南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？先求x1=例子1南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？a未知b2=南大西洋c1=光亮d未知归一化（使得）因，所以判断为鲑鱼再求x2=鲈鱼的概率例子1南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？再求x2=例子2你在家里安装了一套防盗系统该系统对入室盗窃检测很敏感，但有时地震也能触发报警你有两个邻居：Ali和Veli。当你不在家的时候，他们如果听到报警声，会给你打电话Ali听到报警声就会给你打电话，但是有时他会把电话铃声认为是报警声而给你打电话Veli经常在家听音乐，所以有时听不见报警声根据哪个邻居打了电话给你，你是否能够估计家里真的被入室盗窃的概率？例子2你在家里安装了一套防盗系统例子2建模例子2建模例子2系统报警，但是既没有盗窃也没有地震发生，并且Ali和Veli都打电话给你例子2系统报警，但是既没有盗窃也没有地震发生，并且Ali和V例子2计算如下事件的概率系统报警，但是既没有盗窃也没有地震发生，并且Ali和Veli都打电话给你例子2计算如下事件的概率例子2如果Ali打电话给你，计算发生盗窃的置信度例子2如果Ali打电话给你，计算发生盗窃的置信度例子2如果Ali打电话给你，计算发生盗窃的置信度方法一归一化例子2如果Ali打电话给你，计算发生盗窃的置信度例子2如果Ali打电话给你，计算发生盗窃的置信度方法二例子2如果Ali打电话给你，计算发生盗窃的置信度例子2如果Ali和Veli都打电话给你，计算发生盗窃的置信度例子2如果Ali和Veli都打电话给你，计算发生盗窃的置信度例子2如果Ali和Veli都打电话给你，计算发生盗窃的置信度例子2如果Ali和Veli都打电话给你，计算发生盗窃的置信度例子3草地变湿可能有两个原因：洒水装置打开过，或者下过雨如果阴天，则下雨的可能比晴天大如果阴天，打开洒水装置的可能较小假设阴天和晴天等概率例子3草地变湿可能有两个原因：洒水装置打开过，或者下过雨例子3建模例子3建模例子3如果看到草地是湿的，判断洒水装置和下雨哪个原因更为可能？例子3如果看到草地是湿的，判断洒水装置和下雨哪个原因更为可能例子3如果看到草地是湿的，判断洒水装置和下雨哪个原因更为可能？因为，所以下雨造成草地湿的可能性更大例子3如果看到草地是湿的，判断洒水装置和下雨哪个原因更为可能例子3如果看到草地是湿的，并且当时天气晴朗呢？例子3如果看到草地是湿的，并且当时天气晴朗呢？例子3如果看到草地是湿的，并且当时天气晴朗呢？因为，所以洒水造成草地湿的可能性更大例子3如果看到草地是湿的，并且当时天气晴朗呢？因为朴素贝叶斯规则当特征之间的依赖关系未知的时候，常常假设给定类别条件下各个特征条件独立在此假设下的贝叶斯规则称为“朴素贝叶斯规则”（naïveBayesrule）或者“傻瓜贝叶斯规则”（idiotBayesrule）朴素贝叶斯置信网朴素贝叶斯规则当特征之间的依赖关系未知的时候，常常假设给定类Part3期望最大化（EM）算法Part3期望最大化（EM）算法缺失的特征假设有一个基于特征向量x的贝叶斯分类器，每一个x中的一部分特征xg是可见的，而剩下的特征xb缺失，不同样本中缺失特征可能不同如何做决策？方法一直接扔掉含有缺失值的样本方法二用其他已知该特征的样本均值替换xb，即令缺失的特征假设有一个基于特征向量x的贝叶斯分类器，每一个x中期望最大化方法三通过扩展最大似然法，可以在训练集中有缺失值的情况下，对模型参数进行学习期望最大化（expectation-maximization,EM）算法可根据已有数据递归估计似然函数EM算法的两个主要应用在数据不完整或有缺失值的情况下学习当似然方程难以直接求解时，初始化某些未知参数使问题简化期望最大化方法三期望最大化假设样本x服从某种分布，其中