Michael Collins NLP Lecture 6

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

课程网盘地址：

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

这一讲主要介绍了词汇化概率上下文无关法（Lexicalized Probabilistic Context-Free Grammars）。

Chapter 4 词汇化概率上下文无关法(Lexicalized Probabilistic Context-Free Grammars)

1.介绍

在之前的讲义中，我们引入了概率上下文无关法（PCFG）作为统计解析的模型。我们介绍了基本的PCFG形式；描述了如何从一组训练样本（“树库”）中估计PCFG的参数；并且导出了用于使用PCFG进行解析的动态规划算法。

不幸的是，我们描述的基本PCFG是一个相当差的统计解析模型。本文将介绍词汇化的PCFG，它直接构建在常规PCFG的思想上，但提供了更高的解析精度。本讲义的其余部分结构如下：

在第2节中，我们将描述基本PCFG的一些弱点，特别是关注它们对词汇信息缺乏敏感性。
在第3节中，我们将描述推导词汇化PCFG的第一步：在树库解析中向非终止符添加词汇项的过程。
在第4节中，我们将给出词汇化PCFG的正式定义。
在第5节中，我们将描述如何从树库中估计词汇化PCFG的参数。
在第6节中，我们将描述一种用于对词汇化PCFG进行解析的动态规划算法。

2.PCFG作为解析模型的弱点

我们关注PCFG的两个关键弱点：1）对词汇信息缺乏敏感性; 2）对结构偏好缺乏敏感性。问题（1）是转向词汇化PCFG的潜在动机。在后面的讲座中，我们将描述解决问题（2）的词汇化PCFG的扩展。

2.1 缺乏对词汇信息的敏感性

首先，考虑如下解析树：

在PCFG模型下，这棵树将具有概率

$\begin{aligned} &q(\text{S → NP VP}) × q(\text{VP → VB NP}) × q(\text{NP → NNP}) × q(\text{NP → NNP})\\ &×q(\text{NNP → IBM}) × q(\text{VB → bought}) × q(\text{NNP → Lotus}) \end{aligned}$

回想一下，对于任何规则$\alpha\to \beta$，$q(\alpha \to \beta)$是一个相关的参数，可以解释为给定$\alpha$在规则左侧，在规则右侧看到$\beta$的条件概率。

如果我们考虑这个解析树中的词汇项（即IBM，buy和Lotus），我们可以看到PCFG做出了非常强的独立性假设。直观地，每个词汇项的标识仅取决于词汇项上方的词性（POS）：例如，IBM的选择取决于其标签NNP，但不直接依赖于树中的其他信息。更正式地说，给定单词上方的词性POS，字符串中每个单词的选择就条件独立于整个树。这显然是一个非常强的假设，它会导致解析中的许多问题。我们将看到词汇化的PCFG以非常直接的方式解决了PCFG的这种弱点。

现在让我们看一下PCFG在特定类型的歧义——介词短语（PP）歧义下的表现。图1显示了同一句子的两个解析树，包括介词短语（PP）歧义。图2列出了两个解析树的上下文无关规则集。一个关键的观察结果如下：两个解析树具有相同的规则，除了树（a）中的$\text{VP} \to \text{VP PP}$，以及树（b）中的$\text{NP} \to \text{NP PP}$。因此，概率解析器在两个解析树之间进行选择时，将选择树（a），如果

$q(\text{VP} \to \text{VP PP}) > q(\text{NP} \to \text{NP PP})$

将选择树（b），如果

$q(\text{NP} \to \text{NP PP})> q(\text{VP} \to \text{VP PP})$

请注意，此决定完全独立于两个输入句子中的任何词汇信息（单词）。对于这种特殊情形的歧义（将PP或VP的附加到PP，其中只可能附加一个NP或一个VP），如果$q(\text{VP} \to \text{VP PP}) > q(\text{NP} \to \text{NP PP})$，解析器将始终将PP附加到VP ，如果$q(\text{NP} \to \text{NP PP})> q(\text{VP} \to \text{VP PP})$，则反过来总是将PP附加到NP。

