语法树的作用

　　一棵语法树不仅包括了词性(part of speech), 还包括了短语(如名词短语, 动词短语)和结构化的信息(如主语, 谓语和宾语). 这些信息是进行机器翻译所必须的, 例如机器翻译中就需要使用到结构化信息, 来根据不同的语言规定调整主谓宾的顺序.

上下文无关语法

　　上下文无关语法(CFG)定义了描述语法树的要素. CFG 是一个四元组, 即(S, sigma, R, N), 其中 S 表示开始符号, sigma 表示词汇表, R 表示语法规则, N 表示非终端词. 

CFG 的问题

　　CFG 的一个明显的问题是不能解决有歧义句子的语法树解析问题. 从统计上看, 一个语法树解析正不正确, 主要是跟出现概率相关的. 一般的, 正确的语法树出现的概率要大点, 而错误的语法树出现的概率相对较少. 由此可知, 要解决 CFG不能解决的歧义问题, 需要引入语法树出现的鲜艳概率, PCFG 就是这样的一个语法树模型. 

基于概率的上下文无关语法

　　PCFG 是一个五元组, 其定义为(S, sigma, R, N, p). 可以看到, 这基本上与 CFG 类似, 只是多出来一个元素 p, 表示在语料中规则出现的概率. 使用p 可以定义一棵语法树出现的概率为树中所有规则出现概率之积. 这样, 当一个句子在可选的范围内有多棵可能的语法树时, 我们选择先验概率大的那棵树, 这样能最大程度避免解析错误. 

PCFG 的训练

　　对于 PCFG 中的 CFG 部分, 一般是由领域相关的专家给出的, 例如英语专家规定英语的 CFG. 而PCFG 中的 p 是从语料中统计而来. 运用最大似然估计, 可以有: 

　　　　　　P(X -> Y) = count(X->Y)/count(X)

注意到, 规则中包括终端词与非终端词两种元素. 在一个适当规模的语料中, 我们可以认为所有的非终端词都会出现, 但是认为所有的终端词都会出现却是不现实的(想一下我们常听到的那个美国农民日常使用的英语单词只有数千个, 而所有的英语单词却有数万个的情况). 当语料中没有出现, 而在我们的测试样本中却出现了少见的单词时, PCFG 会对所有的语法树都给出概率为0的估计, 这对 PCFG 的模型是一个致命的问题.

　　通常的补救措施是, 对语料中所有单词出现次数进行统计, 然后将出现频率少于 t 的所有单词都换成同一个 symbol. 在进行测试时, 先查找测试句子中的所有单词是否在句子中出现, 若没有出现, 则使用 symbol 代替. 通过这种方法, 可以避免 PCFG 模型给出概率为0 的估计, 同时也不会损失太多的信息.

使用 PCFG 进行语法树解析

　　在使用 CFG 产生语法树时, 通常采用左递归的方法, 从 S 开始, 每次使用一条规则的右部替换左部中第一个非终端词, 直到左部中全部为待解析句子的单词序列为止, 即得到该句子的一棵语法树. 使用这种 brute force 的方法, 预测时间按照句子长度的指数增长. 而使用所谓的 CKY 算法, 可以降低为多项式量级.

　　CKY 是一种 DP 算法, 其要求PCFG 中的R 必须符合 Chromsky Normal Form, 即: 

　　　　　　X -> Y1  Y2 , 其中 Y1和 Y2属于 N　　

　　　　　　X -> Y , 其中 Y 属于 sigma

满足了这种形式后, 可以定义CKY的最优子结构为 Pi(i, j, X), 其表示以 X 为根部非终端词, 涵盖句子中第 i 个到第 j 个单词的语法树的概率. 在这样的定义下, 我们的目标就是寻找到一棵语法树 t, 使得 Pi(1, n, S)最大. DP 算法的一个特点是问题的解是贪婪的, 一个较大问题的解必然依赖于一个较小问题的解, DP 算法按照 bottom-up 的方式, 从解决较小规模的问题开始, 逐渐构建对于目标问题的解. CKY 所定义的递归式如下: 

　　　　　　basic case: Pi(i, i, X) = q(X -> wi)

　　　　　　recursive case: Pi(i, j, X) = max (q(X->YZ) * Pi(i, s, Y) * Pi(s+1, j, Z)),

其中括号中的项为在所有的 X 的规则, 以及一切可能的分裂点 s的情况下得到的最大值.