HMM模型之一(v2.0)

写在前面

之前我在研一时写的隐马模型系列一因为不知道啥原因，在CSDN上的文章找不到了，然后就也一直没写，这次又看到了HMM，就争取把那篇文章复现出来。而且因为已经是第二次写了，就争取写的深入一些。

HMM有三个基本问题：

1. 评估问题：给定模型和两个状态序列，求哪个更有可能。
2. 学习问题：给定观测，求解模型参数。
3. 预测问题：给定模型和观测，求隐状态序列。

HMM被定义为一个三元组$$$(A,B,\pi)$$$，$$$\pi$$$表示初始状态概率向量，A表示状态转移概率矩阵，B表示观测概率矩阵。

两个基本假设：

1. 齐次马尔科夫性假设：只依赖于前一状态。
2. 观测独立性假设：观测只依赖于状态。

前向算法与后向算法

前向算法

刷完了DP算法之后，前向算法其实就很简单了。关键是分解该问题的最优子问题，然后写出递推式。
子问题定义为：

第 i 个隐状态是 i ，生成观测序列的前 t 个元素的概率是多少？

并将子问题定义为前向变量$$$\alpha_t(i)$$$,那么递推式就可以表示为：
$$\alpha_{t+1}(i) = \big[\sum_{j=1}^N\alpha_t^j\big]B(i,o_{t+1})$$

最后输出DP缓存中最后一列的元素和即可。这样的话，该算法的时间复杂度是$$$O(N^2T)$$$，而不是大暴搜的$$$O(N^TT)$$$。

后向算法

后向算法的子问题为：

第 i 个隐状态是 i ，生成观测序列的第 t+1 元素直到最后一个元素的概率是多少？

并将子问题定义为$$$\beta_t(i)$$$，那么递推式就可以表示为：
$$\beta_t(i)=\sum_{j=1}^NA(i,j)B(j,o_{t+1})\beta_{t+1}(j)$$

然后递推变成从前往后了，其实并没有改进算法的效率，这个算法只是为了和前向算法结合去解决后面两个问题的。具体怎么结合呢？

比如说求给定观测序列的概率可以用前向概率和后向概率结合表示：
$$P(O|\lambda) = \sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)A(i,j)B(j,o_{t+1})\beta_{t+1}(j)$$

这里引用我自己之前一篇博客中的图片解释

那么我们不使用那两个大大的求和符号的话，就可以指定某个向量两个时刻时内部两个隐状态的情况下，求输出概率了。那如果在对其中一个隐状态求边缘概率呢呢？那就可以指定某个时刻下其内部隐状态的情况下求输出概率了。那用这个概率除以$$$P(O|\lambda)$$$呢？那就会得到指定时刻内部状态是某个固定取值的后验概率。这个就是BaumWelch算法中的一个关键计算步骤。注意上面的计算都包含时间t，如果再对时间t求和，那得到的概率就不限制时刻了，而是某个内部状态或者某两个内部状态出现在隐藏序列中的概率。