Syntactic Parsing

Question 1

What is syntactic parsing?

Answer 1

It is the process of assigning a syntactic structure to a sentence

Question 2

What are two parsing structures?

Answer 2

Constituency structures and Dependency structures

Question 3

What is the biggest challenge to syntactic parsing?

Answer 3

Ambiguity - specifically structural ambiguity

Question 4

What is structural ambiguity?

Answer 4

It is where multiple parse trees are possible in a grammar for the same sentence

Question 5

What is attachment ambiguity?

Answer 5

It is where a constituent could be attached to multiple places in a parse tree

Question 6

What is coordination ambiguity?

Answer 6

It is where phrases can be conjoined in multiple ways

Question 7

What is syntactic disambiguation?

Answer 7

It is choosing the correct parse

Question 8

What is useful to address ambiguity?

Answer 8

Dynamic Programming

Question 9

What algorithm is a classic dynamic programming approach to parsing?

Answer 9

The CKY algorithm

Question 10

What is dynamic programming the same as?

Answer 10

Chart Parsing

Question 11

What does CKY require grammars to be?

Answer 11

In Chomsky Normal Form (CNF)

Question 12

What are the rules of Chomsky Normal Form?

Answer 12

The right side must be (i) two non-terminal nodes, or (ii) a single terminal node

Question 13

How do we encode a parse tree in CNF?

Answer 13

We use a 2D matrix called a parse table. Indices before and after tokens are called fenceposts

Question 14

What does each cell represent in a parse table?

Answer 14

An entry for i,j

i is the start fencepost index for span

j is the end fencepost index for span

n is the length of the sentence

span (i,j) is constituent phrase with j - i tokens

span (0,n) is the sentence

Question 15

In a parse table, in what order do we move?

Answer 15

You move left to right, bottom to top

Question 16

With the aid of the image, explain how you perform CKY parsing manually.

Answer 16

You start at the first position, and make your way from left to right looking from bottom to top. You look to see if there are any productions that end in any of the values in the cell you are at or below, and have the values that are observed to the left before it. For example, it the cell [0,3] we can produce a Verb (seen in cell [0,1]) followed by a NP (seen in cell [1,3]) by using a production from S, VP or X2.

Question 17

Does the CKY algorithm help to disambiguate possible parse trees?

Answer 17

No - the table is populated with all possible parse trees, it does not choose the best

Question 18

How does neural CKY work?

Answer 18

It learns to classify constituency parsing labels for text spans. Given a particular span, it looks the model can be trained such that it gives the correct constituency parse label.

Question 19

What is the input for a Neural CKY model?

Answer 19

We take our words, tokenize them to get the words, pass it into the word piece tokenizer to get the subwords and pass these to the BERT embedding layer to encode the words. We then use either the first or last subword embedding for each word to get back to words

Question 20

How are the word embeddings used in a Neural CKY model?

Answer 20

A post processing layer that is a deep learning stack (often a transformer) with a MLP is passed the word embeddings which are used to convert this into a sequence classifier to map them to a label.

Question 21

How can embeddings per word be used to represent a span?

Answer 21

Directional vectors where the embedding at the start is subtracted from the end, and vice versa to get a forward and backward vector, which are then concatenated in order to get the fenceposts, although the backward vector uses the values + 1 to account for the fact that the fencepost occurs somewhere between the words.

Question 22

When we have the span vectors for Neural CKY, what do we then do?

Answer 22

We then compute a score using an activation function (e.g. ReLU), the MLP output layer has dimensions equal to the number of non-terminal labels

Question 23

What does the activation function of the MLP produce in Neural CKY?

Answer 23

A distribution across all the possible labels stating which label is the most likely one

Question 24

How do we compute a score for the entire parse tree?

Answer 24

We sum the individual scores for all the possible spans and all possible labels to give a score for each possible parse tree.

Question 25

How is the best parse tree chosen?

Answer 25

The argmax function

Question 26

How frequently does argmax find a complete tree in practice?

Answer 26

95 percent of the time a complete tree is found