针对隐马尔可夫模型第一个问题的解决方法之前向算法

复习, 状态序列(state sequence),观测序列(observation sequence)

问题一 概率计算问题

转载链接:https://zhuanlan.zhihu.com/p/27056207
给定模型的情况下,求某种观测序列出现的概率。

一般方法: 前向、后向算法

举例来说明一下,例子如下:(例子来源于*)
考虑一个村庄,所有村民都健康或发烧,只有村民医生才能确定每个人是否发烧。医生通过询问患者的感受来诊断发烧。村民只能回答说他们觉得正常,头晕或感冒。

医生认为,他的患者的健康状况作为离散的马可夫链。 “健康”和“发烧”有两个状态,但医生不能直接观察他们;健康与发烧的状态是隐藏的。每天都有机会根据患者的健康状况,病人会告诉医生他/她是“正常”,“感冒”还是“头昏眼花”。

比如,给定的HMM模型参数已知,求出三天观察是(Dizzy,Cold,Normal)的概率是多少?对应的HMM模型参数已知的意思,就是说A(trainsition_probability),B(emission_probability),pi 矩阵是已经知道的。
这里仅算两天针对隐马尔可夫模型第一个问题的解决方法之前向算法

这个问题我们最容易想到的解法就是将路径全部遍历一遍, 针对隐马尔可夫模型第一个问题的解决方法之前向算法
假如第一天为 Healthy

第一天为Healthy的概率为:0.6

在第一天为Healthy的基础上,观察为Dizzy的概率为:

P(Dizzy|Healthy)=0.6P(Healthy->Dizzy)=0.6*0.1=0.06

然后求出在第一天为Healthy的基础上,并且第一天表现为Dizzy的前提下,第二天也为Healthy的概率为:

P(Healthy|Healthy,Dizzy)=0.06p(Healthy->Healthy) = P(Dizzy|healthy)07 = 0.06*0.7

针对隐马尔可夫模型第一个问题的解决方法之前向算法
可以看出,一条路径已经求解完了。之后按这个思路求解其他三条路径。之后相加就好了。

问题: 实际中的隐状态个数非常大, 那么我们的计算量是无法忍受的。从图中可以看出,它是随着观测序列长度的增加呈指数级变化。(一旦遇到指数级,就像坐火箭一样,多一个数量都是灾难)

暴力法并不实用。

前向算法

我们首先定义一下前向概率
针对隐马尔可夫模型第一个问题的解决方法之前向算法
针对隐马尔可夫模型第一个问题的解决方法之前向算法
已知:模型 λ、

求解概率(前向概率): 时刻 t 之前的观测序列为 O1,O2,……,Ot 且此时状态为 qi 的概率。

下面,我们可以整理一下前向算法的流程:

输入:隐马尔可夫模型 λ,观测序列 O

输出:观测序列概率 p(o| α)

  • (1)初值
    针对隐马尔可夫模型第一个问题的解决方法之前向算法
    前向概率的定义中一共限定了两个条件,一是到当前为止的观测序列,另一个是当前的状态。所以初值的计算也有两项(观测和状态),一项是初始状态概率,另一项是发射到当前观测的概率。
  • (2)递推对t=1,2,3,…,T-1针对隐马尔可夫模型第一个问题的解决方法之前向算法
    针对隐马尔可夫模型第一个问题的解决方法之前向算法
    每次递推同样由两部分构成,大括号中是当前状态为i且观测序列的前t个符合要求的概率,括号外的是状态i发射观测 t+1的概率。
  • (3)终止
    针对隐马尔可夫模型第一个问题的解决方法之前向算法

慢慢分析: ——把大象装入冰箱,大声告诉我有几步?

步骤(1)初始化前向概率,是初始时刻的状态 i1 = qi 和观测 o1 的联合概率。 也就是我们给个序列的起点,然后再说怎么往后推。

步骤(2),这是关键点,就像我们写递归程序一样,写好递归步骤一样。

计算前向概率(到时刻 t +1 部分观测序列为 ~,且在时刻 t +1 处于状态 qi针对隐马尔可夫模型第一个问题的解决方法之前向算法

其实就是一个映射的过程
针对隐马尔可夫模型第一个问题的解决方法之前向算法
即我们的思路是: 从 t 时刻开始 , 先把 t+1 时刻的第一个状态 q1 的前向概率算出来, 然后再对 t + 1 时刻的所有状态, q1, q2…等等求和, 再把 t + 2 时刻第一个状态 q1 的前向概率算出来,如此循环往复。直到求出概率。

前向算法好在哪里?

与暴力算法对比,它把计算的值都给存起来了,而不是像暴力算法一样,很多值都是重复计算,没有存起来的机制。

利用前向概率计算 P(O | λ) 的计算量是 O(N2T) 阶的, 而不是直接计算的 O(TNT)。针对隐马尔可夫模型第一个问题的解决方法之前向算法

为什么是这样的呢? 因为我们可以看出,暴力算法其实是计算每一条路径,而路径是随着观测序列越长呈指数级增长,示意图:
针对隐马尔可夫模型第一个问题的解决方法之前向算法
所以是 NT 条路径,又因为每个状态对应 T 个观测值, 所以是 TNT

而前向算法其实也没什么高明之处,需要求和的步骤都没有少,只是利用了一些优化手段,如下图,让它变成一个块,一个块的计算,而不是一条路径的计算,这样就可以消去指数变化

针对隐马尔可夫模型第一个问题的解决方法之前向算法
再看下面这张图, 之前讲到过,先求 t+1 时刻的 q1 状态前向概率,然后求和 t+1 时刻的 q1、q2等,求出 t +2 时刻 q1前向概率,如下所示,其实就是先集中求 q1, 这里需要 N 次(状态数量之和),然后再集中求 q2 ,一直求完qN 的前向概率,这里就变成了 N x N 次, 然后把它们求乘以发射概率,得到下一个时刻的 q1。一共递推 T次。
针对隐马尔可夫模型第一个问题的解决方法之前向算法

针对隐马尔可夫模型第一个问题的解决方法之前向算法针对隐马尔可夫模型第一个问题的解决方法之前向算法 芒骁 发布了202 篇原创文章 · 获赞 4 · 访问量 4282 私信 关注
上一篇:【元胞自动机】基于matlab元胞自动机模拟HIV传染【含Matlab源码 236期】


下一篇:mac mysql error You must reset your password using ALTER USER statement before executing this statement.