基础

上下文无关文法(CFG)是一些固定的语法知识，例如

S ->NP, VP 句子可以由动词词组和名词词组构成
NP->Det, Noun Det和Noun可以构成一个名词词组
VP->Verb, NP 动词词组可以由动词+名词词组构成
NP->eyes eyes是名词词组

通过这些规则我们可以找到一个句子的句法分析树。但是我们可能会找到非常多的句法分析树，并且没有办法判断到底使用哪一种。因此想到给每一个语法分配一个概率值。也就是概率上下文无关文法

S->NP VP 1.0
PP->P NP 1.0
VP->V NP 0.7
P->With 1.0
...

一些符号定义

  • G： 语法
  • L： 由语法生成的语言
  • t： 句法分析树
  • {$N^1 … N^n$}: 非终结符号集合，也就是NP，P等参数
  • {$w^1 … w^n$}: 终结符号集合，也就是实实在在的单词
  • $w_1 … w_m$: 句子序列
  • $N^j_{pq}: 覆盖$w_p 到 w_q$的非终结符$N^j$

例如一个句子: astronomers saw stars with eyes,它的句法树可能为

计算句法分析树的概率; $\prod_{i=1..k}P(r(i))$。其中r(i)是CFG规则

计算句子概率

给定一种语法，如何计算这个句子出现的概率？

内部概率: $\betaj (p, q) = P(w{pq} | N_{pq}^j , G)$.这是一种自底向上的方法，首先求单个单词的概率，然后求两个单词结合可能的情况。

也就是说可以将这个文法分成两个小部分，然后计算两个小部分的概率及整合成整体的概率。

外部概率 $\alphaj (p, q) = P(w{1(p-1)}, N{pq}^j , w{(q+1)m} | G)$

确定句子最佳分析树

基本做法和内部概率相似，但是这里我们不需要遍历，只需要找出所有可能中最大的。即