Michael Collins NLP Lecture 4

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

课程网盘地址：

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

这一讲主要介绍了语法解析(Parsing)以及上下文无关法(Context-Free Grammars)。

Chapter 3 概率上下文无关法(Probabilistic Context-Free Grammars (PCFGs))

首先介绍语法解析问题，问题形式如下

语法解析的一个应用是机器翻译，因为不同语言中的语法有所不同，例如

本章介绍的概率上下文无关法为处理语法解析问题的一个常用方法，在此之前，我们先介绍上下文无关法(Context-Free Grammars)。

1.上下文无关法(Context-Free Grammars)

1.1 基本定义

上下文无关法(CFG)是一个四元组$G=(N,\Sigma,R,S)$，其中

$N$是一组有限的非终止符。
$\Sigma$一组有限的终止符。
$R$是形如$X\to Y_1Y_2…Y_n$的有限规则的集合，其中$X\in N,n\ge 0$以及$Y_i\in (N\bigcup \Sigma),i=1…n$。
$S\in N$是唯一的起始符号。

图1显示了一个用于英语片段的非常简单的上下文无关法。在这种情况下，非终止符$N$的集合指定了一些基本的句法类别：例如，S表示“句子”，NP表示“名词短语”，VP表示“动词短语”等等。集合$\Sigma$包含词汇表中的单词集。语法中的起始符号是$S$：正如我们将看到的，这指定每个解析树都有$S$作为其根。最后，我们有无上下文的规则，如

$\text{S} \to \text{NP VP}$

或者

$\text{NN}\to \text{man}$

第一条规则规定S（句子）可以由NP后跟VP组成。第二条规则规定NN（单数名词）可以由单词man组成。

请注意，如上所定义的允许规则集非常广泛：我们可以拥有任何形如$X\to Y_1Y_2…Y_n$的规则，只要$X$是$N$的成员，并且每个$Y_i$是$N$或$\Sigma$的成员。例如，我们可以有“一元规则”，其中$n=1$，如下所示：

$\begin{aligned} \text{NN}&\to \text{man} \\ \text{S}&\to \text{VP} \end{aligned}$

规则的右侧还可以有包含终止和非终止符号的混合规则，例如

$\begin{aligned} \text{VP}&\to \text{ John Vt Mary} \\ \text{NP} &\to \text{the NN} \end{aligned}$

我们甚至可以有$n=0$的规则，此时规则的右侧没有符号。例如

$\begin{aligned} \text{VP}&\to \epsilon \\ \text{NP}&\to \epsilon \end{aligned}$

这里我们用$\epsilon$来代表空字符串。直观地，上述规则允许特定的非终止符（例如，VP）在解析树中没后续单词。

1.2 最左派生规则((Left-most) Derivations)

给定上下文无关法$G$，一个最左派生规则是字符串序列$s_1…s_n$，其中

$s_1= \text{S}$。即，$s_1 $由单个元素组成，即起始符号。
$s_n \in \Sigma^{\star}$ 。即$s_n$仅由终止符号组成（我们用$\Sigma^{\star}$表示由$\Sigma $的单词组成的所有可能字符串的集合。）
每个$s_i,i=2…n$是通过在$s_{i-1}$中选取最左边的非终止符$X$，然后用某个$\beta$替换来得到的，其中$X\to \beta$是$R$中一条规则。

作为一个例子，图1中的最左派生规则如下：

$s_1 =\text{S}$。
$s_2 = \text{NP VP}$。（我们在$s_1$中取最左边的非终止符，即$S$，并选择规则$\text{S}\to \text{NP VP}$，从而用NP替换S，然后紧跟着VP。）
$s_3= \text{DT NN VP}$。（我们使用规则$\text{NP}\to \text{DT NN}$来扩展最左边的非终止符，即NP。）
$s_4 =\text{the NN VP}$。（我们使用规则$\text{DT}\to \text{the}$。）
$s_5 = \text{the man VP}$。（我们使用规则$\text{NN}\to \text{man}$。）
$s_6 = \text{the man Vi}$。（我们使用规则$\text{VP}\to \text{Vi}$。）
$s_7 = \text{the man sleeps}$。（我们使用规则$\text{Vi}\to \text{sleeps}$。）

将派生规则表示为解析树非常方便。例如，上面的推导将表示为图2中所示的解析树。该解析树以S为根，反映了$s_1= \text{S}$的事实。我们在S下面看到了序列NP VP，反映了使用规则$\text{S}\to \text{NP VP}$扩展了S; 我们在NP下面看到DT NN序列，反映了使用$\text{NP}\to \text{DT NN}$规则扩展NP的事实！。

上下文无关法$G$通常将指定一组可能的最左派生规则。每个最左派生将以字符串$s_n \in \Sigma^{\star }$结尾：我们说$s_n $是派生规则产生的结果。可能的派生可以是有限集或无限集（实际上，图1中语法的派生是无限的）。

以下定义非常重要：

如果存在至少一个结果为$s$的派生，则称字符串$s \in \Sigma’$为CFG定义的语言。

2. 歧义(Ambiguity)

注意，一些字符串$s$可能具有多个派生基类(underlying derivation)（即，多于一个派生，其产生的结果为$s$）。在这种情况下，我们说CFG下的字符串是有歧义的。

作为一个例子，参见图3，该例子给出the man saw the dog with the telescope的两个解析树，这两个树在图1中给出的CFG下是有效的。这个例子是介词短语歧义的情况：介词短语（PP）with the telescope可以修饰the dog，或saw the dog。在图中所示的第一个解析树中，PP修饰the dog，导致NP为the dog with the telescope：这个解析树对应于狗拿着望远镜的解释。在第二个解析树中，PP修饰整个VP——saw the dog：这个解析树对应于男人用望远镜看狗的解释。

对于自然语言来说，歧义是一个令人惊讶的严重问题。当研究人员第一次开始为英语等语言构建相当大的语法时，他们惊讶地发现句子通常有很多可能的解析树：中等长度的句子（例如20或30个字的长度）拥有数百，数千甚至数万种可能的解析并不少见。