一、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
)
I = ({i_1,i_2,i_3…i_N})
I
=
(
i
1
,
i
2
,
i
3
.
.
.
i
N
)
状态序列
O
=
(
o
1
,
o
2
,
o
3
.
.
.
o
N
)
O = ({o_1,o_2,o_3…o_N})
O
=
(
o
1
,
o
2
,
o
3
.
.
.
o
N
)
观测序列
A
=
[
a
i
j
]
N
∗
N
A = [a_{ij}]_{N*N}
A
=
[
a
i
j
]
N
∗
N
状态转移概率矩阵
B
=
[
b
j
(
k
)
]
N
∗
N
B = [b_j(k)]_{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
)
P(i_t|i_{t-1},o_{t-1},…,i_1) = P(i_t|i_{t-1})
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
)
O=(o_1,o_2,…,o_n)
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
)
P(X,Y)
P
(
X
,
Y
)
四、维特比算法(Viterbi):解决第三个问题
维特比算法主要用动态规划来求解HMM的预测问题：一直模型和观测序列，求最可能的状态序列
假如状态序列为：
x
1
,
x
2
,
x
3
.
.
.
x
N
x_1,x_2,x_3 … x_N
x
1
,
x
2
,
x
3
.
.
.
x
N
对应观测序列为：
y
1
,
y
3
,
y
3
.
.
.
y
N
y_1,y_3,y_3 … y_N
y
1
,
y
3
,
y
3
.
.
.
y
N
那么我们的问题就转化为：在盲打时候已知输入序列
y
1
,
y
3
,
y
3
.
.
.
y
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
x
1
,
x
2
,
x
3
.
.
.
x
N
。求最可能的汉字序列是什么？
公式：
x
1
,
x
2
,
x
3
.
.
.
x
N
=
A
r
g
M
a
x
P
(
x
1
,
x
2
,
x
3
.
.
.
x
N
∣
y
1
,
y
3
,
y
3
.
.
.
y
N
)
=
A
r
g
M
a
x
∏
i
=
1
N
P
(
y
i
∣
x
i
)
∗
P
(
x
i
∣
x
i
−
1
)
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})
x
1
,
x
2
,
x
3
.
.
.
x
N
=
A
r
g
M
a
x
P
(
x
1
,
x
2
,
x
3
.
.
.
x
N
∣
y
1
,
y
3
,
y
3
.
.
.
y
N
)
=
A
r
g
M
a
x
∏
i
=
1
N
P
(
y
i
∣
x
i
)
∗
P
(
x
i
∣
x
i
−
1
)
其中公式
A
r
g
M
a
x
∏
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})
A
r
g
M
a
x
∏
i
=
1
N
P
(
y
i
∣
x
i
)
∗
P
(
x
i
∣
x
i
−
1
)
主要通过贝叶斯公式变换得来
我们知道贝叶斯公式为：
P
(
A
∣
B
)
=
P
(
B
∣
A
)
∗
P
(
A
)
P
(
B
)
P(A|B) = \frac {P(B|A)*P(A)}{P(B)}
P
(
A
∣
B
)
=
P
(
B
)
P
(
B
∣
A
)
∗
P
(
A
)
那么
P
(
x
∣
y
)
=
P
(
y
∣
x
)
∗
P
(
x
)
P
(
y
)
P(x|y) = \frac {P(y|x)*P(x)}{P(y)}
P
(
x
∣
y
)
=
P
(
y
)
P
(
y
∣
x
)
∗
P
(
x
)
,其中P(y)为已知常数，其中P(x)实际为
P
(
x
t
∣
x
t
−
1
)
P(x_t|x_{t-1})
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)然后我们在第三层继续这个算法:
我们还没有足够的信息判断哪一条一定是全局最短路径的子路径。
(4)然后我们在最后一层继续这个算法:
E点已经是终点了，我们稍微对比一下这三条路径的总长度就能知道哪条是最短路径了。
参考文章
https://clyyuanzi.gitbooks.io/julymlnotes/content/hmm.html
http://www.52nlp.cn/category/hidden-markov-model
https://www.zhihu.com/question/35866596/answer/236886066
http://www.hankcs.com/ml/conditional-random-field.html