Michael Collins NLP Lecture 3

课程主页：http://www.cs.columbia.edu/~cs4705/

课程网盘地址：

链接：https://pan.baidu.com/s/1KijgO7yjL_MVCC9zKZ7Jdg
提取码：t1i3

这一讲主要介绍了标注问题和隐马尔可夫模型。

Chapter 2 标注问题和隐马尔可夫模型

2.1 介绍

在许多NLP问题中，我们希望对序列对进行建模。词性（POS）标注可能是此类问题中最早，最著名的例子。 在POS标注中，我们的目标是建立一个模型，其输入为句子，例如

$$\text{the dog saw a cat}$$

其输出是标注序列

$$\begin{eqnarray*} \text{D N V D N}\tag{2.1} \end{eqnarray*}$$

（这里我们使用D表示定冠词，N表示名词，V表示动词）。标签序列与输入句子的长度相同，因此为句子中的每个单词指定一个标签（在本例中D标注the，N标注dog，V标注saw，依此类推）。

​ 我们将使用$x_1…x_n$来表示标注模型的输入：将其称为句子。在上面的例子中，我们的长度为$n=5$并且

$$x_1 =\text{the}，x_2 =\text{ dog}，x_3 = \text{saw}，x_4 = \text{the}，x_5 = \text{cat}$$

我们使用$y_1…y_n$来表示标注模型的输出：我们经常将其称为状态序列或标注序列。 在上面的例子中，我们有$y_1=\text{D},y_2= \text{N},y_3=\text{V}$，依此类推。

​ 这种类型的问题，其任务是将句子$x_1…x_n$映射到标签序列$y_1…y_n$，通常被称为序列标签问题或标注问题。来看一个具体例子：

​ 我们假设我们有一组训练样本，$(x^{(i)},y^{(i)}), i=1…m$，其中每个$x^{(i)}$是句子$x^{(i)}_1…x^{(i)}_{n_i}$，并且每个$y^{(i)}$是标签序列$y^{(i)}_1…y^{(i)}_{n_i}$（我们假设第$i$个样本具有长度$n_i$）。 因此，$x^{(i)}_j$是第$i$个训练样本中的第$j$个单词，$y^{(i)}_j$是该单词的标注。 我们的任务是学习一个函数，它将训练样本中的句子映射到对应的标签序列。

2.2 两个标注问题的例子：词性标注和命名实体识别

我们首先讨论NLP中标注问题的两个重要例子，词性（POS）标注和命名实体识别。

​ 图2.1给出了一个词性问题的例子。 问题的输入是一个句子。 输出是带标注的句子，其中句子中的每个单词都用其词性标注。 我们的目标是构建一个能够高精度地恢复句子POS标签的模型。 POS标注是NLP中最基本的问题之一，在许多自然语言问题中都很有用。

​ 假设我们有一组训练样本：也就是说，我们有一组句子以及对应的正确POS标签序列。 作为一个示例，宾州树语料库包含大约$100$万个单词（大约$40,000$个句子）以及对应的POS标签。

​ POS标注的主要挑战之一是歧义性。 英语中的许多单词可以采用几种可能的词性——对于许多其他语言也是如此。 图2.1中的例句有几个含糊不清的词。 例如，句子中的第一个词，profits，在这种情况下是名词，但也可以是动词（例如，in the company profits from its endeavors）。 单词topping在这个特定句子中的动词，但也可以是名词（例如the topping on the cake，）。 forecasts和results这两个词在句子中都是名词，但也可以是其他语境中的动词。 如果我们进一步观察，我们会看到该句子中的quarter是一个名词，但它也可以作为一个动词（只是使用频率低很多）。从这个例句我们可以看出，词性歧义性数量多的令人惊讶。

​ 第二个挑战是存在罕见的单词，特别是在我们的训练样例中没有看到的单词。 即使训练数据有一百万个单词，新的句子中也会有很多单词在训练数据中没有出现过。 作为一个例子，诸如Mulally或topping之类的词语可能非常罕见，并且可能在我们的训练样例中未见过。 开发有效处理训练数据中未见过的单词的方法非常重要。

​ 在恢复POS标签时，考虑两种不同的信息来源是有用的。 首先，单个单词对其词性具有统计偏好：例如，quarter可以是名词或动词，但更可能是名词。 其次，语境对单词的词性有重要影响。 特别是，一些POS标签序列比其他序列更可能。 如果我们考虑POS三元组，序列D N V将在英语中频繁出现（例如，the/D dog/N saw/V)，而序列D V N则不太可能出现。

​ 有时这两种来源的信息是冲突的：例如，在句子中

$$\text{The trash can is hard to find}$$

can的词性是名词——但是，也可以是一个语气动词，事实上它更常被看作英语中的一个语气动词。在这句话中，语境已经覆盖了可以成为动词而不是名词的倾向。

​ 在本章的后面，我们将描述标注问题的模型，该模型在制定标注决策时同时考虑了局部和上下文两种信息来源。

​ 第二个重要的示例标注问题是命名实体识别。 图2.2给出了一个例子。 对于这个问题，输入又是一个句子。 输出是标有实体边界的句子。 在此示例中，我们假设有三种可能的实体类型：PERSON，LOCATION和COMPANY。 本例中的输出表明波音公司是一家公司，华尔街是一个地方，艾伦·穆拉利是一个人。 认识到诸如人，地点和组织等实体有许多应用，并且命名实体识别已经在NLP领域中被广泛研究。

