一、概率上下文无关文法（(Probabilistic) Context-Free Grammars）

1、上下文无关文法（Context-Free Grammars）

• 我们也可以称之为词组结构语法(Phrase structure grammars)
• 由四个成分构成G=（T，N，S，R）
  • T表示最终端（terminal），如下图粉色部分的子节点
  • N表示非最终端（nonpreterminal），如下图粉色部分的中间节点
  • S表示开始（S∈N），如下图粉色部分的根节点
  • R表示一系列的规则，格式为X→γ，其中X∈N，γ∈（N∪T），例子如下图左边的规则
    

2、NLP的上下文无关文法（Context-Free Grammars）

• 在NLP的背景下，我们对上下文无关文法的定义进行了一定的修改
• 由六个成分组成G=（T，C，N，S，L，R）
  • T表示最终端（terminal），如上图粉色部分的子节点，和上面定义一致
  • C表示次终端（preterminal），如上图粉色部分的子节点的父节点
  • N表示非最终端（nonpreterminal），如上图粉色部分的中间节点，和上面定义一致
  • S表示开始（S∈N），如上图粉色部分的根节点，和上面定义一致
  • L表示字典（lexicon），格式为X→x，其中X∈C并且x∈T，如上图中间的规则
  • R表示一系列的语法规则，格式为X→γ，其中X∈N，γ∈（N∪C），如上图左边的规则
• 按照惯例，S表示开始。但是，在统计自然语言中，我们在最开始还会使用另外一个节点（ROOT，TOP）
• 对空序列，我们会用e来表示

3、概率上下文无关文法（Probabilistic/stochastic Context-Free Grammars

• 概率上下文无关文法是上下文无关文法的拓展，在原来的四个元素上增加了一个元素P
• 由五个成分构成G=（T，N，S，R，P）
  • T表示最终端（terminal），如下图粉色部分的子节点
  • N表示非最终端（nonpreterminal），如下图粉色部分的中间节点
  • S表示开始（S∈N），如下图粉色部分的根节点
  • R表示一系列的规则，格式为X→γ，其中X∈N，γ∈（N∪T），例子如下图左边的规则
  • P表示概率函数，P的范围是[0,1]，并且和为1，公式如下：
    
• 文法规则表示如下（增加了概率）：
  
• 概率计算
  • 句法结构树的概率P(t)计算：生成它的规则的概率的乘积
  • 字符串的概率P(s)计算: 有这个字符串的句法结构树的和
    
  • 例子：同一个句子的两个不同的句法结构树
    
    第一颗树是动词附属（verb attach），概率计算是0.0008232，第二颗树是名词附属(noun attach)，概率计算是0.00024696。字符串的概率是两者之和0.00107016
    

二、语法转化

1、Chomsky Normal Form

• 我们可以把上下文无关文法（Context-Free Grammars）转化为Chomsky Normal Form的形式。这种形式不会改变语言本身，但是呈现出的句法结构树可能会有所不同。可以使得句法分析更加高效。
• 在这种形式中，所有的规则可以转化为两种形式：X→Y Z或者是X→w，其中X，Y，Z∈N，w∈T
• 为了实现这种形式，空和一对一的规则（X→Y）会被递归地消除
• 一对N的规则（N>2）则会被拆解成新的非终端项（nonterminals）

2、一个转化的例子

• 初始的上下文无关文法（Context-Free Grammars）
  
• 第一步：消除空（e），由于NP→e，要把这一条删除同时保留下这一条的信息，我们可以把左边规则中箭头右侧出现NP的规则做两种假设，比如S→NP VP可以改进为两条规则：S→NP VP和S→VP
  
• 第二步：消除一对一的规则（X→Y）。把一对一的规则转化为字典形式放在字典（lexicon）中。具体如VP→V，则和字典（lexicon）中V在左侧的规则一起生成新规则，如VP→people。并进行迭代消除。
  
  
• 第三步：一对N的规则拆成一对二的规则，比如VP→V NP PP拆成两个规则VP → V @VP_V，@VP_V →NP PP
  
• 在实践中，完整的Chomsky Normal Form转换是很痛苦的，一对N的规则拆分是很容易的，但是空（e）和一对一规则的消除非常麻烦。对于上下文无关文法（CFG）句法分析而言，一对N的规则拆分可以帮助建立二叉树，可以有效降低复杂度。而其他操作不是必要的，充其量就是会使得算法更干净更快而已。下图右边就是一对N的规则拆分的句法分析树。
  
  下图有颜色的部分表示了同一个短语的不同的四个句法结构树，第一个是初始，第二个是去掉了空，第三个是去掉了一对一保留了最高的父节点，第四个是去掉了一对一保留了最低的父节点（三四比起来我们更倾向于四，因为可以保留完整的字典）
  

三、CKY算法

1、算法介绍

• 我们采用CKY算法来进行句法分析的时间复杂度是在O（N³）
• 大致来说，计算方法是一个动态规划的方法。如下图，从最底层开始，最底层的每一格代表对应的一个单词，其中包含若干种可能以及对应的概率。次底层的每一格代表的是次终端（preterminal），包含左下角和右下角两个底层的格子对应的单词构成的成分（constituency）。
  
