背景
隐马尔可夫模型关注的三个问题中的第一个是找到模型观察序列的概率。
蛮力解决方案
已知HMM模型的参数,是隐藏状态转移概率矩阵,是观测状态概率矩阵。对于隐藏状态的初始概率分布记作。已知观测序列,现在我们需要求出出现的条件概率。首先已经知道,即隐藏状态到观测状态的概率,已经知道,即隐藏态之间的转移概率。然后,我们可以直接使用暴力求解的方式。暴力求解过程如下所示:
(1) 任意隐藏序列出现的概率表示为:
(2) 已知隐藏序列,求观察序列的概率,表示为:
(3) 隐藏序列和观察序列的联合概率表示为:
(4) 求边缘概率分布,即观测序列在模型下的概率。
蛮力求解方法只适用于隐藏状态很少的模型。如果隐藏状态太多,会导致计算量巨大。隐藏状态是未知的,需要考虑所有隐藏状态。如果状态数为,则复杂度为时间,表示隐藏序列的长度。总时间复杂度为。
前向算法求HMM观测序列概率
前向算法的本质是动态规划,通过子问题找到全局最优解,这里称为局部状态。对于前向算法,局部状态是前向概率,它是指在给定时刻从隐藏状态到观察状态的概率。 时刻隐藏状态的前向概率定义为:
那么,时间的概率是递归的:
最后,计算给定模型下观察序列的概率:
正向算法解决方案示例
给定三个盒子,每个盒子包含两个彩色球,红色和白色。三个盒子里的球数分别是:
盒子名称 | 1号盒子 | 2号盒子 | 3号盒子 |
---|---|---|---|
红色球数量 | 5 | 4 | 7 |
白色球数量 | 5 | 6 | 3 |
从不同的盒子中取球,并且从1号盒子取球的概率为0.2,从2号盒子取球的概率是0.4,从3号盒子取球的概率是0.4, 总体概率为1。 即初始的状态分布:
二、状态转移概率矩阵为:
观察到的状态概率矩阵为:
求解问题,给定一个观察序列{red, white, red},找到这个观察序列的概率是多少?
具体解决过程如下:
(1) 在第1时刻观察到红色球,此时计算三个状态的前向概率:
盒子1的前向概率:
盒子2的前向概率:
盒子3的前向概率:
(2) 依据递推式,递推第2时刻三个状态的前向概率,观察为白色球,
盒子1的前向概率:
盒子2的前向概率:
盒子3的前向概率:
(3) 依据递推式,递推第3时刻三个状态的前向概率, 观察为红色球,
盒子1的前向概率:
盒子2的前向概率:
盒子3的前向概率:
最后,我们找到观察序列为 {red, white, red} 的概率为:
后向算法求HMM观测序列概率
后向算法求HMM观测序列的概率和前向算法求HMM观测序列的概率是相似的。它们之间的区别主要在动态规划的递推式恰好是相反的。
时刻隐藏状态的前向概率定义为:
然后,递归推导出每个隐藏状态在时间的后向概率:
最后,计算给定模型下观察序列的概率:
文章出处登录后可见!