在这种特定情况下对词汇信息缺乏敏感性——介词短语附加的歧义，已知是高度非最优的。涉及的词汇项可以提供关于是否附加到名词或动词的非常有力的证据。如果我们看一下介词，into，我们会发现带有into作为介词的PP几乎以九倍概率附加到VP而不是NP（这个统计数据来自滨州树库数据）。作为另一个例子，带有介词of的PPs附加到NP的概率大约是附加到VP的概率的100倍。但PCFG在完成附加决定时完全忽略了介词。

作为另一个例子，考虑图3中所示的两个解析树。在这种情况下，可以验证两个解析树具有相同的上下文无关规则集（唯一的区别在于应用这些规则的顺序）。因此，PCFG将为这两个解析树分配相同的概率，同样完全忽略词汇信息。

总之，我们描述的PCFG生成词汇项仅依赖于树中直接位于它们之上的POS。这是一个非常强的独立性假设，这会导致解析器在许多重要的有歧义情况下做出非最佳决策。

2.2 缺乏对结构偏好的敏感性

PCFG的第二个弱点是他们对结构偏好缺乏敏感性。我们通过几个例子来说明这个弱点。

首先，考虑president of a company in Africa的两个可能解析，如图4所示。这个名词短语再次涉及一个介词短语附加歧义的案例：PP in Africa可以附加于president或company。可以再次验证这两个解析树包含完全相同的上下文无关规则集，因此在PCFG下将获得相同的概率。

在这种情况下，词汇信息当然可以再次提供帮助。然而，另一个有用的信息来源可能是关于结构偏好的基本统计（忽略词汇项的偏好）。第一个解析树涉及以下形式的结构，其中最后的PP（在示例中in Africa）附加到最近的NP（company）：

最后的PP的这种附加通常被称为紧密附加(close attachment)，因为PP附加在最接近的NP上。第二个解析结构具有形式

其中PP附加到更远的NP（示例中的president）。

我们可以再次从树库中查看结构1与2的频率的统计数据：结构1的频率大约是结构2的频率的两倍。因此，对于紧密附加存在相当显著的偏好。同样，我们强调PCFG为这两棵树分配相同的概率，因为它们包含相同的规则集：因此在这种情况下，PCFG无法捕捉到紧密附加的偏好。

还有许多其他例子，这些例子中紧密附加是消除歧义结构的有用提示。当在两个不同动词的附加之间做出选择时，偏好性可能会更强。例如，考虑以下这句话

$\text{John was believed to have been shot by Bill}$

在这里，介词PP by Bill可以修饰动词shot（比尔正在射击）或believe（比尔正在相信）。然而，来自树库的统计数据显示，当PP可以附加到两个潜在动词时，附加到最近动词的可能性大约是20倍。同样，基本的PCFG通常会给出相同的两个结构提供相同的概率，因为它们包含相同的规则集。

3.树库的词汇化

我们现在描述词汇化的PCFG如何解决PCFG的第一个基本弱点：他们对词汇信息缺乏敏感性。本节中描述的第一个关键步骤是对底层树库进行词汇化。

图5显示了词汇化之前和之后的解析树。词汇化步骤已经用诸如$\text{S(questioned)}$或$\text{NP(lawyer)}$的新的终止符替换了诸如S或NP的非终止符。

本节的其余部分将详细描述树的词汇化方法。首先，我们给出了这一步骤的潜在动机。基本的想法是将基本PCFG中诸如此类的规则

$\text{S→ NP VP}$

替换为词汇化PCFG中的规则

$\text{S(questioned) →NP(lawyer) VP(questioned)}$

符号$\text{S(questioned),NP(lawyer),VP(questioned)}$是语法中的非终止符。每个非终止符现在包括一个词汇项；由此产生的模型对词汇信息的敏感度要高得多。

