1、Ch 04. 参数模型Part 1 隐马尔可夫模型马尔可夫链 状态状态 t时刻的状态 长度为T的离散时间上的状态序列例如： 转移概率转移概率（矩阵） 为从状态 到 的转移概率,1,2,iiij马尔可夫链 状态转移图 马尔可夫链 j-阶马尔可夫过程阶马尔可夫过程 下一时刻为某个状态的概率仅与最近的j个状态有关 一阶马尔可夫过程一阶马尔可夫过程 任一时刻为某状态的概率仅与上一时刻的状态相关仅与最近的j个状态有关仅与上一个状态有关隐马尔可夫模型 隐马尔可夫模型隐马尔可夫模型（Hidden Markov Model，缩写，缩写为为HMM） 状态不可见不可见 在t时刻，隐藏的状态以一定的概率激发出可见的
2、可见的符号符号 ，其取值表示为 长度为T的离散时间上的可见符号序列例如： 观察到可见符号的概率(1), (2), ( )Txxx TX6511523,v v v v v vX( ( )|( )jkkjbP x tvt1jkkb( )x t123,v v v 隐马尔可夫模型 状态转移图一个例子 盒子编号不可见 每次从任一盒子中取出一个小球 隐藏状态隐藏状态：盒子编号 可见符号可见符号：小球 盒子i中取出各种小球的概率 得到某个特定小球序列的概率？离散HMM的符号表示隐藏状态集隐藏状态集可见符号集可见符号集状态序列状态序列观察序列观察序列状态转移概率状态转移概率观察到可见符号的概率观察到可见符号的
3、概率初始状态概率初始状态概率完整的完整的HMM参数向量参数向量HMM三大核心问题 估值问题估值问题 已知已知 观察到特定符号序列X HMM模型参数向量 求求 似然函数 解码问题解码问题 已知已知 观察到特定符号序列X HMM模型参数向量 求 最有可能产生X的隐状态序列HMM三大核心问题 学习（或参数估计）问题学习（或参数估计）问题 已知已知 观察到特定符号序列X 求求 模型参数向量 的估计值例如：ML估计估值问题 直接计算直接计算HMM模型产生可见长度为T的符号序列X的概率其中， 表示状态 的初始概率假设HMM中有c个隐状态，则计算复杂度为 ！例如：c=10，T=20，基本运算1021次！(1
4、)()TO c T估值问题 解决方案 递归计算t时刻的计算仅涉及上一步的结果，以及 ， ，和 HMM向前算法向前算法 HMM向后算法向后算法( ) t(1)t( )x t估值问题 HMM向前算法向前算法定义 ：t时刻在状态时刻在状态i，并且已观察到，并且已观察到x(1)，x(2)， x(t)的概率的概率 初始化初始化对每一个隐状态i，计算 递归递归for t=2 to T对每一个隐状态j，计算end 最后最后2()()TO c TO c T计算复杂度计算复杂度( )it估值问题 HMM向前算法向前算法估值问题 HMM向后算法向后算法（向前算法的（向前算法的时间反演时间反演版本）版本）定义 ：t
5、时刻在状态时刻在状态i，并且已，并且已逆向逆向观察到观察到x(T)，x(T-1)， x(t)的概率的概率 初始化初始化对每一个隐状态i，计算 （假设T时刻每个状态的概率相同） 递归递归for t=T-1 to 1对每一个隐状态i，计算end 最后最后2()()TO c TO c T计算复杂度计算复杂度( )( )ix TibTc( )it( )1( )(1)ciijjix tjtatb1(| )(1)ciiiP X 例子 HMM为 ：吸收状态吸收状态，即序列结束时的必然状态。该状态产生唯一的特殊可见符号v0，表示HMM过程结束例子 已知t=0时状态为 ，即 现观测到的序列为 计算HMM产生这个
6、特定观测序列的概率？10101112123130.2,0.3,0.1,0.4aaaa41320V ,v v v v例子 解HMM用于分类 为每一个类别建立一个HMM 每个HMM有自己的参数向量 ，该参数向量可以从属于类别i的样本中学习（估计）得到。 贝叶斯决策 决策结果i1(|) ()(|)(|) ()iiiciiiPPPPPX XX *argmax( (|) ()iiiiPPX HMM用于语音识别 “从左到右”（left-to-right）HMM 为每个单词发音建立一个HMM，其参数为 用向前算法计算发音序列X的类条件概率 取决于语言本身和上下文语义 用贝叶斯公式计算X的后验概率 最大后验概
7、率指示语音内容发音“viterbi”的“从左到右”HMM(|)iP X i()iP (|)iP X解码问题 已知一个观察序列XT，寻找最可能的隐状态序列 穷举法 把所有可能的隐状态序列的概率都计算一遍 计算复杂度()TO c T解码问题 Viterbi算法算法 初始化初始化对每个隐状态i，计算 递归递归for t=2 to T:对每一个隐状态j，计算end 最后最后for t=T-1 to 1（路径回溯）:end2()()TO c TO c T计算复杂度计算复杂度例子 HMM为例子 已知t=0时状态为 ，即 现观测到的序列为 计算最可能的隐状态序列？10101112123130.2,0.3,0
8、.1,0.4aaaa41320V ,v v v v例子 解.00271(2)1练习：练习：把此图填写完整，并回溯最佳状态路径把此图填写完整，并回溯最佳状态路径解码问题 对于较长的序列，Viterbi算法可能导致计算机下下溢出溢出 改进改进：基于对数的Viterbi算法 优点 变乘为加 避免下溢出 结果与Viterbi算法一样解码问题 对数对数Viterbi算法算法 初始化初始化对每个隐状态i，计算 递归递归for t=2 to T:对每一个隐状态j，计算end 最后最后for t=T-1 to 1（路径回溯）:end学习问题 从一组训练样本D=X1, X2, Xn 中，学习HMM的参数向量 不
9、存在根据训练集确定HMM最优参数的算法 常用算法向前向后算法向前向后算法（forward-backward algorithm）又称Baum-Welch重估计算法重估计算法（Baum-Welch re-estimation algorithm） 核心思想核心思想 通过递归方式更新HMM中的参数，以得到能够最好解释训练样本的HMM参数学习问题 Baum-Welch重估计公式重估计公式 已知X和 的情况下，t时刻为状态i，t+1时刻为状态j的后验概率(1)( )( )(| )iijjkjijTta bttPX向前向前向后向后1( )1( )( )kTjltlv tvjkTjltltbt 学习问题
10、向前向后算法向前向后算法 初始化 repeat基于 和X，利用Baum-Welch重估计公式计算 until 收敛 返回参数估计结果Part 2 贝叶斯置信网特征相关性 某些情况下，关于分布的先验知识并非直接是概率分布的形式，而是有关各个特征分量之间的统计相关性（或独立性）关系x1和x3统计独立，而其他特征对不独立相关性例子 汽车的状态 发动机温度 油温 油压 轮胎内气压 相关性 油压与轮胎内气压相互独立独立 油温与发动机温度相关相关贝叶斯置信网 用图的形式来表示特征之间的因果依赖性 贝叶斯置信网（贝叶斯置信网（Bayesian belief net） 因果网（因果网（causal netwo
11、rk） 置信网（置信网（belief net） 有向无环图 节点间的连线具有方向性方向性 图中无循环无循环路径 仅讨论离散情况贝叶斯置信网 每个节点节点A, B, C,代表一个系统变量（特征） 每个节点可能的离散取值 A的值：a1, a2, a3, 例如 A表示灯的状态 a1=开， a2=关，P(a1)=0.7，P(a2)=0.3 节点之间的有向连接连接表示变量之间的依赖关系 从A到C的连接表示 ，或 任意节点的状态可通过与其相连的节点的状态推断(|)ijP ca( | )P c a联合概率 线性链( , , , )( ) ( | ) ( | ) ( | )P a b c dP a P b a
12、 P c b P d c( , , )( | ) ( | )( ) ( | )aP b c dP c b P d cP a P b a( , )( | )( ) ( | ) ( | )abP c dP d cP a P b a P c b联合概率 简单回路( , , , )( ) (| ) (| ) ( |, )P e f g hP e P f e P g e P h f g( , , )( |, )( ) (| ) (| )eP f g hP h f gP e P f e P g e( , )( ) (| ) (| ) ( |, )efP g hP e P f e P g e P h f g
13、任意节点取特定值的概率 线性链任意节点取特定值的概率 简单回路, , ,( )( , , , )( ) (| ) (| ) ( |, )e f ge f gP hP e f g hP e P f e P g e P h f g例子1 鱼分类置信网0.60.20.20.20.30.5例子1 求“一条夏天在北大西洋捕获的鱼为光泽暗淡宽度窄的鲈鱼”的概率0.60.20.20.20.30.5例子1 求“一条夏天在北大西洋捕获的鱼为光泽暗淡宽度窄的鲈鱼”的概率 夏天： 北大西洋： 光泽暗淡： 宽度窄： 鲈鱼：3a1b3c2d2x31232312313222(,)() ( ) (|,) (|) (|)0.
14、25 0.6 0.6 0.5 0.40.018P a b x c dP a P b P xa b P cx P dx例子11. 冬天在南大西洋捕获到鲑鱼的概率2. 在南大西洋捕获光亮度高的鲈鱼的概率3. 夏天在北大西洋捕获一条宽的并且光亮度高的鱼的概率0.60.20.20.20.30.5 给定除目标变量X之外的变量的取值情况，确定其它变量的概率 证据 ，其中 表示变量i的取值情况 例如，鱼分类置信网 已有证据 ：已知冬季 ：渔民更喜欢南大西洋 ：鱼的光泽较亮 ：由于遮挡，无法测出宽度,.ABCeeee证据ie注意注意 的位置！的位置！ie置信度 考虑某个节点X X之前的节点集合称为X的父节父节
15、点点P，X之后的节点集合称为X的子节点子节点C 例子： X的父节点：A，B X的子节点：C，D 估计X的概率时，需区别对待X的父节点和子节点 证据e：除X以外各节点的变量取值情况 在给定e的情况下，命题x=(x1, x2,)的置信度（belief） 必须进行归一化，使得x所有取值的概率之和为1置信度 对X的子节点 假设子节点之间无连接 例如：置信度 对X的父节点 假设父节点之间无连接 表示父节点 处于状态n时的取值 忽略除了X的父节点和子节点之外的节点相互依赖性，简化上式置信度 命题x的置信度 节点X取某个特定值的概率等于两个因子的乘积 第一个取决于子节点 第二个取决于父节点证据 简单情况 直
16、接表示变量i的取值 置信度对固定的e， 为常数ie( , )( | )( , )( )P xP xP xPeeee例子1 鱼分类置信网0.60.20.20.20.30.5例子1 南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？0.60.20.20.20.30.5例子1 南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？a未知 b2=南大西洋c1=光亮 d未知1121121,212111,21112121111(| )( ,)( , , )( ) () (| ,) (|) ( |)() (|)( ) (| ,)( |)() (|) () (|a da dadP xP x b cx a b c dP a P
17、 b P xa b P cx P d xP b P cxP a P xa bP d xP b P cxP a P xae122122313241421121,)() (|,)() (|,)() (|,) (|)(|)0.4 0.6 0.25 0.70.25 0.80.25 0.1 0.25 0.3 1.00.114bP a P xa bP a P xa bP a P xa bP dxP dx先求先求x1=鲑鱼的概率鲑鱼的概率e:例子1 南大西洋捕获一条光亮的鱼，判断鲑鱼还是鲈鱼？a未知 b2=南大西洋c1=光亮 d未知 归一化（使得 ）因 ，所以判断为鲑鱼鲑鱼2(| )0.042P xe再求再
18、求x2=鲈鱼的概率鲈鱼的概率12(| )(| )1P xP xee1(| )0.63P xe2(| )0.27P xe12(| )(| )P xP xee例子2 你在家里安装了一套防盗系统 该系统对入室盗窃检测很敏感，但有时地震也能触发报警 你有两个邻居：Ali和Veli。当你不在家的时候，他们如果听到报警声，会给你打电话 Ali听到报警声就会给你打电话，但是有时他会把电话铃声认为是报警声而给你打电话 Veli经常在家听音乐，所以有时听不见报警声 根据哪个邻居打了电话给你，你是否能够估计家里真的被入室盗窃的概率？例子2 建模例子2 系统报警，但是既没有盗窃也没有地震发生，并且Ali和Veli都
19、打电话给你例子2 计算如下事件的概率 系统报警，但是既没有盗窃也没有地震发生，并且Ali和Veli都打电话给你例子2 如果Ali打电话给你，计算发生盗窃的置信度例子2 如果Ali打电话给你，计算发生盗窃的置信度 方法一方法一归一化(|)( ,)(| ) (| ) ( |, ) ( ) ( )vcaeP B ACP B ACP AC a P vc a P a B e P B P e (|)(,)(| ) (| ) ( |, ) () ( )vcaePB ACPB ACP AC a P vc a P aB e PB P e (|)0.01620.0513P B AC例子2 如果Ali打电话给你，计
20、算发生盗窃的置信度 方法二方法二例子2 如果Ali和Veli都打电话给你，计算发生盗窃的置信度例子2 如果Ali和Veli都打电话给你，计算发生盗窃的置信度( ,)(|,)(,)(| ) (| ) ( |, ) ( ) ( )( ,)(,)29aeP B AC VCP B AC VCP AC VCP AC a P VC a P a B e P B P eP B AC VCPB AC VC 例子3 草地变湿可能有两个原因：洒水装置打开过，或者下过雨 如果阴天，则下雨的可能比晴天大 如果阴天，打开洒水装置的可能较小 假设阴天和晴天等概率例子3 建模例子3 如果看到草地是湿的，判断洒水装置和下雨哪个
21、原因更为可能？例子3 如果看到草地是湿的，判断洒水装置和下雨哪个原因更为可能？(| , ) ( | ) ( | ) ( )( ,)( |)()( ,)(,)0.27810.4300.2781 0.369crP W S r P S c P r c P cP S WP S WP WP S WPS W(| , ) ( | ) (| ) ( )( ,)(|)()( ,)(,)0.45810.7080.6471csP W s R P s c P R c P cP R WP R WP WP R WPR W因为因为 ，所以下雨造成草地湿的可能性更大，所以下雨造成草地湿的可能性更大(|)(|)P S WP R
22、 W例子3 如果看到草地是湿的，并且当时天气晴朗呢？例子3 如果看到草地是湿的，并且当时天气晴朗呢？( |) ()(| , ) ( |)( ,)( |,)(,)( ,)(,)0.22950.8360.22950.045rP SC PCP W S r P rCP S WCP S WCP WCP S WCPS WC(|) ()(| , ) ( |)( ,)(|,)(,)( ,)(,)0.09450.3440.2745sP RC PCP W s R P sCP R WCP R WCP WCP R WCPR WC因为因为 ，所以洒水造成草地湿的可能性更大所以洒水造成草地湿的可能性更大(|,)(|,)P
23、 S WCP R WC朴素贝叶斯规则 当特征之间的依赖关系未知的时候，常常假设给定类别条件下各个特征条件独立 在此假设下的贝叶斯规则称为“朴素贝叶斯规则”（nave Bayes rule）或者“傻瓜贝叶斯规则”（idiot Bayes rule） 朴素贝叶斯置信网1( |)(|)dkikipp xxPart 3 期望最大化（EM）算法缺失的特征 假设有一个基于特征向量x的贝叶斯分类器，每一个x中的一部分特征xg是可见的，而剩下的特征xb缺失，不同样本中缺失特征可能不同 如何做决策？ 方法一 直接扔掉含有缺失值的样本 方法二 用其他已知该特征的样本均值 替换xb，即令bx()gbxx x期望最大
24、化 方法三方法三 通过扩展最大似然法，可以在训练集中有缺失值的情况下，对模型参数进行学习 期望最大化期望最大化（expectation-maximization, EM）算法可根据已有数据递归估计似然函数 EM算法的两个主要应用 在数据不完整或有缺失值的情况下学习 当似然方程难以直接求解时，初始化某些未知参数使问题简化期望最大化 假设样本x服从某种分布 ，其中 为未知参数向量 样本集 ，其中 ， 为完整的（或好的）部分， 为缺失的（或损坏的）部分 将 和 构成的集合分开表示 已知某个对 的假设 （不一定准确），关于缺失特征在由 确定的分布下求对数似然函数的期望，得到一个有关 的函数( | )p
25、 x ln(,| ) (|;)igbbgbp DDp DDdD期望最大化 含义含义：参数向量 是对参数的当前估计， 为改进当前估计的一个候选参数向量。对于每一个 ，可计算训练集的对数似然函数，由于存在缺失值 ，该似然函数需对 进行边缘化，而边缘积分中 的分布由当前估计 确定 ln(,| ) (|;)igbbgbp DDp DDdD期望最大化 期望最大化（EM）算法期望最大化例子 二维正态分布的EM算法 数据集 概率模型 二维正态分布， 目标：估计正态分布的参数向量212200例子 解 初始化均值位于原点，协方差矩阵为单位矩阵，即 计算 E步步例子例子 M步步 迭代E步和M步， 在3次迭代后收敛于0( |)0Q 0.667002.01.02.0例子小结 一阶马尔可夫链 隐马尔可夫模型（HMM） HMM的三大核心问题 估值问题 HMM向前算法向前算法 HMM向后算法向后算法 解码问题 Viterbi算法算法 对数对数Viterbi算法算法 学习问题 向前向后算法向前向后算法小结 贝叶斯置信网是描述特征之间因果关系的有向无环图 根据贝叶斯置信网计算联合概率 证据 给定证据下的置信度小结 期望最大化（EM）算法 E步步 M步步
