【NLP冲吖~】二、隐马尔可夫模型（Hidden Markov model, HMM）

0、马尔可夫模型

某一状态只由前一个状态决定，即为一阶马尔可夫模型；
状态间的转移依赖于前n个状态的过程，即为n阶马尔可夫模型

马尔科夫链：

如果$S_{t+1}$只依赖于前一时刻$S_t$，不依赖于$S_1,...,S_{t-1}$，则称$S_1,S_2,...,S_T,...$为马尔科夫链，这种性质叫做马尔可夫性。

$\ast \ast S_1,...,S_{t-1},S_t,S_{t+1}\ast \ast$

$S_1,...,S_{t-1}$表示过去；$S_t$表示现在；$S_{t+1}$表示未来。
马尔可夫性想告诉我们的是，未来只与现在有关，与过去无关。

马尔可夫模型定义：

存在一类重要的随机过程：如果一个系统有N个状态$S_1$,$S_2$,$S_3$,…,$S_N$，随着时间的推移，该系统从一个状态转移到另一个状态。如果用$q_t$表示系统在时间$t$的状态变量，那么$t$时刻的状态取值为$S_j(1<=j<=N)$的概率取决于前$t-1$个时刻（1,2,3，…,t-1）的状态，该概率为：
$P(q_t=S_j|q_{t-1}=S_i,q_{t-2}=S_k,...)$

1、假设一：如果在特定情况下，系统在时间t的状态下只与其在时间$t-1$的状态相关，则该系统构成一个离散的一阶马尔可夫链：
$P(q_t=S_j|q_{t-1}=S_i,q_{t-2}=S_k,...)=P(q_t=S_j|q_{t-1}=S_i)$

2、假设二：如果只考虑独立于时间$t$的随机过程，状态与时间无关，那么
$P(q_t=S_j|q_{t-1}=S_i)=a_{i}j$
其中 1<=i，j<N
即：$t$时刻状态的概率取决于前$(t-1)$个时刻（1,2,3，…,t-1）的状态，且状态的转移与时间无关，则该随机过程为马尔可夫模型。

马尔可夫模型的两个要素是 初始状态分布 和 状态转移概率矩阵。

1、隐马尔可夫模型

在马尔可夫模型中，每个状态表示了一个可观察的事件，所以，马尔可夫模型又称为可视化马尔可夫模型（visibleMarkovmodel，VMM），这使得模型的适应性有所限制。

隐马尔可夫模型（HMM）就是为了解决这样的限制而产生的。在这样的情景下，系统中会有两组状态，一组是不可观察、隐藏的状态，另一种是可观察的状态。模型具体的状态序列是未知的，状态转移的概率是已知的。因此，该模型是一个双重随机过程，包括模型的状态转换和特定状态下可观察的事件的随机。

与马尔可夫模型相比，隐马尔可夫有三要素，分别是：
初始状态为 $I=(i_1,i_2,...,i_T)$，$i_1$为第1个时刻的初始状态；
状态空间为 $Q=(q_1,q_2,...,q_N)$，表示有N个状态可以相互转移；
由初始状态和状态空间可得初始状态分布
$\Pi =({\pi }_1,{\pi }_2,...,{\pi }_N)$，其中 ${\pi }_i=P(i_1=q_i)$ 【$i_1$中的i与$q_i$中的i含义不同】

状态转移矩阵$A=[a_{11},...]$，$a_{11}$表示状态1到状态1的转换概率，A为N行N列的矩阵，每行之和为1。

观测空间为 $V=(v_1,v_2,...,v_M)$，表示有M个观测状态；
观测状态为 $O=(O_1,O_2,...,O_T)$，$O_1$为初始观测状态。
观测概率矩阵$B=[b_1(1),...]$，$b_1(1)$表示在第1个状态上得到第一个观测状态的概率。
$b_j(k)=P(O_t=v_k|i_t=q_j)$
B为N行M列的矩阵，每行之和为1。

2、算法

根据隐马尔可夫模型定义，可以将一个长度为T的观测序列$O=(o_1,o_2,...,o_T)$的生成过程描述为以下算法：
输入：隐马尔可夫模型 λ = （A，B，π），观测序列长度T；
输出：观测序列O = (o_1,o_2,…,o_T);
（1）按照初始状态分布π产生状态$i_1$;
（2）令t=1；
（3）按照状态$i_t$的观测概率分布$b_{i_t}(k)$生成$o_t$;
（4）按照状态$i_t$的状态转移概率分布{a_{i_t},i_{t+1}} 产生状态$i_{t+1},i_{t+1}$ = 1,2,…,N；
（5）令$t=t+1$，如果$t<T$，重复（3）-（5），否则，结束。

3、三个基本问题

给定一个隐马尔可夫模型（HMM），可以解决三个基本问题。

（1）评估【Evaluation】

给定HMM，即 $\mu =[\pi ，A，B]$，求某个观测序列的概率。
例如：给定一段文本的隐马尔可夫模型，包括第一个单词的概率分布，单词转移概率矩阵，特定单词下该词词性的概率分布。求序列中每一个单词为某个词性的概率。

（2）解码【Decoding】

给定HMM，即 $\mu =[\pi ，A，B]$，以及某个观测序列，求得其可观测序列。
例如：给定一段文本的隐马尔可夫模型，包括第一个单词的概率分布，词性转移概率矩阵，特定单词下该词词性的概率分布。并且已知每个单词的词性序列。求得词性序列对应的文本序列。

（3）学习【Learning】

给定一个观测序列，求得一个隐马尔可夫模型。
例如：已知一个文本序列。求得一个文本的隐马尔可夫模型，包含：第一个词的词性，词性转移概率矩阵，特定单词该词的词性概率分布。

4、关于三个问题的算法计算

参考大佬博客https://zhuanlan.zhihu.com/p/88362664

5、隐马尔可夫模型在NLP中的应用

NLP中序列标注（文本词性标注、命名体识别）问题https://blog.csdn.net/echoKangYL/article/details/86983973

冷知识

马尔可夫是苏联人，他是切比雪夫的学生。