从某种意义上说，以形式的角度来看，没有任何改变：我们将简单地从具有相对较少数量的非终止符（S，NP等）的PCFG转移到具有更大的非终止符集合的PCFG（$\text{S(questioned),
NP(lawyer)}$等）。然而，这将导致语法中规则和非终止符数量的急剧增加：因此，我们必须谨慎估计基本PCFG的参数。我们将在下一节中描述如何做到这一点。

然而，首先，我们将描述如何执行词汇化过程。关键的想法对每个上下文无关规则

$X → Y_1 Y_2 . . . Y_n$

确定规则主部(head)的索引$h\in \{1…n\}$。上下文无关规则的主部直观地对应于规则的“中心”或最重要的子项。例如，对于规则

$\text{S→ NP VP}$

主部将是$h = 2$（对应于VP）。对于规则

$\text{NP→NP PP PP PP}$

主部将是$h = 1$（对应于NP）。对于规则

$\text{PP→ IN NP}$

主部将是$h = 1$（对应于IN），依此类推。

一旦识别出每个上下文无关规则的主部，就可以通过树库中的解析树自下而上地传播词汇信息。例如，如果我们考虑子树

并假设如下规则的主部为$h=2$(NN)

$\text{NP→DT NN}$

词汇化的子树是

诸如DT或NN之类的词性接收它们下面的词汇项作为它们的主要单词。树中较高的非终止符接收来自其主要子项的词汇项：例如，本例中的NP接收词汇项lawyer，因为这是与NN相关联的词汇项，NN是NP的主要子项。为清楚起见，我们用上划线对词汇化解析树中每个主要规则做标记（在这个例子中，我们有$\overline {\text{NN}}$）。有关完整词汇化树的示例，请参见图5。

另一个例子，考虑图5中解析树中的VP。在对VP进行词汇化之前，解析结构如下（我们使用前面描述的步骤填充树中较低的词汇项）：

然后我们将Vt识别为规则$\text{VP→Vt NP}$的主部，并按如下方式对树进行词汇化：

总之，一旦识别出每个上下文无关规则的主部，词汇项就可以通过解析树自下而上传播，以提供如图5（b）所示的词汇化树。

剩下的问题是如何识别主部。理想情况下，每个规则的主部都会在所讨论的树库中注释：但实际上，这些注释通常不存在。相反，研究人员通常使用一组简单的规则来自动识别每个无上下文规则的主部。

作为一个示例，图6给出了一组示例规则，其标识左侧是NP的规则的主部。图7显示了一组用于VP的规则。在这两种情况下，我们都看到寻找特定的孩子的规则（例如，NP案例的NN，VP案例的Vi）。这些规则具有相当的启发性，但依赖于一些指导，尽管它们很简单，但它们在实际中效果很好。

4.词汇化PCFGs

词汇化PCFG的基本思想是替换诸如此类的规则

$\text{S→ NP VP}$

为如下词汇化的规则，如

$\text{S(examined) → NP(lawyer) VP(examined)}$

因此，我们用诸如$\text{S(examined)}$或$\text{NP(lawyer) }$之类的词汇化非终止符替换了简单的非终止符，例如$\text{S}$或$\text{NP}$。

以形式的角度来看，没有任何改变：我们可以像处理常规的PCFG一样对待新的词汇化语法。我们刚刚将语法中的非终止符数量从一个相当小的数量（比如$20$或$50$）扩展到一个大得多的数量（因为每个非终止符现在都有一个词汇项，我们可以轻松地拥有成千上万个的非终止符）。

词汇化PCFG中的每个规则都将具有相关参数，例如上述规则将具有参数

$q(\text{S(examined) → NP(lawyer) VP(examined)})$

模型中存在大量参数，我们在估计它们时必须要小心：下一节将介绍参数估计方法。

接下来我们将以Chomsky正规形式给出词汇化PCFG的正式定义。首先，我们需要处理一个细节：词汇化PCFG中的每个规则左侧都有带有主单词的非终止符，例如规则

$\text{S(examined) → NP(lawyer) VP(examined)}$

