Dependency Parsing

Question 1

What is a dependency grammar?

Answer 1

They are structures that are based on grammatical relations that have been defined by linguists.

Question 2

What type of word order to dependency grammars have?

Answer 2

They have a free word order

Question 3

What do the edges and nodes represent in a dependency grammar?

Answer 3

The labels for edges are grammatical relations and nodes are words

Question 4

What do grammatical relations connect?

Answer 4

They connect head and dependent words

Question 5

What is the type of a grammatical relation called?

Answer 5

Its grammatical function

Question 6

What type of graph is a dependency tree?

Answer 6

It is a directed graph as the head node can only have arc coming into it

Question 7

What is a dependency tree made up of?

Answer 7

Vertices = nodes = words or sometimes stems/affixes

Arcs = Grammatical function relationships

Question 8

How many incoming arcs does the root node have?

Answer 8

None

Question 9

How many arcs does each vertice have coming into it?

Answer 9

Just one

Question 10

How many vertices can the root node reach through some path?

Answer 10

The root node has a path to every vertice

Question 11

What does it mean if an arc is projective?

Answer 11

We say an arc is projective if for a head and all of its dependents, there is a path to connect them all directly.

Question 12

In the image, is the arc connecting flight and was projective? Why?

Answer 12

The arc is not projective, because even though we can go from ‘flight’ to ‘was’, and from ‘was’ to ‘which’, there is no path to get from ‘flight’ to either ‘this’ or ‘morning’

Question 13

In the image below, is the arc from ‘was’ to ‘late’ projective?

Answer 13

It is projective, as we can go from ‘was’ to ‘late’, and from ‘late’ we can go to ‘already’ directly

Question 14

What do older parsing algorithms assume?

Answer 14

They assume that trees are always projective. English based Treebanks are guaranteed to be projective, but in other languages this is not the case and graphs can often include non-projective trees

Question 15

What Treebanks are used that include dependency graphs?

Answer 15

The Penn Treebank and the Ontonotes dataset

Question 16

How can we move from Parse-Structures (Constituency Grammars) to Dependency Structures?

Answer 16

We can identify head-dependent structures using head rules, and then we can connect children to heads using a dependency relation

Question 17

What are some problems that arise from translating parse-structures to dependency structures?

Answer 17

We cannot represent non-projective structures (as there are no examples in phrase-structured treebanks)

There is a lack of structure in flat noun phrases

Question 18

When would you prefer a dependency graph over a constituent based structure?

Answer 18

For training relational extraction models (clause argument detection) as clauses need subject and object grammar

Question 19

What is transition based dependency parsing?

Answer 19

These are based on the classic shift-reduce parsing where the basic idea is that we have a CFG, a stack and a list of words. We encode the words in the input buffer, shift the words onto the stack, match the words on the stack against the grammar, replacing the pairs of words that match with the left hand side of the CFG.

E.g. We have a determiner and nominal on the stack and noun phrases are made up of det + nom, we replace them with a NP

Question 20

What is the Arc Standard approach?

Answer 20

It is a simple and effective transition based dependency parsing approach

Question 21

What is an Oracle?

Answer 21

it is a model that provides the correct transition operator (add left arc, add right arc, do a shift, finished) given a configuration state when doing the Arc Standard approach to dependency parsing

Question 22

What happens when we perform a left arc?

Answer 22

We connect the 1st word of the stack (head) with the 2nd word (dep)

Question 23

What happens when we perform a right arc?

Answer 23

We connect the 2nd word of the stack (dep) with the 1st word (head)

Question 24

What happens when we perform a shift?

Answer 24

We move the next word in the input buffer into the stack

Question 25

Explain what is happening in the image

Answer 25

It shows the Arc Standard approach to dependency parsing. We start with the root node, check the oracle and shift the first word onto the stack, we check the oracle and shift the second word onto the stack. The oracle then says to perform a right arc from ‘book’ to ‘me’. We the consult the oracle again, it says to shift 3 times. We then perform a left arc having consulted the Oracle, which connects ‘flight’ to ‘morning’. This continues until we reach the point where the Oracle states that we are done.

