Michael Collins NLP Lecture 5

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

课程网盘地址:

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

这一讲主要介绍了概率上下文无关文法(Probabilistic Context-Free Grammars (PCFGs))。

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

3.1 基本定义

给定上下文无关文法$G$,我们将使用以下定义:

  • $\mathcal T_G ​$是语法$G​$下所有可能的最左派生(解析树)的集合。当语法$G​$在上下文中很清楚时,我们通常将其简写为$\mathcal T ​$。

  • 对于任何派生$t\in \mathcal T_G ​$,我们用$\text{yield}(t)​$来表示由$t​$的产生的字符串$s\in \Sigma’​$(即,$\text{yield}(t)​$是$t​$中的单词序列)。

  • 对于给定的句子$s\in \Sigma’​$,我们用$\mathcal T_G(s)​$表示集合

    也就是说,$\mathcal T_G(s)​$是$s​$的可能解析树的集合。

  • 如果句子$s​$有一个以上的解析树,即$|\mathcal T_G(s)|>1​$,则句子$s​$是有歧义的。

  • 如果句子$s$至少有一个解析树,即$|\mathcal T_G(s)|>0$,则句子$s$是语法合理的。

​ 概率上下文无关法中的关键思想是扩展我们的定义,以给出可能派生的概率分布。 也就是说,我们将找到一种方法来定义解析树上的分布,$p(t)​$,使得对于任何$t\in \mathcal T_G ​$,

以及满足

乍一看这似乎很难:每个解析树$t​$都是一个复杂的结构,而集合$\mathcal T_G ​$很可能是无限集。 但是,我们将看到对无上下文法有一个非常简单的扩展,它允许我们定义函数$p(t)​$。

​ 为什么这是一个有用的问题? 一个关键的想法是,一旦我们有函数$p(t)​$,我们就按概率大小顺序对任何句子进行可能的解析。 特别是,给定句子$s​$,我们可以返回

作为我们解析器的输出——即这是该模型下$s​$最可能的解析树。 因此,如果我们的分布$p(t) ​$是我们语言中不同解析树概率的良好模型,那么我们将有一种处理歧义的有效方法。

​ 这给我们留下了以下问题:

  • 我们如何定义函数$p(t)​$?

  • 我们如何从训练样本中学习模型$p(t)$的参数?

  • 对于给定的句子,我们如何找到最可能的解析树,即

    最后一个问题将被称为解码或解析问题。

​ 在下面的部分中,我们通过定义概率上下文无关法(PCFGs)来回答这些问题,这是一种无上下文法的一般推广。

3.2 PCFGs的定义

概率无上下文法(PCFGs)定义如下:

定义1 (PCFGs)

一个PCFG由以下元素组成:

  1. 上下文无关法$G=(N,\Sigma,R,S)​$

  2. 对每个规则$\alpha \to \beta\in R​$,定义参数

    参数$q(\alpha \to \beta)$可以解释为假设扩展的非终止符是$\alpha$,选择规则$\alpha \to \beta$的条件概率 。 对于任何$X\in N$,我们都有约束条件

    另外对任何$\alpha \to \beta\in R​$,都有

    给出一个包含规则$\alpha_1\to \beta_1,\alpha_2\to \beta_2…\alpha_n\to \beta_n​$的解析树$t \in \mathcal T_G​$,PCFG下$t​$的概率是

​ 图4显示了一个示例PCFG,它具有与图1所示相同的上下文无关法。对原始上下文无关法的唯一补充是每个规则$\alpha \to \beta \in R​$的参数$q(\alpha \to \beta)​$。这些参数中的每一个都被约束为非负的,此外我们还有约束,对于任何非终止符$X\in N​$,

这简单地说明,对于任何非终止符$X$,规则左侧具有该非终止符的所有规则的参数值的总和必须为$1$。 我们可以在图4中验证此属性是否适用于PCFG。例如,我们可以验证此约束适用于$X = \text{VP}$,因为

​ 为了计算任何解析树$t​$的概率,我们简单地将它包含的下文无关规则的$q​$值相乘。 例如,如果我们的解析树是

那么我们有

​ 直觉上,PCFG假设解析树是根据以下过程随机生成的:

  • 定义$s_1= S,i=1$
  • 当$s_i​$至少包含一个非终止符:
    • 在$s_i​$中找到最左边的非终止符,称之为$X​$。
    • 从分布$q(X\to \beta)$选择某个规则$X\to \beta$。
    • 通过用$\beta$替换$s_i$中最左边的$X$来创建$s_{i+1}$。
    • 令$i=i+1$

因此,我们简单地将概率添加到最左派生的每个步骤中, 整棵树的概率是这些单独选择的概率的乘积。

3.3 从语料库中推导PCFG

定义了PCFG之后,接下来的问题如下:我们如何从语料库中推导出PCFG? 我们将假设一组训练数据,它是一组解析树$t_1,t_2,…,t_m​$。 和以前一样,$\text{yield}(t_i)​$是语料库中的第$i​$个句子。

