概率上下文无关文法 PCFG

小象实战讲义 · 自然语言处理

在上一节中，我们学习了上下文无关文法（CFG）如何为句子生成多种可能的句法解析树。然而，CFG 无法告诉我们哪种解析更“合理”或更“常见”。本节我们将引入概率上下文无关文法（PCFG），通过为每条语法规则赋予概率，量化不同解析树的可能性，从而在句法歧义中做出基于数据的、更优的选择。这是从纯语法规则迈向统计句法分析的关键一步。

💡 核心导读

• PCFG 的定义：在 CFG 的基础上，为每条重写规则 α → β 引入一个概率 q(α → β)，构成一个概率化的语法模型。
• 概率的来源与估计：规则概率通常从已标注的句法树库（Treebank）中，通过最大似然估计（MLE）统计得出。
• 解析树的概率计算：一棵解析树的概率等于其所有节点所用规则概率的乘积。
• CKY 算法：一种基于动态规划的高效算法，用于在 PCFG 下为给定句子寻找概率最大的解析树（最可能解析）。
• 乔姆斯基范式（CNF）：一种算法侧的规范形式——每条规则只能是 X → Y Z 或 X → w。要说清边界：PCFG 这个模型本身并不要求 CNF（它对 α → β 的长度没有限制），是 CKY 这类自底向上的动态规划算法要求 CNF；把语法转成 CNF 是为了跑算法，转换后概率可等值换算，语言不变。

从 CFG 到 PCFG：引入不确定性

回顾 CFG，它由四元组 (N, Σ, S, R) 定义。PCFG 在此基础上增加了一个关键组件：概率函数 Q。

一个 PCFG 定义为五元组 (N, Σ, S, R, Q)，其中：

• N：非终结符集合（如 S, NP, VP）。
• Σ：终结符集合（词汇表）。
• S：起始符号。
• R：规则集合，每条规则形如 α → β，其中 α ∈ N，β ∈ (N ∪ Σ)*。
• Q：从规则 R 到概率的映射函数 q(α → β)，满足概率公理。

概率公理：对于任意非终结符 α ∈ N，其所有可能的展开规则的概率之和必须为 1。即： $$\sum_{\beta: (\alpha \rightarrow \beta) \in R} q(\alpha \rightarrow \beta) = 1$$

这意味着，给定一个非终结符 α，它按规则展开的所有可能性覆盖了一个完整的概率分布。

规则概率的直观例子

以我们熟悉的句子 “the man saw the dog with the telescope” 及其语法为例（本节玩具词表只收 the，不收 a，所以限定词规则只有一条）。假设从语料库中我们统计得到部分规则的概率如下：

• IN → with: 0.6
• IN → in: 0.4
• NN → man: 0.1
• NN → woman: 0.1
• NN → dog: 0.3
• NN → telescope: 0.5
• S → NP VP: 1.0
• VP → Vt NP: 0.5
• VP → VP PP: 0.3
• VP → Vi: 0.2
• NP → DT NN: 0.8
• NP → NP PP: 0.2
• PP → IN NP: 1.0
• Vt → saw: 1.0
• Vi → sleeps: 1.0
• DT → the: 1.0

注意，对于每个非终结符（如 VP），其所有规则概率之和为 1（0.5+0.3+0.2=1）。这些概率并非人为指定，而是从大量已标注的句法树语料中通过最大似然估计（MLE） 计算得来。

这里有一处容易写错、也值得提前点明：上表只列了 DT → the 一条规则，因为本节的玩具词表里只有 the 这一个限定词，语料中不存在 a，所以 DT 的全部展开 就是”the”这一种，概率自然为 1.0。若真要把 DT → a 也收进规则集，两者就不能同时是 1.0（同一左部的概率和为 2，违反概率公理），必须按语料频次分成一对和为 1 的数（例如 0.9 与 0.1）；而且一旦改动，凡树中含 k 个 DT 的解析树概率都会乘以 0.9^k，下游的 CKY 表格与练习答案也要同步改。规则表的改动永远不是”只改一行”——这是 PCFG 实现中最常见的连锁错误来源。

最大似然估计（MLE）计算规则概率

