Constituency Parsing

Question 1

Constituency Parsing

Constituency Parsing

Answer 1

• Parsing based on syntax, structure of the sentence
• Tree-structured: syntactic analysis of sentences (focus on structure, POS)
• Common Things: noun phrases, verb phrases, prepositional phrases
• Doesn’t work for all languages

Question 2

Constituency Parsing

Constituency Parsing: Challenges

Answer 2

1. PP (Prepositional Phrase) attachment
2. Modifier Scope
3. Complement Structure
4. Coordination Scope

Question 3

Constituency Parsing: Challenges

PP (Prepositional Phrase) Attachment

Answer 3

Different parsings of a sentence can be incorrect/produce wrong meaning

Question 4

Constituency Parsing: Challenges

Modifier Scope

Answer 4

Modifier describes an object.
Ex: “plastic cup holder” (does plastic describe the cup or the holder?)

Question 5

Constituency Parsing: Challenges

Complement Structure

Answer 5

Complementary tokens can refer to different objects.
Ex: “The students complained to the professor that they didn’t understand.” (“they” can refer to the professor or the students)

Question 6

Constituency Parsing: Challenges

Coordination Scope

Answer 6

Some tokens can be classified using multiple labels
Ex: “The man picked up the hammer and saw.” (“saw” can be a verb or a noun)

Question 7

Context-Free Grammars

Context-Free Grammars (CFG)

Answer 7

• Symbols that can be rewritten as one or more symbols
• Represented as a tuple
• Can have ambiguity (multiple results possible)

Question 8

Context-Free Grammars

CFG Lexicon

Answer 8

Consists of “preterminals” (POS tags) rewriting as terminals (words)

Question 9

Context-Free Grammars

CFG Representation

Answer 9

Written as a tuple: (N, T, S, R)
N = nonterminals
T = terminals
S = start symbol
R = rules

Question 10

PCFGs

Probabalistic Context-Free Grammars

Answer 10

• Probabilites associated with rewrites
• Normalize by source symbol

Question 11

PCFGs

PCFG Equation

Answer 11

P(T) = product_rET (r|parent(r))

Tree T is the series of rule applications

Question 12

PCFGs

Learning a PCFG

Answer 12

• Given a set of example trees, the underlying CFG can simply be all production rules seen in the corpus
• Learning Goal: estimate the probability of each production rule
• Maximum Liklihood Estimation

Question 13

PCFGs

PCFG Maximum Likelihood Estimation

Answer 13

P(a->b) = count(a->b) / count(a)

(similar to HMMs)

Question 14

PCFGs

Chomsky Normal Form (CNF)

Answer 14

• To parse efficiently, we binarize PCFGs by always using Chomsky Normal Form
• Means that trees can only have either two non-terminal subtree children or one (terminal) leaf value

Question 15

Inference

CKY

Answer 15

• Find argmax_T( P(T) )
• Dynamic Programming: chart maintains the best way of building symbol X over span(i, j)
• Like Viterbi
• Basically… continously split text and assign label until reach terminal

Question 16

Parser Evaluation

Answer 16

Precision: number of correct brakets / num predicated brackets
Recall: number of correct brackets / num of gold brackets
F1: harmonic mean of precision and recall

Question 17

Dependency VS Constituency

Answer 17

Dependency: more univeral, models PP attachment better, easier to build, faster
Constituency: doesn’t work for all languages, models coordination better, harder to build (needs to learn grammar and then use it), slower