在左侧有$\text{S(examined) }$。此外，该规则有两个子项。两个子项中的一个必须具有与左侧相同的词汇项：在此例子中，$\text{VP(examined)}$是具有此属性的子项。要明确哪个子项与左侧共享词汇项，我们将为规则添加注释，使用$\to _1$指定左子项与父项共享词汇项，并使用$\to _2$指定右子项与父项共享词汇项。所以上面的规则现在写成了

$\text{S(examined)} \to_2 \text{NP(lawyer) VP(examined)}$

在这种情况下，额外的符号似乎是不必要的，因为很明显第二个子项是规则的主部——它是唯一一个和规则左侧具有相同词汇项的子项，$\text{examined}$。但是，这些信息对于两个子项都有相同词汇项的规则很重要：例如规则

$\text{PP(in)} \to_1 \text{PP(in) PP(in)}$

以及

$\text{PP(in)} \to_2\text{PP(in) PP(in)}$

这里我们需要指定两个子项中哪一个是规则的主部。

现在我们给出如下定义：

定义1（Chomsky正规形式的词汇化PCFG）

Chomsky正规形式的词汇化PCFG是一个$6$元组$G =(N,\Sigma,R,S,q,\gamma)$，其中：

$N$是语法中的一组有限的非终止符。
$\Sigma$是语法中一组有限的词汇项。
$R$是规则的集合。每个规则采用以下三种形式之一：
$\begin{aligned} &1.X(h)\to_1 Y_1(h)Y_2(m)，其中X,Y_1,Y_2\in N,h,m\in\Sigma\\ &2.X(h)\to_2 Y_1(m)Y_2(h)，其中X,Y_1,Y_2\in N,h,m\in\Sigma\\ &3.X(h)\to h，其中X\in N, h\in \Sigma \end{aligned}$
对于每个规则$r\in R$，存在相关参数
$q(r)$
其中参数满足$q(r)\ge 0$，对于任何$X\in N,h\in\Sigma$，
$\sum_{r\in R:LHS(r)=X(h)} q(r)=1$
我们使用$LHS(r)$来指代任何规则$r$的左侧。
对于每个$X\in N,h\in\Sigma$，存在参数$\gamma(X,h)$。我们有$\gamma(X,h)\ge 0$以及$\sum_{X\in N,h\in \Sigma}\gamma(X,h)=1$.

给定语法下的最左派生$r_1,r_2,…r_N$，其中每个$r_i$是$R$的成员，派生的概率是

$\gamma(LHS(r_1))\times \prod_{i=1}^N q(r_i)$

例如，考虑图5中的解析树，这里重复如下：

因此，该模型看起来非常类似于常规PCFG，其中树的概率为某些项的乘积，每一项是树中的每个规则。一个区别是我们要乘以树的根：$\gamma( \text{S, questioned})$，这一项可以解释为在树的根部选择非终止符$ \text{S(questioned)}$的概率。（回想一下，在常规PCFG中，我们指定特定的非终终止符号，例如$\text{S}$，总是出现在树的根部。）

5.词汇化PCFG的参数估计

我们现在描述一种在词汇化PCFG中进行参数估计的方法。模型中规则（以及因此产生的参数）的数量非常大。然而，通过本课程前面描述的适当的平滑使用技术，对于语言模型，我们可以推导出在实际中稳健且有效的估计。

首先，对于给定如下形式的规则

$X(h)\to_1 Y_1(h)Y_2(m)$

或

$X(h)\to_2 Y_1(m)Y_2(h)$

定义以下变量：$X$是规则左侧的非终止符； $H$是该非终止符的主部；$R$是使用的规则，形式为$X→_1 Y_1 Y_2$或$X→_2 Y_1 Y_2$的形式；$M$是修饰词。

例如，对于规则

$\text{S(examined)}\to_2 \text{NP(lawyer) VP(examined)}$

我们有

$\begin{aligned} X&=S\\ H&=\text{examined}\\ R&=\text{S} \to_2 \text{NP VP}\\ M&=\text{lawyer} \end{aligned}$

