Michael Collins NLP Lecture 1

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

课程网盘地址：

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

最近开始学习Michael Collins的NLP课程，该课程以前是在Coursera上，但Cousera改版后下架了，好在找到了视频以及课程主页，主页上有讲义，练习题，作业等等，争取在寒假把这份课程学完并做一些笔记。话不多少，进入第一讲，这一讲的内容为介绍什么是NLP以及语言模型。

Chapter 1 语言模型

1.1 介绍

​ 在本章中，我们将考虑从某种语言的一组句子构建语言模型的问题。 语言模型最初是为语音识别问题而开发的; 它们仍然在现代语音识别系统中发挥着核心作用。 它们也广泛用于其他NLP应用程序。 最初为语言建模开发的参数估计技术，如本章所述，在许多其他场景中都很有用，例如本书后面章节中考虑的标记和解析问题。

​ 我们的任务如下。 假设我们有一个语料库，它是某种语言的一组句子。 例如，我们可能有几年来自纽约时报的文本，或者我们可能有来自网络的大量文本。给定这个语料库，我们想估计一个语言模型的参数。

​ 语言模型定义如下。 首先，我们将$\mathcal V$定义为语言中所有单词的集合。 例如，在构建我们可能拥有的英语语言模型时，我们有

$$\mathcal V= \{\text{the, dog, laughs, saw, barks, cat, ...}\}$$

实际中，$\mathcal V$可能非常大，例如有几千，几万个单词等等，但我们总假设$\mathcal V$为有限集。语言中的句子为一系列单词

$$x_1x_2...x_n$$

其中整数$n\ge 1$，并且$x_i\in \mathcal V,i\in \{1…(n-1)\}$，这里我们还假设$x_n$为特殊符号，STOP（其中STOP不在集合$\mathcal V$内），后面将看到这个符号带来的方便之处。下面给几个句子的例子

$$\begin{aligned} & \text{the dog barks STOP} \\ & \text{the cat laughs STOP} \\ & \text{the cat saw the dog STOP} \\ & \text{the STOP} \\ & \text{cat the dog the STOP} \\ & \text{cat cat cat STOP} \\ & \text{STOP} \\ & \text{...} \end{aligned}$$

​ 我们定义$\mathcal V^{\dagger} $为词汇$\mathcal V$中单词构成的句子，这是一个无限集，因为句子可以是任意长度。

​ 接着，我们给出如下定义：

定义 1（语言模型）

一个语言模型由有限集$\mathcal V$，以及函数$p(x_1,x_2,…x_n)$构成，其中

$$\begin{aligned} &1.对于任意\langle x_1...x_n \rangle \in \mathcal V^{\dagger}，p(x_1,...,x_n)\ge 0\\ &2.\sum_{\langle x_1...x_n \rangle \in \mathcal V^{\dagger}} p(x_1,...,x_n) =1 \end{aligned}$$

因此，$p(x_1,…,x_n)$是定义在$\mathcal V^{\dagger}$中句子上的概率分布。

​ 下面是一个从训练语料库学习语言模型的（非常糟糕的）方法的例子。定义$c(x_1…x_n)$为句子$x_1…x_n$出现在训练语料库中的次数，$N$为训练语料库中的句子总数。然后我们定义

$$p(x_1...x_n)=\frac{c(x_1...x_n)}{N}$$

然而，这是一个非常差的模型：特别是它会将概率$0$分配给在训练语料库中没有出现的任何句子。 因此，它无法推广到训练数据中未出现的句子。 本章的关键是介绍对训练数据中未出现的句子进行推广的方法。

​ 乍一看，语言建模问题似乎是一项相当奇怪的任务，为什么我们要考虑它呢？有几个原因：

• 1.语言模型在广泛的应用中都非常有用，最明显的例子是语音识别和机器翻译。在许多应用程序中，拥有一个良好的“先验”分布$p(x_1…x_n)$非常有用。例如，在语音识别中，语言模型与模拟不同单词的发音的声学模型相结合：思考它的一种方式是声学模型产生大量候选句子以及概率；然后使用语言模型根据它们作为语言中句子的可能性来重新排序这些可能性。
• 2.我们描述的用于定义函数$p$的技术，以及用于从训练样本估计结果模型的参数的技术，在课程期间的其他几个内容中将是有用的：例如，我们在后面看到的隐马尔可夫模型，以及在自然语言解析的模型中就有应用。