​ 乍一看，命名实体问题与标注问题不同——在图2.2中，输出不包含句子中每个单词的标注。 但是，将命名实体识别映射到标注问题是很简单的。 基本方法如图2.3所示。 句子中的每个单词要么被标注为不是实体的一部分（标签NA），要么作为特定实体类型的开始（例如，标签SC对应Start Company），或作为特定实体类型的延续（例如，标签CC对应Continue Company）。

​

2.3 生成模型(Generative Models)和噪声信道模型(The Noisy Channel Model)

在本章中，我们将标注问题视为监督学习问题。 在本节中，我们描述了一种用于监督学习的重要模型：生成模型。 然后我们将继续描述一种特定类型的生成模型，隐马尔可夫模型，应用于标注问题。

​ 监督学习问题的设置如下。 我们假设训练样本为$(x^{(1)},y^{(1)})…(x^{(m)},y^{(m)})$，其中每个样本包括输入$x^{(i)}$和标签$y^{(i)} $。 我们使用$\mathcal X$来表示可能的输入集合，使用$\mathcal Y$来表示可能的标签集合。 我们的任务是学习将$x$映射到标签$f(x)$的函数$f:\mathcal X \to \mathcal Y$。

​ 自然语言处理中的许多问题是监督学习问题。例如，在标注问题时，每个$x^{(i)}$是单词序列$x^{(i)}_1…x^{(i)}_{n_i}$，并且每个$y^{(i)}$将是标签序列$y^{(i)}_1…y^{(i)}_{n_i}$（我们使用$n_i$来指代第$i$个训练样本的长度）。 $\mathcal X$表示所有序列$x_1…x_n$，$\mathcal Y$表示所有标注序列$y_1…y_n$。我们的任务是学习函数$f:\mathcal X \to \mathcal Y$将句子映射到标签序列。在机器翻译中，每个输入$x$将是源语言中的句子（例如，中文），并且每个“标签”将是目标语言中的句子（例如，英语）。在语音识别中，每个输入将是一些对话的记录——例如可能使用傅立叶变换进行预处理——并且每个标签是整个句子。我们在所有这些例子中的任务是利用$(x^{(i)},y^{(i)}),i=1…n$来学习从输入$x$到标签$y$的函数。

​ 定义函数$f(x)$的一种方法是通过条件概率模型。 在这种方法中，我们定义了一个模型，该模型对任意$(x,y)$定义了条件概率

$$p(y|x)$$

模型的参数根据训练样本来估计。 给定一个新的测试样本$x$，模型的输出是

$$f(x) =\arg \max_{y\in \mathcal Y} p(y|x)$$

因此，我们简单地将最可能的标签$y$作为模型的输出。 如果我们的模型$p(y|x)$接近给定输入的真实条件分布，则函数$f(x)$将接近最优解。

​ 通常用于机器学习和自然语言处理的生成模型是另一个选择。 在生成模型中，我们不是直接估计条件分布$p(y|x)$，而是对$( x,y)$的联合概率建模

$$p(x,y)$$

模型$p(x,y)$的参数从训练样本$(x^{(i)},y^{(i)}),i=1…n$中估计。 在许多情况下，我们按如下方式分解概率$p(x,y)$：

$$\begin{eqnarray*} p(x,y)= p(y)|p(x|y) \tag{2.2} \end{eqnarray*}$$

然后分别估计模型$p(y)$和$p(x|y)$。 这两个模型具有以下解释：

• $p(y)$是标签$y$的先验分布
• $p(x|y)$是个给定标签$y$，输出$x$的概率

我们将看到，在许多情况下以这种方式分解模型非常方便；例如，语音识别的经典方法基于这种类型的分解。

​ 给定生成模型，我们可以使用贝叶斯法则来推导任何$(x,y)$的条件概率$p(y|x)$：

$$p(y|x)= \frac {p(y)p(x|y)}{p(x)}$$

其中

$$p(x) =\sum_{y\in \mathcal Y} p(x,y)= \sum_{y\in \mathcal Y} p(y) p(x|y)$$

因此，联合概率模型非常通用，这是因为我们也可以推导出概率$p(x)$和$p(y|x)$。

​ 我们在将联合模型应用于新的测试样本时直接使用贝叶斯法则。 给定输入$x$，我们模型的输出$f(x)$可以按如下方式推导：

$$\begin{eqnarray*} f(x) &&=\arg \max_y p(y|x)\\ &&=\arg \max_y \frac {p(y)p(x|y)}{p(x)} \tag{2.3}\\ &&=\arg \max_y {p(y)p(x|y)} \tag{2.4} \end{eqnarray*}$$

公式 2.3遵循贝叶斯法则。公式2.4成立因为分母$p(x)$不依赖于$y$，因此不会影响$\arg \max$。 这很方便，因为这意味着我们不需要计算$p(x)$，而这可能是一项计算量很大的操作。

​ 将联合概率分布分解为$p(y)$和$p(x|y)$项的模型通常称为噪声信道模型(noisy-channel models)。 直观地，当我们看到测试样本$y$时，我们假设数据是分两步生成的：首先，选择标签$y$的概率为$p(y)$； 第二，样本$x$从分布$p(x|y)$生成。 模型$p(x|y)$可以解释为“通道”，它以标签$y$作为输入，并以$x$作为其输出。 我们的任务是给定观测到的$x$，找到最可能的标签$y$。

​ 综上所述：

• 我们的任务是学习从输入$x$映射到标签$y=f(x)$的函数。 我们假设训练样本为$(x^{(i)},y^{(i)}),i=1…n$

• 在噪声信道(noisy channel)方法中，我们使用训练样本来估计模型$p(y)$和$p(x|y)$。 这些模型定义了一个联合（生成）模型

  $$p(x,y)= p(y) p(x|y)$$

