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$作为其根。 最后,我们有无上下文的规则,如

或者

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

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

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

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

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

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

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

  • $s_1= \text{S}$。即,$s_1 $由单个元素组成,即起始符号。
  • $s_n \in \Sigma’$ 。即$s_n$仅由终止符号组成(我们用$\Sigma’$表示由$\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’ ​$结尾:我们说$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个字的长度)拥有数百,数千甚至数万种可能的解析并不少见。

本讲测验题

课内部分

1.

a:一棵解析树:

b:二棵解析树:

c:注意此处有$k+1$的叶节点,所以数量为$C_k$

2.

略,见习题解析。

3.

4.

本文标题:Michael Collins NLP Lecture 4

文章作者:Doraemonzzz

发布时间:2019年02月10日 - 13:19:00

最后更新:2019年05月25日 - 21:55:03

原始链接:http://doraemonzzz.com/2019/02/10/Michael Collins NLP Lecture 4/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。