8.4_HMM-Part-of-Speech-Tagging.md

8.4 HMM 词性标注（HMM Part-of-Speech Tagging）

在这一节中，我们将会介绍我们的第一个序列标注算法，即隐马尔可夫模型（Hidden Markov Model），并展示如何将其应用于词性标注。简单回顾一下，一个序列标注器的任务是为序列中的每个单元分配一个标签，从而将一个观察序列（sequence of observations）映射到一个相同长度的标签序列。HMM 是一个经典模型，它引入了序列建模的许多关键概念，我们将在更多现代模型中再次看到这些概念。

HMM 是一个概率序列模型：给定一个单元序列（单词、字母、语素和句子等任何东西），它会计算所有可能的标签序列服从的概率分布，并选择最佳的那个标签序列。

8.4.1 马克可夫链（Markov Chains）

HMM 是一种加强版的马尔可夫链。马尔可夫链（Markov chain）模型可以告诉我们关于随机变量或者随机状态（states）序列的概率，其中每一个值都可以从一些集合中取。这些集合可以是词、标签，或者代表任何东西的符号，例如天气。马尔可夫链做了一个非常强的假设，即如果我们想预测该序列未来的某个状态，那么唯一重要的是当前状态。在当前状态之前的所有状态都对未来没有影响，只有当前状态会影响未来状态。这就好像要预测明天的天气一样，你可以根据今天的天气来预测，但你不能根据昨天的天气。

更正式地说，考虑一个状态变量序列 $q_1,q_2,\ldots,q_i$。马尔可夫模型关于这个序列的概率的马尔科夫假设（Markov assumption）体现在：当预测未来时，过去并不重要，只有现在才重要。

$$马尔可夫假设：P(q_i = a | q_1 \ldots q_{i-1}) = P(q_i = a | q_{i-1}) \tag{8.3}$$

图 8.8a 显示了一个马尔可夫链，用于为一个天气事件序列分配概率，其中的词汇表包括 HOT、COLD 和 WARM。图中的节点表示状态，而边表示状态转移及其概率。转移是一种概率：从一个状态出发的所有弧线的值的和必须为 1。图 8.8b 显示了一个用于给词序列 $w_1, \ldots, w_t$ 分配概率的马尔可夫链。这个马尔可夫链想必已经很熟悉了；事实上，它表示的是一个二元语言模型（bigram language model），每条边表示概率 $p(w_i|w_j)$。根据图 8.8 中的两个模型，我们可以给我们词汇表中的任何序列分配一个概率。

从形式上看，马尔可夫链是由以下部分组成的：

$Q = q_1 q_2 \ldots q_N$	$N$ 个状态（states）的集合
$A = a_{11} a_{12} \ldots a_{N1} \ldots a_{NN}$	转移概率矩阵（transition probability matrix）$A$，每一个 $a_{ij}$ 表示从状态 $i$ 转移到状态 $j$ 的概率，s.t. $\Sigma_{j=1}^{n} a_{ij} ; \forall{i}$
$\pi = \pi_1, \pi_2, \ldots, \pi_N$	状态所服从的初始概率分布（initial probability distribution），$\pi_i$ 表示马尔可夫链从状态 $i$ 开始的概率。一些状态 $j$ 可能有 $\pi_j = 0$，意味着它们不可能是初始状态。另外，$\Sigma_{i=1}^{N} \pi_i = 1$

在继续之前，请使用图 8.8a 中的样本概率（$\pi = [0.1, 0.7, 0.2]$）来计算以下每个序列的概率：

(8.4)
hot hot hot hot

(8.5)
cold hot cold hot

这些概率的差异告诉了你一个被编码在图 8.8a 中的关于真实世界的天气事实，那么这个事实是什么？

8.4.2 隐马尔可夫模型（The Hidden Markov Model）

当我们需要计算一个观察事件序列的概率时，马尔可夫链是很有用的。然而，在许多情况下，我们感兴趣的事件是隐藏的（hidden）：我们并不能直接观察它们。例如，我们不能直接观察到文本中的词性标签。相反，我们看到的是单词，并且必须从单词序列中推断出标签。我们称这些标签为隐藏的，因为它们没有被观察到。

