HMM算法详解
一、HMM模型的基本元素
1、 HMM的五个基本元素
HMM中，有5个基本元素：{I,O,A,B,π}，我结合序列标志任务对这5个基本元素做一个介绍：
(1)I:状态序列。在这里，是指每一个词语背后的标注。
(2)O:观测序列。在这里，是指每一个词语本身。
(3)A:状态转移概率矩阵。在这里，是指某一个标注转移到下一个标注的概率。
(4)B:观测概率矩阵，也就是发射概率矩阵。在这里，是指在某个标注下，生成某个词的概率。
(5)π:初始概率矩阵。在这里，是指每一个标注的初始化概率。
其中：
$I = ({i_1,i_2,i_3...i_N})$ 状态序列
$O = ({o_1,o_2,o_3...o_N})$ 观测序列
$A = [a_{ij}]_{N*N}$ 状态转移概率矩阵
$B = [b_j(k)]_{N*N}$ 观测概率矩阵
π 初始状态概率向量
2、HMM模型
模型：λ = (A,B,π)
A,B,π为隐马尔可夫模型的三个要素
这三个元素都是通过统计得到的，这三个值就是模型的参数，得到这三个值的过程就是模型训练的过程，所以说HMM算法是比较简单的算法。模型已经知道了，可以认为各个状态的全连接路径已经知道了，给个观测序列，通过veterbi算法求解所有路径中的最优路径。
3、HMM模型的两个假设
- (1)齐次马尔科夫假设（又叫一阶马尔科夫假设）
隐藏的马尔科夫链在任意时刻t的状态只依赖于前一时刻的状态，与其他时刻状态及观测状态无关。
$P(i_t|i_{t-1},o_{t-1},...,i_1) = P(i_t|i_{t-1})$
- (2)观测独立假设
任意时刻的观测状态只依赖于该时刻的马尔科夫链的状态，与其他时刻的观测状态无关。
而以上的这些元素，都是可以从训练语料集中统计出来的。最后，我们根据这些统计值，应用维特比（viterbi）算法，就可以算出词语序列背后的标注序列了。
二、隐马尔可夫模型有三种应用场景
我们做命名实体识别只用到其中的一种——求观察序列的背后最可能的标注序列。
最后，来说下HMM解决的三个问题：
1、Evaluation(概率计算问题)
已知模型参数 λ= (A, B, π),计算某个观测序列发生的概率，即求P(O|λ)
2、Learning(学习问题)
给定观测序列$O=(o_1,o_2,...,o_n)$，如何调整模型参数 λ=(π, A, B), 使得P(O|λ)最大？，这个就是求模型的算法
3、Decoding(预测问题或者叫解码问题) 最常用
给定观测序列O和模型 λ，求最有可能的状态序列S(s1,s2,...st+1)。
例如：通过实体标注和训练，我们可以得到模型λ，现在给定了一个观测序列=我在凤凰金融工作，求最有可能的命名实体有哪些，想找到对应的状态序列S=(我，在，凤凰金融，工作)。
三、求模型λ：解决第二个问题
HMM是一种生成模型，所以求的是联合概率
注意：我们平时所说的，求模型指的是求目标函数，例如在线性回归中我们的目标函数为$h(λ)=λ_1X+λ_2$，求目标函数只需要求得参数λ，所以平时我们说求模型就是求参数。$P(X,Y)$
四、维特比算法(Viterbi):解决第三个问题
维特比算法主要用动态规划来求解HMM的预测问题：一直模型和观测序列，求最可能的状态序列
假如状态序列为：$x_1,x_2,x_3 ... x_N$
对应观测序列为：$y_1,y_3,y_3 ... y_N$
那么我们的问题就转化为：在盲打时候已知输入序列$y_1,y_3,y_3 ... y_N$，对应的最可能汉字$x_1,x_2,x_3 ... x_N$。求最可能的汉字序列是什么？
公式：
$x_1,x_2,x_3 ... x_N = ArgMaxP(x_1,x_2,x_3 ... x_N|y_1,y_3,y_3 ... y_N)$
$= ArgMax \prod_{i=1}^N P(y_i|x_i)*P(x_i|x_{i-1})$
其中公式$ArgMax \prod_{i=1}^N P(y_i|x_i)*P(x_i|x_{i-1})$主要通过贝叶斯公式变换得来
我们知道贝叶斯公式为：$P(A|B) = \frac {P(B|A)*P(A)}{P(B)}$
那么$P(x|y) = \frac {P(y|x)*P(x)}{P(y)}$,其中P(y)为已知常数，其中P(x)实际为$P(x_t|x_{t-1})$,根据马尔科夫假设当前时刻假设之和前一时刻相关。
例如，输入观测序列：
我 爱 中 国
O O O B
O B O I
O O B I
B O I B
也就是求的第三行是最优路径：
四、维特比算法(Viterbi)
注意：viberbi算法计算过程中计算的是两个点之间的最短路径，不是计算的两个层之间的最短路径1.性质
如果概率最大的路径p(或者说最短路径)经过某个点，比如途中的a，那么这条路径上的起始点S到a的这段子路径Q，一定是S到X22之间的最短路径。否则，用S到a的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优性原理。
2.算法
假如你从S和E之间找一条最短的路径，除了遍历完所有路径，还有什么更好的方法？
实际上在所有路径中肯定有一条最短路径：
我们开始从头一步一步求解：
(1)首先起点是S，从S到A列的路径有三种可能：S-A1、S-A2、S-A3，如下图：
我们不能武断地说S-A1、S-A2、S-A3中的哪一段必定是全局最短路径中的一部分，目前为止任何一段都有可能是全局最短路径的备选项。
(2).然后开始第二层
<1>我们先从第二层的第一个节点开始：
如上图，经过B1的所有路径只有3条：
S-A1-B1
S-A2-B1
S-A3-B1
如果说最终的第二层的节点是从B1经过的话，肯定要从这三条路径中选择一条最短的路径，那么其他的两条可以删除了。
<2>然后我们开始了第二层的第二个节点：
同理，如上图，经过B2的路径有3条：
S-A1-B2
S-A2-B2
S-A3-B2
如果说最终的第二层的节点是从B2经过的话，肯定要从这三条路径中选择一条最短的路径，那么其他的两条可以删除了。
<3>然后我们开始了第二层的第三个个节点：
同理，如上图，经过B3的路径也有3条：
S-A1-B3
S-A2-B3
S-A3-B3
如果说最终的第二层的节点是从B3经过的话，肯定要从这三条路径中选择一条最短的路径，那么其他的两条可以删除了。
<4>所有第二层的阶段遍历完了之后，剩下三条路径了。
我们还没有足够的信息判断哪一条一定是全局最短路径的子路径。
(3)然后我们在第三层继续这个算法:
下来讲到C列了，类似上面说的B列，我们从C1、C2、C3一个个节点分析。
经过C1节点的路径有：
S-A3-B1-C1、
S-A1-B2-C1、
S-A2-B3-C1
和B列的做法一样，从这三条路径中找到最短的那条（假定是S-A3-B1-C1），其它两条路径同样道理可以删掉了。那么经过C1的所有路径只剩一条，如下图：
同理，我们可以找到经过C2和C3节点的最短路径，汇总一下：
我们还没有足够的信息判断哪一条一定是全局最短路径的子路径。
(4)然后我们在最后一层继续这个算法:
E点已经是终点了，我们稍微对比一下这三条路径的总长度就能知道哪条是最短路径了。
参考文章
https://clyyuanzi.gitbooks.io/julymlnotes/content/hmm.html
http://www.52nlp.cn/category/hidden-markov-model
https://www.lookfor404.com/%E7%94%A8%E9%9A%90%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%A8%A1%E5%9E%8Bhmm%E5%81%9A%E5%91%BD%E5%90%8D%E5%AE%9E%E4%BD%93%E8%AF%86%E5%88%AB-ner%E7%B3%BB%E5%88%97%E4%BA%8C/
https://www.zhihu.com/question/35866596/answer/236886066
http://www.hankcs.com/ml/conditional-random-field.html