NLP第9章-句法分析
句法分析可以分为句法结构分析和依存关系分析。获取整个句子的句法结构的目的称为完全句法分析，获取局部成分的目的称为局部分析，依存分析简称依存分析。
一般来说，句法分析有三个任务:
确定输出字符串是否属于某种语言。
消除输入句子中的词汇和结构歧义。
分析输入句子的内部结构，如构成和上下文。
第二和第三项任务一般是句法分析的主要任务。
一般来说，一个解析器的构建需要考虑两个部分:一个是语法的形式化表达和词条信息的描述，形式化的语法规则构成规则库，词条信息由词典或同义词提供，规则库和词典或同义词构成句法分析的知识库；另一部分是基于知识库的分析算法。
语法形式化属于句法理论的研究领域。目前，自然语言处理中广泛使用的是上下文无关文法(CFG)和基于约束的文法，后者也被称为unity文法。
简单来说，句法结构分析方法可以分为两类:基于规则的分析方法和统计分析方法。
基于规则的句法结构分析方法的基本思想是人工组织语法规则，建立语法知识库，通过条件约束和检查消除句法结构歧义。
根据句法分析树形成方向的不同，人们通常将这些方法分为三种:自顶向下分析法、自底向上分析法以及两者的结合。自顶向下的分析算法实现了规则推导的过程，分析树从根节点开始生长，最终形成分析句的叶节点。自底向上分析算法的实现过程就是这个思路，从句子符号串开始，执行不断规范的过程，最后形成根节点。
基于规则的语法结构分析可以利用手工编写的规则，分析输入句子所有可能的句法结构；对于特定的领域和目的，使用有针对性的规则可以更好地处理句子中的一些歧义和一些语法外现象。
而对于一个中等长度的输入句子，使用覆盖面较大的语法规则来分析所有可能的句子结构是非常困难的，即使分析了，也很难实现有效的消歧，选出最可能的分析结果；手写的规则比较主观，需要泛化，面对复杂的上下文很难保证正确率。手工编写规则是一项复杂的工作，规则的领域联系紧密，不利于句法分析系统向其他领域的移植。
基于规则的解析算法可以成功处理程序语言的编译，但对于自然语言的处理却始终难以摆脱困境，因为程序语言所使用的知识受到上下文无关文法子类的严格限制，而自然语言处理系统所使用的形式化描述方法却远远超过上下文无关文法的表达能力；而且人在使用编程语言的时候，所有的表达式都要服从机器的要求，这是一个人服从机器的过程。这个过程是从语言的无限集合到有限集合的映射过程，而在自然语言处理中，恰恰相反，自然语言处理实现了机器跟踪和服从人的语言，从语言的有限集合推导到无限集合的过程。
完整的语法分析
基于PCFG的基本分析方法
基于概率上下文无关文法的短语结构分析方法可以说是目前最成功的语法驱动的统计句法分析方法，可以看作是规则方法和统计方法的结合。
PCFG是CFG的延伸，例如:
PCFG
当然，同一符号的不同生成公式的概率之和是1。NP是名词短语，VP是动词短语，PP是介词短语。
基于PCFG的句法分析模型满足以下三个条件:
位置不变性:子树的概率不依赖于子树管辖的词在句子中的位置。
上下文无关:子树的概率不依赖于子树控制范围之外的词。
祖先独立性:子树的概率不依赖于子树的祖先节点。
根据上面的语法，“他用花遇见珍妮”有两种可能的语法结构:
而且我们可以把树中的所有概率相乘得到两个子树的整体概率，选择概率较大的子树作为最佳结构。
像嗯，PCFG有三个基本问题:
给定一个句子w = w1w2 … wn和语法G，如何快速计算概率P(W|G)？
给定一个句子w = w1w2 … wn和语法g，如何选择句子的最佳结构？也就是说，句法结构树T被选择为具有最大概率。
给定PCFG G和句子w = w1w2 … wn，如何调整G的概率参数使句子的概率最大化？
首先是第一个问题。在HMM中，我们使用前向算法和后向算法来计算观察序列的O概率。同样，这里我们用向内算法和向外算法计算P(W|G)。
首先，我们定义内向变量αij(A ),它与正向变量相似但不同。非终结符A的αij(A)推导出W中字符串wiw(i+1)…wj的概率，那么P(W|G)自然等于α1n(S)，S为起始符号。计算是从起始符号s推导出整句的概率W=w1w2…wn。
所以只要有一个αij(A)的递推公式，就可以计算出P(W|G)，递推公式如下:
根据定义，αii(A)自然等于符号A输出wi的概率；αij(A)的计算思路是，这个子串wiw(i+1)…wj可以分成两部分，前一部分wiw(i+1)…wk由非终结符b生成，后一部分wkw(k+1)…wj由非终结符c生成，这样依次乘以概率，一个大问题可以分成两个小问题，两个小问题可以进一步
以下是内部变量计算方法的示意图:
这个问题也可以用外向算法解决。
首先，定义了外向变量。βij(A)是在推导语句W = W1Wn(暗示A将生成WIW)的过程中，初始符号S将生成符号串W 1 w2…W(I-1)AW(J+1)…Wn的概率也就是说，βij(A)是S推导以节点A为根节点的子树以外的其他部分的概率。
《统计自然语言处理》(第二版)这本书错了。这里我给出自己的理解。书中给出的算法步骤如下:
很明显，错误，初始化已经初始化了结果，所以这个算法没什么，正好等于1。
这是作者对外向变量定义的模糊理解。外向变量的定义上面给出了，有一句话“它暗示A会生成wiw(i+1)…wj”。问题是A会产生WIW (I+1) … WJ。这是条件还是推论？
看这个算法的初始化意义。说β1n(A)，当A=S时，是1，不代表S是0。这是什么意思？意思是句子“暗示A将生成Wiw (I+1) … WJ”是条件，β1n(S)已经暗示S生成W = W1W2 … WN，所谓W1W2 … W (I-1)。s，所以概率自然是1。
但是第三步，作者明白了什么？作者以“暗示A将生成Wiw (I+1) … WJ”这句话作为推论，认为在β1n(S)中，S将生成W = W1W2 … WN是一个推论，真的是恰到好处，要求的结果是S将生成W = W1W2。
那我的理解是什么？用这个公式计算出来的β1n(S)确实是正确的，含义其实也包含了那句“它暗示A会生成WIW (I+1)...WJ”是一个推论，但右边公式中连续递归生成的β1n(S)才是”。
我倾向于在第三步中给β1n(S)加一个星号来表示意思上的不同。
书中还给出了外向变量的计算方法示意图，我觉得也很费解:
他说βij(A)是这两种情况的概率和。我们知道J比I大，所以这个图中的K既比I小又比J大，是不是很搞笑？只能说图上两个C不是一个C，K也不是一个K。
那为什么我理解为一？除了同样的字母，他前面说过“B的形状-& gt；AC或b->；规则CA "和"使用b->；AC或b->；CA”两个规则的情况，这显然是给人一种顺序交换的误解。
另外，对内向变量的使用也是不一致的，所以可以说这本书对外向算法的解释是很失败的。而且外向算法的计算还是需要内向算法的递归，直接用内向算法确实不错，外向算法需要定义更多的变量。
然后是第二个问题，就是选择最佳的句子结构，即给定一个句子w = w1w2 … wn和语法g，
选择概率最大的语法结构树。这个问题类似于HMM中的问题，仍然采用动态规划的思想来解决。最后用CYK算法生成概率最大的句法结构树。
第三个问题是如何调整G的概率参数，使给定PCFG G和句子W = W1W2 … Wn的句子概率最大化。与HMM相反，PCFG在这里使用的算法叫做内向算法。和正反演算法一样，也属于一种EM算法。其基本思想是给G(满足规范化条件)的产生式随机赋一个概率值，得到文法G0。然后根据G0和训练数据，可以计算出每条规则的使用次数的期望值，用该期望值进行最大似然估计，得到文法g的新的参数值，新的文法标记为G1，然后循环执行，g。
PCFG只是一个特殊的上下文无关语法模型。根据PCFG的模型和句子，句子的句法分析和语法结构树的生成依赖于CYK算法。CYK算法是用于确定任何给定的字符串W是否属于上下文无关文法的算法。
基于PCFG的句法分析模型存在很多问题，例如，由于PCFG没有对词汇进行建模，所以它对词汇信息不敏感。因此，人们提出了词汇化短语结构分析器，有效地提高了基于PCFG的句法分析器的能力。
而且我们上面也提到了PCFG的三个独立假设，这也导致了规则之间缺乏结构依赖(就像HMM的三个假设并不完全合理)，而在自然语言中，每个非终结符产生的概率往往与其上下文结构有关，于是有人提出了一种方法来细化非终结符，并用其父节点的句法标记信息来标注每个非终结符。
D.Klein提出了一种具有潜在注释的上下文无关文法(PCFG-LA ),它使得非终结符的精化可以自动进行。为了避免陷入局部最优，对EM算法进行了改进，并提出了一种分层的“分裂-合并”策略，以获得精确而紧凑的PCFG-拉模型。基于PCFG-LA的Berkeley分析器作为非词汇化分析器的代表，在性能和运行速度方面是开源短语结构分析器中最好的。其语法树如下:
普通语法树和PCFG-拉语法树的比较实例
这个X是一个隐含标记，xi的取值范围一般是人为设定的，一般取1到16之间的整数。而且PCFG-LA也类似于HMM模型，原始非终结点对应HMM模型中的观察输出，隐含标记对应HMM模型中的隐含状态。
浅层语法分析(局部语法分析)
在完整的语法分析中，确定一个句子所包含的所有句法信息以及句子中各成分之间的关系是一项非常困难的任务。到目前为止，句法分析器的各个方面都难以达到令人满意的程度。为了降低问题的复杂性，获得一定的句法结构信息，浅层句法分析应运而生。
浅层语法分析只需要识别一个句子中的一些结构，比如非递归的名词短语和动词短语，通常称为语块。
浅层句法分析将句法分析分解为两个主要的子任务，一是词块的识别和分析，二是词块之间的依存关系分析。其中，词块的识别和分析是主要任务。浅层解析在一定程度上简化了解析的任务，也有利于解析系统在大规模真实文本处理系统中的快速应用。
基本名词短语是词块中的一个重要类别，指简单的、非嵌套的名词短语，没有其他子短语，基本名词短语在结构上是独立的。例子如下:
基本名词短语识别是从一个句子中识别出所有的基本名词短语。按照这种理解，一个句子中成分的总和可以简单地分为两类:碱基NP和非碱基NP，于是碱基NP的识别就变成了一个分类问题。
base NP有两种表示方式，一种是括号分隔，另一种是IOB表示法。括号分离法是用方括号定义base NP的边界，里面是base NP，外面不属于base NP。在IOB记法中，字母B表示基数NP的开始，I表示当前单词在基数NP内，O表示该单词在基数NP外。
基于SVM的基本名词短语识别方法
因为基本NP识别是一个多值分类问题，而基本SVM算法解决的是一个二值分类问题，所以一般可以采用成对的方法和一个对另一个的方法。
一般情况下，SVM需要从上下文的单词、词性和基本NP标志中提取特征来完成判断。一般当单词窗口长度为5(当前单词及其前后两个单词)时，识别效果最好。
基于WINNOW的基本名词短语识别方法
WINNOW是一种解决二分法问题的错误驱动的机器学习方法，可以从大量不相关的特征中快速学习。
WINNOW的稀疏网络(SNoW)学习结构是一种多类分类器，专门用于处理特征识别领域的大规模学习任务。WINNOW算法具有处理高维独立特征空间的能力，而自然语言处理中的特征向量恰恰具有这种特性，所以WINNOW算法也常用于词性标注、拼写错误检查和文本分类。
简单WINNOW的基本思想是，给定特征向量、参数向量和实阈值θ，将参数向量全部初始化为1，代入训练样本，求特征向量和参数向量的内积，并与θ进行比较。大于θ则判定为正例，小于θ则判定为反例。将结果与正确答案进行比较，并根据结果改变权重。
如果把正例估计成反例，那么就把X的权展开，它的原值是1。如果反例被估计为正例，那么原值为1的X的权重降低。然后重新评估和改变重量，直到训练完成。
这其实让我想起了LR算法，因为LR算法也是特征向量和参数向量的内积。最后送到Sigmoid函数得到判断结果，然后大于0.5的值为正例，小于0.5的值为反例。其实只要Sigmod函数输出0.5，输入就是WINNOW算法中的真实阈值θ。但不同的是WINNOW算法只确定大小，不确定概率，而LR使用Sigmoid函数给出概率。LR利用这个给定的概率，通过最大化训练集的生成概率来调整参数，而WINNOW则是一种直接而朴素的错误情况，来增加或减少相关参数。Visual LR比WINNOW收敛速度更快，因为它使用了梯度下降，WINNOW的优势是可以处理大量的特征。
基于条件随机场的基本名词短语识别方法
基于条件随机场的基NP识别方法与SVM方法有几乎相同的效果，优于基于WINNOW的识别方法、基于MEMM的识别方法和感知器方法，基于条件随机场的识别方法在运行速度上比其他方法有明显的优势。
依存语法理论
在自然语言处理中，我们有时不需要或者只需要整句的短语结构树，还需要知道句子中词与词之间的依存关系。用词与词之间的依存关系来描述语言结构的框架就成了依存语法，也叫依存语法。利用依存语法进行句法分析也是自然语言理解的重要手段之一。
有人认为所有的结构语法现象都可以概括为三个核心:关联、组合、换位。句法关联确立了词与词之间的从属关系，由主导词和从属词组成。谓语中的动词是句子的中心，支配其他成分，不受其他任何成分支配。
依存语法的本质是一种结构语法，主要研究构造句子时深层语义结构反映到表层语法结构的情况和条件，谓语和体词的共现关系，并据此划分谓语的词性。
有三种常用的依赖关系结构图:
计算机语言学家J. Robinson提出了依存语法的四个公理:
一个句子只有一个独立成分。
一个句子的所有其他成分都从属于某个成分。
没有一个组件可以依赖于两个或多个组件。
如果成分A直接从属于成分B，而成分C位于句子中的A和B之间，那么成分C属于成分A、成分B或A和B之间的成分..
这四个公理相当于依赖图和依赖树上的形式约束:单父节点、连通、无环和投射，从而保证了句子的依赖分析结果是有根树结构。
这里提到了可投射性。如果单词之间的依存弧绘制时没有任何交集，则它们是射影的(参考上面的两个有向图)。
为了便于理解，我国学者提出了依存结构树应满足的五个条件:
简单节点条件:只有端点，没有非端点
单父节点条件:除了根节点没有父节点外，所有节点都只有一个父节点。
单根节点条件:一棵依赖树只能有一个根节点，支配其他节点。
不相交条件:依赖树的分支不能彼此相交。
互斥条件:自上而下的支配关系和自左而右的先行关系互斥。如果两个节点之间存在支配关系，那么它们不能存在于先行关系中。
这五个条件有交集，但完全基于依存表达式的空间结构，比四个公理更直观实用。
Gaifman 1965给出了依赖文法的形式化表示，证明了依赖文法与上下文无关文法没有区别。..
类似于上下文无关语法的语言形式限制了被分析语言的投射性，难以直接处理含有非投射现象的自由语序语言。基于约束满足的约束文法和相应的依存分析方法是在20世纪90年代发展起来的，可以处理这类非投射语言问题。
基于约束满足的分析方法以约束依存文法为基础，将依存句法分析视为一个可以用约束满足问题来描述的有限构造问题。
约束依赖文法使用一系列正式的和描述性的约束来移除不满足约束的依赖分析，直到留下合法的依赖树。
生成依赖分析、判别依赖分析和确定依赖分析是数据驱动的统计依赖分析中三种有代表性的方法。
生成依赖分析方法
生成式依存分析方法利用联合概率模型生成一系列依存句法树并赋予其概率分值，然后利用相关算法寻找概率分值最高的分析结果作为最终输出。
生成依赖分析模型使用方便，其参数训练只寻找训练集中相关组件的计数，计算先验概率。但在产生式方法中使用了联合概率模型，然后在分解概率乘积时进行近似假设和估计。而且由于全局搜索，算法复杂度高，所以效率低，但这类算法在精度上有一定优势。但是，类似于CYK算法的推理方法使得这类模型难以处理非投影问题。
判别依赖分析方法
判别依赖分析方法采用条件概率模型，避免了联合概率模型所要求的独立性假设(考虑到判别模型CRF抛弃了生成模型HMM的独立性假设)，训练过程是寻找使目标函数(训练样本的生成概率)最大化的参数θ(类似于Logistic回归和CRF)。
判别法不仅在推理上进行穷举搜索，而且在训练算法上具有全局最优性。需要对训练样本重复句法分析的过程来迭代参数。训练过程也是一个推理过程，训练和分析的时间复杂度是一致的。
确定性依赖方法
确定性依存分析方法在特定方向上逐个取一个要分析的词，对每个输入词产生单一的分析结果，直到序列中的最后一个词。
这种算法在每一步分析中都要根据当前的分析状态进行决策(比如判断是否依赖于前一个词)，所以这种方法也叫决策分析法。
确定性解析方法的基本思想是通过一个确定的解析动作序列，得到一个唯一的句法表达式，即依赖图(有时可能有回溯和打补丁)。
短语结构与依存结构的关系
短语结构树可以一一对应地转换成依存树，反之亦然。因为依存关系树可以对应于多个短语结构树。