To generate training data for Oracle, some reference parses and training oracle are needed. Training oracle, which is the model to generate training data for oracle, will 
$$\left ( 1 \right )$$ Choose LEFTARC if it produces a correct head-dependent relation given the reference parse and the current configuration.
$$\left ( 2 \right )$$ Otherwise, choose RIGHTARC if (1) it produces a correct head-dependent relation given the reference parse and (2) all of the dependents of the word at the top of the stack has already been assigned.
$$\left ( 3 \right )$$Otherwise, choose SHIFT.


Generating Training Data for Oracle


The real oracle can be a feature-based classifier using logistic regression. Features for this kind of oracle include word forms, parts of speech, case markings.


Feature-based classifier


Parser takes top two words from the stack and one word from the buffer. Encoding of these words are found out with the help of an encoder. The words and its encodings are concatenated and sent to a feed forward network to generate the prediction for transition.


Oracle Implemented by a Neural Classifier for Transition-based parser

Head words are attached to its corresponding dependent words as early as possible. The transition operations on the words are LEFTARC ,RIGHTARC, SHIFT and REDUCE.


LEFTARC: Assert a head-dependent relation between the word at the front of
the input buffer and the word at the top of the stack; pop the stack.

RIGHTARC: Assert a head-dependent relation between the word on the top of
the stack and the word at front of the input buffer; shift the word at the front
of the input buffer to the stack.

SHIFT: Remove the word from the front of the input buffer and push it onto
the stack.

REDUCE: Pop the stack.

Arc-Eager Transition-Based Parsing System

Comparison of Arc-Standard and Arc-Eager Transition Systems

Beam search in transition-based dependency parsing.

In transition-Based Dependency Parsing, the oracle can tell which transition is appropriate to make. It can be trained by supervised machine learning.
The oracle takes the configuration of the stack and the word list of one sentence as its input and predicts appropriate transition. 


University of Colorado at Boulder

Dependency Parsing is fundamentally based on the dependency grammars in terms of grammar formalisms. In these formalisms, phrasal constituents and phrase-structure rules do not play a direct role as Constituent Parsing. Instead, the syntactic structure of a sentence is describe solely in terms of the words in a sentence and an associated set of directed binary grammatical relations that hold among the words.

Dependency Parsing

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

illustrated with directed, labeled arcs from heads to dependents.
It is called typed dependency structure because the labels are drawn from a fixed inventory of grammatical relations.
Note that it includes a root node that explicitly marks the root of the tree, the head of the entire structure.

Example of typed dependency structure

A major advantage is that It can deal with languages that are morphologically rich and have a relatively free word order.
Moreover, dependency-based approach enables the head-dependent relations to provide an approximation to the semantic relationship between predicates and their arguments which makes them directly useful for many applications such as coreference resolution, question answering and information extraction. 

Advantage of Dependency Parsing

Selected dependency relations from the Universal Dependency set

Examples of core Universal Dependency relations

Simple application of UD scheme on the sentence

Dependency treebanks have been created using such approaches —having human annotators directly generate dependency structures for a given corpus, or using automatic parsers to provide an initial parse and then having annotators hand correct the parses. We can also use a deterministic process to translate existing constituent-based treebanks into dependency trees through the use of head rules.

Treebanks

A dependency structure can be represented as a directed graph G=(V,A), consisting of a set of vertices V, and a set of ordered pairs of vertices A, which we’ll call arcs. There are also further constraints placed on dependency structures.

Dependency Formalisms

Graph based parsers score entire trees, and can produce non-projective trees. The graph based algorithm focuses on two problems, assigning a score to each edge, and finding the best parse tree given the scores of all potential edges.

Graph-Based

As with phrase structure-based parsing, the evaluation of dependency parsers proceeds by measuring how well they work on a test set. An obvious metric would be exact match (EM) — how many sentences are parsed correctly; however, most of the times this metric is too pessimistic. Alternative methods are:
- Labelled attachment score (LAS), which looks at the proper assignment of a word to its head along with the correct dependency relation.
- Unlabelled attachment score (UAS), which looks at the correctness of the assigned head, ignoring the dependency relation.
- Label accuracy score (LS), which looks at tokens with correct labels, ignoring where the relations are coming from.

Learn Before

Related

Learn After