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)$表示集合

  $$\{t:t\in \mathcal T_G ,\text{yield}(t)=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 $，

$$p(t)\ge 0$$

以及满足

$$\sum_{t\in \mathcal T_G } p(t)=1$$

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

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

$$\arg \max_{t\in \mathcal T_G(s)} p(t)$$

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

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

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

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

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

  $$\arg \max_{t\in \mathcal T_G(s)} 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)$$

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

   $$\sum_{\alpha \to \beta\in R:\alpha =X} q(\alpha \to \beta) = 1$$

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

   $$q(\alpha \to \beta) \ge 0$$

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

   $$p(t) =\prod_{i=1}^n q(\alpha_i\to \beta_i)$$

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

$$\sum_{\alpha \to \beta\in R:\alpha =X} q(\alpha \to \beta) = 1$$

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

$$\begin{aligned} \sum_{\alpha \to \beta\in R:\alpha =\text{VP}} q(\alpha \to \beta) &= q(\text{VP} \to\text{Vi})+q(\text{VP} \to\text{Vt NP})+q(\text{VP} \to\text{VP PP})\\ &=0.3+0.5+0.2\\ &=1 \end{aligned}$$

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

那么我们有

$$\begin{aligned} p(t) =\ &p(\text{S} \to \text{NP VP}) \times p(\text{NP} \to \text{DT NN}) \times p(\text{DT} \to \text{the}) \times p(\text{NN} \to \text{dog}) \times \\ & p(\text{VP} \to \text{Vi}) \times p(\text{Vi} \to \text{sleeps}) \end{aligned}$$

​ 直觉上，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 $。

• 参数的最大似然估计为

  $$q_{ML}(\alpha \to \beta) = \frac{\text{Count}(\alpha \to \beta)}{\text{Count}(\alpha)}$$

  其中$\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$次，那么

$$q(\text{VP}\to \text{Vt Np}) =\frac{105}{1000}$$

3.4 用PCFG解析

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

$$\arg \max_{t\in \mathcal T_G(s)} p(t)$$

本节将描述针对此问题的动态规划算法——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$个单词。 算法的输出是

$$\arg \max_{t\in \mathcal T_G(s)} p(t)$$

​ 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$为树的根。

• 定义

  $$\pi(i,j ,X) = \max_{t\in \mathcal T(i,j ,X) } p(t)$$

  （如果$\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$，那么

$$p(t) =\prod_{i=1}^m q(\alpha_i\to \beta_i)$$

​ 特别的，我们有

$$\pi(1,n ,S) =\max_{t\in \mathcal T(s)} p(t)$$

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

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

$$\pi(i,i ,X)=\begin{cases} q(X\to x_i) & 如果X\to x_i \in R\\ 0 & 其他情形 \end{cases}$$

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

$$\begin{eqnarray*} \pi(i,j ,X) =\max_{X\to Y\ Z \in R,s\in \{i...(j-1)\}} (q(X\to Y\ Z)\times \pi(i, s, Y) \times \pi(s+1, j, Z))\tag {1} \end{eqnarray*}$$

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

​ 图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中的递归规则的示例，考虑解析句子

$$x_1...x_8= \text{the dog saw the man with the telescope}$$

并考虑$π(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 \}$。 因此，我们对以下几项取最大值：

$$q(\text{VP}\to \text{Vt NP}) \times \pi(3,3,\text{Vt})\times \pi(4,8,\text{NP})\\ q(\text{VP}\to \text{VP PP}) \times \pi(3,3,\text{VP})\times \pi(4,8,\text{PP})\\ q(\text{VP}\to \text{Vt NP}) \times \pi(3,4,\text{Vt})\times \pi(5,8,\text{NP})\\ q(\text{VP}\to \text{VP PP}) \times \pi(3,4,\text{VP})\times \pi(5,8,\text{PP})\\ q(\text{VP}\to \text{Vt NP}) \times \pi(3,5,\text{Vt})\times \pi(6,8,\text{NP})\\ q(\text{VP}\to \text{VP PP}) \times \pi(3,5,\text{VP})\times \pi(6,8,\text{PP})\\ ...\\ q(\text{VP}\to \text{Vt NP}) \times \pi(3,7,\text{Vt})\times \pi(8,8,\text{NP})\\ q(\text{VP}\to \text{VP PP}) \times \pi(3,7,\text{VP})\times \pi(8,8,\text{PP})$$

​ 我们如何证明这种递归定义？ 关键的观察是任何以$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$。

• 我们有

  $$p(t) = q(X \to Y\ Z) × p(t_1) × p(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$的更高得分子树。

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

$$\pi(i,j ,X) =\max_{X\to Y\ Z \in R,s\in \{i...(j-1)\}} (q(X\to Y\ Z)\times \pi(i, s, Y) \times \pi(s+1, j, Z))$$

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

$$q(X\to Y\ Z)\times \pi(i, s, Y) \times \pi(s+1, j, Z)$$

这是以$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)= \sum_{t\in \mathcal T_G(s)} p(t)$$

这里$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$为树的根。

• 定义

  $$\pi(i,j ,X) = \sum_{t\in \mathcal T(i,j ,X) } p(t)$$

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

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