• 给定一个新的测试样本$x$，我们预测标签

  $$f(x) =\arg \max_{y\in \mathcal Y} p(y|x)$$

  找到输入$x$的输出$f(x)$通常被称为解码问题。

2.4 生成标注模型

我们现在看看如何将生成模型应用于标注问题。 我们假设我们有一个有限的词汇表$\mathcal V$，例如$\mathcal V$可能是英语中的一组单词，例如$\mathcal V = \{the，dog，saw，cat，laughs\}$。 我们用$\mathcal K$来表示可能的标签集；再次，我们假设这个集合是有限的。 然后我们给出以下定义：

定义 1 (生成标注模型)

假设一组有限的词汇表$\mathcal V$和一组有限的标签$\mathcal K$。将$\mathcal S$定义为所有序列/标签——序列对$\langle x_1…x_n,y_1…y_n \rangle$，它满足$n\ge 0,x_i \in \mathcal V,i=1…n$以及$y_i \in \mathcal K,i=1…n$。生成标注模型是函数$p$，它满足：

• 1.对任意$\langle x_1…x_n,y_1…y_n \rangle\in S$

  $$p( x_1...x_n,y_1...y_n)\ge 0$$

• 2.此外，

  $$\sum_{\langle x_1...x_n,y_1...y_n \rangle\in S}p( x_1...x_n,y_1...y_n) =1$$

因此，$p( x_1…x_n,y_1…y_n)$是序列对上的概率分布（即，集合$\mathcal S$上的概率分布）。

​ 给定生成标注模型，从句子$x_1…x_n$到标注序列$y_1…y_n$的函数定义为

$$f(x_1...x_n) =\arg \max_{y_1...y_n} p( x_1...x_n,y_1...y_n)$$

其中$\arg \max$是所作用的范围是所有$y_i \in \mathcal K，i\in \{1…n\}$的序列。 因此，对于任何输入$x_1…x_n$，我们将最高概率标签序列作为模型的输出。

​ 引入生成标注模型后，有三个关键问题:

• 我们如何定义生成标注模型$p( x_1…x_n,y_1…y_n)$？

• 我们如何从训练样本中估计模型的参数？

• 对于任意输入$x_1…x_n$，我们如何有效地找到

  $$\arg \max_{y_1...y_n} p( x_1...x_n,y_1...y_n)$$

下一节将介绍如何使用三元隐马尔可夫模型来回答这三个问题。

2.5 三元隐马尔可夫模型(Trigram HMMs)

在本节中，我们将介绍了一种重要的生成标注模型，三元隐马尔可夫模型，描述了如何从训练样本中估计模型的参数，并描述如何为任何句子找到最可能的标签序列。

2.5.1 三元隐马尔可夫模型的定义

我们现在将给出三元隐马尔可夫模型（Trigram HMMs）的正式定义。下一节将展示这种模型是如何推导的，并给出模型背后的一些直觉。

定义 2 (三元隐马尔可夫模型(Trigram HMMs))

一个三元隐马尔可夫模型由表示词汇表的有限集合$\mathcal V$和表示标签的有限集合$\mathcal K $以及以下参数组成：

• 对任何满足 $$s\in \mathcal K \bigcup \{ \text{STOP}\}以及u,v\in K \bigcup\{*\}$$

的三元组$(u,v,s)$，定义参数

$$q(s|u,v)$$

该参数的值可以解释为在标签二元组$(u,v )$之后立即看到标签$s$的概率。

• 对任意 $$x\in \mathcal V,s\in \mathcal K$$ 定义参数 $$e(x|s)$$ $e(x|s)$的值可以解释为观测值$x$与状态$s$配对的概率。

​ 将$\mathcal S$定义为所有序列/标签——序列对$\langle x_1…x_n,y_1…y_n \rangle$的集合，序列对满足$n\ge 0,x_i \in \mathcal V,i=1…n$，$y_i \in \mathcal K,i=1…n$并且$y_{n+1}=\text{STOP}$。

​ 然后我们定义任何$\langle x_1…x_n,y_1…y_{n+1} \rangle\in \mathcal S$的概率为

$$p( x_1...x_n,y_1...y_{n+1})=\prod_{i=1}^{n+1}q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^n e(x_i|y_i)$$

这里我们假设

$$y_0= y_{-1}= *$$

​ 举个例子，如果我们有$n=3$，$x_1…x_3$等the dog laughs，而$y_1…y_4$等于标签序列D N V STOP，那么

$$\begin{aligned} p( x_1...x_n,y_1...y_n) =& q(\text{D} |*, *) \times q(\text{N} |*, \text{D})\times q(\text{V} |\text{D},\text{N})\times q(\text{STOP}|\text{N}, \text{V}) \\ &\times e(\text{the}|\text{ D})\times e(\text{dog}|\text{ N})\times e(\text{laughs}|\text{ V}) \end{aligned}$$

​ 请注意，此模型形式是噪声通道模型。 如下乘积

$$q(\text{D} |*, *) \times q(\text{N} |*, \text{D})\times q(\text{V} |\text{D},\text{N})\times q(\text{STOP}|\text{N}, \text{V})$$

是标签序列D N V STOP的先验概率，这里我们利用了二阶马尔可夫模型（三元模型），非常类似于我们在前一讲中得到的语言模型。如下乘积

$$e(\text{the}|\text{ D})\times e(\text{dog}|\text{ N})\times e(\text{laughs}|\text{ V})$$

可以解释为条件概率$p(\text{the dog laughs}|\text{D N V STOP})$：即条件概率$p(x|y)$，其中$x$是句子the dog laughs，$y$是标签序列D N V STOP。

​

2.5.2 三元隐马尔可夫模型的独立假设

