自然语言处理学习笔记十二（依存句法分析）_依存句法分析 聚类

        词法分析之后，语法分析也是理解语言的重要一环。对于简单句子，还可以通过分词进行理解；但对于长句子，还得通过语法来分析才能更好的理解。

       语法分析是自然语言处理中的一个重要的任务，其目标就是分析句子的语法结构并将其表示为容易理解的结构。

一、短语结构树

        由于语言满足复合性原理，通过分解句子为短语、分解短语为单词，下游应用将会得到更多更深层次的结构化信息。

     1.1  上下文无关文法

      语言其实具备自顶而下的层级关系，固定数量的语法结构能够生成无数句子。在整理好完整的语法集合的情况下，大部分句子都可以通过语法来生成，这样的语法被称为上下文无关文法。

    1.2    短语结构树

     上下文无关文法，由终结符、非终结符、推导规则等构件组成。基于上下文无法文法理论，从S出发，逐步推导非终结符，一个非终结符至少产生一个下级符号，层层递推就得到了一棵语法树。

    1.3  宾州树库和中文树库

      语言学家制定短语结构语法规范，将大量句子人工分解为树形结构，形成了一种语料库，称为树库。常见的英文树库有宾州树库，中文有中文树库。

二、依存句法树

      依存句法数关注的是句子中词语之间的语法联系，并且将其约束为树形结构。

     2.1  依存句法理论

      该理论认为词与词之间存在主从关系，是一种二元不等价的关系。在句子中，如果一个词修饰另一个词，则称修饰词为从属词，被修饰的词语称为支配词，两者之间的语法关系称为依存关系。

     2.2  中文依存句法树库

     作为一种语言学资源，由大量人工标注的依存句法树组成的语料库称为依存句法树库。

     2.3  依存句法数的可视化

      CoNLL格式是树库格式，是一种偏向于“机读”的形式。一些常用的依存句法树可视化工具，有南京大学的Dependency Viewer。

三、依存句法分析

      依存句法分析是指分析句子的依存语法的一种中高级NLP任务，其输入通常是词语和词性，输出则是一棵依存句法树。

     3.1  基于图的依存句法分析

       依存句法树其实就是完全图（每对顶点都相连的图）的一个子图。如果为完全图中的每条边是否属于句法树的可能性打分，然后利用Prim之类的算法找出最大生成树作为依存句法树。这样将整棵树的分数分解为每条边上的分数之和，然后再图上搜索最优解的方法统称为基于图的算法。

       在传统的机器学习时代，基于图的依存句法分析器往往运行开销大。这是由于传统机器学习所依赖的特征过于稀疏，训练算法需要在整个图上进行全局的结构化预测等。为此，另一种基于转移的路线在传统机器学习框架下显得更加实用。

     3.2  基于转移的依存句法分析

      我们将一颗依存句法树的构建过程表示为两个动作，如果机器学习模型能够根据句子的某些特征准确地预测这些动作，那么计算机就能够根据这些动作拼装出正确的依存句法树，这种拼装动作称为转移这种算法统称为基于转移的依存句法分析。

四、基于转移的依存句法分析

        虽然基于转移的依存句法分析涉及许多组件，但是其原理依然属于监督学习的范畴。我们先定义一台虚拟机器，这台机器根据自己的状态和输入的单词预测下一步要执行的转移动作。

        4.1  Arc-Eager转移系统

        4.2  特征提取

         一般通过手工制定的特征模板提取特征，可采用单词的组合特征或者单词的聚类信息作为特征。对单词的聚类算法常用的是Brown聚类算法，其原理就是利用相似单词的左右上下文也相似这一语言现象进行层次化聚类。

        4.3  Static  和  Dynamic Oracle

        对于基于转移的依存句法分析器而言，它学习和预测的对象是一系列转移动作。然而依存句法树库是一棵树，并不是现成的转移动作序列。此时就需要一个算法将语料库中的依存句法树转换成正确的转移动作序列，以供机器学习模块学习。这种正确的转移动作序列称为规范，其质量好坏影响机器学习模块的学习效果。

        静态规范：人工直接编写一些规则来为每棵树生成一个规范，该类算法就是静态规范。

        动态规范：由于今天规范并不能保证是最简单最容易学习的一种，存在着很多的局限性，存在一类算法并不显式地输出唯一规范，是让机器学习模型自由试错，一旦无法拼装出正确语法树，则惩罚模型，这类算法称为动态规范。

        动态规范的试验准确率要比静态规范高出几个百分点。

        4.4  Dynamic Oracle 与感知机在线学习

        感知机是传统机器学习时代常用的分类器，作为结构化预测的依存句法分析也不例外。感知机的原理依然适用于依存句法分析。训练句法分析器时，结构化感知机算法迭代式地优化线性模型，使其将最高的分值赋予可抵达正确句法树的转移序列。

       虽然动态规范使得模型能够自由搜索一条可达正确句法树的转移路径，然而每次转移动作都是贪心地选取分数最高的备选动作，而没有考虑全局转移动作构成序列的分数之和；分数越高说明通过执行该动作序列抵达正确句法树的可能性越大。为了进一步提高句法分析器的准确率，有必要使用一些常用的搜索算法。如下面的柱搜索。

        4.5  柱搜索

       从图的视角来看，在基于转移的依存句法分析中，系统的每个状态为图中的节点，模型预测相邻两个节点的转移分数为边上的分数，故句法分析问题转换成了最长路径搜索问题。在理论上可以通过一些动态规划算法实现，但由于路径过长、分支过多，在计算上不可行；一种近似的柱搜索算法可以较好地平衡效果和效率。其原理就是在每个时刻仅仅维护分数最高的前 k 条子路径，这里的k 又称为柱宽，由于柱的大小固定，随着搜索的深入，计算量和存储空间都不会增加。

       4.6 应用

       利用依存句法分析，可以实现一个意见抽取。