根据这些定义，规则的参数具有以下解释：

$\begin{aligned} &q(\text{S(examined)}\to_2 \text{NP(lawyer) VP(examined)})\\ =& P(R=\text{S} \to_2 \text{NP VP},M=\text{lawyer}| X=S,H=\text{examined}) \end{aligned}$

推导$q(\text{S(examined)}\to_2 \text{NP(lawyer) VP(examined)})$的估计的第一步是使用链式法则将上述表达式分解为两项：

$\begin{eqnarray*} &&P(R=\text{S} \to_2 \text{NP VP},M=\text{lawyer}| X=S,H=\text{examined}) \\ =&& P(R=\text{S} \to_2 \text{NP VP}| X=S,H=\text{examined})\tag{3} \\ &&\times P(M=\text{lawyer}|R=\text{S} \to_2 \text{NP VP}, X=S,H=\text{examined}) \tag{4} \end{eqnarray*}$

根据概率论的链式法则，这一步是准确的。

我们现在将得出公式3，4中量的各自的平滑估计。首先，对于公式3定义以下最大似然估计：

$\begin{aligned} q_{ML}(\text{S} \to_2 \text{NP VP}| S,\text{examined}) &= \frac{\text{Count}(R=\text{S} \to_2 \text{NP VP},X=S,H=\text{examined})} {\text{Count}(X=S,H=\text{examined})} \\ q_{ML}(\text{S} \to_2 \text{NP VP}| S)&= \frac{\text{Count}(R=\text{S} \to_2 \text{NP VP},X=S)} {\text{Count}(X=S)} \end{aligned}$

这里$\text{Count}(…)$表达式是直接从训练样本（树库中的词汇化树）导出的计数。我们对下式的估计

$P(R=\text{S} \to_2 \text{NP VP}| X=S,H=\text{examined})$

定义为

$\lambda_1 \times q_{ML}(\text{S} \to_2 \text{NP VP}| S,\text{examined}) +(1-\lambda_1) \times q_{ML}(\text{S} \to_2 \text{NP VP}| S)$

其中$\lambda_1$表示两个估计的相对权重（我们有$0\le \lambda_1\le 1$）。$\lambda_1$的值可以使用本课程语言建模讲义中描述的方法进行估计。

接下来，考虑我们对公式4中表达式的估计。我们可以定义以下两个最大似然估计：

$\begin{aligned} q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP},\text{examined}) &= \frac{\text{Count}(M=\text{lawyer},R=\text{S} \to_2 \text{NP VP},H=\text{examined})} {\text{Count}(R=\text{S} \to_2 \text{NP VP},H=\text{examined})} \\ q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP})&= \frac{\text{Count}(M=\text{lawyer},R=\text{S} \to_2 \text{NP VP})} {\text{Count}(R=\text{S} \to_2 \text{NP VP})} \end{aligned}$

我们对下式的估计

$P(M=\text{lawyer}|R=\text{S} \to_2 \text{NP VP}, X=S,H=\text{examined})$

定义为

$\lambda_2 \times q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP},\text{examined}) +(1-\lambda_2) \times q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP})$

其中$0\le \lambda_2\le 1$是指定两项的相对权重的参数。

将这些估计放在一起，我们对规则参数的最终估计如下：

$\begin{eqnarray*} &&P(R=\text{S} \to_2 \text{NP VP},M=\text{lawyer}| X=S,H=\text{examined}) \\ =&&(\lambda_1 \times q_{ML}(\text{S} \to_2 \text{NP VP}| S,\text{examined}) +(1-\lambda_1) \times q_{ML}(\text{S} \to_2 \text{NP VP}| S)) \\ &&\times (\lambda_2 \times q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP},\text{examined}) +(1-\lambda_2) \times q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP})) \end{eqnarray*}$

可以看出，该估计结合了特定于词汇的信息，例如估计

$q_{ML}(\text{S} \to_2 \text{NP VP}| S,\text{examined}) \\ q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP},\text{examined})$