我们现在描述如何导出三元隐马尔可夫模型：特别的，我们描述了在模型中做出的独立性假设。 考虑一对随机变量序列$X_1…X_n$和$Y_1…Y_n$，其中$n$是序列的长度。 我们假设每个$X_i$可以在有限集合$\mathcal V $中取任何值。 例如，$\mathcal V $可能是英语单词，例如$\mathcal V = \{the，dog，saw，cat，laughs\}$。 每个$Y_i$可以在有限集合$\mathcal K$中取任何值。 例如，$\mathcal K$是用于英语的可能的词性标签的集合，例如， $K = \{\text{D},\text{N},\text{V}… \}$。

​ 长度$n$本身是一个随机变量——即它可以在不同的句子中变化，我们将使用类似构建可变长马尔可夫过程的方法。

​ 我们的任务是对于任何观察序列$x_1…x_n$与状态序列$y_1…y_n$模拟联合概率

$$P(X_1=x_1...X_n =x_n,Y_1= y_1...Y_n=y_n)$$

其中每个$x_i$是$\mathcal V$的成员，并且每个$y_i$是$\mathcal K$的成员。

​ 我们将发现定义一个额外的随机变量$Y_{n+1}$会很方便，它的值总是STOP。 这将与可变长马尔可夫序列中看到的STOP符号起类似作用，如之前的讲义中所述。

​ 隐马尔可夫模型的关键思想是以下定义：

$$\begin{eqnarray*} &&P(X_1=x_1...X_n =x_n,Y_1= y_1...Y_{n+1}=y_{n+1}) \\ =&& \prod_{i=1}^{n+1}P(Y_i=y_i|Y_{i-2}=y_{i-2},Y_{i-1}=y_{i-1}) \prod_{i=1}^nP(X_i=x_i|Y_i=y_i) \tag{2.5} \end{eqnarray*}$$

其中

$$y_0= y_{-1}= *$$

*是特殊的开始符号。

​ 注意上式和我们对三元隐马尔可夫模型的定义的相似性。 在三元HMM中，我们假设联合概率如公式2.5所示，此外我们假设对于任何$i$以及任意$y_{i-2},y_{i-1},y_i$，

$$P(Y_i=y_i|Y_{i-2}=y_{i-2},Y_{i-1}=y_{i-1}) = q(y_i|y_{i-2},y_{i-1})$$

以及对于任何$i$以及任意$x_i,y_i$

$$P(X_i=x_i|Y_i=y_i) =e(x_i|y_i)$$

​ 我们现在描述公式2.5是如何推导出来的，特别地，我们将关注模型中的独立假设。 首先，我们可以将联合概率写为

$$\begin{eqnarray*} &&P(X_1=x_1...X_n =x_n,Y_1= y_1...Y_{n+1}=y_{n+1}) \\ =&&P(Y_1= y_1...Y_{n+1}=y_{n+1}) \times P(X_1=x_1...X_n =x_n|Y_1= y_1...Y_{n+1}=y_{n+1}) \tag{2.6} \end{eqnarray*}$$

根据条件概率的定义，这一步是准确的。 因此，我们将联合概率分解为两个部分：第一个部分为选择标注序列$y_1…y_{n+1}$的概率；第二个部分为给定标签序列，选择单词序列$x_1… x_n$的概率。 请注意，这与噪声通道模型中的分解类型完全相同。

​ 现在考虑看到标签序列$y_1…y_{n+1}$的概率。 我们作出如下的独立假设：我们假设对于任何序列$y_1…y_{n+1}$，

$$P(Y_1= y_1...Y_{n+1}=y_{n+1}) = \prod_{i=1}^{n+1}P(Y_i=y_i|Y_{i-2}=y_{i-2},Y_{i-1}=y_{i-1})$$

也就是说，我们假设序列$Y_1…Y_{n+1}$是二阶马尔可夫序列，即每个状态仅取决于序列中的前两个状态。

​ 接下来，考虑给定标签序列，选择单词序列$x_1…x_n$的概率。 我们做出以下假设：

$$\begin{eqnarray*} &&P(X_1=x_1...X_n =x_n|Y_1= y_1...Y_{n+1}=y_{n+1}) \\ =&& \prod_{i=1}^n P(X_i =x_i|X_1=x_1...X_{i-1}=x_{i-1},Y_1=y_1 ...Y_{n+1}=y_{n+1}) \\ =&&\prod_{i=1}^n P(X_i =x_i|Y_i =y_i) \tag{2.7} \end{eqnarray*}$$

由链式法则，上述推导的第一步是准确的。 第二步涉及独立性假设，即对于$i=1…n$，

$$P(X_i =x_i|X_1=x_1...X_{i-1}=x_{i-1},Y_1=y_1 ...Y_{n+1}=y_{n+1}) = P(X_i =x_i|Y_i =y_i)$$

因此，我们假设随机变量$X_i$的值仅取决于$Y_i$的值。 更正式地说，给定$Y_i$的值，$X_i $的值条件独立于先前的观测值$X_1…X_{i-1}$，以及其他状态的值$Y_1…Y_{i-1}Y_{i+1}…Y_n$。

​ 考虑这个模型的一种有用的方法是考虑以下产生序列对$y_1…y_{n+1},x_1…x_n$的随机过程：

• 1.初始化$i=1$，以及

  $$y_0 =y_{-1}=*$$

• 2.从如下分布中生成$y_i$

  $$q(y_i|y_{i-2},y_{i-1})$$

• 3.如果$y_i =\text{STOP}$，那么返回$y_1…y_{i},x_1…x_{i-1}$。否则，从如下分布中产生$x_i$

  $$e(x_i|y_i)$$

  令$i=i+1$，返回步骤2

