HMM(隐马尔可夫模型)

含义

HMM(Hidden Markov Model), 中文称作隐含马尔科夫模型, 因俄国数学家马尔可夫而得名. 它一般以文本序列数据为输入, 以该序列对应的隐含序列为输出.

• 什么是隐含序列
  序列数据中每个单元包含的隐性信息, 这些隐性信息之间也存在一定关联

EG：

import jieba.posseg as psgtext = "他喜欢看动画片"# 对文本进行分词处理
res = psg.lcut(text,True)
print(res)#[pair('他', 'r'), pair('喜欢', 'v'), pair('看', 'v'), pair('动画片', 'n')]# 每个词对应的隐含序列为
hidden_sequence = ["r","v","v","n"]

在posseg.lcut中可以看到隐马模型HMM，默认为True

作用

在NLP领域, HMM用来解决文本序列标注问题. 如分词, 词性标注, 命名实体识别都可以看作是序列标注问题.

隐含假设

隐含序列中每个单元的可能性只与上一个单元有关

使用过程

状态序列隐藏的马尔可夫链随机生成的状态的序列
观测序列每个状态生成一个观测，而由此产生的观测的随机序列

HMM的输入为一个句子进行分词后的语句为w1(word1),w2,w3…

HMM的输出为对应分词的词性q1,q2,q3…

HMM的目标在于最大化隐状态的条件概率（直白一点就是一个词它有K种词性，那么HMM的作用在于选择它最大可能是哪一种词性），即：
$$P(q_1,q_2...q_n|w_1,w_2...w_n)=\frac{P(w_1,w_2...w_n|q_1,q_2...q_n)P(q_1,q_2...q_n)}{P(w_1,w_2...w_n)}$$
$P(q_1,q_2...q_n|w_1,w_2...w_n)$为每个单词在对应词性下的概率

假设一个词它有K种词性，那么$P(q_1,q_2...q_n|w_1,w_2...w_n)$就有$K^n$种概率，而HMM的作用就是找到最大概率的那一种可能，即

因为分母$P(w_1,w_2...w_n)$的概率是一定的，所以可以直接省略

根据HMM模型的假设，$q_i$的设定只和$q_{i-1}$，所以$P(q_1,q_2...q_n)\approx {\prod }_{i=1}^{n}P(q_i|q_{i-1})$

此外HMM假设每个词的生成都是独立的，所以$P(w_1,w_2...w_n|q_1,q_2...q_n)={\prod }_{i=1}^{n}P(w_i|q_i)$

所以$argmaxP(q_1,q_2...q_n|w_1,w_2...w_n)=argmax{\prod }_{i=1}^{n}P(w_i|q_i)P(q_i|q_{i-1})$

由上可以知道，当我们知道了${\prod }_{i=1}^{n}P(w_i|q_i)P(q_i|q_{i-1})$的最大值，也就意味着我们找到了对应词语所可能的词性

那么我们将如何计算呢？

对于$P(w_i|q_i)$和$P(q_i|q_{i-1})$的计算，我们通常采用统计方法来估计其值

i.e.

C(w,q)	出现次数	C(q)	出现次数	P(w|q)
C(花，v)	30	C(v)	100	P(花|v)=0.3
C(花，n)	10	C(n)	200	P(花|n)=0.05

C(w,q)word作为动词在文本中出现的次数

C(q)q词性在文本中出现的次数

P(w|q)word作为q词性在文本中出现的概率

C(qi-1,qi)	出现次数	C(qi-1)	出现次数	P(qi｜qi-1)
C(v，n)	40	C(v)	100	P(n|v)=0.4

得到上述知识后，我们应该有种想法，只要我们依次遍历1～n，累乘计算的乘积进行比较，那么就一定会得到一种最大的概率

但是这种方法对于单词量巨大且词性丰富的文本来说简直就是一场灾难，因此我们不得不使用一种方法来降低其复杂度，下面我们来引进维特比算法

维特比算法

本质：动态规划实现最短路径

维特比算法是多步骤每步多选择模型的最优选择问题
其在每一步的所有选择都保存了前续所有步骤到当前步骤当前选择的最小总代价（或者最大价值）以及当前代价的情况下前继步骤的选择。
依次计算完所有步骤后，通过回溯的方法找到最优选择路径。符合这个模型的都可以用viterbi算法解决，隐马模型的第三问题刚好符合这个模型，所以才采用了viterbi算法。

详情见知乎
通俗地讲解 viterbi 算法

它的核心观点是利用动态规划来降低复杂度，每一次来计算当前word下最有可能的前i种词性

先简明说明维特比在检索最大可能词性中的定义$f(i,j)$，它表示在所有$q_i=j$的词性序列中能达到的前i位最大HMM概率值，通俗地来讲在最后一个词性为j的情况下，排在前i位的最大概率为$f(i,j)$

初始化为
$$f(1,j)=P(w_i｜j)$$
递推公式为
$$f(i+1,j)=ma{x}_{1<=k<=K}f(i,k)P(w_{i+1}|j)P(j|k)$$
$K$为文本中的词性种类

复杂度：$O(K^2\ast N)$

遍历横向K，遍历纵向N，确定了一个单词词性之后，在此基础上又将面临K个选择

通俗地来讲就是先将一个单词作为词性集合中任意一种词性的概率算出来

然后在此基础上计算下一个单词词性为词性集合中任意一种词性的概率，此时将要考虑上一个单词作为哪种词性时的概率最大就作为该单词词性的概率

i.e.

就好比我先算出APPLE作为各个词性的概率，然后计算RUN作为NOUN的概率时，就要考虑前一个单词APPLE的词性作为哪一种词性时，RUN作为NOUN的概率最大，HE也是类似。

复杂度解释：

考虑到APPLE有K种可能词性，一共有N个单词，并且在计算RUN作为NOUN时又要和APPLE作为K种词性要比较，所以复杂度为$O(K^2\ast N)$