HMM | Machine Learning

见李航老师的《统计学习方法》第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)$ 结果的算法：

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

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

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

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)

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