2.5.3 估计三元隐马尔可夫模型的参数

假设我们有一些训练数据。 训练数据由一组样本构成，其中每个样本是句子$x_1…x_n $与标签序列$y_1…y_n$。 给定这些数据，我们如何估计模型的参数？ 我们将看到这个问题有一个简单而直观的答案。

​ 将$c(u,v,s)$定义为在训练数据中看到三个状态序列$(u,v,s)$的次数：例如，$c(\text{V,D,N})$是训练语料库中标签序列V，D，N出现的次数。 类似地，将$c(u,v)$定义为看到标签二元组$(u,v)$的次数。 将$c(s)$定义为在语料库中看到状态$s$的次数。 最后，将$c(s\leadsto x)$定义为语料库中状态$s$和观测值$x$同时出现的次数：例如，$c(\text{ N}\leadsto \text{dog})$将是看到与单词dog的标签为N的次数。

​ 根据上述定义，最大似然估计是

$$q(s|u,v)= \frac{c(u,v,s)}{c(u,v)}$$

以及

$$e(x|s) = \frac{c(s\leadsto x)}{c(s)}$$

例如，我们将有估计

$$q(\text{N}|\text{V,D}) =\frac{c(\text{V,D,N})}{c(\text{V,D})}$$

以及

$$e(\text{dog}|\text{N})=\frac{c(\text{N}\leadsto \text{dog})}{c(\text{N})}$$

因此，估计模型的参数很简单：我们只是从训练语料库中读取计数，然后如上所述计算最大似然估计。

​ 在某些情况下，使用第一章描述的技术来平滑我们对$q(s|u,v)$的估计是有用的。 例如定义

$$q(s|u,v) =\lambda_1 \times q_{ML}(s|u,v)+\lambda_2\times q_{ML}(s|v)+ \lambda_3 \times q_{ML}(s)$$

其中$q_{ML}$项是从语料库中的计数得出的最大似然估计，$\lambda_1,\lambda_2,\lambda_3$平滑参数，满足

$$\lambda_1\ge 0,\lambda_2\ge 0,\lambda_3 \ge 0\\ \lambda_1+\lambda_2+\lambda_3=1$$

​ 这些估计的一个问题是，如果单词$x$出现的不频繁，则$e(x|s)$的值将是不可靠的：更糟糕的是，如果在训练数据中没有看到单词$x$，则我们有$e(x|s)=0$。 第2.7.1节描述了该问题的解决方案。

2.5.4 对HMM解码：维特比算法

我们现在转向查找输入句子$x_1…x_n $的最可能的标注序列的问题。 该问题为找到

$$\arg\max _{y_1...y_{n+1}} p( x_1...x_n,y_1...y_{n+1})$$

其中$\arg \max$所作用的范围是所有$y_i \in \mathcal K，i=1…n$以及$y_{n+1}=\text{STOP }$的序列。 我们假设$p$有如下形式

$$\begin{eqnarray*} p( x_1...x_n,y_1...y_{n+1})=\prod_{i=1}^{n+1}q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^n e(x_i|y_i) \tag{2.8} \end{eqnarray*}$$

回想一下，我们在这个定义中假设

$$y_0=y_{-1}=*$$

以及

$$y_{n + 1} =\text{ STOP}$$

​ 解决该问题的蛮力算法为简单地枚举所有可能的标签序列$y_1…y_{n+1}$，然后在函数$p$下对它们进行评分，并获得最高的评分序列。 例如，给定输入句子

$$\text{the dog barks}$$

并假设可能的标签集是$\mathcal K = \{\text{D,N,V}\}$，我们会考虑所有可能的标签序列：

$$\begin{aligned} \text{D} && \text{D}&&\text{D} && \text{STOP} \\ \text{D} && \text{D}&&\text{N} && \text{STOP}\\ \text{D} && \text{D}&&\text{V} && \text{STOP} \\ \text{D} && \text{N}&&\text{D} && \text{STOP}\\ \text{D} && \text{N}&&\text{N} && \text{STOP}\\ \text{D} && \text{N}&&\text{V} && \text{STOP}\\ ... \end{aligned}$$

在这种情况下，有$3^3=27$个可能的序列。

​ 然而，对于较长的句子，这种方法的效率非常低下。 对于长度为$n$的输入句子，存在$|\mathcal K|^n$种可能的标签序列。 关于于长度$n$的指数增长意味着对于任何合理长度的句子，蛮力搜索将不易处理。

基本算法

相反，我们可以使用通常称为维特比算法的动态规划算法有效地找到最高概率对应的标签序列。算法的输入是句子$x_1…x_n$。 给定这个句子，对于任何$k\in \{1…n\}$，对于任意满足

$$y_i \in \mathcal K,i=1...k\\ y_0=y_{-1}=*$$

的序列$y_{-1},y_0,y_1…y_k$，我们定义函数

$$\begin{eqnarray*} r(y_{-1},y_0,y_1...y_k) =\prod_{i=1}^k q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^k e(x_i|y_i) \tag{2.9} \end{eqnarray*}$$

这只是公式2.8定义的$p$的截断版本，这里我们只考虑前$k$项。特别的，注意到

$$\begin{eqnarray*} p( x_1...x_n,y_1...y_{n+1}) &&=r(*,*,y_1...y_n)\times q(y_{n+1}|y_{n-1},y_n) \\ &&=r(*,*,y_1...y_n)\times q(\text{STOP}|y_{n-1},y_n) \\ \tag{2.10} \end{eqnarray*}$$