Question 26

When we perform a left or right arc, which word is removed from the stack?

Answer 26

The word that the relation is going to is removed from the stack, the word that the relation starts from remains on the stack.

Question 27

What are some problems with the arc standard approach?

Answer 27

It is a greedy algorithm - other parse trees that are viable may be ignored

It assumes that the Oracle is 100 percent perfect which is not true in practice

The action set is needed for each relation, meaning that large action space needs to be processed

Question 28

What are some alternatives to the Arc Standard approach?

Answer 28

The Arc Eager approach and the Beam Search

Question 29

How is the Oracle created?

Answer 29

It is trained on treebanks using a supervised ML approach. We compile training examples of configurations and transition pairs. Configurations are a stack, word list and existing relation set. A transition is the action type. Feature templates are used for this model

Question 30

What features can be used when creating an Oracle?

Answer 30

Lemmas, POS, wordforms, word embeddings, dependency relations

Question 31

What is an issue with picking lots of features for Oracle training?

Answer 31

It can slow the machine learning training down

Question 32

When we have an appropriate feature template for an Oracle, what do we do next?

Answer 32

We apply it to the training input to create the inputs for the ML algorithm. X is the value set for the feature types. Y is the actions that we take for the the same input from the reference parse tree. We then apply an ML algorithm such as LR, SVM or deep learning models

Question 33

What is Graph-Based dependency parsing?

Answer 33

it is a different way of doing dependency parsing where we encode possible trees as directed graphs. They allow for the production of non-projective graphs and can handle long distance dependencies by scoring entire trees

Question 34

What is the edge-factored approach?

Answer 34

It is a graph based approach to dependency parsing. We have a score which we want to maximise, which is the sum of the score for all its edges. We have an input sentence, and a number of possible parse trees. We want to find the best possible parse tree by taking argmax of all possible parse trees for that sentence.

Question 35

What type of tree do we need to perform edge-factored dependency parsing?

Answer 35

They must be a maximum spanning tree, where every vertex (node) has one incoming edge

Question 36

What type of selection do we use with edge-factored DP and what else do we perform?

Answer 36

We use greedy selection to choose the most probable edge weight, and we perform cleanup to avoid cycles by adjusting weights using heuristics

Question 37

Explain what the image shows.

Answer 37

It shows edge factored dependency parsing. We start at the root, and take the most probable edge, which is 12, then we do this again from the node we have reached, which is book, and choose the most probable edge again, which is 7 to take us to flight. Then from flight we go to that. Although we could go to flight, we will create a cycle, therefore a cleanup needs to be performed.

Question 38

How is cleanup performed?

Answer 38

It is performed by subtracting the max edge weight (incoming) from all edge weights (incoming)

We then collapse nodes in a cycle into a single node

This process is then repeated recursively

Question 39

Explain the following image

Answer 39

This image shows how cleanup is performed in edge-factored dependency parsing. Here, we look at each node and its incoming edges and subtract the maximum edge from all of the other incoming edges. We then observe to see if there are any cycles, which in the top right graph, there are. We therefore collapse that node into a single node, called tf and adjust the edges such that we have a valid graph. This is repeated for as long as we have cycles

Question 40

How do we train a supervised ML approach to parse the edge factored graphs?

Answer 40

We apply a feature template to the training examples to produce X. We then produce a Y which is the edge probability or predictions. We have the ground truths and use a standard supervised learning algorithm as we did for the transition based approach (Arc Factored)

Question 41

What does Dozat’s model do for GB-DP?

Answer 41

It uses a LSTM model using features from (word, POS and character) embeddings. The character embeddings help handle rare words that are not in the training vocabulary

Question 42

How is Dependency Parsing evaluated?

Answer 42

Exact Match (is it perfect? conservative and minor errors cause failure)

Labelled Attachment Score (TP = correct assignment of word → head + dep relation)

Unlablled Attachment Score (TP = correct assignment of word → head)

Label Accuracy Score (percentage of words with correct edge label)