> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/hmm.md).

# HMM

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

## HMM生成过程##\#

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F4d40a1c25bdf236c1c020156498bb4043aec5292.png?generation=1589383943184082\&alt=media)

**预测时候**，寻找最优的隐藏状态序列$$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)$$结果的算法：

![前向算法](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fc8a10d29276c91d57646ca4e99c3aea45a12eaf3.png?generation=1589383942445974\&alt=media) ![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F333e73800f4b062ab40d59e5b19f8018ded83914.png?generation=1589383943791018\&alt=media)

### 后向###\#

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F4d8e716caf8bc82422b68f439c928af2be70b5e7.png?generation=1589383943426761\&alt=media)

![前向后向算法](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fead03424bd8cc12a573784eda125bec1dde39774.png?generation=1589383942872324\&alt=media)

[HMM相关文章索引](http://www.52nlp.cn/hmm%E7%9B%B8%E5%85%B3%E6%96%87%E7%AB%A0%E7%B4%A2%E5%BC%95)