隐马尔科夫模型HMM自学（二）

现在的位置: 首页 > 综合 > 正文

RSS

隐马尔科夫模型HMM自学（二）

2019年06月04日 ⁄ 综合 ⁄ 共 2692字 ⁄ 字号小中大 ⁄ 评论关闭

找到观察序列的概率

崔晓源翻译

Finding the probability of an observed sequence

1、穷举搜索方法

对于水藻和天气的关系，我们可以用穷举搜索方法的到下面的状态转移图（trellis）：

图中，每一列于相邻列的连线由状态转移概率决定，而观察状态和每一列的隐状态则由混淆矩阵决定。如果用穷举的方法的到某一观察状态序列的概率，就要求所有可能的天气状态序列下的概率之和，这个trellis中共有3*3=27个可能的序列。

可见计算复杂度是很大，特别是当状态空间很大，观察序列很长时。我们可以利用概率的时间不变性解决复杂度。

2、采用递归方法降低复杂度

我们采用递归的方式计算观察序列的概率，首先定义部分概率为到达trellis中某一中间状态的概率。在后面的文章里，我们把长度为T的观察状态序列表示为：

2a. Partial probabilities, (

's)

在计算trellis中某一中间状态的概率时，用所有可能到达该状态的路径之和表示。

比如在t=2时间，状态为cloudy的概率可以用下面的路径计算：

用

t ( j ) 表示在时间t时状态j的部分概率。计算方法如下：

t ( j )= Pr( observation | hidden state is j ) * Pr(all paths to state j at time t)

最后的观察状态的部分概率表示，这些状态所经过的所有可能路径的概率。比如：

这表示最后的部分概率的和即为trellis中所有可能路径的和，也就是当前HMM下观察序列的概率。

Section 3 会给出一个动态效果介绍如何计算概率。

2b.计算初始状态的部分概率

我们计算部分概率的公式为:

t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

但是在初始状态，没有路径到达这些状态。那么我们就用probability乘以associated observation probability计算：

这样初始时刻的状态的部分概率就只与其自身的概率和该时刻观察状态的概率有关。

书接上文，前一话我们讲到了Forward Algorithm中初始状态的部分概率的计算方法。这次我们继续介绍。

2c.如何计算t>1时刻的部分概率

回忆一下我们如何计算部分概率：

t ( j )= Pr( observation | hidden state is j ) * Pr(all paths to state j at time t)

我们可知（通过递归）乘积中第一项是可用的。那么如何得到Pr(all paths to state j at time t) 呢？

为了计算到达一个状态的所有路径的概率，就等于每一个到达这个状态的路径之和：

随着序列数的增长，所要计算的路径数呈指数增长。但是在t时刻我们已经计算出所有到达某一状态的部分概率，因此在计算t+1时刻的某一状态的部分概率时只和t时刻有关。

这个式子的含义就是恰当的观察概率（状态j下，时刻t+1所真正看到的观察状态的概率）乘以此时所有到达该状态的概率和（前一时刻所有状态的概率与相应的转移概率的积）。因此，我们说在计算t+1时刻的概率时，只用到了t时刻的概率。这样我们就可以计算出整个观察序列的概率。

2d.复杂度比较

对于观察序列长度T，穷举法的复杂度为T的指数级；而Forward Algorithm的复杂度为T的线性。

=======================================================

最后我们给出Forward Algorithm的完整定义

We use the forward algorithm to calculate the probability of a T long observation sequence;

where each of the y is one of the observable set. Intermediate probabilities ('s) are calculated recursively by first calculating for all states at t=1.

Then for each time step, t = 2, ..., T, the partial probability is calculated for each state; [Formula]

that is, the product of the appropriate observation probability and the sum over all possible routes to that state, exploiting recursion by knowing these values already for the previous time step. Finally the sum of all partial probabilities gives the probability of the observation, given the HMM, . [Formula] =======================================================