自定义语法与CFG
什么是语法解析?
在自然语言学习过程中,每个人一定都学过语法,例如句子可以用主语,谓语,宾语来表示。
在自然语言的处理过程中,由许多应用场景都需要考虑句子的语法,因此研究语法解析变得非常重要。
语法解析有两个主要的问题,其一是句子语法在计算机中的表达与存储方法,以及语料数据集,其二是语法解析的算法
对于第一个问题,我们可以用树状结构图来表示,如下图所示,S表示句子:NP,VP,PP是名词,动词,介词短语;
N,V,P分别是名词,动词,介词
上下文无关语法
为了生成句子的语法树,我们可以定义如下的一套上下文无关的语法
1.N表示一组非叶子节点的标注,例如{是,NP,VP,N,...}
2.E表示一组叶子节点的标注,例如{boeing,is}
3.R表示一组规则,每条规则可以表示为
4.S表示语法树开始的标注
举例来说,语法的一个语法子集可以表示为下图所示,当给定一个句子时,我们便可以按照从左到右的顺序来解析
语法,例如the man sleeps就可以表示为(S(NP (DT the)(NN man)) (VP sleeps)).
概率分布的上下文无关语法
上下文无关的语法可以很容易的推到出一个句子的语法结构,但是缺点是推导出的结构可能存在二义性
由于语法的解析存在二义性,我们就需要找到一种方法从多种可能的语法树找出最可能的一颗树,一种常见
的方法既是PCFG。如下图所示,除了常规的语法规则以外,我们还对每一条规则赋予了一个概率,对于每一
课生成的语法树,我们将其所以规则的概率的乘积作为语法树的出现概率。
训练算法
我们定义了语法解析的算法,而这个算法依赖于CFG中对于N,E,R,S的定义以及PCFG中的P(x),上文中我们提到了Penn
Treebank通过手工的方法已经提供了一个非常大的语料数据集,我们的任务就是从语料库中训练PCFG所需要的参数
1.统计出语料库中所有的N与E
2.利用语料库中的所有规则作为R
3.针对每个规则A->B,从语料库中估算p(x)=p(A->B)/p(A);
在CFG的定义的基础上,我们重新定义一种叫chomsky的语法格式。这种格式要求每条规则只能是X->Y1 Y2或者
X->Y的格式,实际上chomsky语法格式保证生产的语法树总是二叉树的格式,同时任意一颗语法树总是能够转换成
chomsky语法格式。
语法树预测算法
假设我们已经有一个PCFG的模型,包括N,E,R,S,p(x)等参数,并且语法树总数chomsky语法格式,当输入一个句子x1
x2,....,xn时,我们要如何计算句子对应的语法树尼?
第一种方式是暴力遍历的方法,每个单词X可能有m=len(N)种取值,句子长度是n,每种情况至少存在n个规则,所以在时间
复杂度O(m/n)的情况下,我们可以判断出所有可能的语法树,并计算出最佳的那个
第二种方法当然是动态规划,我们定义w[i,j,x]是第i个单词至第j个单词由标注X来表示的最大概率,直观来讲,例如
xi,xi+1,...,xj,当X=PP时,子树可能是多种解释方法,如(P,NP)或者(PP PP),但是w[i,j,PP]代表的是继续
往上一层递归时,我们只选择当前概率最大的组合方式。特殊情况下,因此,动态规划的方程可以表示为
关于动态规划方法,leetcode里由不少案例可以说明
语法解析按照上述的算法过程便完成了,虽说PCFG也有一些缺点,例如:1)缺乏词法信息,2)连续短语的处理等,但总体来讲
它给语法解析提供了一种非常有效的实现方法。