E.1 概率上下文无关文法

对上下文无关文法最简单的扩充，是 概率上下文无关文法（Probabilistic Context-Free Grammar, PCFG），也称随机上下文无关文法（Stochastic Context-Free Grammar, SCFG），最早由 Booth（1969）提出。回忆一下，上下文无关文法 $G$ 由四个参数 $(N,\Sigma,R,S)$ 定义；概率上下文无关文法也由四个参数定义，但对 $R$ 中每条规则略作扩充：

$N$ ：非终结符（变量）的集合；
$\Sigma$ ：终结符的集合，且与 $N$ 不相交；
$R$ ：规则或产生式的集合，每条形如 $A\to\beta\;[p]$ ，其中 $A$ 是非终结符， $\beta$ 是由 $(\Sigma\cup N)^*$ 中符号组成的字符串， $p$ 是 0 到 1 之间的数，表示 $P(\beta\mid A)$ ；
$S$ ：指定的开始符号。

也就是说，PCFG 与标准 CFG 的区别在于， $R$ 中每条规则都附有一个条件概率：

A\to\beta\quad[p]\tag{E.1}

这里 $p$ 表示给定非终结符 $A$ 时，把它展开为序列 $\beta$ 的概率，也就是给定左部（LHS）非终结符 $A$ 时某个展开式 $\beta$ 的条件概率。该概率可以写作

P(A\to\beta),\qquad P(A\to\beta\mid A),\qquad \text{或}\quad P(RHS\mid LHS).

因此，考虑一个非终结符所有可能的展开时，它们的概率之和必须为 1：

\sum_\beta P(A\to\beta)=1

图 E.1 给出一个 PCFG，它是微型英语 CFG 语法及词典 $\mathcal L_1$ 的概率扩充。每个非终结符的所有展开概率之和都是 1。还要注意，这些概率只是为教学目的编造的。真实语法中，每个非终结符有多得多的规则，因此任何特定规则的概率通常都小得多。

语法	概率	词典	概率
S → NP VP	.80	Det → that / a / the	.10 / .30 / .60
S → Aux NP VP	.15	Noun → book / trip / meal / money / flight / dinner	.10 / .30 / .05 / .05 / .40 / .10
S → VP	.05	Verb → book / include / prefer	.30 / .30 / .40
NP → Pronoun	.35	Pronoun → I / she / me / you	.40 / .05 / .15 / .40
NP → Proper-Noun	.30	Proper-Noun → Houston / NWA	.60 / .40
NP → Det Nominal	.20	Aux → does / can	.60 / .40
NP → Nominal	.15	Preposition → from / to / on / near / through	.30 / .30 / .20 / .15 / .05
Nominal → Noun	.75
Nominal → Nominal Noun	.20
Nominal → Nominal PP	.05
VP → Verb	.35
VP → Verb NP	.20
VP → Verb NP PP	.10
VP → Verb PP	.15
VP → Verb NP NP	.05
VP → VP PP	.15
PP → Preposition NP	1.0

图 E.1 微型英语 CFG 语法和词典的概率扩充。这些概率仅用于教学，并非根据语料库估计；真实语料库包含更多规则，所以各规则的真实概率会小得多。

如果该语言中所有句子的概率之和为 1，就称 PCFG 是一致的。某些递归规则会使一些句子的推导无限循环，从而导致语法不一致。例如，概率为 1 的规则 $S\to S$ 会产生永不终止的推导，使概率质量丢失。关于一致和不一致语法的更多细节，参见 Booth and Thompson（1973）。

PCFG 有什么用途？它可以估计与句子及其分析树有关的多种有用概率，包括某棵特定分析树的概率（用于消歧）和某个句子或句子片段的概率（用于语言模型）。下面具体说明。

E.1.1 PCFG 用于消歧¶

PCFG 为句子 $S$ 的每棵分析树 $T$ （即每个推导）分配概率，这一属性可用于消歧。例如，考虑图 E.2 中句子“Book the dinner flight”的两种分析。左边合理的分析表示“预订提供晚餐的航班”；右边不合理的分析则只能表示类似“代表‘晚餐’预订航班”的意思，正如结构相似的“Can you book John a flight?”表示“你能替 John 预订一个航班吗？”

一棵特定分析树 $T$ 的概率，定义为树中 $n$ 个非终结节点展开时所用 $n$ 条规则的概率之积，其中规则 $i$ 可写成 $LHS_i\to RHS_i$ ：

P(T,S)=\prod_{i=1}^nP(RHS_i\mid LHS_i)\tag{E.2}