​ 每个解析树$t_i​$是一系列上下文无关规则:我们假设我们语料库中的每个解析树在其根处都有相同的符号$S​$。然后我们可以按如下方式定义$\text{PCFG}(N,\Sigma,R,S,q)​$:

  • $N​$是解析树$t_1…t_m​$中所有非终止符。

  • $\Sigma$是解析树$t_1…t_m$中所有单词。

  • 起始符为$S​$。

  • 规则集$R$包含解析树$t_1…t_m$中所有规则$\alpha \to \beta $。

  • 参数的最大似然估计为

    其中$\text{Count}(\alpha \to \beta)$是规则$\alpha \to \beta$在解析树$t_1…t_m$中出现的次数,$\text{Count}(\alpha)$是非终止符$\alpha $在解析树$t_1…t_m$中出现的次数。

​ 例如,如果规则$\text{VP}\to \text{Vt Np}​$在我们的语料库中出现$105​$次,然后非终止符$\text{VP}​$出现$1000​$次,那么

3.4 用PCFG解析

一个关键的问题如下:给出一个句子,我们如何为$s$找到最高得分的解析树,或者更明确地说,我们如何找到

本节将描述针对此问题的动态规划算法——CKY算法。

​ 我们提出的CKY算法适用于限制类型的PCFG:采用Chomsky正规形式(CNF)的PCFG。虽然CNF中对语法的限制可能起初似乎是限制性的,但结果并不是一个强有力的假设。可以将任何PCFG转换为CNF中的等效语法:我们将在作业中更多地查看这个问题。

​ 在接下来的部分中,我们首先描述CNF中语法的概念,然后描述CKY算法。

3.4.1 Chomsky正规形式(Chomsky Normal Form)
定义2 (Chomsky Normal Form)

上下文无关法$G=(N,\Sigma,R,S)$是Chomsky正规形式如果每个规则$\alpha \to \beta $采用以下两种形式之一:

  • $X\to Y_1 Y_2$,其中$X\in N, Y_1\in N,Y_2 \in N$。
  • $X\to Y$,其中$X\in N, Y\in \Sigma$。

因此,语法中的每个规则要么将非终止符$X$重写为两个非终止符$Y_1,Y_2$;要么将非终止符$X$重写一个终止符$Y$。

​ 图5显示了Chomsky正规形式的PCFG的示例:

3.4.2 使用CKY算法进行解析

我们现在描述用于在CNF中使用PCFG进行解析的算法。 该算法的输入是Chomsky正规形式的PCFG,$G=(N,\Sigma,R,S,q)​$,并且$s = x_1…x_n​$,其中$x_i​$是句子中第$i​$个单词。 算法的输出是

​ CKY算法是一个动态规划算法。 算法中的关键定义如下:

  • 对于给定的句子$x_1…x_n​$,对于任意$X\in N​$以及任意$(i,j), 1\le i \le j \le n​$,定义$\mathcal T(i,j ,X) ​$为短语$x_i…x_j​$的解析树,其中非终止符$X​$为树的根。

  • 定义

    (如果$\mathcal T(i,j ,X) ​$是空集,定义$\pi(i,j ,X)=0​$)

​ 因此,$\pi(i,j ,X)$是代表短语$x_i…x_j$的任何解析树的最高分数,其中这些解析树满足非终止符$X$为树的根。如果树$t$包含规则$\alpha_1\to \beta_1,\alpha_2\to \beta_2…\alpha_m\to \beta_m$,那么

​ 特别的,我们有

​ CKY算法的关键点点可以递归定义$\pi​$,这允许简单的自下而上动态规划算法。 该算法是“自下而上”的,在这种意义上,首先计算$j = i​$的情况下的$\pi(i,j ,X)​$,然后是$j = i + 1​$的情况,依此类推。

​ 递归定义中的基本情况如下:对于所有$i=1…n$以及$X\in N$,

​ 递归定义如下:对于所有$(i,j),1\le i \le j \le n$以及$X\in N$,

本讲义的下一部分将说明此递归定义的理由。

​ 图6显示了基于这些递归定义的最终算法。 该算法自下而上填充$\pi ​$值:首先使用递归中的基本情况填充$\pi(i,i ,X)​$;然后令$j=i+1,j=i+2​$,等等。

​ 注意,该算法存储$(i,j,X)$对应的反向指针值$bp(i,j,X)$。 这些值记录得分最高的解析树对应的规则$X\to Y Z$以及分界点$s$,利用反向指针就可以恢复句子的最高得分对应的解析树。除此之外,算法的时间复杂度为$O(n^3|N|^3)$

3.4.3 算法的证明

作为如何应用等式1中的递归规则的示例,考虑解析句子

并考虑$π(3,8,\text{VP})$的计算。 这将是具有根VP的任何树的最高分,跨越短语$x_3…x_8=\text{saw the man with the telescope}$。 公式1规定,为了计算这个值,我们要对两个选择取$\max$:首先,选择规则集$R$中一个规则$\text{VP}\to Y Z$,注意这里有两个规则,$\text{VP}\to \text{Vt NP}$和$\text{VP}\to \text{VP PP}$。 第二,选择$ s\in \{3,4,…7 \}$。 因此,我们对以下几项取最大值:

