依存语法理论
在自然语言处理中，我们有时不需要或者不仅仅需要整个句子的短语结构树，而且要知道句子中词与词之间的依存关系。用词与词之间的依存关系来描述语言结构的框架成为依存语法，又称从属关系语法。利用依存语法进行句法分析也是自然语言理解的重要手段之一。
有人认为，一切结构语法现象可以概括为关联、组合和转位这三大核心。句法关联建立起词与词之间的从属关系，这种从属关系由支配词和从属词联结而成，谓语中的动词是句子的中心并支配别的成分，它本身不受其他任何成分支配。
依存语法的本质是一种结构语法，它主要研究以谓词为中心而构句时由深层语义结构映现为表层语法结构的状况及条件，谓词与体词之间的同现关系，并据此划分谓词的词类。
常用的依存于法结构图示有三种：
计算机语言学家J. Robinson提出了依存语法的四条公理：
- 一个句子只有一个独立的成分
- 句子的其他成分都从属于某一成分
- 任何一个成分都不能依存于两个或两个以上的成分
- 如果成分A直接从属于成分B，而成分C在句子中位于A和B之间，那么，成分C或者属于成分A，或者从属于B，或者从属于A和B之间的某一成分。
这四条公理相当于对依存图和依存树的形式约束：单一父节点、连通、无环和可投射，由此来保证句子的依存分析结果是一棵有根的树结构。
这里提一下可投射，如果单词之间的依存弧画出来没有任何的交叉，就是可投射的（参考上面的两个有向图）。
为了便于理解，我国学者提出了依存结构树应满足的5个条件：
- 单纯结点条件：只有终结点，没有非终结点
- 单一父结点条件：除根节点没有父结点外，所有的结点都只有一个父结点
- 独根结点条件：一个依存树只能有一个根结点，它支配其他结点
- 非交条件：依存树的树枝不能彼此相交
- 互斥条件：从上到下的支配关系和从左到右的前于关系之间是相互排斥的，如果两个结点之间存在着支配关系，它们就不能存在于前于关系
这五个条件是有交集的，但它们完全从依存表达的空间结构出发，比四条公理更直观更实用。
Gaifman 1965年给出了依存语法的形式化表示，证明了依存语法与上下文无关文法没有什么不同..
类似于上下文无关文法的语言形式对被分析的语言的投射性进行了限制，很难直接处理包含非投射现象的自由语序的语言。20世纪90年代发展起来了约束语法和相应的基于约束满足的依存分析方法，可以处理此类非投射性语言问题。
基于约束满足的分析方法建立在约束依存语法之上，将依存句法分析看做可以用约束满足问题来描述的有限构造问题。
约束依存语法用一系列形式化、描述性的约束将不符合约束的依存分析去掉，直到留下一棵合法的依存树。
生成式依存分析方法、判别式依存分析方法和确定性依存分析方法是数据驱动的统计依存分析中具有代表性的三种方法。
生成性依存分析方法
生成式依存分析方法采用联合概率模型生成一系列依存语法树并赋予其概率分值，然后采用相关算法找到概率打分最高的分析结果作为最后输出。
生成式依存分析模型使用起来比较方便，它的参数训练时只在训练集中寻找相关成分的计数，计算出先验概率。但是，生成式方法采用联合概率模型，再进行概率乘积分解时做了近似性假设和估计，而且，由于采用全局搜索，算法的复杂度较高，因此效率较低，但此类算法在准确率上有一定优势。但是类似于CYK算法的推理方法使得此类模型不易处理非投射性问题。