所得概率 $P(T,S)$ 既是分析树与句子的联合概率，也是分析树本身的概率 $P(T)$ 。为什么？根据联合概率的定义：

P(T,S)=P(T)P(S\mid T)\tag{E.3}

由于分析树已经包含句子的全部词语， $P(S\mid T)=1$ ，所以：

P(T,S)=P(T)P(S\mid T)=P(T)\tag{E.4}

可以把推导所用各规则的概率相乘，计算图 E.2 两棵树的概率。令左树为 $T_{left}$ ，右树为 $T_{right}$ ：

P(T_{left})=.05*.20*.20*.20*.75*.30*.60*.10*.40=2.2\times10^{-6}

P(T_{right})=.05*.10*.20*.15*.75*.75*.30*.60*.10*.40=6.1\times10^{-7}

图 E.2 一个歧义句子的两棵分析树。左侧分析对应合理含义“预订提供晚餐的航班”，右侧分析对应不合理含义“代表‘晚餐’预订航班”。

图 E.2 的左树概率远高于右树。因此，选择 PCFG 概率最高分析的消歧算法会正确选择左树。

下面形式化“选择概率最高的分析就是正确消歧方式”这一直觉。考虑给定句子 $S$ 的所有可能分析树。词串 $S$ 称为任何覆盖 $S$ 的分析树的产出（yield）。在所有产出为 $S$ 的分析树中，消歧算法选择给定 $S$ 时概率最大的分析树：

\hat T(S)=\operatorname*{argmax}_{T\;s.t.\;S=\operatorname{yield}(T)}P(T\mid S)\tag{E.5}

按定义， $P(T\mid S)$ 可改写为 $P(T,S)/P(S)$ ：

\hat T(S)=\operatorname*{argmax}_{T\;s.t.\;S=\operatorname{yield}(T)}\frac{P(T,S)}{P(S)}\tag{E.6}

因为我们在同一句子的所有分析树上取最大值，所以每棵树的 $P(S)$ 都是常数，可以消去：

\hat T(S)=\operatorname*{argmax}_{T\;s.t.\;S=\operatorname{yield}(T)}P(T,S)\tag{E.7}

又因为上面已证明 $P(T,S)=P(T)$ ，选择最可能分析的最终公式简化为选择概率最高的分析树：

\hat T(S)=\operatorname*{argmax}_{T\;s.t.\;S=\operatorname{yield}(T)}P(T)\tag{E.8}

E.1.2 PCFG 用于语言建模¶

PCFG 的第二个属性，是能为构成句子的词串分配概率。这对语音识别、机器翻译、拼写纠错、辅助沟通及其他应用中的语言建模都很重要。无歧义句子的概率是 $P(T,S)=P(T)$ ，即该句唯一分析树的概率；歧义句子的概率则是该句所有分析树的概率之和：

P(S)=\sum_{T\;s.t.\;S=\operatorname{yield}(T)}P(T,S)\tag{E.9}

PCFG 对语言建模还有一项有用特征：它能为句子的子串分配概率。例如，假设要知道给定目前看到的全部词 $w_1,\ldots,w_{i-1}$ 时，下一个词 $w_i$ 的概率。一般公式为：

P(w_i\mid w_1,w_2,\ldots,w_{i-1})=\frac{P(w_1,w_2,\ldots,w_{i-1},w_i)}{P(w_1,w_2,\ldots,w_{i-1})}\tag{E.11}

第 3 章用 n 元语法近似这一概率，只以最后一个或两个词为条件，而不是整个上下文；二元语法近似为：

P(w_i\mid w_1,w_2,\ldots,w_{i-1})\approx\frac{P(w_{i-1},w_i)}{P(w_{i-1})}\tag{E.12}

然而，n 元语法模型只能利用几个上下文词，因此忽略了可能有用的预测线索。考虑 Chelba and Jelinek（2000）的句子，在其中预测 after：

（E.13） the contract ended with a loss of 7 cents after trading as low as 9 cents

三元语法只能根据 7 cents 预测 after，但动词 ended 和主语 contract 显然会是有用的预测因素，PCFG 句法分析器能帮助我们利用这些因素。事实上，PCFG 可以像式（E.11）那样以整个先前上下文 $w_1,w_2,\ldots,w_{i-1}$ 为条件。

总之，PCFG 既可以用于句法分析中的消歧，也可以用于语言模型中的词预测。这两类应用都要求我们能够计算给定句子 $S$ 时分析树 $T$ 的概率。下面几节介绍计算这一概率的算法。