第十一章：概率语法

基于规则的句法剖析主要使用 Chomsky 的上下文无关语法。之前的自顶向下、自底向上、左角、CYK、Earley、线图分析法等都对歧义无能为力，于是有了新的改进：一方面是给上下文无关语法的规则加上概率，另一方面是除了加上概率外，还考虑规则的中心词对于规则概率的影响。这些称为 “概率语法”。

概率上下文无关语法与句子的歧义

上下文无关语法（CFG）定义为四元组：G={N, Σ, P, S}，N 是非终极符号集合，Σ 是终极符号集合，S 是初始符号，P 是重写规则。规则形式为 A→β，A 是单独的非终极符号，β 可以由终极符号组成，也可以由非终极符号组成。

在句法分析时，由于词的词性和词义的多样性会导致歧义，于是学者们试图通过基于统计的方法，计算上下文无关语法重写规则的使用概率。

概率上下文无关语法的基本原理

概率上下文无关语法（Probabilistic Context-Free Grammar，PGFG）由 Booth 1967 年最早提出。在每一个重写规则 A→β 上增加一个条件概率 p：A→β[p]，于是上下文无关语法可定义为五元组：G={N, Σ, P, S, D}，D 是给每一个规则指派概率 p 的函数。这个函数表示某个非终极符号 A 重写为符号 β 时的概率 p。规则可写为：p(A→β) 或 p(A→β|A)，从 A 写为 β 时应考虑所有情况且其概率和为 1。

如果句子有歧义，每一个树形图都会有一个概率，一个树形图 T 的概率等于从每一个非终极符号的结点 n 扩充的规则 r 的概率的乘积：

$P(T) = \prod_{n \in T} p(r(n))$

其中，n 表示非终极符号的结点，r 表示由该非终极符号扩充的规则，小写字母 p 表示规则 r 的概率，P 表示整个树形图 T 的概率。从句子 S 的若干个树形图中选出最好的 T(S) = arg max P(T)。

用于 CYK 算法叫作 “概率 CYK 算法”，同样也有 Earley 算法、概率线图分析法等。

如何获取概率？

• 使用句子已经的到剖析的语料库：树库，对其中的树形图进行统计
• 通过未加工的语料库自动学习语法规则，采用 “向内向外算法”（Baker 1979 年提出）

概率上下文无关语法的三个假设

• 假设一：位置无关性假设：子结点的概率与该子结点所直接管辖的字符串在句子中的位置无关
• 假设二：上下文无关性假设：子结点的概率与不受该子结点直接管辖的其他符号串无关
• 假设三：祖先结点无关性假设：子结点的概率与支配该结点的所有祖先结点的概率无关

概率上下文无关语法存在结构依存和词汇依存的问题。

• 结点上规则的转写与节点在树形图中的位置是有关的（如代词）
• PP 附着（PP 可以做 VP 的状语，或它前面 NP 的修饰语）问题
• 并列结构的歧义

概率词汇化上下文无关语法

Charniak 1997 年提出，剖析树的每一个结点要标上该结点的中心词，因此规则数目比概率上下文无关语法多很多，因为结点上除了语法标记还有词汇，也就是说统计的时候不是统计树库某一类标记的概率，而是某个具体的词的概率。

除此之外，还有一些附加条件，以及各种回退和平滑算法。还有一些剖析器包括更多的因素，比如，区分论元成分与附属成分，对于树形图中那些比较接近的词汇依存关系比那些比较疏远的词汇依存关系给以更大的权重，考虑在给定成分中的三个最左的词类，考虑一般的结构依存关系等等。

小结

• 概率上下文无关语法与句子的歧义
  • 基于统计的方法，计算上下文无关语法重写规则的使用概率。
• 概率上下文无关语法的基本原理
  • 概率上下文无关语法（Probabilistic Context-Free Grammar，PGFG）由 Booth 1967 年最早提出。在每一个重写规则 A→β 上增加一个条件概率 p：A→β[p]，于是上下文无关语法可定义为五元组：G={N, Σ, P, S, D}，D 是给每一个规则指派概率 p 的函数。
  • 如果句子有歧义，每一个树形图都会有一个概率，一个树形图 T 的概率等于从每一个非终极符号的结点 n 扩充的规则 r 的概率的乘积。
• 概率上下文无关语法的三个假设
  • 三个假设：
    • 位置无关
    • 上下文无关
    • 祖先结点无关
  • 问题：
    • 结点上规则的转写与节点在树形图中的位置是有关的（如代词）
    • PP 附着（PP 可以做 VP 的状语，或它前面 NP 的修饰语）问题
    • 并列结构的歧义
• 概率词汇化上下文无关语法
  • Charniak 1997 年提出，剖析树的每一个结点要标上该结点的中心词，因此规则数目比概率上下文无关语法多很多，因为结点上除了语法标记还有词汇，也就是说统计的时候不是统计树库某一类标记的概率，而是某个具体的词的概率。

这章内容非常简单，其思想与隐马尔科夫有些类似，不过后面的改进都没有提到基于贝叶斯的推理。可能是个不错的改进方向。