以及较少依赖词汇信息的估计，例如

$q_{ML}(\text{S} \to_2 \text{NP VP}| S) \\ q_{ML}(\text{lawyer}|\text{S} \to_2 \text{NP VP})$

最终结果是一个对词汇信息敏感的模型，但它仍然是健壮的，因为我们使用了模型中大量参数的平滑估计。

6.用词汇化的PCFG进行解析

词汇化PCFG的解析算法与常规PCFG的解析算法非常相似。回想一下，对于常规PCFG，用于解析的动态规划算法利用动态规划表$\pi(i,j,X)$。每一项$\pi(i,j,X)$存储以非终止符$X$为根的任何解析树的最高概率，单词$i…j$包含在输入句中。可以使用递归定义完成这些值，如下所示。假设算法的输入句子是$x_1…x_n$。递归的基本情况是$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)) \end{eqnarray*}$

因此，我们对所有$X→Y\ Z$的规则，以及所有分裂点$s∈\{i…(j - 1)\}$取最大值。这种递归是合理的，因为任何以$X$为根的解析树，跨越单词$i…j$，必须由以下选项组成：

树根处的规则$X→Y\ Z$。
分裂点$s∈\{i…(j - 1)\}$。
以$Y$为根，跨越单词$\{i…s\}$的子树。
以$X$为根，跨越单词$\{(s+1)…j\}$的子树。

现在考虑词汇化PCFG的情形。关键的区别在于语法中的每个非终终止符包括词汇项。一个重要的观察是对于给定的输入句子$x_1…x_n$，该句子的解析树只能包含具有$x_1…x_n$之一的词汇项的非终止符。

根据这一观察结果，我们将定义一个动态规划表，其中$\pi(i,j,h,X)$满足

$1\le i\le j\le n, h\in\{i...j\},X\in N$

其中$N$是语法中非词汇化的非终止符的集合。我们给出以下定义：

定义2（用于词汇化PCFG的动态规划表）

$\pi(i,j,h,X)$是任何树根为非终止符$X$和词汇项为$h$的解析树的最高概率，跨越输入中的单词$i…j$。

例如，考虑以下句子：

$\text{workers dumped the sacks into a bin}$

在这种情况下，我们有$n = 7$（句子中有七个单词）。作为一个示例，

$\pi(2, 7, 2,\text{VP})$

将是以$\text{VP(dumped)}$为根的任何子树的最高概率，跨越句子中的单词$2…7$。

可以使用递归定义再次计算$\pi$的值：

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

请注意，这与常规PCFG的基本情形非常相似。例如，上例中，我们将取

$\pi(1,1 ,1,\text{NNS}) =q\text{(NNS(workers) →workers)}$

我们现在考虑递归定义。例如，考虑为我们的例句完成$\pi(2, 7, 2,\text{VP})$的值。考虑以下跨越单词$2…7$的子树，有词汇项$x_2 =\text{dumped}$并在其树根的标签为$\text{VP}$：

我们可以看到这个子树有以下子部分：

分裂点$s\in \{1…6\}$的选择。在这种情况下，我们选择$s=4$（规则$\text{VP(dumped}) →_1 \text{VBD(dumped) PP(into)}$下，分裂点在$x_4=\text{sacks}$后面）。
修饰词$m$的选择。在这种情况下，我们选择$m = 5$，对应于$x_5 =\text{into}$，因为$x_5$是规则$\text{VP(dumped}) →_1 \text{VBD(dumped) PP(into)}$第二个子项的主部。
在树根处选择规则：在这种例子中，规则是$\text{VP(dumped}) →_1 \text{VBD(dumped) PP(into)}$。

更一般地，为了计算任何$\pi(i,j,h,X)$的值，我们需要搜索$s,m$和形如$X(x_h)\to_1 Y_1(x_h)\ Y_2(x_m)$或$X(x_h)\to_2Y_1(x_m)\ Y_2(x_h)$的所有可能的选择。图8显示了此步骤的伪代码。请注意，在枚举$s$和$m$的可能值时需要注意。如果$s$在范围$h…(j-1)$内，那么$h$必须来自左子树；因此$m$必须来自右子树，从而$m$必须在范围$(s+1)…j$内。相反，如果$s$在$i…(h-1)$的范围内，那么$m$必须在左子树中，即在$i … s$的范围内。图8中的伪代码分别处理这两种情况。

