HMM

见李航老师的《统计学习方法》第10章。对前向后向计算方法及EM计算模型参数的推导都很明了。 page174 有三个基本问题：概率计算问题，学习问题，预测问题。

HMM生成过程###

预测时候，寻找最优的隐藏状态序列$S^* = \arg \max_s P_{\theta}(S|O)$ ，需要用到Viterbi Algorithm，主要是动态规划的思想。

训练.不完全数据###

若是完全标注的数据，可以简单的统计出各个概率。 若数据有很多是未标注的怎么办？ EM！

求模型的参数：$\lambda = (A,B,\pi)$ 已知：观测序列O 未知：隐藏状态序列I

那么： $P(O|\lambda) = \sum_I P(O|I,\lambda) P(I|\lambda)$ .

E步：

$$Q(\lambda,\bar \lambda) = E_I [\log P(O,I|\lambda) | O, \bar \lambda] \\ = \sum_I \log P(O,I|\lambda) P(I|O, \bar \lambda) \\ = \sum_I \log P(O,I|\lambda) \frac {P(O,I|\bar \lambda)} {P(O|\bar \lambda)} \\ \approx \sum_I \log P(O,I|\lambda) P(O,I|\bar \lambda) \quad \text{去掉了与I无关的分母} \\ = \sum_I \log \pi_i P(O,I|\bar \lambda) + \sum_I (\sum_{t=1}^{T-1} \log a_{i,i+1}) P(O,I|\bar \lambda) + \sum_I (\sum_{t=1}^T \log b_{i_t} (o_t) ) P(O,I|\bar \lambda)$$

M步： 如《统计学习方法》，上上式三个子项逐一用拉格朗日函数求解。 最后的解$\pi_i = \frac {P(O,i_1=i|\bar \lambda)}{P(O|\bar \lambda)}$中有个式子$P(O|\bar \lambda)$ ,如何高效计算？前向后向算法。

前向后向算法###

若给定$\lambda = (A,B,\pi)$和观测序列，计算观测序列O出现的概率$P(O|\lambda)$ . 具体Status未知，此时计算量很大。

前向####

最简单的：$\alpha_t(k) = P(o_{1:t},s_t=k) = \sum_{s_{1:t-1}} P(o_{1:t},s_{1:t-1},S_t=k)$ 。 但是，看看求和的集合，这个时间复杂度不可接受。 于是乎想到了一种利用$\alpha_{t-1}(l)$结果的算法：

后向####

前向后向算法

HMM相关文章索引