$$\pi(1,n ,S)= \sum_{t\in \mathcal T_G(s)} p(t) =p(s)$$

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

$$\pi(i,i ,X)=\begin{cases} q(X\to x_i) & 如果X\to x_i \in R\\ 0 & 其他情形 \end{cases}$$

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

$$\begin{eqnarray*} \pi(i,j ,X) =\sum_{X\to Y\ Z \in R,s\in \{i...(j-1)\}} (q(X\to Y\ Z)\times \pi(i, s, Y) \times \pi(s+1, j, Z))\tag {2} \end{eqnarray*}$$

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

本讲测验题

Coursera部分

1.

利用定义计算即可

$$p=0.9\times 1\times 0.8\times 0.5\times 1\times 1=0.36$$

2.

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

3.

利用公式

$$q_{ML}(\alpha \to \beta) = \frac{\text{Count}(\alpha \to \beta)}{\text{Count}(\alpha)}$$

此处

$$\text{Count}(\text{NP})= 7,\text{Count}(\text{NP}\to \text{NP PP})=2$$

所以答案为

$$\frac 2 7 \approx 0.286$$

4.

显然我们应该有

$$q(\text{VP}\to \text{V N/PP})\times q(\text{V N/PP} \to \text{N PP})= q(\text{VP}\to \text{V N PP})$$

所以

$$q(\text{VP}\to \text{V N/PP})= 0.4$$

5.

利用定义即可

$$\pi(1,2,\text{NP}) =0.5\times 1.0\times 0.1 = 0.05$$

6.

利用公式

$$\pi(i,j ,X) =\max_{X\to Y\ Z \in R,s\in \{i...(j-1)\}} (q(X\to Y\ Z)\times \pi(i, s, Y) \times \pi(s+1, j, Z))$$

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

$$\begin{aligned} q(\text{VP}\to \text{V NP})\times \pi(3,3,\text{V}) \times \pi (4,8,\text{NP})&=0.002\\ q(\text{VP}\to \text{VP PP})\times \pi(3,5,\text{VP}) \times \pi (6,8,\text{PP})&=0.05\\ q(\text{VP}\to \text{VP NP})\times \pi(3,6,\text{VP}) \times \pi (7,8,\text{NP})&=0.02\\ q(\text{VP}\to \text{VP N})\times \pi(3,7,\text{VP}) \times \pi (8,8,\text{N})&=0.001 \end{aligned}$$

所以

$$\pi(3,8,\text{VP})=0.05$$

课内部分

1.

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

$$\pi(i, s, Y) \times \pi(s+1, j, Z)$$

2.

回顾之前定义的$\pi(i, j ,X)$，在left-branch条件下一定有$i=1$，所以可以得到如下算法：

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

  • 令$j=1+l$

  • $X\in N $，计算

    $$\pi(1, j, X)=\max _{x \rightarrow Y Z \in R}(q(X \rightarrow Y Z) \times \pi(1, j-1, Y) \times \pi(j, j, Z))$$

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

3.

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

4.

$$\begin{aligned} &\mathrm{S} \rightarrow \mathrm{A} \text { FA } &q(\text{A}|*) \\ &\mathrm{S} \rightarrow \mathrm{B}\ \mathrm{FB} &q(\text{B}|*)\\ &\mathrm{S} \rightarrow \mathrm{A} & q(\text{A}|*)\times q (\text{STOP|A}) \\ &\mathrm{S} \rightarrow \mathrm{B} & q(\text{B}|*)\times q (\text{STOP|B}) \\ &\mathrm{FA} \rightarrow \mathrm{A}\ \mathrm{FA} &q (\mathrm A | \mathrm A)\\ &\mathrm{FA} \rightarrow \mathrm{A} & q (\mathrm A | \mathrm A) \times q(\mathrm {STOP} | \mathrm A)\\ &\mathrm{FA} \rightarrow \mathrm{B}\ \mathrm{FB}& q (\mathrm B | \mathrm A) \\ &\mathrm{FA} \rightarrow \mathrm{B}& q (\mathrm B | \mathrm A) \times q(\mathrm {STOP} | \mathrm B)\\ &\mathrm{FB} \rightarrow \mathrm{A}\ \mathrm{FA} &q (\mathrm A | \mathrm B)\\ &\mathrm{FB} \rightarrow \mathrm{A}&q (\mathrm A | \mathrm B)\times q(\mathrm {STOP} | \mathrm A) \\ &\mathrm{FB} \rightarrow \mathrm{B}\ \mathrm{FB} &q (\mathrm B | \mathrm B)\\ &\mathrm{FB} \rightarrow \mathrm{B} &q (\mathrm B | \mathrm B) \times q(\mathrm {STOP} | \mathrm B) \\ &\mathrm A \rightarrow \mathrm s & e (\mathrm s |\mathrm A)\\ &\mathrm A \rightarrow \mathrm t& e (\mathrm t |\mathrm A)\\ &\mathrm{B} \rightarrow \mathbf{s}& e (\mathrm s |\mathrm B)\\ &\mathrm B \rightarrow\mathrm t& e (\mathrm t |\mathrm B) \end{aligned}$$

（注意上述概率没有归一化。）