1.2 马尔可夫模型

我们现在转向一个关键问题：给定一个训练语料库，我们如何学习函数$p$？ 在本节中，我们描述马尔可夫模型，这是概率论的核心思想; 在下一节中，我们将描述三元语言模型(trigram language models)，这是一类重要的语言模型，直接建立在马尔可夫模型的思想基础之上。

1.2.1 固定长度序列的马尔可夫模型

考虑一系列随机变量，$X_1,X_2,…,X_n$。 每个随机变量可以取有限集$\mathcal V$中的任何值。现在我们假设序列的长度$n$是某个固定数（例如，$n = 100$）。 在下一节中，我们将描述如何将方法推广到$n$也是随机变量的情况，从而允许不同的序列具有不同的长度。

​ 我们的目标如下：我们想对任何序列$x_1…x_n$的概率进行建模，其中$n\ge 1 ，x_i\in \mathcal V,i=1…n$，即对联合概率进行建模

$$P(X_1=x_1,X_2= x_2,...,X_n=x_n)$$

一共存在$|\mathcal V|^n$种$x_1…x_n$可能的序列：很明显，列出所有$|\mathcal V|^n$个概率是不可行的。 我们想建立一个更简洁的模型。

​ 注意到如下等式

$$P(a,b|c)= P(b|c)P(a|b,c)$$

所以可以利用条件概率对上式进行重写

$$\begin{aligned} P(X_1=x_1,X_2= x_2,...,X_n=x_n) &= P(X_1=x_1)P(X_2= x_2,...,X_n=x_n |X_1=x_1) \\ &= P(X_1=x_1)P(X_2= x_2|X_1=x_1)P(X_3= x_3,...,X_n=x_n |X_1=x_1,X_2= x_2)\\ &=P(X_1=x_1)\prod_{i=2}^n P(X_i=x_i|X_1=x_1,...,X_{i-1}=x_{i-1}) \end{aligned}$$

​ 在一阶马尔可夫过程中，我们做出以下假设，这大大简化了模型：

$$\begin{eqnarray*} P(X_1=x_1,X_2= x_2,...,X_n=x_n)&&= P(X_1=x_1)\prod_{i=2}^n P(X_i=x_i|X_1=x_1,...,X_{i-1}=x_{i-1})\tag{1.1} \\ &&= P(X_1=x_1)\prod_{i=2}^n P(X_i=x_i|X_{i-1}=x_{i-1})\tag{1.2} \end{eqnarray*}$$

其中(1.1)利用到之前的结论，(1.2)利用到如下事实：对于任何$i\in \{2,…,n\}$和任何$x_1,…,x_i$，

$$P(X_i=x_i|X_1=x_1,...,X_{i-1}=x_{i-1})= P(X_i=x_i|X_{i-1}=x_{i-1})$$

这是（一阶）马尔可夫假设。我们假设序列中第$i$个单词仅取决于前一个单词$x_{i-1}$。 更正式地说，我们假设$X_i$的值在给定$X_{i-1}$的值情形下，条件独立于$X_1,…,X_{i-2}$。

​ 在二阶马尔可夫过程中（二阶马尔可夫过程形成三元语言模型的基础），我们做出一个稍微弱一些的假设，即每个词依赖于序列中的前两个词：

$$\begin{eqnarray*} &&P(X_i=x_i|X_1=x_1,...,X_{i-1}=x_{i-1})\\ = &&P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1}) \end{eqnarray*}$$

由此得出整个序列的概率为

$$\begin{eqnarray*} &&P(X_1=x_1,X_2= x_2,...,X_n=x_n)\\ =&& \prod_{i=1}^n P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})\tag{1.3} \end{eqnarray*}$$

为方便起见，我们假设在此定义中

$$x_0=x_{-1}=*$$

其中*是句子中的特殊的“开始”符号。

1.2.2 句长可变的马尔可夫序列

在上一节中，我们假设序列的长度$n$是固定的。然而，在许多应用中，长度$n$本身可以变化。 因此，$n$本身就是一个随机变量。 有多种方法可以对这种可变性进行建模：在本节中，我们将介绍最常用的语言建模方法。

​ 方法很简单：我们假设序列中的第$n$个单词$X_n$始终等于特殊符号，即STOP符号。 此符号只能出现在序列的末尾。 我们使用与以前完全相同的假设：例如，在二阶马尔可夫假设下，对任意的$n\ge 1$，我们有

