基于HMM的词性标注方法

1 HMM模型概念

首先来理解以下什么是HMM，HMM是隐马尔可夫模型（Hidden Markov Model）的简称，是一种统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析。

为了比较容易上手，下面用通过一个例子来理解这个概念：
例子来自一文搞懂HMM（隐马尔可夫模型），以及感谢另一博主：https://blog.****.net/meiqi0538/提供的帮助

假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。第三个骰子有八个面（称这个骰子为D8），每个面（1，2，3，4，5，6，7，8）出现的概率是1/8。

假设我们开始掷骰子，我们先从三个骰子里挑一个，挑到每一个骰子的概率都是1/3。然后我们掷骰子，得到一个数字，1，2，3，4，5，6，7，8中的一个。不停的重复上述过程，我们会得到一串数字，每个数字都是1，2，3，4，5，6，7，8中的一个。例如我们可能得到这么一串数字（掷骰子10次）：1 6 3 5 2 7 3 5 2 4

这串数字叫做可见状态链。但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是你用的骰子的序列。比如，隐含状态链有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8

一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（骰子）之间存在转换概率（transition probability）。在我们这个例子里，D6的下一个状态是D4，D6，D8的概率都是1/3。D4，D8的下一个状态是D4，D6，D8的转换概率也都一样是1/3。这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。这样就是一个新的HMM。

同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability），有的地方叫发射概率。就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。


和HMM模型相关的算法主要分为三类，分别解决三种问题：

1. 知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道每次掷出来的都是哪种骰子（隐含状态链）。
2. 还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出这个结果的概率。
3. 知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率），观测到很多次掷骰子的结果（可见状态链），我想反推出每种骰子是什么（转换概率）。
   在这三个问题中，第一个问题称为解码问题，目标是求隐含状态链；第二个问题意义不大；第三个问题是求转换概率。在词性标注中。主要涉及第一个问题，下面只对第一个问题进行求解。

我知道我有三个骰子：六面骰，四面骰，八面骰。我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。

其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后依照第零个问题的解法把每个序列对应的概率算出来。然后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。
另外一种很有名的算法叫做维特比算法(Viterbi algorithm)。 要理解这个算法，我们先看几个简单的列子。
首先，如果我们只掷一次骰子：

看到结果为1.对应的最大概率骰子序列就是D4，因为D4产生1的概率是1/4，高于1/6和1/8.
把这个情况拓展，我们掷两次骰子：

结果为1，6.这时问题变得复杂起来，我们要计算三个值，分别是第二个骰子是D6，D4，D8的最大概率。显然，要取到最大概率，第一个骰子必须为D4。这时，第二个骰子取到D6的最大概率是
同样的，我们可以计算第二个骰子是D4或D8时的最大概率。我们发现，第二个骰子取到D6的概率最大。而使这个概率最大时，第一个骰子为D4。所以最大概率骰子序列就是D4 D6。
继续拓展，我们掷三次骰子：

同样，我们计算第三个骰子分别是D6，D4，D8的最大概率。我们再次发现，要取到最大概率，第二个骰子必须为D6。这时，第三个骰子取到D4的最大概率是
同上，我们可以计算第三个骰子是D6或D8时的最大概率。我们发现，第三个骰子取到D4的概率最大。而使这个概率最大时，第二个骰子为D6，第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。

写到这里，大家应该看出点规律了。既然掷骰子一二三次可以算，掷多少次都可以以此类推。我们发现，我们要求最大概率骰子序列时要做这么几件事情。首先，不管序列多长，要从序列长度为1算起，算序列长度为1时取到每个骰子的最大概率。然后，逐渐增加长度，每增加一次长度，重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了，重新计算的话其实不难。当我们算到最后一位时，就知道最后一位是哪个骰子的概率最大了。然后，我们要把对应这个最大概率的序列从后往前推出来。

2序列标注问题 (Sequence Labeling Problem)

序列标注问题是从序列预测另一个相关序列的过程，如下：

词性标注：是指标注句子种每个词对应的词性