给定一个已标注的句法树库，规则 α → β 的概率 q(α → β) 可以通过以下公式估计： $$q_{ML}(\alpha \rightarrow \beta) = \frac{\text{Count}(\alpha \rightarrow \beta)}{\text{Count}(\alpha)}$$ 其中：

• Count(α → β) 是语料库中规则 α → β 出现的次数。
• Count(α) 是语料库中非终结符 α 作为规则左端出现的总次数。

例如，要估计 IN → with 的概率，我们统计语料中所有介词短语，看 IN 展开为 with 的次数，再除以 IN 出现的总次数。

计算解析树的概率

在 PCFG 中，一棵解析树 t 的概率 P(t) 定义为树中所有节点所用规则概率的乘积。假设树 t 包含 n 个节点，对应规则 r1, r2, ..., rn，则： $$P(t) = \prod_{i=1}^{n} q(r_i)$$

计算示例：考虑句子 “the man saw the dog” 的一种简单解析（假设没有 PP 附着歧义）。 解析树的一部分规则序列可能为：

1. S → NP VP (q=1.0)
2. NP → DT NN (q=0.8)
3. DT → the (q=1.0)
4. NN → man (q=0.1)
5. VP → Vt NP (q=0.5)
6. Vt → saw (q=1.0)
7. NP → DT NN (q=0.8)
8. DT → the (q=1.0)
9. NN → dog (q=0.3)

则该解析树的概率为： P(t) = 1.0 * 0.8 * 1.0 * 0.1 * 0.5 * 1.0 * 0.8 * 1.0 * 0.3 = 0.0096

通过比较不同解析树的概率，我们可以量化地判断哪一种句法结构更可能。对于有歧义的句子，我们选择 P(t) 最大的那棵树作为最可能的解析。

PP 到底挂在谁身上？ 拿完整句子 “the man saw the dog with the telescope” 来说，with the telescope 既可以修饰 dog（NP 附着，望远镜是狗叼着的），也可以修饰 saw（VP 附着，用望远镜看）。两棵树用到的规则只差一处：前者把 PP 并进 NP，用到 NP → NP PP（q=0.2）；后者把 PP 并进 VP，用到 VP → VP PP（q=0.3）。其余规则完全相同，所以两棵树的概率之比就等于这两条规则之比：

$$\frac{P(t_{\text{NP附着}})}{P(t_{\text{VP附着}})} = \frac{0.2}{0.3} \approx 0.667$$

也就是说，VP 附着（saw ... with the telescope，用望远镜看）的概率是 NP 附着的 1.5 倍，模型会选 VP 附着。这个例子同时暴露了 PCFG 的软肋：决定胜负的只是两条全局规则概率，与”狗”和”望远镜”的现实搭配常识毫无关系——这正是后面要讲词汇化 PCFG 的动机。

乔姆斯基范式（CNF）

为了简化算法（特别是接下来的 CKY 算法），我们通常将 PCFG 转换为乔姆斯基范式（Chomsky Normal Form, CNF）。

一个 CNF 语法中的每条规则必须是以下两种形式之一：

1. 二元规则：X → Y Z，其中 X, Y, Z ∈ N（都是非终结符）。
2. 一元终结规则：X → w，其中 X ∈ N，w ∈ Σ（终结符）。

转换意义：任何 CFG/PCFG 都可以转换为等价的 CNF。转换过程可能引入额外的非终结符和规则，但不会改变语法生成的语言集合。CNF 保证了句法树是二叉树（除了叶子节点），这极大地简化了动态规划算法的设计。

我们之前示例中的语法规则，大部分已经符合 CNF（如 NP → DT NN, Vt → saw）。对于不符合的规则（例如 VP → Vt NP PP 这样的三元规则），可以通过引入新的非终结符将其拆分为多个二元规则。

CKY 算法：寻找最可能解析

给定一个已转换为 CNF 形式的 PCFG（CNF 是 CKY 递推的实现前提，不是 PCFG 模型本身的要求）和一个句子 s = w1 w2 ... wn，Cocke–Kasami–Younger (CKY) 算法 可以高效地计算出该句子的最可能解析树及其概率。

算法核心思想：动态规划

