Theme
下面继续 Lecture 7。这一讲的核心是：把 CFG 从“能不能 parse”升级为“哪个 parse 更可能”，也就是 Probabilistic Context-Free Grammar, PCFG。它和前面 HMM 的关系非常强：HMM 是 chain 上的概率 DP，PCFG 是 tree 上的概率 DP。
Lecture 7：Probabilistic CFG 与概率句法分析
1. 本讲核心目标
前面如果已经学过 CFG 和 CYK，你可以把它们理解为：
但问题是：一个句子可能有多个合法 parse tree。
例如课件中的 “book the dinner flight” 可以有不同结构：
text
VP → Verb NP NP
book | the dinner | flight也可以是：
text
VP → Verb NP
book | the dinner flightCYK 只能告诉你这些 parse tree 都合法，但不能告诉你：
所以 PCFG 要解决的问题是：
这对应三个任务：
| 任务 | 问题 | 类比 HMM |
|---|---|---|
| Sentence probability | 句子概率是多少？ | Forward |
| Inside / Outside | 子树内部与外部概率 | Forward / Backward |
| Optimal parse tree | 最可能的 parse tree 是哪棵？ | Viterbi decoding |
2. 从 CFG 到 PCFG：方法论演进
2.1 CFG 的局限
普通 CFG 有 production rules，例如：
它只能表达：
这个结构是否合法。
但它无法表达：
比
更常见还是更罕见。
因此普通 CFG 无法排序 parse trees。
2.2 PCFG 的改进
PCFG 给每条 production rule 加概率：
其中：
| 符号 | 含义 |
|---|---|
| non-terminal 左侧符号 | |
| rule 右侧，可以是 terminals 或 non-terminals | |
| 从 展开成 的概率 |
同一个 left-hand side 的所有规则概率必须和为 1：
例如课件中：
表示当我们要展开 时，有 0.7 概率选择 ，有 0.3 概率选择 。
3. Parse Tree 的概率
一棵 parse tree 的概率等于树中所有 production rules 概率的乘积：
其中：
| 符号 | 含义 |
|---|---|
| 一棵 parse tree | |
| PCFG grammar | |
| 树 中使用的一条 production rule | |
| 该 production rule 的概率 |
直觉上，每生成一个节点，就乘上这次展开的概率。整棵树的概率就是整个 derivation path 的概率。
4. Sentence Probability：为什么需要 marginalization？
一个句子 的概率不是某一棵树的概率，而是所有能生成它的 parse trees 的概率总和：
其中：
| 符号 | 含义 |
|---|---|
| 输入句子 | |
| 所有能生成该句子的 parse trees | |
| 某棵 parse tree 的概率 |
这一步和 HMM 完全类似：
HMM 中：
PCFG 中：
区别只是 hidden structure 从 sequence 变成了 tree 。
5. 为什么不能暴力枚举所有树？
因为 parse trees 的数量可能指数级大。
对一个长句子，合法二叉树结构数量本身就增长很快，再乘上不同 non-terminal 标号，枚举所有树不可行。
所以我们需要 DP。
这就是 Inside Algorithm 和 Outside Algorithm 的来源。
6. PCFG 的三个独立性假设
为了让概率计算可 tractable，PCFG 做了三个关键假设。课件第 5 页把它们可视化成三棵树：同一个子树的概率不依赖位置、外部上下文、祖先路径。
6.1 Place Invariance
同一个 non-terminal 生成同一类子树的概率，不依赖它出现在句子的什么位置。
形式上：
对于不同 是一样的。
意思是：
一个 在句首还是句尾，展开规则概率相同。
6.2 Context-Free
某个子树如何展开，不依赖它外面的词。
意思是：
如果当前子树覆盖 span ，那么 span 外部的上下文不影响它的内部展开。
6.3 Ancestor-Free
某个节点如何展开，不依赖它的祖先节点。
意思是：
当前 是从 下来的，还是从 下来的，规则概率一样。
这是很强的简化假设，也是 PCFG 的局限之一。
7. 为什么这些假设重要？
因为它们让 tree probability 可以分解为局部 rule probability 的乘积。
例如课件第 6 页展示：
可以化简为：
关键原因是：
子树之间不需要考虑复杂依赖。
这正是 PCFG 可计算的基础。
8. Inside Probability
Inside probability 是本讲最重要概念之一。
8.1 定义
课件定义：
表示：
non-terminal 生成 span 内部词串的概率。
换句话说：
是“这棵子树内部生成这段 words 的概率”。
8.2 类比 HMM Forward
HMM forward：
是从左到右累计历史。
PCFG inside：
是从叶子往上累计子树概率。
所以：
| HMM | PCFG |
|---|---|
| chain prefix | tree span |
| forward probability | inside probability |
| time step | span |
| hidden state | non-terminal |
9. Inside Algorithm：Base Case
如果 span 长度为 1：
即只覆盖一个词 。
那么：
如果 grammar 中有规则：
则：
否则为 0。
这是叶子节点情况。
10. Inside Algorithm：递推公式
假设 grammar 已转成 CNF，即每条非终结符规则形如：
对于 span ，枚举切分点：
左子树覆盖：
右子树覆盖：
则：
这是本讲最核心公式。
11. Inside 公式为什么是 sum？
因为 sentence probability 要考虑所有可能 parse trees。
对于同一个 span ，root 是 ，可能有很多构造方式：
- 不同左 child
- 不同右 child
- 不同切分点
每一种都是一种可能 derivation。
所以要把它们全部加起来。
这和 HMM Forward 的求和完全一样：
Inside 是树结构上的版本：
12. Sentence Probability from Inside
如果起始符号是：
句子长度是 ，那么整句概率是：
也就是：
起始符号 生成整个 span 的 inside probability。
13. Inside Example：课件例子
课件第 10 页计算了几个 span。
例如 span 是：
规则：
概率：
并且：
所以：
再看 span ：
规则：
所以：
再看 span ：
可以有两种 derivation：
第一种：
概率贡献：
第二种：
概率贡献：
Inside 要求和：
这说明：
Inside probability 不是选最优树，而是把所有树加起来。
14. Outside Probability
Inside 只看子树内部。
Outside 看的是：
该子树外部的概率。
14.1 定义
直觉：
“假设 span 已经被 non-terminal 代表，那么外部结构生成剩余词的概率。”
课件把它和 inside 对应画成一个大三角：里面的小三角是 ，外部大区域是 。
15. Outside 和 Inside 的关系
如果某个 non-terminal 覆盖 span ，那么整句概率可以分成：
其中：
- ：内部生成 span
- ：外部生成其他部分，并留下 这个节点
因此：
课件第 14 页给了这个结论。
16. Outside Algorithm 的 Base Case
如果：
覆盖整个句子：
则外面什么都没有。
因此：
其他 non-terminal：
因为整句必须从 start symbol 开始。
17. Outside Algorithm 为什么需要 Inside？
这是 quiz 里重点。
Outside 要计算某个子树外部概率时，需要知道它的 sibling subtree 生成对应 span 的概率。
那个 sibling probability 正是 inside probability。
例如目标节点是左孩子：
父节点可能是：
规则：
右 sibling 是：
那么外部概率需要乘上 sibling 的 inside：
所以 Outside Algorithm 依赖 Inside Algorithm 的结果。
18. Optimal Parse Tree：PCFG 中的 Viterbi
现在进入 decoding。
前面 Inside 是求所有树的总概率：
但最优 parse tree 要求：
所以它是 CYK 的概率版，也是 HMM Viterbi 的树结构版。
18.1 定义 Viterbi Parse Probability
定义：
表示：
non-terminal 生成 span 的最高概率 parse tree。
18.2 Base Case
若 span 长度为 1：
18.3 Recursive Case
这和 Inside 的递推几乎一样，只是：
课件第 15 页明确说：finding optimal tree is decoding, similar to Viterbi algorithm for HMM。
19. Backpointer
为了恢复树结构，需要记录：
其中：
表示：
最优树中：
- 左孩子是
- 右孩子是
- split point 是
然后从：
开始回溯，恢复整棵 parse tree。
20. Optimal Tree Example
课件第 16 页继续用：
对比两个候选：
第一种：
概率：
第二种：
概率：
Viterbi parse 取最大值：
因此最优 backpointer 是：
意思是：
span 的 root 是 ，最优切分在位置 2：
而不是：
21. Inside vs Viterbi-CYK：关键区别
| 算法 | 目标 | 操作符 | 输出 |
|---|---|---|---|
| Inside | 句子总概率 | ||
| Viterbi-CYK | 最优 parse tree | best tree | |
| Outside | 外部上下文概率 | span 外部概率 |
最容易犯的错误是：
把 Inside 的 probability 当成最优树概率。
Inside 是所有树的总和，不是最佳树。
22. 和 HMM 三算法的统一对比
| HMM | PCFG | 含义 |
|---|---|---|
| Forward | Inside | 对所有 hidden structures 求和 |
| Backward | Outside | 计算外部/未来 contribution |
| Viterbi | Viterbi-CYK | 找最优 hidden structure |
| Hidden sequence | Parse tree | latent structure |
| Time step | Span | DP 状态维度 |
这就是本讲最核心的架构理解：
HMM 是线性链上的 latent-variable model。
PCFG 是树结构上的 latent-variable model。
两者都用 dynamic programming 处理指数级 latent structures。
23. 本讲总结
Lecture 7 的核心公式有三个。
第一，parse tree probability：
第二，sentence probability：
第三，Inside recursion：
以及最优树版本：
一句话概括：
PCFG = CFG + rule probabilities；Inside/Outside 用 DP 计算所有 parse trees 的边缘概率；Viterbi-CYK 用 max 替代 sum 来找最可能 parse tree。