一种简单的做法是建立一个词典，词典里有每个词的词性，然后通过查表进行词性标注，显然这个方案是不可行的，第一词典的词不可能包括需要进行词性标注的句子的所有的词；第二在一些语言中例如中文，一个词可能有多个词性；第三词性的不同标注可能导致句子的意思不一样，这就需要我们在标注词性是考虑整个句子的相关信息，才能准确的把词性找出来。

3 基于HMM的词性标注方法

基于HMM的词性标注方法是词性标注的最基本和简单的方法，掌握本基础对自然语言处理是十分重要的。

3.1 HMM词性标记模型

基于HMM的词性标注方法是一种生成式模型，假设我们在构造一个句子时，首先想到的是一个词性序列，然后根据这个序列产生一个合乎文法的句子序列，如下：

接着假设我们脑海中产生词性的方式是一个马尔可夫链，如下图所示，这实际上相当于上文例子中提到的转移概率。

假设我们从脑海里得到的词性序列如下图红色箭头顺序，从start开始到end结束。

那么其产生概率为p(“PN V D N”)=0.40.80.250.950.1。然后进行第二步：产生句子。

如上图所示，从“PN”这个词性中选择了“John”的几率是0.2；从“V”这个词性中选择了“John”的几率是0.17；从“D”这个词性中选择了“John”的几率是0.63；从“N”这个词性中选择了“John”的几率是0.17。最终从词性序列“PN V D N”产生出句子“John saw the saw”的几率：P(“John saw the saw”|“PN V D N”)=0.20.170.63*0.17。这个步骤实际上对应上文例子中的发射概率
实际上，HMM模型是帮助我们描述如何产生出一句话的过程。

我们用X表示句子序列，Y表示词性序列，如上图所示，你会觉得这个形状似曾相识，不错，这与上文投骰子的例子十分相似。在上图中，我们把X看作是可见状态链，Y看作是隐藏状态链，可以得出以下式子：
$P(x, y)=P(y) P(x \mid y)\tag{1}$P(x,y)=P(y)P(x∣y)(1)
其中
$\begin{aligned} P(y) &=P(P N \mid \text {start}) \\ & \times P(V \mid P N) \\ & \times P(D \mid V) \\ & \times P(N \mid D)\\ & \times P(\text {end} \mid N) \end{aligned}\tag{2}$P(y)​=P(PN∣start)×P(V∣PN)×P(D∣V)×P(N∣D)×P(end∣N)​(2)

$\begin{array}{c} P(x \mid y)=P(\text { John } \mid P N) \\ \times P(\text { saw } \mid V) \\ \quad \times P(\text { the } \mid D) \\ \quad \times P(\text { saw } \mid N) \end{array}\tag{3}$P(x∣y)=P( John ∣PN)×P( saw ∣V)×P( the ∣D)×P( saw ∣N)​(3)
从中总结公式：
$P(y)=P\left(y_{1} \mid \text {start}\right) \times \prod_{l=1}^{L-1} P\left(y_{l+1} \mid y_{l}\right) \times P\left(\text {end} \mid y_{L}\right)\tag{4}$P(y)=P(y1​∣start)×l=1∏L−1​P(yl+1​∣yl​)×P(end∣yL​)(4)

$P(x \mid y)=\prod_{l=1}^{L} P\left(x_{l} \mid y_{l}\right) \tag{5}$P(x∣y)=l=1∏L​P(xl​∣yl​)(5)

其中式（4)的P(y)称为转移概率，式（5）的P(x)称为发射概率。$P\left(y_{1} \mid \text {start}\right)$P(y1​∣start)表示开始时选择的第一个词性的几率；$\prod_{l=1}^{L-1} P\left(y_{l+1} \mid y_{l}\right)$∏l=1L−1​P(yl+1​∣yl​)表示可见状态链中间的转移概率；$P\left(\text {end} \mid y_{L}\right)$P(end∣yL​)表示最后一个词性在结尾的几率。$P\left(x_{l} \mid y_{l}\right)$P(xl​∣yl​)表示从词性$y_{l}$yl​中选择词语$x_{l}$xl​的几率。
将（4）、（5）代入（1）中：
$P(x, y)=P\left(y_{1} \mid \text {start}\right) \prod_{l=1}^{L-1} P\left(y_{l+1} \mid y_{l}\right){P\left(e n d \mid y_{L}\right)} \prod_{l=1}^{L} P\left(x_{l} \mid y_{l}\right)\tag{6}$P(x,y)=P(y1​∣start)l=1∏L−1​P(yl+1​∣yl​)P(end∣yL​)l=1∏L​P(xl​∣yl​)(6)
接下来的问题就是如何计算转移概率和发射概率了，实际上他们来自训练数据。