隐马尔可夫模型（hidden Markov model）（HMM）同时支持可观察事件（如我们在输入中所看到的词）和我们认为在概率模型中具有因果关系的隐藏事件（如词性标签）。HMM 是由以下几个部分组成的：

$Q = q_1 q_2 \ldots q_N$	$N$ 个状态（states）的集合
$A = a_{11} a_{12} \ldots a_{N1} \ldots a_{NN}$	转移概率矩阵（transition probability matrix）$A$，每一个 $a_{ij}$ 表示从状态 $i$ 转移到状态 $j$ 的概率，s.t. $\Sigma_{j=1}^{n} a_{ij} ; \forall{i}$
$O = o_1 o_2 \ldots o_T$	由 $T$ 个观察值组成的序列，每个观察值都来自一个词汇表 $V = v_1, v_2, \ldots, v_V$
$B = b_i(o_t)$	观察值似然（likelihoods）序列，也称为发射概率（emission probabilities），每一个表示从状态 $q_i$ 产生观察值 $o_t$ 的概率
$\pi = \pi_1, \pi_2, \ldots, \pi_N$	状态所服从的初始概率分布（initial probability distribution），$\pi_i$ 表示马尔可夫链从状态 $i$ 开始的概率。一些状态 $j$ 可能有 $\pi_j = 0$，意味着它们不可能是初始状态。另外，$\Sigma_{i=1}^{N} \pi_i = 1$

一阶隐马尔可夫模型包含两个简化的假设。首先，与一阶马尔可夫链一样，一个特定状态的概率只取决于前一个状态：

$$马尔可夫假设：P(q_i | q_1 \ldots q_{i-1}) = P(q_i | q_{i-1}) \tag{8.6}$$

其次，一个输出观察值 $o_i$ 的概率只取决于产生该观察值的状态 $q_i$ ，而不取决于任何其他状态和其他观察值：

$$输出独立：P(o_i | q_1, \ldots, q_i, \ldots, q_T, o_1, \ldots, o_i, \ldots, o_T) = P(o_i | q_i) \tag{8.7}$$

8.4.3 HMM 标注器组件（The components of an HMM tagger）

让我们先看看 HMM 标注器的组成部分，然后再看如何用它来进行标注。一个 HMM 有两个组成部分，即概率 $A$ 和 $B$。

矩阵 $A$ 包含标签转移概率 $P(t_i|t_{i-1})$，表示在给定前一个标签的情况下，出现当前标签的概率。例如，情态动词后面很可能是一个基本形式的动词，即 VB，如 race，所以我们会期望这种概率会很高。我们通过统计一个标注语料库中第一个和第二个标签的出现次数，来计算这个转移概率的最大似然估计：

$$P(t_i|t_{i-1}) = \dfrac{C(t_{i-1}, t_i)}{C(t_{i-1})} \tag{8.8}$$

例如，在 WSJ 语料库中，MD 出现了 13124 次，其中后面跟着 VB 的情况出现了 10471 次，所以其 MLE 估计为

$$P(VB|MD) = \dfrac{C(MD, VB)}{C(MD)}=\dfrac{10471}{13124}=0.80 \tag{8.9}$$

让我们先通过一个标注任务例子看看这些概率是如何被估计和使用的，然后我们再回到解码算法。

在 HMM 标注中，概率是通过统计标注训练语料库来估计的。在这个例子中，我们将使用标注好的 WSJ 语料库。

发射概率 $B$，$P(w_i|t_i)$，表示给定一个标签（例如 MD），其对应词是某个给定词（如 will）的概率。该发射概率的 MLE 是

$$P(w_i|t_i) = \dfrac{C(t_i, w_i)}{C(t_i)} \tag{8.10}$$

在 WSJ 语料库中出现的 13124 次 MD 中，其对应词是 will 的有 4046次：

$$P(will|MD) = \dfrac{C(MD, will)}{C(MD)}=\dfrac{4046}{13124}=0.31 \tag{8.11}$$

我们在第四章中见过这种贝叶斯模型；请记住，这个似然项不是在问“will 这个词最可能的标签是什么？” 那将是后验概率 $P(MD|will)$。相反，$P(will|MD)$ 回答的是一个略显反常的问题：“如果我们要生成一个 MD，那么这个情态动词有多大可能是 will？”