​ 使用$\mathcal K_k$来表示序列中位置$k$处的允许标注集合将很方便（$k\in \{-1…n\}$）：更准确地说，定义

$$\mathcal K_{-1}=\mathcal K_{0} = \{*\}$$

以及

$$\mathcal K_k = \mathcal K , k\in \{1...n\}$$

​ 接下来，对于任何$k\in \{1…n\},u\in \mathcal K_{k-1},v\in \mathcal K_k$，将$S(k,u,v)$定义为满足$y_{k-1}=u,y_k=v,y_i \in \mathcal K_i,i \in \{-1…k\}$的$y_{-1},y_0,…,y_k$构成的序列集合。 因此，$S(k,u,v)$是长度为$k$的所有以二元组$(u,v)$为结尾的标签序列的集合。定义

$$\begin{eqnarray*} \pi(k, u,v ) =\max_{\langle y_{-1},y_0, y_1,...,y_k\rangle \in S(k,u,v)} r(y_{-1},y_0,...,y_k) \tag{2.11} \end{eqnarray*}$$

因此，$\pi(k, u,v )$是任何长度为$k$且以二元组$(u,v)$为结尾的序列的最大概率。

​ 我们现在发现可以按如下方式有效地计算所有$(k,u,v)$对应的$\pi(k, u,v )$。 首先，作为基础情形定义

$$\pi(0, *,*)=1$$

​ 接下来，我们给出递归定义。

命题 1

对于任何$k\in \{1…n\},u\in \mathcal K_{k-1},v\in \mathcal K_k$，我们给出如下递归定义：

$$\begin{eqnarray*} \pi(k, u,v ) =\max_{w \in \mathcal K_{k-2}} (\pi(k-1, w,u) \times q(v|w,u)\times e(x_{k}|v)) \tag{2.12} \end{eqnarray*}$$

该定义是递归的，因为该定义使用了$\pi(k-1, u,v )$。 这个定义将是我们的动态规划算法的关键。

​ 我们怎样才能证明这种递归的合理性？ 回想一下，$\pi(k, u,v )$是任何以二元组$(u,v)$结尾的序列$y_{-1}…y_k$的最高galvanized。 任何此类序列必须具有$y_{k-2}=w$（对于某个$w$）。任何长度为$k-1$，以二元组$(w,u)$结尾的序列的最高概率是$\pi(k-1,w,u)$，因此任何长度为$k$，以三元组$(w,u,v)$结尾的序列的概率最高是

$$\pi(k-1, w,u) \times q(v|w,u)\times e(x_{k}|v)$$

在公式2.12中我们只是关于$w$搜索上式所有可能值，并返回最大值。

​ 我们的第二个命题如下：

命题 2

$$\begin{eqnarray*} \max _{y_1...y_{n+1}} p( x_1...x_n,y_1...y_{n+1})= \max_{u \in \mathcal K_{n-1},v \in \mathcal K_{n}} (\pi(n,u,v) \times q(\text{STOP}|u,v)) \tag{2.13} \end{eqnarray*}$$

上述命题从公式2.10可以直接推出。

​ 图2.4展示了将这些想法放在一起的算法。 该算法将句子$x_1…x_n$作为输入，并返回下式作为输出

$$\max _{y_1...y_{n+1}} p( x_1...x_n,y_1...y_{n+1})$$

该算法首先使用递归定义得到$\pi(k, u,v)$。 然后它使用公式2.13计算任何序列的最高概率。

​ 上述算法一共要迭代$n$次，每次遍历的标签为$(w,u,v)$，所以时间复杂度为$O(n|\mathcal K|^3)$，因此算法关于序列的长度是线性的，关于标签的数量是立方的。

带有反向指针的维特比算法

我们刚刚描述的算法将句子$x_1…x_n$作为输入，然后返回下式作为输出

$$\max _{y_1...y_{n+1}} p( x_1...x_n,y_1...y_{n+1})$$

然而，我们真正想要的是返回最高概率序列的算法，即对任意$x_1…x_n$，返回

$$\arg \max _{y_1...y_{n+1}} p( x_1...x_n,y_1...y_{n+1})$$

​ 图2.5显示了实现此目标的修改算法。 关键步骤是在每一步存储反向指针$bp(k,u,v)$，该指针记录$u,v$之前的状态$w$，$w$使在位置$k$以$(u,v)$结束的序列达到最大概率。 在算法结束时，我们解开反向针以找到最高概率序列，然后返回此序列。 该算法依然在$O(n|\mathcal K|^3)$时间内运行。

2.6 总结

我们在本章中已经介绍了许多重点，但最终结果相当简单：我们已经推导出一个从训练语料库中学习标注的完整方法，并将其应用于新的句子。 主要内容如下：

• 三元隐马尔可夫模型有参数$q(s|u,v)$和$e(x|s)$，并且定义任何句子$x_1…x_n$与标签序列$y_1…y_{n+1}$（其中$y_{n+1}=\text{STOP} $） 对应的联合概率

  $$p( x_1...x_n,y_1...y_{n+1})=\prod_{i=1}^{n+1}q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^n e(x_i|y_i)$$

• 给定一个训练语料库，我们可以从中得出计数，参数的最大似然估计是

  $$q(s|u,v)= \frac{c(u,v,s)}{c(u,v)}$$

  以及

  $$e(x|s) = \frac{c(s\leadsto x)}{c(s)}$$

• 给定一个新的句子$x_1…x_n$，以及我们从训练语料库中估计的参数$q$和$e$，我们可以使用图2.5中的算法（维特比算法）找到$x_1…x_n$的最高概率标签序列。

2.7 更进一步的材料

2.7.1 处理未知的单词