​ 我们如何证明这种递归定义? 关键的观察是任何以$X$为根且跨越短语$x_i…x_j $的树$t$,必须包含以下步骤:

  • 在树的顶部选择某个规则$X\to Y Z\in R​$。

  • 选择$s \in \{i… j -1\}$,我们将其称为规则的“分裂点”。

  • 选择以$Y​$为根且跨越短语$x_i…x_s ​$的树$t_1​$。

  • 选择以$Z$为根且跨越短语$x_{s+1}…x_j $的树$t_2$。

  • 我们有

    即,树的概率是三项的乘积:树顶部规则的概率,以及子树$t_1$和$t_2 $的概率。

​ 例如,考虑以下树,以VP为根,跨越短语$x_3…x_8$:

​ 在这种情况下,我们树顶部的规则为$\text{VP}\to \text{VP PP}$;分裂点的选择是$s = 5$;以VP为根,代表$x_3…x_s$的树是

以及PP为根,代表$x_{s+1}…x_8​$的树是

​ 第二个关键观察如下:

  • 如果最高得分树以非终止符$X​$为根并且跨越短语$x_i…x_j​$,使用规则$X\to Y Z​$和分裂点$s​$,那么它的两个子树必须是:
    • 1)以$Y$为根,跨越短语$x_1…x_s$的最高得分树。
    • 2)以$Z$为根,跨越短语$x_{s+1}…x_j$的最高得分树。

​ 上述证明是利用反证法。 如果条件(1)或条件(2)不满足,我们总能找到一个更高的得分树,其根为$X$,跨越单词$x_i… x_j$,具体方式为通过选择跨越短语$x_1…x_s$或跨越短语$x_{s+1}…x_j$的更高得分子树。

​ 现在让我们回顾一下我们的递归定义:

我们看到等式右边涉及搜索所有可能的规则$X\to Y Z\in R$和可能的分裂点$s$。对于每个选择规则和分裂点,我们计算

这是以$X$为根,跨越词$x_i…x_j$的最高得分树(给定这个规则和分裂点)。 该定义使用值$\pi(i, s, Y)$和$\pi(s+1, j, Z)$,对应于两个最高得分子树。 我们对所有可能的规则和分割点选择取最大值。

3.4.5 树内求和的内部算法(The Inside Algorithm for Summing over Trees)

我们现在描述第二种非常相似的算法,该算法对给定句子的所有解析树的概率求和,从而计算PCFG下句子的概率。 该算法称为内部算法。

​ 算法的输入再次是Chomsky正规形式的PCFG,$G=(N,\Sigma,R,S,q)$,并且句子$s = x_1… x_n$,其中$x_i$是句子中第$i$个单词。 算法的输出是

这里$p(s)$是PCFG生成字符串$s$的概率。

​ 我们定义如下内容:

  • 对于给定的句子$x_1…x_n$,对于任意$X\in N$以及任意$(i,j), 1\le i \le j \le n$,定义$\mathcal T(i,j ,X) $为短语$x_i…x_j$的解析树,其中非终止符$X$为树的根。

  • 定义

    (如果$\mathcal T(i,j ,X) $是空集,定义$\pi(i,j ,X)=0$)

​ 该定义和之前相比只是将$\max$更换为$\text{sum}​$,特别的,我们有

​ 我们使用和之前非常相似的递归定义。 首先,基本情况如下:对于所有$i=1…n$以及$X\in N$,

​ 递归定义如下:对于所有$(i,j),1\le i \le j \le n$以及$X\in N$,

​ 图7显示了基于这些递归定义的算法。 该算法与CKY算法基本相同,但在递归定义中用sum替换max。 再次“自下而上”计算$\pi$值。

本讲测验题

Coursera部分

1.

利用定义计算即可

2.

作图比较麻烦,简述思路。这里一共有两个解析树,计算的概率分别为$0.00015$和$0.00027$,所以最高概率为$0.00027$

3.

利用公式

此处

所以答案为

4.

显然我们应该有

所以

5.

利用定义即可

6.

利用公式

此处将可能的情形都列出即可

所以

课内部分

1.

不难看出$\pi(i, j, X)$代表短语$x_i…x_j$的解析树的数量,其中这些解析树满足非终止符$X$为树的根,所以应该填写

2.

回顾之前定义的$\pi(i, j ,X)$,这里一定有$i=1$,所以可以得到如下算法:

  • 对$l=1 \ldots(n-1)$

    • 令$j=1+l$

    • $X\in N ​$,计算

  • 返回$\pi (1, n, S)$

3.

作图后不难发现所有概率均相同。

本文标题:Michael Collins NLP Lecture 5

文章作者:Doraemonzzz

发布时间:2019年02月11日 - 15:32:00

最后更新:2019年05月26日 - 16:34:56

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

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