隐马尔科夫模型HMM自学（4-1）

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计算：

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

编者注：隐马尔科夫模型HMM自学系列由崔晓源翻译。