回忆一下，我们对HMM中概率的参数估计是

$$e(x|s) = \frac{c(s\leadsto x)}{c(s)}$$

其中$c(s\leadsto x)$为语料库中状态$s$和观测值$x$同时出现的次数，$c(s)$为在语料库中看到状态$s$的次数。

​ 该估计的一个主要问题是，对于训练数据中未见过的任何单词$x$，对于所有状态$s$，$e(x|s) $将等于$0$。 因此，对于任何包含训练数据中从未见过的单词的测试句$x_1 … x_n$，很容易验证对任意$y_1…y_{n+1}$

$$p( x_1...x_n,y_1...y_{n+1})= 0$$

因此，模型将在测试句子上完全失败。 特别的，对下式取$\arg \max$将没有意义

$$\arg \max _{y_1...y_{n+1}} p( x_1...x_n,y_1...y_{n+1}) =0$$

因为每个标签序列有同样的最大值$0$。

​ 这是一个棘手的问题，因为无论我们的训练数据多么大，测试句中都不可避免地会出现训练数据中从未见过的单词。 例如，英语的词汇量非常大; 但在测试数据中总是遇到新单词。 以图2.2和2.3中使用的句子为例：

$$\text {Profits soared at Boeing Co., easily topping forecasts on Wall Street,} \\ \text {as their CEO Alan Mulally announced first quarter results.}$$

在这句话中，很可能在训练数据中没有看到Mulally这个词。 同样地，在英语中，topping是一个相对不常见的单词，在训练语料中可能没有看到过。

​ 在本节中，我们将描述一个简单但非常有效的方法来解决这个问题。关键的想法是将训练数据中的低频词，以及在测试数据中看到但在训练中从未见过的词，映射到相对较小的一组伪单词，例如，我们可以将单词Mulally映射到伪单词initCap，将单词1990映射到伪单词fourDigitNum，依此类推。 这里伪单词initCap用于第一个字母是大写字母，其余字母是小写字母的任何单词。 伪单词fourDigitNum用于任何四位数字。

​ 图2.6显示了一组伪单词的例子，它将HMM标注符应用于命名实体识别问题。 这组伪单词是手工选择的，并且是为了保留关于不同单词的拼写特征的一些有用信息而明确选择的：例如单词的大小写特征，以及不同数字类型的子分类（主要为了处理日期）。

​ 一旦定义了从单词到伪单词的映射，我们进行如下操作。 将$f(x)$定义为将单词$x$映射到其伪单词$f(x)$的函数。 我们定义了计数截断参数$\gamma$：一个典型的值是$\gamma =5$。该参数的作用是，对于训练数据中看到的任何出现次数少于$\gamma$的单词，我们只需将单词$x$替换为伪单词$f(x)$。 此映射适用于训练和测试样本中的单词：因此，在训练数据中从未见过但在测试数据中看到的单词也会映射到其伪单词。 一旦执行了这种映射，我们就可以用与之前完全相同的方式估计HMM的参数，我们在训练数据中的一些单词现在是伪单词。 类似地，如果输入句子中的一些单词是伪单词，我们依然可以应用维特比算法进行模型解码。

​ 将低频词映射到伪单词具有“关闭词汇表”的效果：通过这种映射，测试数据中的每个词在训练数据中至少会被看到一次（通常，我们可以假设每个伪单词在训练集中至少出现一次）。 因此，对于测试数据中的某些单词$x$，我们永远不会遇到$e(x|s)=0$的问题。 此外，通过仔细选择伪单词集，将保留有关不同单词拼写的重要信息。 有关应用映射之前和之后的示例句子，请参见图2.7。

​

​ 该方法的缺点是在定义到伪词的映射时需要人为选择，并且该映射会根据所考虑的任务而变化（例如，不同的映射可以用于命名实体识别而不是POS标注）。 在后面的章节中，我们将看到基于对数线性模型的想法，可以说是低频率和未知单词问题的更清晰的解决方案。

本讲测验题

Coursera部分

1.

Jane为人名，所以选b（回顾课件的例子）

2.

利用乘法原理可得可能的标签序列数量为

$$2\times 1\times 3\times 3\times 2=36$$

3.

由转移概率参数可得，标签序列必然为

$$\text{D ,N ,STOP}$$

由发射参数可得，可能的序列有$2\times 1=2$种

$$\text{dog dog}\\ \text{the dog}$$

4.

利用公式

$$p( x_1...x_n,y_1...y_{n+1})=\prod_{i=1}^{n+1}q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^n e(x_i|y_i)$$

此处$n=4$，所以选c

5.

只要将

$$q(y_i|y_{i-2},y_{i-1})$$

修改为

$$q(y_i|y_{i-1})$$

所以选b

6.

由

$$e(x|s) = \frac{c(s\leadsto x)}{c(s)}$$

可得，

$$c(\text{N})=2, c(\text{N}\leadsto \text{cat})= 1\\ e(\text{cat}|\text{N}) =\frac 1 2$$

7.

注意公式为

$$q(s|u,v) =\lambda_1 \times q_{ML}(s|u,v)+\lambda_2\times q_{ML}(s|v)+ \lambda_3 \times q_{ML}(s) \\ \begin{aligned} q_{ML}(w|u,v)&= \frac{c(u,v,w)}{c(u,v)} \\ q_{ML}(w|v)&= \frac{c(v,w)}{c(v)} \\ q_{ML}(w)&= \frac{c(w)}{c()} \end{aligned}$$

所以

$$c(\text{N},\text{V})=2,c(\text{N},\text{V},\text{STOP})=2\\ c(\text{V},\text{STOP})=2,c(\text{V})=2\\ c()=8,c(\text{STOP})=2 \\ q(\text{STOP}|\text{N},\text{V}) =\frac 1 3\times(1 +1 +\frac 2 8)=\frac 3 4$$

