13.依存句法与语义依存分析

自定义语法与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）连续短语的处理等，但总体来讲

        它给语法解析提供了一种非常有效的实现方法。