NLP-统计句法分析与CYK算法

Posted on 2021-06-13 Edited on 2021-06-14

基于PCFG的句法分析(统计句法分析)

一. 基于PCFG的句法分析

1.基于CFG的句法分析缺陷：

即使对于一个中等长度的句子，要分析出所有可能的句子结构的复杂度往往使程序无法实现。
即使能分析出句子所有可能的结构，也难以实现有效的消歧，并选择出最有可能的分析结果
手工编写的规则一般带有一定的主观性，不具备普遍性
写规则本身是一件困难工作，而且规则和领域密切相关，不利于句法分析系统向其他领域移植

2.概率上下文无关文法(PCFG):

基于概率上下文无关文法的句法分析既有规则方法的特点，又运用了概率信息，因此可以认为是规则方法和统计方法的结合。该方法是为规则增添了概率的简单CFG，指明了不同重写规则的可能性大小，其一般形式为：

$A \rightarrow \alpha \quad p$，其中p = P( $A \rightarrow \alpha$)，且满足：$\sum_{\alpha}P(A \rightarrow \alpha) = 1$。

3.前提假设：

位置不变性(place invariance)：子树的概率不依赖于该子树所管辖的单词在句子中的位置
上下文无关性(context-free)：子树的概率不依赖于子树控制范围以外的单词
祖先无关性(ancestor-free)：子树的概率不依赖于推导出子树的祖先节点

4.评测指标：

精度(Precision):

$P = \frac{分析得到的正确短语数}{分析得到的所有的短语数} \times 100%$

召回率(Recall):

$P = \frac{分析得到的正确短语数}{标准树库中的短语个数} \times 100%$

F值(F-measure):

$F = \frac{(\beta^2+1)\times P \times R}{\beta^2 \times P + R} \times 100%$，当$\beta = 1$时，称作F1测度

5.PCFG优点：

(1). 可利用概率减少分析过程的搜索空间

(2). 可以利用概率对概率较小的子树剪枝，加快分析效率

(3). 可以定量地比较两个语法的性能

6.PCFG缺点：

(1). 无法解释终结符不同位置概率不同

(2). 无法解释不同产生式的推导非独立

(3). 无法解释固定搭配等的一系列依赖于特定单词的推导

二. CYK 算法：

1.CYK算法是基于动态规划思想设计的一种自底向上语法分析算法，他要求CFG的文法是满足乔姆斯基范式(CFG)的。

2.CNF范式：这是用于约束文法形式的，他要求，对于一个$\epsilon - free$的文法(不含生成空串的规则的文法)，他的每一个规则，要么是$A \rightarrow B C$要么是$A \rightarrow a$的。

对于$A \rightarrow BCD$这类右部含多个非终结符的，我们可以将它们拆成$A \rightarrow BD_1$和$D_1 \rightarrow CD$这样(右部更多的话就接着拆)，而对于$A \rightarrow Bc$这样既含非终结符有含终结符，现将非终结符用一个规则表示$C \rightarrow c$，然后原文法规则就可以表示成$A \rightarrow BC$，如果含多个终结符，也是这样，将终结符用一个文法表示，然后原文法的终结符用对应的非终结符替换，在拆成右部为两个非终结符的表示形式。

3.算法示例：

词串W，长度n，则需要构造一个形如下的(n+1)X(n+1)的三角阵：

注：解释(n+1)X(n+1)，这里算法采用节点之间的边来表示一个词，也就是边<0,1>表示词the，所以节点是n+1，对应构造的三角阵也就是行列为n+1。

注：这只是一个很简单的例子，给出了算法的处理步骤，每一步处理的顺序和table表的构建过程。红色问号表示在词串序列<i,j>无法构造出一颗完整的子树。

通过例子我们发现，仅仅是根据这个三角阵(table)我们还无法得出一棵树，因为我们没有记录路径，这是我们用过backTrace来完成这一部分。

4.算法伪代码：

定义：函数len(W)用于计算词序列W的长度，table[i,j,X]用于存放三角阵中以X为根节点，词串从i到j的概率；backTrace[i,j,A] = {k,B,C}用于存放以A为根节点，词串从i到j的子树结构：左半部分i$$k背柜月为B，右半部分k$$j被规约成C；函数BuidTree用于构造整个分析序列的句法结构树，根节点为S。

input：待分析的次序列W和PCFG规则集R

output：最有可能的句法结构及其概率大小

伪代码：

// 伪代码
def CYK(W,R)：
	for j from 1 to len(W):
        // 更新当前词能规约出的非终结符及其概率，为后续做准备
        for all {A | (A -> W[j]) in R}
        	table[j-1,j,A]=P(A -> W[j])
        // 根据当前词更新结果，由底向上构造子树，并将最优(概率最大)的结果保存
        for i from j-2 to 0: // 子树i~j
            for k from i+1 to j-1: // 计算子树i~j的最优分叉方法：遍历每一种分叉方法，找出概率最大的。而对于某一特定分叉，当且仅当每一分支的子树的概率最大，当前分法的概率最大，可用动态规划方法。
                for all {A | (A->BC) in R, and table[i,k,B]>0 and table[k,j,C]>0}:
                    if(table[i,j,A] < P(A->BC)*table[i,k,B]*table[k,j,C]):
                        table[i,j,A] = P(A -> BC)*table[i,k,B]*table[k,j,C]
                        backTrace[i,j,A]={k,B,C}
	return BuildTree(backTrace[1,len(W),S]),table[1,len(W),S]