8.

回顾公式为

$$\pi(0, *,*)=1 \\ \pi(k, u,v ) =\max_{w \in \mathcal K_{k-2}} (\pi(k-1, w,u) \times q(v|w,u)\times e(x_{k}|v))$$

因为

$$q(\text{D}|*,*)=1$$

所以

$$\pi(1, \text{*}, \text{D})= \max_{w \in \mathcal K_{-1}} (\pi(0, w,*) \times q(\text{D}|w,*)\times e(\text{the}|\text{D}))= \pi(0, *,*) \times q(\text{D}|*,*)\times e(\text{the}|\text{D})=0.8 \\ \pi(2, \text{D}, \text{N})= \max_{w \in \mathcal K_{0}} (\pi(1, w,\text{D}) \times q(\text{N}|w,\text{D})\times e(\text{dog}|\text{N})) = \pi(1, \text{*}, \text{D}) \times q(\text{N}|*,\text{D})\times e(\text{dog}|\text{N})=0.64\\ \pi(3, \text{N}, \text{V})=\max_{w \in \mathcal K_{1}} (\pi(2, w,\text{N}) \times q(\text{V}|w,\text{N})\times e(\text{barks}|\text{V}))= \pi(2, \text{D}, \text{N})\times q(\text{V}|\text{D},\text{N})\times e(\text{barks}|\text{V}) =0.64$$

9.

利用

$$\pi(k, u,v ) =\max_{w \in \mathcal K_{k-2}} (\pi(k-1, w,u) \times q(v|w,u)\times e(x_{k}|v))$$

可得

$$\begin{aligned} \pi(4, \text{P},\text{D} ) &=\max_{w \in \mathcal K_{2}} (\pi(3, w,\text{P}) \times q(\text{D}|w,\text{P})\times e(\text{the}|\text{D}))\\ &=\pi(3, \text{N},\text{P}) \times q(\text{D}|\text{N},\text{P})\times e(\text{the}|\text{D}) \\ &=0.2\times 0.4\times 0.6 \\ &=0.048 \end{aligned}$$

课内部分

1.

显然标注序列必然为

$$\text{D,N,V,STOP}$$

单词序列为

$$\begin{aligned} \text{the dog dog}\\ \text{the dog barks}\\ \text{the barks dog}\\ \text{the barks barks}\\ \end{aligned}$$

2.

part 1

初始化：

$$\pi(0, *, *, *)=1$$

算法：

• 对$k=1\ldots n$,

  • 对$u\in \mathcal K_{k-2},v\in \mathcal K_{k-1}, w\in \mathcal K_k$, $$\pi(k, u,v,w) =\max_{s\in \mathcal K_{k-3}}\left(\pi(k-1, s,u, v) \times q(w | s, u,v) \times e\left(x_{k} | w\right)\right)$$

• 返回

  $$\max _{u\in \mathcal K_{n-2},v\in \mathcal K_{n-1}, w\in \mathcal K_n} (\pi(n, u, v,w) \times q(\mathrm{STOP} | u, v,w))$$

part 2

只要对每个$e(x|w)$中的$x$也进行搜索即可，算法如下：

初始化：

$$\pi(0, *, *)=1$$

算法：

• 对$k=1\ldots n$,

  • 对$u\in \mathcal K_{k-1},v\in \mathcal K_{k}$, $$\pi(k, u,v) =\max_{w\in \mathcal K_{k-2}, x\in \mathcal V}\left(\pi(k-1, w,u) \times q(v | w,u) \times e\left(x | v\right)\right)$$

• 返回

  $$\max _{u\in \mathcal K_{n-1},v\in \mathcal K_{n}} (\pi(n, u, v) \times q(\mathrm{STOP} | u, v))$$

3.

初始化：

$$\pi(0, *, *)=1$$

算法：

• 对$k=1\ldots n$,

  • 对$u\in \mathcal K_{k-1},v\in \mathcal K_{k}$, $$\pi(k, u,v) =\max_{w\in \mathcal K_{k-2}}\left(\pi(k-1, w,u) \times q(v | w) \times e\left(x_k | v\right)\right)$$

• 返回

  $$\max _{u\in \mathcal K_{n-1},v\in \mathcal K_{n}} (\pi(n, u, v) \times q(\mathrm{STOP} | u, v))$$

4.

首先回顾维特比算法：

从训练数据的特点，前三个标签必然为（注意其余情形概率为$0$）

$$\text{DT,NN,VB}$$

对于$k=4$，因为

$$q(u|\text{VB})e(\text{in}|u)=\begin{cases} 非零& u=\text{IN} \\ 0& 其他 \end{cases}$$

第一个句子的$y_4=\text{IN}$，同理第二个句子的$y_4=\text{VB}$。最后从训练数据的特点可以确定其余标签。

5.

考虑如下例子（来自参考解答）：

$$\text{the/DT the/NN the/DT the/DT the/DT the/DT}$$

最大似然估计为

$$\begin{array}{c}{e(\text {the } | \mathrm{DT})=e(\text {the } | \mathrm{NN})=1} \\ {q(\mathrm{NN} | \mathrm{DT})=1 / 5 \quad q(\mathrm{DT} | \mathrm{DT})=3 / 5 \quad q(\mathrm{STOP} | \mathrm{DT})=1 / 5}\end{array}$$

因为$q(\mathrm{DT} | \mathrm{DT})$最大，所以概率最大的标签序列为

$$\text{DT DT DT DT DT DT STOP}$$