图9给出了使用词汇化PCFG进行解析的完整算法。该算法首先完成$\pi$值的递归定义的基本情况。然后它填充其余的值，从$j = i + 1$的情况开始，然后是$j = i + 2$的情况，依此类推。最后，步骤

$(X',h') =\arg \underset{X\in N,h\in \{1...n\}}{\max} \gamma(X,h) \times \pi (1,n, h,X)$

找到对于输入句子的最可能解析树的树根的$X’(h’)$：注意在该步骤中考虑$\gamma$项。然后可以通过从$bp(1,n,h’,X’)$开始的反向指针来恢复最高概率树。

本讲测验题

Coursera部分

1.

1.that

利用

$\text{SBAR}\rightarrow \text{COMP}^{*}$

2.said

利用

$\mathrm{S} \rightarrow \mathrm{NP}\ \mathrm{VP}^{*},\mathrm{VP} \rightarrow \mathbf{V}^{*} \ \mathrm{SBAR}$

3.said

利用

$\mathrm{VP} \rightarrow \mathbf{V}^{*} \ \mathrm{SBAR}$

2.

根据乘法原理可得选(a)

3.

(b)(c)(d)

4.

画图后可得使用的参数为：

(a)(c)(f)

5.

回顾课件中的计算公式：

预测结果为：

$\begin{aligned} \text{NP} : & 2\to3 \\ \text{NP} : & 5\to6 \\ \text{NP} : & 2\to6 \\ \text{PP} : & 4\to6 \\ \text{VP} : & 1\to6 \end{aligned}$

真实结果为：

$\begin{aligned} \text{NP} : & 2\to3 \\ \text{NP} : & 5\to6 \\ \text{VP} : & 1\to3 \\ \text{PP} : & 4\to6 \\ \text{VP} : & 1\to6 \end{aligned}$

所以精确度为

$\frac{4}{5}$

6.

回顾课件中的计算公式：

预测结果为：

$\begin{aligned} \text{ROOT}_0, \text{saw}_1,&\text{ROOT}\\ \text{saw}_1,\text{with}_4,&\text{VP}\to_1 \text{VP PP}\\ \text{dog}_3,\text{with}_4, & \text{NP}\to_1 \text{NP PP}\\ \text{dog}_3, \text{the}_2 ,&\text{NP}\to_2 \text{DT NN}\\ \text{with}_4 , \text{telescope}_6,&\text{PP}\to_1 \text{IN NP}\\ \text{telescope}_6,\text{the}_5,&\text{NP}\to_2 \text{DT NN}\\ \end{aligned}$

真实结果为：

$\begin{aligned} \text{ROOT}_0, \text{saw}_1,&\text{ROOT}\\ \text{saw}_1,\text{with}_4,&\text{VP}\to_1 \text{VP PP}\\ \text{saw}_1,\text{dog}_3, & \text{VP}\to_1 \text{Vt NP}\\ \text{dog}_3, \text{the}_2 ,&\text{NP}\to_2 \text{DT NN}\\ \text{with}_4 , \text{telescope}_6,&\text{PP}\to_1 \text{IN NP}\\ \text{telescope}_6,\text{the}_5,&\text{NP}\to_2 \text{DT NN}\\ \end{aligned}$

所以Dependency Accuracies为

$\frac 5 6 \approx 0.833$

一共有$6$条规则，有$5$条符合。

7.

注意两棵树中不同的规则为

$\begin{aligned} 树1:&\text{N}' \to \text{NN }\text{N}'\\ 树2:&\text{N}' \to \text{N}'\text{ N}' \end{aligned}$

所以(a)(b)均错误，选(c)