$$\begin{eqnarray*} &&P(X_1=x_1,X_2= x_2,...,X_n=x_n)\\ =&& \prod_{i=1}^n P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})\tag{1.4} \end{eqnarray*}$$

其中$x_n=\text{STOP},x_i\in \mathcal V,i=1…(n-1)$

​ 我们假设了一个二阶马尔可夫过程，在每一步我们从如下分布中生成一个符号$x_i$

$$P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})$$

其中$x_i$可以是$\mathcal V $的成员，或者可以是STOP符号。 如果我们生成STOP符号，我们就完成了序列。 否则，我们在序列中生成下一个符号。

​ 更正式地说，产生句子的过程如下：

• 1.初始化$i=1,x_0= x_{-1}=*$

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

  $$P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})$$

• 3.如果$x_i=\text{STOP}$，那么返回序列$x_1…x_i$。否则，令$i=i+1$，然后返回步骤2

因此，我们现在有一个模型可以生成长度不同的序列。

本讲测验题

Coursera部分

回顾语言模型的定义：

一个语言模型由有限集$\mathcal V$，以及函数$p(x_1,x_2,…x_n)$构成，其中

$$\begin{aligned} &1.对于任意\langle x_1...x_n \rangle \in \mathcal V^{\dagger}，p(x_1,...,x_n)\ge 0\\ &2.\sum_{\langle x_1...x_n \rangle \in \mathcal V^{\dagger}} p(x_1,...,x_n) =1 \end{aligned}$$

1.

条件1显然满足，然后注意单词只有一个，所以长度为$n$的序列唯一，因此

$$\sum_{\langle x_1...x_n \rangle \in \mathcal V^{\dagger}} p(x_1,...,x_n) = \sum_{n\le N} \frac 1 N = 1$$

从而满足条件2。所以这题选(a)

2.

条件1显然满足，然后长度为$2$的句子一共有两种：the STOP,dog STOP，所以

$$\sum_{\langle x_1...x_n \rangle \in \mathcal V^{\dagger}} p(x_1,...,x_n) = \sum_{n=2} \frac 1 2 = 1$$

从而满足条件2。所以这题选(a)

3.

$10$个位置，每个位置有$3$个选择，所以答案为$3^{10}$，这题选(c)

课内部分

1.

因为单词有有$3$个，所以长度为$n$的词组有$3^{n-1}$个，注意概率之和为$1$，所以

$$\sum_{n=1}^{\infty} \gamma(n) \times 3^{n-1}\times 0.5^n=1$$

因为

$$\sum_{n=1}^{\infty} 0.5^n =1$$

所以取

$$\gamma(n) =\frac{1}{3^{n-1}}$$

2.

Q1：

$$\begin{aligned} \sum_{u \in \mathcal{V}} \sum_{v \in \mathcal{V}} P\left(X_{1}=u, X_{2}=v\right) &=\sum_{u \in \mathcal{V}} \sum_{v \in \mathcal{V}} P(X_{1}=u)P( X_{2}=v)\\ &=\sum_{u \in \mathcal{V}}P( X_{2}=v)\\ &=1 \end{aligned}$$

Q2：

$$\begin{aligned} \sum_{u \in \mathcal{V}} \sum_{v \in \mathcal{V}} P\left(X_{1}=u, X_{2}=v \right) &=\sum_{u \in \mathcal{V}} \sum_{v \in \mathcal{V}} P(X_{1}=u)P( X_{2}=v|X_1= u)\\ &=\sum_{u \in \mathcal{V}} P(X_{1}=u)\sum_{v \in \mathcal{V}} P( X_{2}=v|X_1= u)\\ &=\sum_{u \in \mathcal{V}} P(X_{1}=u)\\ &=1 \end{aligned}$$

3.

Q1：

因为

$$q(\text{there}) > q(\text{their})$$

所以我们总有

$$p(w_1,\ldots ,\text{there}, \ldots,w_n) > p(w_1,\ldots ,\text{their}, \ldots,w_n)$$

即总是选择$\text{there}$，所以这不是一个好的解决方案。

Q2：

这个方法考虑了上下文，该方法的问题是可能概率为$0$，就会无法比较。

4.

这里给出老师的例子：

1a) The dog in the park was big
1b) The dogs in the park were big

显然was，were和dog是否为复数有关，这就违反了模型的假定。