图 8.9 表示有着 3 个状态（译者注：VB、MD、NN，即词性标签，观察值 $o_i$ 指的是词，如 will）的 HMM 标注器，解释了 HMM 的转移概率 $A$和观察值似然 $B$。完整的标注器对每个标签都有一个状态。

8.4.4 HMM 标注的解码部分（HMM tagging as decoding）

对于任何包含隐变量的模型，如 HMM，确定与观察值序列相对应的隐变量序列的任务被称为解码（decoding）。更正式来说：

解码：给定一个 HMM $\lambda = (A, B)$ 和一个观察值序列 $O = o_1, o_2, \ldots, o_T$ 作为输入，找出最有可能的状态序列 $Q = q_1 q_2 q_3 \ldots q_T$。

对于词性标注，HMM 解码的目标给定 $n$ 个词的序列 $w_1 \ldots w_n$，选择最有可能的标签序列 $t_1 \ldots t_n$：

$$\hat{t}{1:n} = \argmax{t_1 \ldots t_n} P(t_1 \ldots t_n | w_1 \ldots w_n) \tag{8.12}$$

我们在 HMM 中实际会使用贝叶斯法则来计算：

$$\hat{t}{1:n} = \argmax{t_1 \ldots t_n} \dfrac{P(w_1 \ldots w_n | t_1 \ldots t_n) P(t_1 \ldots t_n)}{P(w_1 \ldots w_n)} \tag{8.13}$$

此外，我们继续简化公式 8.13，直接去掉分母 $P(w_1^n)$：

$$\hat{t}{1:n} = \argmax{t_1 \ldots t_n} P(w_1 \ldots w_n | t_1 \ldots t_n) P(t_1 \ldots t_n) \tag{8.14}$$

HMM 标注器又做了两个简化假设。第一个假设是，一个词出现的概率只取决于它自己的标签，而与邻近的词和标签都无关：

$$P(w_1 \ldots w_n | t_1 \ldots t_n) \approx \prod_{i=1}^n P(w_i | t_i) \tag{8.15}$$

第二个假设，即 bigram 二元假设，指一个标签的概率只取决于前一个标签，而不是整个标签序列：

$$P(t_1 \ldots t_n) \approx \prod_{i=1}^n P(t_i | t_{i-1}) \tag{8.16}$$

将公式 8.15 和公式 8.16 代入公式 8.14 中，得到以下用于计算二元标注器下最有可能的标签序列的公式：

$$\hat{t}{1:n} = \argmax{t_1 \ldots t_n} P(t_1 \ldots t_n | w_1 \ldots w_n) \approx \argmax_{t_1 \ldots t_n} \prod_{i=1}^n \overbrace{P(w_i|t_i)}^{发射概率} \overbrace{P(t_i|t_{i-1})}^{转移概率} \tag{8.17}$$

公式 8.17 的两部分正好对应于我们刚才定义的发射概率 $B$ 和转移概率 $A$！

8.4.5 维特比算法（The Viterbi Algorithm）

HMM 的解码算法是如图 8.10 所示的维特比（Viterbi）算法。作为动态规划的一个例子，Viterbi 算法类似于第二章的动态规划最小编辑距离算法。

Viterbi 算法首先建立一个概率矩阵或者叫网格（lattice），其中每列为每个观察值 $o_t$，每行为状态图中的每个状态。因此，在单个组合自动机（single combined automaton）中，每列（观察值）对于每个状态 $q_i$ 都有一个单元格。图 8.11 显示了 Janet will back the bill 这个句子对应的网格 lattice。

网格中的每个单元格，$v_t(j)$，表示给定的 HMM $\lambda$ 在“看到”前 $t$ 个观测值，并通过最可能的状态序列 $q_1, \ldots, q_{t-1}$ 后，处于状态 $j$ 的概率。每个单元格 $v_t(j)$ 的值都是通过递归的方式计算的，即每次都取到达该单元格的最可能的路径（译者注：贪心？）。从形式上看，每个单元格表示的概率是

$$v_t(j) = \max_{q_1, \ldots, q_{t-1}} P(q1 \ldots q_{t-1}, o_1, o_2 \ldots o_t, q_t = j | \lambda) \tag{8.18}$$

