做外贸的阿里巴巴网站是哪个,怎么免费建立网站,怎么查看一个网站是哪家公司做的,展览网站建设方案转载自 隐马尔科夫模型-前向算法
隐马尔科夫模型-前向算法
在该篇文章中讲了隐马尔科夫模型#xff08;HMM#xff09;一基本模型与三个基本问题 隐马尔科夫模型-基本模型与三个基本问题#xff0c;这篇文章总结一下隐马尔科夫链#xff08;HMM#xff09;中的前向与后…转载自 隐马尔科夫模型-前向算法
隐马尔科夫模型-前向算法
在该篇文章中讲了隐马尔科夫模型HMM一基本模型与三个基本问题 隐马尔科夫模型-基本模型与三个基本问题这篇文章总结一下隐马尔科夫链HMM中的前向与后向算法首先给出这俩个算法是为了解决HMM的第一个基本问题。
先回忆一下第一个问题
第一个问题是求给定模型的情况下求某种观测序列出现的概率。比如给定的HMM模型参数已知求出三天观察是(Dizzy,Cold,Normal)的概率是多少(对应的HMM模型参数已知的意思就是说的A(trainsition_probability),B(emission_probability),pi矩阵是已经知道的。) 相关条件如下图所示 由上图所示也就是说可以写成如下代码
trainsition_probability [[0.7,0.3],[0.4,0.6]] emission_probability [[0.5,0.4,0.1],[0.1,0.3,0.6]]
pi [0.6,0.4]
在第一个问题中我们需要求解出三天观察是(Dizzy,Cold,Normal)的概率是多少
这里为了演示简单我只求解出俩天观察为(Dizzy,Cold)的概率是多少
这个问题太好求解了最暴力的方法就是将路径全部遍历一遍。下面尽可能通俗易懂的说明一下 首先画出时间序列状态图如下 下面我详细走一遍一条路径的暴力算法这样既可以避开公式的晦涩也不失正确性。其它路径完全类似
第一天为Healthy的概率为0.6
在第一天为Healthy的基础上观察为Dizzy的概率为PDizzy|Healthy0.6*P(Healthy-Dizzy)0.6*0.10.06
然后求出在第一天为Healthy的基础上并且第一天表现为Dizzy的前提下第二天也为Healthy的概率为 P(Healthy|Healthy,Dizzy) P(Dizzy|healthy)*07 0.06*0.7上面求完的时候代表下图中的红线已经转移完了。 好那么当在前面基础上第二天观察为Cold的概率为 P(Cold|(Healthy,Dizzy),(Healthy)) P(Healthy|Healthy,Dizzy)*0.4 0.06*0.7*0.4现在我们已经完成一条路径的完整结果了。
就是在第一天隐含状态为Healthy和第二天隐含状态为Healthy的基础上观察序列为DizzyCold的概率为 PDizzy,Cold|Healthy,Healthy 0.06*0.7*0.40.0168
那么同理我们就可以求出其它三条路径。 1在第一天隐含状态为Healthy和第二天隐含状态为Fever的基础上观察序列为DizzyCold的概率 2在第一天隐含状态为Fever和第二天隐含状态为Healthy的基础上观察序列为DizzyCold的概率 3在第一天隐含状态为Fever和第二天隐含状态为Fever的基础上观察序列为DizzyCold的概率
然后最后的第一个问题的结果就是将这四个结果相加起来就可以了。是不是很简单那么为了还需要前向后向算法来解决这个事呢
其实这个算法在现实中是不可行的。我给的例子由于是为了讲解容易状态值和观察值都很小但是实际中的问题隐状态的个数是非常大的。
那么我们的计算量是不可以忍受的。
我们可以稍微估计一下加入状态值是N个观察值是K个。总共观察长度为T。
那么我们的路径总个数就是N的T次方,我的天这个复杂度已经接受不了了到达了每个隐含状态的时候还需要算一遍观察值出现的概率每个隐状态计算一遍到观察值的概率。又要乘以NT当然这已经对前面很大复杂度构成不了多少作用了
所以我们得出结论暴力法在这里并不实用于是就引出了前向后向算法。它们都是基于动态规划思想求解。下面介绍一下
1、前向算法
我们首先定义一下前向概率
定义给定隐马科夫模型lamda定义到时刻t为止的观测序列为01,02,03....0t且状态为qi的概率为前向概率记作
可以递推地求得前向概率及观测序列概率。
下面我们可以整理一下前向算法的流程
输入隐马尔可夫模型观测序列
输出观测序列概率
(1)初值 前向概率的定义中一共限定了两个条件。
一是到当前为止的观测序列另一个是当前的状态。所以初值的计算也有两项观测和状态一项是初始状态概率另一项是发射到当前观测的概率。
(2)递推对t1,2,3,.....,T-1 每次递推同样由两部分构成大括号中是当前状态为i且观测序列的前t个符合要求的概率括号外的是状态i发射观测t1的概率。
下面稍微解释一下公式 (3)终止 由于到了时间T一共有N种状态发射了最后那个观测所以最终的结果要将这些概率加起来因为每个隐状态都可能产生我们需要的观测值所以都要加起来。
公式可以用下面的转移图表示假设我要求第二层某个结点的前向概率等于前一层所有结点到该结点的转移如下图 由于每次递推都是在前一次的基础上进行的所以降低了复杂度计算只存在于相邻的俩个时间点。计算如下图所示 下方标号表示时间节点每个时间点都有N种状态所以相邻两个时间之间的递推消耗N^2次计算。
而每次递推都是在前一次的基础上做的所以只需累加O(T)次所以总体复杂度是O(T)个N^2即0TN^2,这比起我们前面说的暴力法的复杂度已经好了太多了。
到这里为止前向算法也就讲完了。本文通过一个具体简单例子走了一遍过程期间有一些自己的总结和理解希望对大家有帮助~ 2、python实现代码
代码如下