CKY 算法采用自底向上（bottom-up）的动态规划策略。其核心是填充一个三维表格（或二维表格的每个单元格是一个字典）。

我们定义：

• π[i, j, X]：表示句子中从第 i 个词到第 j 个词（包含）的子串，以非终结符 X 为根的所有可能解析树中，概率最大的那棵树的概率值。
• bp[i, j, X]：回溯指针，记录为了达到 π[i, j, X] 的最大概率，子串 [i, j] 应该在哪个位置 s 分割，以及分割后的左右子非终结符 Y 和 Z。

算法递推公式

1. 初始化（长度为 1 的子串）： 对于每个位置 i (1 ≤ i ≤ n) 和每个非终结符 X： $$\pi[i, i, X] = \begin{cases} q(X \rightarrow w_i) & \text{if } (X \rightarrow w_i) \in R \\ 0 & \text{otherwise} \end{cases}$$ bp[i, i, X] 为 None（因为是叶子节点）。

2. 递归计算（长度 l 从 2 到 n）： 对于每个起始位置 i (1 ≤ i ≤ n-l+1)，令 j = i + l - 1。 对于每个非终结符 X： $$\pi[i, j, X] = \max_{\substack{(X \rightarrow Y Z) \in R \\ s \in [i, j-1]}} \left[ q(X \rightarrow Y Z) \times \pi[i, s, Y] \times \pi[s+1, j, Z] \right]$$ 同时，记录使上式取最大值的 (s, Y, Z) 到 bp[i, j, X] 中。 如果最大值是 0，则 π[i, j, X] = 0。

3. 最终结果： 句子 s 的最可能解析树的概率是 π[1, n, S]。 通过从 bp[1, n, S] 开始递归回溯，可以重建整棵最可能解析树。

算法演示（概念性伪代码）

为了清晰展示 CKY 算法的流程，我们使用一个极简的语法和句子进行概念演示。请注意，以下代码块是伪代码，用于说明算法逻辑，并非完整可执行的 PCFG 解析器。

# 伪代码：CKY算法核心逻辑
输入：句子 words = [w1, w2, ..., wn]，符合CNF的PCFG规则集R及其概率q
输出：最大概率值 max_prob，回溯指针表 bp

# 初始化三维表格 π 和 bp
n = len(words)
初始化 π[1..n][1..n][所有非终结符] = 0
初始化 bp[1..n][1..n][所有非终结符] = None

# 步骤1：初始化（处理单个词）
for i in range(1, n+1):
    for 每个非终结符 X:
        if 存在规则 (X -> words[i-1]) in R:
            π[i][i][X] = q(X -> words[i-1])

# 步骤2：动态规划（处理更长的子串）
for length in range(2, n+1):          # 子串长度
    for i in range(1, n - length + 2): # 起始位置
        j = i + length - 1            # 结束位置
        for 每个非终结符 X:
            max_prob = 0
            best_split = None
            best_Y = None
            best_Z = None
            # 遍历所有可能将[i,j]分为[i,s]和[s+1,j]的方式
            for s in range(i, j):
                # 遍历所有能生成Y和Z的规则 X -> Y Z
                for 规则 (X -> Y Z) in R:
                    prob = q(X -> Y Z) * π[i][s][Y] * π[s+1][j][Z]
                    if prob > max_prob:
                        max_prob = prob
                        best_split = s
                        best_Y = Y
                        best_Z = Z
            if max_prob > 0:
                π[i][j][X] = max_prob
                bp[i][j][X] = (best_split, best_Y, best_Z)

# 步骤3：读取结果
max_prob = π[1][n][S]
# 通过 bp[1][n][S] 递归回溯即可构建完整的解析树

计算示例片段

让我们手动模拟一个极小片段的计算，以理解 π 和 bp 的填充过程。考虑句子片段 “saw the dog” (w3, w4, w5)，我们关注计算 π[3, 5, VP]（即“saw the dog”作为一个 VP 的最大概率）。

假设相关规则和概率如下（简化版）：

• VP → Vt NP (q=0.5)
• Vt → saw (q=1.0)
• NP → DT NN (q=0.8)
• DT → the (q=1.0)
• NN → dog (q=0.3)

