1 隐马尔可夫模型 - 定义
- 隐马尔可夫模型（hidden markov model, HMM）是可用于标注问题 [自动分词、词性标注、命名实体识别等] 的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型；
- 隐马尔可夫模型定义如下：隐马尔可夫模型是一种有向概率图模型。描述由一个隐藏的马尔科夫链生成不可观测的状态随机序列（状态序列，state sequence），再由各个状态序列生成一个观测从而产生观测随机序列（观测序列，observation sequence）的过程。
2 隐马尔可夫模型 - 用于中文分词
2.1 中文分词例子
- 输入：
我想去乌鲁木齐 - 输出：
我/S 想/S 去/S 乌/B 鲁/M 木/M 齐/E
注意： B表示一个词的开始；M表示一个词的中间；E表示一个词的结尾；S表示单独成词；
2.2 中文分词 - 问题建模
-
表示输入的将要分词的句子（观测序列）；
-
表示输出的句子分词结果（状态序列）；
- 中文分词问题就是：给定
最大化；
隐马尔可夫模型，使用贝叶斯公式将条件概率
的求解：
注意：都是一样的；
2.3 隐马尔可夫模型三要素
- 观测序列（待分词的句子）：
；
- 状态序列（分词结果）：
；
- 观测空间
，表示所有可能的观测集合；即中文中所有可能的词，大小为
；
- 状态空间
，表示所有可能的状态集合；即分词标签
，大小为
；
- 初始概率分布
：
；
- 发射概率分布
：
；
- 转移概率分布
：
；包含一个结束符
；
-
隐马尔可夫模型：
隐马尔可夫模型.png
3 隐马尔可夫模型 - 两个基本假设
- 齐次马尔科夫假设： 即假设隐藏的马尔可夫链在任意时刻
的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关；
%20%3D%20p(y_t%7Cy_%7Bt-1%7D))
- 观测独立性假设： 即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关；
%20%3D%20p(x_t%7Cy_t))
4 隐马尔可夫模型 - 3个基本问题
- 概率计算问题： 给定模型
和观测序列
下观测序列
；
- 学习问题： 已知观测序列
- 预测问题： 也称为解码问题。已知模型
最大的状态序列
4.1 概率计算问题
- 可使用前向（forward）、后向（backward）算法计算
4.2 学习问题
- 隐马尔可夫模型的学习，根据训练数据是包括 观测序列 和对应的 状态序列 还是只有观测序列，可以分别由 监督学习 与 无监督学习 实现；
4.2.1 监督学习方法
- 使用极大似然估计法来估计隐马尔可夫模型的参数。
- 转移概率
%20%3D%20%5Cfrac%7BCount(y_l%2C%20y_%7Bl%2B1%7D)%20%7D%7B%20Count(y_l)%20%7D)
- 发射概率
%20%3D%20%5Cfrac%7B%20Count(x_l%2C%20y_l)%20%7D%7B%20Count(y_l)%20%7D)
- 初始概率
Count(start)，训练语料总数；
%20%3D%20%5Cfrac%7B%20Count(start%2C%20y_1)%20%7D%7B%20Count(start)%20%7D)
4.2.2 无监督方法 [Baum-Welch 算法]
- 由于监督学习需要使用标注的训练数据，而人工标注训练数据往往代价很高，有时就会利用无监督学习方法；
- 隐马尔可夫模型实际上是一个含有隐变量的概率模型：
它的参数学习可以由 EM算法 实现。
4.3 预测问题
-
HMM模型问题定义如下，找出
使得联合概率
；一般使用viterbi算法求解，其时间复杂度为
；
- 隐马尔可夫的预测问题，一般使用维特比算法求解。维特比算法实际是动态规划（Dynamic Programming）解隐马尔可夫模型预测问题，即用动态规划求概率最大路径（最优路径）。这时一条路径对应着一个状态序列。
- 维特比算法解HMM预测问题：
输入：模型
；
输出：最优路径；
（1）初始化
（2）开始递推，对；注意：
表示转移概率，
表示发射概率；
（3）终止
（4）最优路径回溯，对
求得最优路径：
4.3.1 HMM预测过程例子
-
隐马尔可夫模型的三个概率矩阵如下：
HMM三个概率矩阵.png
- Viterbi算法解码过程：维特比算法时间复杂度为：
维特比算法.png
5. HMM算法总结
- HMM算法总结如下：
（1）HMM对联合概率进行建模：；
（2）HMM inference目标为：；
（3）HMM参数估计：可以采用简单的统计方法，或者采用无监督式的方式使用EM算法学习网络参数；
- HMM的缺点：HMM算法并不一定能够保证
；
HMM算法缺点.png
参考资料
- 《统计学习方法》- 李航
- 结构化预测 - 序列标注，[李宏毅，机器学习2016] https://www.bilibili.com/video/BV1Ux411S7Yk?p=24
- 李宏毅，机器学习2016 - 课程主页 http://speech.ee.ntu.edu.tw/~tlkagk/courses_ML16.html
- 如何通俗地讲解 viterbi 算法？https://www.zhihu.com/question/20136144