假设训练数据中已经标记了每个词的词性，那么式（6)中$P\left(y_{l+1} \mid y_{l}\right)$P(yl+1​∣yl​)求解如下：

$P\left(y_{l+1}=s^{\prime} \mid y_{l}=s\right)=\frac{\operatorname{count}\left(s \rightarrow s^{\prime}\right)}{\operatorname{count}(s)}\tag{7}$P(yl+1​=s′∣yl​=s)=count(s)count(s→s′)​(7)
$P\left(y_{l+1} \mid y_{l}\right)$P(yl+1​∣yl​)的值为$y_{l}$yl​后面出现$y_{l+1}$yl+1​的次数，除以$y_{l}$yl​的出现次数。
同理$P\left(x_{l} \mid y_{l}\right)$P(xl​∣yl​)的值如下：
$P\left(x_{l}=t \mid y_{l}=s\right)=\frac{\operatorname{count}(s \rightarrow t)}{\operatorname{count}(s)}\tag{8}$P(xl​=t∣yl​=s)=count(s)count(s→t)​(8)

3.2 HMM词性标记计算

本节介绍如何利用HMM模型进行词性序列的预测。
依然是上文的例子：

X为句子，式可见状态序列；Y是词性序列，是隐藏状态序列：

我们要做的事就是预测出Y。那么实际上就是计算在X序列条件下生成的Y序列中概率最大的Y序列：
$\begin{aligned} y &=\arg \max _{y \in Y} P(y \mid x) \\ &=\arg \max _{y \in Y} \frac{P(x, y)}{P(x)} \\ &=\arg \max _{y \in \mathbb{Y}} P(x, y) \end{aligned}\tag{9}$y​=argy∈Ymax​P(y∣x)=argy∈Ymax​P(x)P(x,y)​=argy∈Ymax​P(x,y)​(9)
即预测值为：
$\tilde{y}=\arg \max _{y \in \mathbb{Y}} P(x, y)\tag{10}$y~​=argy∈Ymax​P(x,y)(10)

3.3 预测问题（解码问题）

上文我们已经了解到了句子HMM词性预测的方法，那么，接下来的问题就是如何进行解码，即如何解$\tilde{y}=\arg \max _{y \in \mathbb{Y}} P(x, y)$y~​=argmaxy∈Y​P(x,y)，一般有两种方法，穷举和维特比算法(Viterbi algorthm)。显然，在数据量大的时候，简单且暴力的穷举法是不太可行的，使用维特比算法比较多，而维特比算法在本文的第一节已经有相关的介绍了。

4 HMM词性预测的缺点

根据公式（10）有，预测的概率值大于实际概率：
$(x, \hat{y}): P(x, \hat{y})>P(x, y)\tag{11}$(x,y^​):P(x,y^​)>P(x,y)(11)
那么会存在预测概率值最大的对应的词性并不是正确答案的现象出现，举个栗子：
转移概率和发射概率如下：

假设训练数据：

N后面跟V，由V生成单词c这样的数据有9条；P后跟V，由V生成单词a这样的数据有9条；
N后面跟D，由D生成单词a这样的数据有1条。现预测$y_{1}$y1​的值，在训练数据中，已经有N–>D–>>a，正确$y_{1}$y1​的值应该是D，而HMM会认为是V，因为N–>V出现了9次，V–>a出现了9次，因此HMM选择了V作为$y_{1}$y1​的值，“脑补”了新的序列。实际上产生这种现象的主要原因是，转移概率和发射概率是分开训练的，这也是HMM的明显的缺点。

本文主要根据自己的理解来写，如有问题欢迎指正！第三、四节参考李宏毅教授公开视频，感谢！