Dependency parsing

Overview

A dependency parse assigns each word a head word and a label for the relation between them, so that the sentence forms a tree with a root, normally the main predicate 2004.10643 §2.3. The Universal Dependencies (UD) guidelines fix one inventory of relation types for many languages, so that trees from different treebanks can be compared 2004.10643 §2.3.

The four cards describe the concept from different sides:

• As a tool inside a pipeline: an easy-first parser supplies the dependency tree from which a system reads the verb and subject attached to each number in a word problem 1608.01413 §4.2.
• As an annotation target: the UD v2 scheme defines the labels and the tree format of a UD-annotated treebank 2004.10643 §2–§3.
• As one stage of a toolkit: scispaCy retrains spaCy's components on biomedical data. A joint tagger and arc-eager, transition-based parser runs in the same pipeline as its tokenizer and NER 1902.07669 §2 1902.07669 §3.
• As a measured component: a parser that scores head-dependent arcs and decodes a maximum spanning tree sits on top of a pretrained encoder. The FlauBERT paper reports its UAS and LAS on the French Treebank, varying the input representation 1912.05372 §5.5 1912.05372 tab. 7.

Only the scispaCy card compares parser architectures. It sets its transition-based parser against a Biaffine parser on GENIA 1.0 converted to UD 1902.07669 tab. 4. That comparison is author-reported and covers one treebank. The arithmetic card gives no parser accuracy, and its parser version is not stated 1608.01413 §4.2.

Variants

Easy-first parser as a pipeline component

The parser is one stage of a system that predicts arithmetic expressions. The system uses it to find, for each quantity, the first verb reached by walking up the tree, and that verb's subject 1608.01413 §4.2. Parser version is not stated 1608.01413 §4.2. Card: Solving General Arithmetic Word Problems.

Universal Dependencies scheme

The scheme has one head per word, a fixed list of universal relation types, and language-specific subtypes. Version 2 changes several relations and the coordination attachment, so converters from version 1 need to move cc and punct markers 2004.10643 §3.3. The scispaCy card's GENIA-derived training trees are UD v1.0 1902.07669 §3.1, so they need the same v1-to-v2 conversion before they match v2 output. Card: Universal Dependencies v2. The annotation scheme itself is covered on dependency-treebank.

Transition-based parser in a biomedical toolkit

The scispaCy parser is arc-eager and transition-based, trained with a dynamic oracle. It predicts POS tags in the same model 1902.07669 §3. Its training trees come from GENIA 1.0, converted to UD v1.0 with the Stanford Dependency Converter. OntoNotes 5.0 annotations are mixed in for robustness 1902.07669 §3.1. The medium model reports UAS 90.60 and LAS 88.79 on GENIA, and the small model 89.69 and 87.67 1902.07669 tab. 4. The authors say the parser trails a Biaffine parser by 2–3 points and runs about nine times faster 1902.07669 §3.2. Card: ScispaCy: Fast and Robust Models for Biomedical Natural Language Processing.

Arc-scoring parser on a pretrained encoder

The parser follows Dozat (2017) and decodes trees with a maximum spanning tree. Its word input is the concatenation of trained word and tag embeddings and at most one pretrained vector. Dropout applies to the word and tag embeddings, not to the BERT-style representations 1912.05372 §5.5. The tags are predicted, taken from the shared task 1912.05372 §5.5. Card: FlauBERT: Unsupervised Language Model Pre-training for French.

On the French Treebank, the paper reports LAS of 85.11 with no pre-training, 82.04 with fastText vectors, 85.86 with mBERT, 88.13 with CamemBERT, 88.35 with FlauBERT-base and 88.47 with FlauBERT-large 1912.05372 tab. 7. These are author-reported, on one treebank.

When to use which

Implementation sketch

The common core of the neural parser is to score every candidate head for each word and then decode one tree from those scores 1912.05372 §5.5. The scorer's architecture is not described beyond its input, so only the decoding step is fixed.

# Graph-based parse: score candidate arcs, then decode a tree  [arxiv:1912.05372 §5.5]
# Input:  token representations (n, d); index 0 is the root
# Output: head index for every word

def parse(token_reprs):
    # Score each candidate arc from head h to dependent d  [arxiv:1912.05372 §5.5]
    arc_scores = arc_scorer(token_reprs)            # (n, n)
    # Decode the tree as a maximum spanning tree over the arc scores
    #   [arxiv:1912.05372 §5.5]; the paper names the decoder, not the algorithm
    return maximum_spanning_tree(arc_scores)

The scispaCy parser is a different family. It is arc-eager and transition-based, so it builds the tree as a sequence of transitions rather than by scoring all arcs at once 1902.07669 §3. The paper names the system but gives no transition table or pseudocode, so this page does not sketch it.

The pipeline use from the arithmetic system, by contrast, walks up an existing parse. It finds the first verb above a quantity token. Its tag set and parser are not stated 1608.01413 §4.2.

# Find the verb a quantity attaches to  [arxiv:1608.01413 §4.2]
# Input:  head index per token (root has None); tag per token; quantity index
# Output: index of the first verb above the quantity, or None

def associated_verb(heads, tags, quantity_index):
    # Walk upward through heads until a verb is found  [arxiv:1608.01413 §4.2]
    node = heads[quantity_index]
    while node is not None:
        if tags[node] == "VERB":  # tag name is illustrative; paper gives none
            return node
        node = heads[node]
    return None

Contradictions

None known. The cards measure different things: a feature stage, an annotation scheme, a toolkit's accuracy and speed, and a parser's accuracy on a French treebank. The scispaCy scores are on GENIA converted to UD, and the FlauBERT scores are on the French Treebank. They are on different treebanks and should not be compared. Within scispaCy, the speed comparison is not like for like 1902.07669 tab. 2.

Papers

• Solving General Arithmetic Word Problems: uses an easy-first dependency parse as an input stage for quantity schemas.
• Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection: defines the dependency representation and relation inventory used by UD.
• FlauBERT: Unsupervised Language Model Pre-training for French: a French BERT-style encoder whose representations feed an arc-scoring dependency parser, evaluated on the French Treebank.
• ScispaCy: Fast and Robust Models for Biomedical Natural Language Processing: a spaCy-based biomedical pipeline with a joint arc-eager parser, compared with a Biaffine parser on GENIA converted to UD.