译者注：注意 HMM $\lambda = (A, B)$，其中 $A$ 为状态转移概率 $P(q_i | q_{i-1})$，$B$ 为发射概率 $P(o_t | q_i)$。在词性标注中，观察值 $o$ 就是词，状态 $q$ 就是词性标签。

我们通过在前面所有可能的状态序列中取最大值 $\max_{q_1, \ldots, q_{t-1}}$ 来表示最可能的路径。像其他动态规划算法一样，Viterbi 算法递归地填充每个单元格。鉴于我们已经计算出了在时间 $t-1$ 时处于每个状态的概率，所以我们可以取到达当前单元格的所有扩展路径中的概率最大值作为当前时间 $t$ 的概率值。对于在时间 $t$ 时的给定状态 $q_j$，其值 $v_t(j)$ 的计算方法是

$$v_t(j) = \max_{i=1}^N v_{t-1}(i) a_{ij} b_j(o_t) \tag{8.19}$$

在公式 8.19 中，三个相乘的因子分别是

$v_{t-1}(i)$	前一个时刻的前一个 Viterbi 路径概率
$a_{ij}$	前一个状态 $q_i$ 到当前状态 $q_j$ 的转移概率
$b_j(o_t)$	给定当前状态 $j$，观察值 $o_t$ 的状态观察值似然

8.4.6 例子（Working through an example）

下面我们以标注句子 Janet will back the bill 为例，目标是得到正确的标签序列（另见图 8.11）：

(8.20)
Janet/NNP will/MD back/VB the/DT bill/NN

假设我们的 HMM 由图 8.12 和 8.13 中的两个表来定义。图 8.12 列出了隐藏状态（词性标签）之间相互转换的概率 $a_{ij}$。图 8.13 表示 $b_i(o_t)$ 概率，即给定标签时观察值的似然。这个（稍微简化的）表格数据来自对 WSJ 语料库中的统计。因此，Janet 这个词只作为 NNP 出现，back 有4个可能的词性，而 the 这个词既可以作为定语，也可以作为 NNP 出现（在“Somewhere Over the Rainbow”这样的标题中，所有词都被标注为 NNP）。

图 8.14 是图 8.11 的详细版本，即用于计算观察值序列“Janet will back the bill”的最佳隐藏状态序列的 Viterbi 网格。

有 $N=5$ 个状态列。我们从第 1 列（对应于词 Janet）开始，将每个单元格的 Viterbi 值设置为转移概率 $\pi$（状态 $i$ 的初始概率，我们可以从图 8.12 的 <s> 项中得到），与给定该单元格标签时词 Janet 的观察值似然的乘积。这一列中的大部分单元格都是零，因为 Janet 这个词不可能是这些标签中的任何一个。读者应该可以在图 8.14 中看到这一点。

接下来，更新 will 列中的每个单元格。对于每个状态，我们根据公式 8.19 来计算 $viterbi[s,t]$，取前一列中通往当前单元的所有路径的扩展值的最大值。我们已经给出了 MD、VB 和 NN 单元格的值。每个单元格都取前一列 7 个单元格的最大值，再乘以相应的转移概率；在这个例子中，它们中的大多数都是零。然后再乘以相应的观察值概率，并取其中最大值。在这个例子中，最终的数值（译者注：即最大值），2.772e-8，来自前一列的 NNP 状态。读者可以继续完成图 8.14 中剩余的单元格，并回溯看看 Viterbi 算法是否返回了正确的状态序列 NNP MD VB DT NN。

译者注：说白了，就是前一列所有单元格的值，分别乘以相应的标签转移概率，取最大值，再乘上相应的发射概率。为什么公式 8.19 是先乘发射概率再取最大值的？两种方法是一样的，因为发射概率是固定的，可以提出来。

特别注意：虽然上面提到 $N=5$ 即 5 个状态列（state columns），但是这个 $N$ 和公式 8.19 中的 $N$ 是不同的。在这个例子中，公式 8.19 中的 $N$ 是 7，即有 7 个状态（词性标签）。所以该公式中，$i$ 和 $j$ 都指的是状态（词性标签），而 $t$ 指的是观察值（词）。