租二级目录做网站,wordpress+边框插件,怎样给公司做网站,浙江建设网官方网站1. 前言
前向算法和后向算法主要还是针对HMM三大问题之一的评估问题的计算#xff0c;即给定模型参数#xff0c;计算观察序列的概率。文章不介绍过多公式#xff0c;主要看两个例子
复习一下HMM的三大要素#xff08;以海藻#xff08;可观测#xff09;和天气#x…1. 前言
前向算法和后向算法主要还是针对HMM三大问题之一的评估问题的计算即给定模型参数计算观察序列的概率。文章不介绍过多公式主要看两个例子
复习一下HMM的三大要素以海藻可观测和天气隐状态为例
①初始概率向量当前时刻天气的可能性属于先验概率
②状态转移矩阵从当前天气转移到下一个天气的可能性比如P(雨天|晴天)即为晴天转移到雨天的概率
③混淆矩阵当前天气为某种天气的时候海藻状态为某种状态的可能性比如P(干燥|晴天)即为晴天时候海藻干燥的概率
问题给定HMM模型参数以及海藻的三天状态干燥、湿润、湿透。
目的求解海藻出现这三种状态的概率。
2. 穷举搜索直接计算
2.1 理论介绍
已知给定HMM模型参数λ(πAB)和观察序列
求解观测序列O出现的概率P(O|I,λ)
方法列举所有可能的状态分别求解各个状态序列与观测序列的联合概率P(O,I | λ)最后求和就得到了P(O|λ)
具体过程
①状态序列出现的概率是 ②对于其中一种状态序列观测序列的概率是 依据贝叶斯公式可以计算 ③求和 2.2 实例推导
给定隐马尔可夫模型也就是在模型参数(π,A,B)已知的情况下我们想找到观察序列的概率。
最直接的方法是列举出每种可能的转移如下图所示(借用英文文献中的那个例子) 图中展示了三天的海藻状态第一列对应第一天海藻为dry时候三种可能的天气隐状态第二列对应第二天海藻为damp时候三种可能的天气隐状态第三列对应第三天海藻为soggy时候三种可能的天气隐状态每个隐状态都有一个概率指向当前可能的海藻状态由混淆矩阵给出从第一天到第二天和第二天到第三天的天气隐状态之间都有转移概率由转移概率矩阵给出。
计算观察序列概率的方法是找到所有的可能路径因为每种海藻观察情况都有三种可能天气所以共有3327条路径即27种不同的天气序列然后将所有可能的观察序列的概率加和起来: 不适用于大的模型和较长的序列。可以利用概率的时间不变性减少问题的复杂性。 3.前向算法
3.1 理论推导
前向概率给定隐马尔科夫模型λ定义到时刻 t 部分观测序列为,状态的概率为前向概率 说白了就是计算当给出模型参数的时候计算一个观测序列和第 t 时刻为状态的联合概率这是一个递推的过程可以一层一层的计算而不是像列举法直接一条路径走到头然后再计算下一条路径最后能够通过加和递推得到P(O|λ)
已知因马尔科夫模型λ和观测序列O
输出观测序列概率P(O | λ )
方法前向概率递推得到P(O,I | λ)加和得到P(O | λ)
具体过程
① 初值,计算第一个时间点处于各隐状态的概率 等式右边表示最初第i个状态出现的概率乘以在这个状态下某个观测状态的概率。不懂没关系待会看天气的实例解释。
② 递推 中括号意思就是当前层的所有N个隐状态与下一层的第i个状态的连接里面的 α 是到时刻t部分观测序列为且在 t 时刻处于状态 j 的概率前向计算给出第一层用的是过程①a是 t 时刻第 j 个状态到 t1 时刻第 i 个状态的转移情况转移矩阵给出中括号外面乘以的b是当前状态下对应观测情况发生的概率比如当前是晴天那么晴天对应海藻湿润的概率是什么呢?就是b由混淆矩阵给出。 ③终止 其实就是求解在时刻t所有状态的概率求和。
前向算法的高效在于利用路径结构将前向概率递推到全局。在t1时刻计算每个状态与观测情况的联合概率t2...T的时候计算状态与观测情况的联合概率时都用到了前一个时刻刚计算出来的联合概率。
穷举法时间复杂度TNT
前向算法的时间复杂度N2T其中T是指观察序列的长度N是指隐藏状态数目。
【注】每次前向得到的均为隐状态和观测情况的联合概率因而最后一步需要来一次加法。
3.2 实例分解
将上述三步推广到三天海藻观察和天气状态中
1计算t1时的局部概率
局部概率的计算公式
αt ( j ) Pr( t1时刻的海藻观察 | 隐藏状态 j ) x Pr( t1 时刻每个隐状态可能发生的初始概率 所以初始时刻状态 j 的局部概率依赖于此状态的初始概率及相应时刻我们所见的观察概率。
2 计算 t 1 时的局部概率
αt ( j ) Pr( t 时刻海藻的观察情况 | 隐藏状态 j ) x Pr( t 时刻状态到 t1时刻状态的转移概率
假设乘号左边项Pr( 观察情况 | 隐藏状态 )已经有了需要考虑右边Pr( t 时刻所有指向 j 状态的路径
计算到达某个状态的所有路径的概率。可以计算到达此状态的每条路径的概率并对它们求和。 计算α所需要的路径数目随着观察序列的增加而指数级递增。但是t-1时刻给出了所有到达此状态的前一路径概率。因此我们可以通过t-1时刻的局部概率定义 t 时刻的局部概率。即 我们计算的这个概率等于相应的观察概率 ( t1时在状态 j 的观察概率)与该时刻到达此状态的概率总和上一步每个局部概率的计算结果与相应的状态转移概率乘积后再相加的乘积。假设式子中t1拿上图为例第三列的中间节点代表的就是观察海藻处于某种状态时出现某种天气的概率即b后面的加和项就是第二列三个节点的概率与对应转移到第三排中间结点概率的乘积的和。
3将第2步按照下表j所有状态加和起来即可
4. 后向算法
后向概率给定隐马尔可夫模型定义在时刻t状态为的条件下从t1时刻到T的部分观测序列为后向概率 用递推方法求后向概率但是并非用简单的加法得到P(O|λ)
具体过程(参考李航《统计学习方法》)
输入隐马尔可夫模型λ观测序列O
输出观测序列概率P(O|λ)
①初始化后向概率最终时刻的所有状态规定 ②对于tT-1,T-2,...1递推计算时刻 t 状态为条件下时刻t1之后的观测序列为的后向概率其实就是第t1 时刻的N个状态到t 时刻状态的转移概率乘以t1时刻每个隐状态对应的观察情况为o(t1)的概率再乘以状态j之后的观测序列的后向概率,此项能够递推得到 ③计算一种加和但是与前向算法的加和还不一样它的含义是与步骤②一样的只不过初始概率 π 代替了转移概率 a 5. 统一写法
《统计学习方法》中将前向算法和后向算法统一起来归纳了 6. 前向算法实例
6.1 海藻的实例
由马尔可夫模型MM可知由一个状态转移至另一个状态中存在着转移概率并对这种转移概率可以依据其紧接的前一种状态推算出来与该系统原始状态和此次转移前的马尔可夫过程无关。
隐马尔可夫模型(Hidden Markov models ,HMM)是马尔可夫链的一种它的状态不能直接观察到但能通过观测向量序列观察到每个观测向量都是通过某些概率密度分布表现为各种状态每一个观测向量是由一个具有相应概率密度分布的状态序列产生的。
假设连续观察三天的水藻湿度为(DryDampSoggy)求出该观察序列的概率。天气状态有三类(Sunny,Cloudy,Rainy)而且海藻湿度和天气有一定关系。
已知 1 隐藏状态SunnyCloudyRainy 海藻湿度有四类{DryDryishDampSoggy} 2 观察状态序列{DryDampSoggy} 3 初始状态序列Sunny(0.63)Cloudy(0.17)Rainy(0.20) 4 状态转移矩阵 Sunny Cloudy Rainy Sunny 0.5 0.375 0.125 Cloudy 0.25 0.125 0.625 Rainy 0.25 0.375 0.375 Cloudy(昨天)→Sunny(今天)的概率是0.25
Sunny(昨天)→Rainy(今天)的概率是0.125
5 混淆矩阵 Dry Dryish Damp Soggy Sunny 0.6 0.2 0.15 0.05 Cloudy 0.25 0.25 0.25 0.25 Rainy 0.05 0.10 0.35 0.50
怎么计算观察序列的概率
即统计P(observation|Sunny,Sunny, Sunny)P(observation| Sunny, Sunny, Cloudy) P(observation| Sunny,Sunny,Rainy) P(observation| Sunny, Cloudy, Sunny) P(observation| Sunny, Cloudy,Cloudy) P(observation| Sunny, Cloudy, Rainy) …总共33种可能性。
实际由于马尔可夫模型第二天的状况只取决于第一天第三天的只取决于第二天与第一天的天气没关系。
① 先求第一天的P(Day1-Sunny),P(Day1-Cloudy),P(Day1-Rainy),Day1的海藻湿度是Dry
P(Day1-Sunny) 0.63*0.6;
P(Day1-Cloudy)0.17*0.25;
P(Day1-Rain)0.20*0.05;
② 再求第二天的P(Day2-Sunny),P(Day2-Cloudy),P(Day2-Rainy), Day2的海藻湿度是Damp
P(Day2-Sunny)(P(Day1-Sunny)*0.5 P(Day1-Cloudy)*0.25 P(Day1-Rainy)*0.25)* 0.15
P(Day2-Cloudy) (P(Day1-Sunny)*0.375 P(Day1-Cloudy)*0.125 P(Day1-Rainy)*0.375) * 0.25
P(Day2-Rainy) (P(Day1-Sunny)*0.125P(Day1-Cloudy)*0.625 P(Day1-Rainy)*0.375)* 0.35
同理继续求第三日的各天气概率Day3的海藻湿度是soggy。
P(Day3-Suny)(P(Day2-Sunny)*0.5 P(Day2-Cloudy)*0.25 P(Day2-Rainy)*0.25)* 0.05
P(Day3-Cloudy) (P(Day2-Sunny)*0.375 P(Day2-Cloudy)*0.125 P(Day2-Rainy)*0.375) * 0.25
P(Day3-Rainy)(P(Day2-Sunny)*0.125 P(Day2-Cloudy)*0.625 P(Day2-Rainy)*0.375)* 0.50
推出
P(observationlist) P(Day3-Sunny)P(Day3-Cloudy)P(Day3-Rainy) 0.030319
6.2 盒中取球的实例
已知HMM模型参数
转移概率矩阵A 0.50.20.30.30.50.20.20.30.5
混淆矩阵B 0.50.50.40.60.70.3
初始概率
π(0.2 , 0.4 , 0.4)
求解三次取球颜色为红、白、红的概率P(O|λ)
提示盒子相当于三种隐状态两种颜色的球相当于观测情况观测序列由红、白、红给出
1计算初值 2递推计算 3终止条件 7. 后向算法实例
关于后向算法直接以6.2盒子隐和球观测的实例为例推导吧
1初始化第三次取球为红球时候即最终时刻所有状态的概率为1 式中下标为观测情况括号为隐状态比如第一个式子意思就是第一个隐状态对应的观测到红球的概率
2逆推迭代倒数第二次观察情况为白球的情况 第一个式子表示的是第二次观测如果状态为1那么第二、三次观测为白、红的联合概率分布a是第二层隐状态第一个盒子转移到第三层隐状态三个盒子的转移概率b表示第三层的三个隐状态观测到红球的概率β等式右边表示已知模型参数和第三层隐状态求第三次观测到红球的概率其实第1步计算是1
第二个式子表示的是第二次观测如果状态为2那么第二、三次观测为白、红的联合概率分布a是第二层隐状态第二个盒子转移到第三层隐状态三个盒子的转移概率b表示第三层的三个隐状态观测到红球的概率β等式右边表示已知模型参数和第三层隐状态求第三次观测到红球的概率其实第1步计算是1
同理推导第一层的情况 3计算加和 可以发现前向算法和后向算法的结果相同
【注】前向算法中计算结果舍去了一位结果应该是0.035512