• 举例而言：下面的例子中有两个词people fish，根据字典（lexicon），people对应三种成分（NP，V，N），fish对应四种成分（VP，NP，V，N）。接下来，计算的是两个单词组合的成分。根据规则NP→ NP NP，people fish的成分是NP的时候概率是=P(NP→people)*P(NP→fish)*P(NP→ NP NP)=0.350.140.1=0.0049。当有两种组合的结果成分是相同的时候，我们选取最大的概率放入对应的格子中。
  

2、算法拓展

• 一对一规则：可以整合进算法。虽然可能会使得算法比较混乱，但是不会影响到算法的复杂度
• 空：可以使用fencepost整合进算法，并且不会影响算法的复杂度。例子如下，假设有n个单词，底层构建的时候选用0-n位置，在每个整数位都可以插入空，在整数之间的位置则是单词。
  
• 二分化，即去掉一对N规则是很有必要的。这是使得算法复杂度降低从指数级到O（N³）的关键，所以在进行CKY算法之前，一定要进行二分化。

3、代码

function CKY(words, grammar) returns [most_probable_parse,prob]
  score = new double[#(words)+1][#(words)+1][#(nonterms)]  //存储格子中所有可能成分和对应的概率
  back = new Pair[#(words)+1][#(words)+1][#nonterms]] //指针，指出最佳的成分
  
  ****接下来主要处理字典lexicon*****
  for i=0; i<#(words); i++ 对每个单词
    for A in nonterms 对每个非终端
      if A -> words[i] in grammar 如果A指向对应的单词的话，就在score中存储
        score[i][i+1][A] = P(A -> words[i])
    //handle unaries 下面部分处理一对一规则
    boolean added = true
    while added 
      added = false
      for A, B in nonterms
        if score[i][i+1][B] > 0 && A->B in grammar 一对一规则搜寻
          prob = P(A->B)*score[i][i+1][B]
          if prob > score[i][i+1][A] 判断一对一的概率是否会比原来的大，如果是的话就覆盖原来的概率
            score[i][i+1][A] = prob
            back[i][i+1][A] = B
            added = true
            
   ****接下来主要处理语法规则*****
	for span = 2 to #(words)
	  for begin = 0 to #(words)- span
	    end = begin + span
	    for split = begin+1 to end-1 对一串语句而言，选择二分的节点
	      for A,B,C in nonterms
	            prob=score[begin][split][B]*score[split][end][C]*P(A->BC) 计算对应的概率
	        if prob > score[begin][end][A] 如果概率大于原来的概率就覆盖，修改back指针
	          score[begin]end][A] = prob
	          back[begin][end][A] = new Triple(split,B,C)
	    //handle unaries  下面部分处理一对一规则
	    boolean added = true
	    while added
	      added = false
	      for A, B in nonterms
	        prob = P(A->B)*score[begin][end][B];
	        if prob > score[begin][end][A]  判断一对一的概率是否会比原来的大，如果是的话就覆盖原来的概率
	          score[begin][end][A] = prob
	          back[begin][end][A] = B
	          added = true
return buildTree(score, back)

四、例子

• 没有空（e）的规则
  
• socre数组，行数和列数都是单词数
  
• 第一步：利用lexicon在score中写入规则：以0-1的fish为例，对应的lexicon是N→fish 0.2和V→fish 0.6（下面每一步的结果都在下一步的图中给出）
  
• 第二步：处理字典部分的一对一规则。以0-1的fish为例，已有的lexicon是N→fish 0.2和V→fish 0.6。可以找到一对一语法规则VP→V（概率是0.60.1），NP→N（概率是0.70.2），因为原来的概率是0，所以对其直接进行覆盖。对一共四个的语法规则再迭代，可以找到一对一的语法规则S→VP（概率为0.60.10.1）
  
• 第三步：处理语法规则。计算次底层的概率，以fish和people为例
  • NP -> NP NP : P(NP->N)*P(NP->N)*P(NP -> NP NP)=0.14*0.35*0.1
  • VP ->V NP: P(V->fish)*P(NP->N)*P(VP ->V NP)=0.6*0.35*0.5
  • S->NP VP: P(NP->N)*P(VP->V)*P(S->NP VP)=0.14*0.01*0.9=0.00126
    
• 第四步：处理一对一语法规则。以fish和people为例，S->VP:P(VP ->V NP)*P(S->VP)=0.6*0.35*0.5*0.1=0.0105，比之前算出的概率大，覆盖S的概率
  
• 第五步，计算第三层的语法规则。以fish people fish为例，可能存在两种可能：二元分割点在1，二元分割点在2。分别计算可能的概率，并进行一对一规则的处理。
  
• 第六步：计算最后一层。
  
• 结果
  

五、成分句法分析评估方法

• 计算方法：对每一格单词间隔进行索引，将每个嵌套的成分，从上到小从左到右用索引表示出来。比如下面的句法分析，第一层的S是0-11，接下来NP是0-2，VP是2-9。
  
  基于上面的成分索引，计算对应的precision和recall。标注评价是另外给出的一个正确率。
  
• PCFGs模型的优点