并且我们已经计算出：

• π[3, 3, Vt] = q(Vt → saw) = 1.0
• π[4, 4, DT] = q(DT → the) = 1.0
• π[5, 5, NN] = q(NN → dog) = 0.3
• π[4, 5, NP] = q(NP → DT NN) * π[4,4,DT] * π[5,5,NN] = 0.8 * 1.0 * 0.3 = 0.24

现在计算 π[3, 5, VP]：

• 只有一种规则分解：VP → Vt NP
• 分割点 s 只能是 3（因为 Vt 只覆盖一个词）。
• prob = q(VP → Vt NP) * π[3,3,Vt] * π[4,5,NP] = 0.5 * 1.0 * 0.24 = 0.12
• 因此，π[3, 5, VP] = 0.12，bp[3,5,VP] = (3, Vt, NP)。

这个简单的片段展示了 CKY 如何通过组合更小子串的最优解，来构建更大子串的最优解。

PCFG 的局限性与今天的方法

PCFG 是统计句法分析的重要基石，但它有明显的局限性：

1. 独立性假设过强：PCFG 假设每条规则的应用是独立的，不考虑词汇信息（Lexicalization）和更远的上下文。例如，动词 “saw” 后接哪种 NP 结构，可能与 “saw” 本身有关，但基础 PCFG 无法建模。
2. 缺乏词汇化：规则 NP → DT NN 的概率是全局的，不会因为中心词 NN 是 “dog” 还是 “telescope” 而改变。

现代方法的发展：

• 词汇化 PCFG (Lexicalized PCFG)：在规则中引入词汇信息（如中心词），显著提升了精度，但增加了模型复杂度。
• 基于判别式的句法分析器：使用机器学习模型（如感知机、条件随机场）直接学习从句子到句法树的映射，而非生成式模型。
• 神经句法分析：利用循环神经网络（RNN）、图神经网络（GNN）或 Transformer 来编码句子，并直接预测句法树结构，在许多基准测试上达到了 state-of-the-art 的性能。

尽管基础 PCFG 已不是工业界主流，但其核心思想——为结构化预测问题定义概率模型，并用动态规划进行高效解码——深刻影响了后续的序列标注、机器翻译等众多 NLP 任务。

📝 动手练一练

1. 概念辨析：在 PCFG 中，为什么对于每个非终结符 α，其所有规则 α → β 的概率之和必须为 1？如果和不等于 1，在计算整棵解析树概率时会有什么问题？

2. 手算练习：假设有一个极简的 PCFG，规则和概率如下：

   • S → NP VP (1.0)
   • NP → N (0.7) | NP → DT N (0.3)
   • VP → V (0.4) | VP → V NP (0.6)
   • N → dog (0.8) | N → cat (0.2)
   • V → chases (1.0)
   • DT → the (1.0)

   对于句子 “the dog chases”，请列出所有可能的解析树，并计算每棵树的概率。哪一棵是最可能解析？

本章小结

本节我们系统学习了概率上下文无关文法（PCFG），它是将概率思想融入句法分析的关键桥梁。

• PCFG 扩展了 CFG，为每条语法规则赋予概率，使得我们可以计算和比较不同句法解析树的似然度。
• 规则概率通过最大似然估计从树库中获得，体现了数据驱动的思想。
• 解析树的概率是其所有节点规则概率的乘积。
• CKY 算法 是一种基于动态规划的高效算法，在已转换为 CNF 形式的 PCFG 下为句子找到概率最大的解析树，其核心是自底向上填充概率表 π 和回溯表 bp。
• 尽管基础 PCFG 有独立性假设过强等局限，但其模型框架和解码算法为后续更复杂的句法分析模型奠定了基础。

📋 行动清单

• 理解 PCFG 中规则概率必须满足和为1的约束，并明白其必要性。
• 掌握从树库中用最大似然估计计算规则概率的方法。
• 能够手动计算给定 PCFG 和简单句子的解析树概率。
• 理解 CKY 算法的动态规划思想，特别是 π[i,j,X] 和 bp[i,j,X] 的定义与递推公式。

—— 小象教研组