Aims to find syntactic dependencies between words and identify the type of dependency. 旨在发现词与词之间的句法依存关系，并确定依存关系的类型。
Explain how all the words in a sentence relate to each other 解释一个句子中的所有单词互相之间的联系。
image.png
For a tree: All the words, except one, are dependent on another word in the sentence 对于一棵树:除了一个词（根），所有的词都依赖于句子中的另一个词
• Root = special token which is not a dependent. Sometimes omitted. 根=非从属的特殊token。有时省略。
• Dependents = all other words, which are directly or indirectly linked to the root word In a dependency tree: 从属词=直接或间接链接到从属树中的根词的所有其他词:
• Nodes represent words 节点代表单词
• Edges represent dependencies (from head to dependent) 连线代表依赖关系

Analyses the grammatical structure of sentences, by establishing relationships between “head” words and “modifier”/“dependent” words: 通过建立“head” words and “modifier”/“dependent” words，分析句子的语法结构
- Build a tree that assigns a single ”head” or “parent” word to each word in the sentence 建立一棵树，为句子中的每个单词指定一个“head”或“parent”字
- The root of the tree is (typically) the main verb in the sentence 树根通常是句子中的主要动词
- Examples of dependency types: http://universaldependencies.org/docsv1/en/dep/index.html

Syntactic structure consists of lexical items, linked by binary asymmetric relations called dependencies 句法结构由被称为依赖关系的二元不对称关系连接的词汇项组成

head → dependent

head (governor) : grammatically most important 语法上最重要

dependent (modifier): modifier, object, or complement 修饰语、宾语或补语

image.png

Formal definition for unlabeled dependency trees: 未标记依赖树的正式定义:
image.png
Dependency parsing: task of mapping an input string to a dependency graph satisfying certain conditions (see following slides) 依赖解析:将输入字符串映射到满足特定条件的依赖图的任务(参见下面的幻灯片)

image.png
image.png
Crossing lines! 交叉线
English has very few non-projective cases 英语中很少有非投射依赖数
Which is good because methods that only allow projective dependency trees/forests tend to be simpler/faster 这很好，因为只允许投射依赖树/森林的方法往往更简单/更快

Well-Formedness 良好形式

A dependency tree is well-formed iff 一个良好形式的依赖树需要满足以下条件。
• Single head: Each word has only one head 单头:每个单词只有一个head
• Acyclic: The graph should be acyclic i.e. has no cycles 无循环:图应该是无循环的，即没有循环
• Connected: There is a path between any pair of nodes 连接:任何一对节点之间都有一条路径
• Projective: if an edge from word A to word B implies that there exists a directed path in the graph from A to every word between A and B in the sentence 投射:如果从单词A到单词B的一条边意味着在从A到句子中的A和B之间的每个单词的图中存在一条有向路径
Note: the graph may be a forest rather than a single tree. In which case it need not be connected, and not every node has a head. 注意:该图可能是一个森林，而不是一棵树。在这种情况下，它不需要连接，并且不是每个节点都有头。

Parsing Algorithms 解析算法

Graph-based parsing 基于图的解析
Eisner (CYK variant)
McDonald (Maximum Spanning Tree)

Transition-based parsing 基于转换的解析
Covington
Yamada and Matsumuto
Nivre Arc-eager

Nivre’s Parsing Algorithm (Arc-eager) [3]

Transition-based 基于转换的
image.png、
image.png

Parsing Details

− Each dependency graph has an artificial root so it might form a tree 每个依赖图都有一个人工根，因此它可能会形成一棵树
− Parsing starts with an initial configuration and terminates when it reaches through a sequence of transitions (aka when the buffer is empty) 解析从初始配置开始，当到达一系列转换时(也就是当缓冲区为空时)终止
− Result does not have to be a tree, it could be a forest 结果可以不是一个树，而是一个森林
• Choosing which transitions? 选择哪些转化？
− Priority ordering of transitions 转化的优先度：
− Using the order shown, pick the first transition with pre-conditions that are met: 使用所示顺序，选择满足先决条件的第一个过渡:
− Left-arc, Right arc, Reduce, Shift
− Guided parsing (Oracle, Machine Learning) 引导式解析(甲骨文，机器学习)

rammatical Rules for the Example

image.png

Example

image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————

image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————
image.png
————————————————————————————————————————————

Configurations of the Example 示例的配置

image.png

Properties of Nivre’s Algorithm

O(n) : Linear time complexity 线性时间复杂度
Full dependency graphs are well-formed 完全依赖图格式良好
Though they might be a forest rather than a tree. 尽管他们可能是一个森林 而不是一个树

Guided Parsing

Train a classifier to predict parse transitions!
• image.png
• A is a set of typed dependencies (arcs) Feature space:

Feature space:
image.png

Dependency Structures vs. Phrase Structures

Most training data for dependency parsing consists of: (sentence, ground truth parse) 大多数依赖解析的训练数据包括:(句子、基本事实解析)

To train a classifier we need tuples of the form: (configuration, correct parser action) 为了训练分类器，我们需要以下形式的元组:(配置，正确的解析器动作)

There are deterministic algorithms (called oracles) for turning a (sentence, ground truth parse) tuple into a sequence of (configuration, correct parser actions). 有确定性算法(称为预言)可以将一个(句子，基本事实解析)元组转换成一系列(配置，正确的解析动作)。
• Guaranteed to give a sequence of actions producing the gold tree (if possible, to construct) 保证给出生成树的一系列动作(如果可能，进行构建)
• Typically, only give one way to get the gold tree 通常，只给出一种获得树的方法

image.png

Off-the-Shelf Dependency Parsers

spaCy (https://spacy.io/)
Stanza (from Stanford) (https://stanfordnlp.github.io/stanza/)
MaltParser (Nivre) (http://www.maltparser.org/)
Demos:
https://explosion.ai/demos/displacy
https://demo.allennlp.org/constituency-parsing

Dependency Structures vs. Phrase Structures

• Dependency structures explicitly represent 依赖结构明确表示
− Head-dependent relations (directed arcs) —头部相关关系(有向弧)
− Functional categories (arc labels) —功能类别(弧形标签)
− predicate-argument structure —谓词-自变量结构
• Dependency structure independent of word order 独立于词序的依存结构
− Suitable for free word order languages, such as Indian languages 适用于自由词序语言，如印度语
• Phrase structures explicitly represent 短语结构明确表示
− Phrases (non-terminal nodes) 短语(非终端节点)
− Structural categories (non-terminal labels) 结构类别(非终端标签)
− Fragments are directly interpretable 片段可以直接解释