[XCS224N] Lecture 5 – Dependency Parsing

Phrase structure: organize words into nested constituents.

Context-Free Grammars

context-free grammars (CFGs)

  • start with words, words are given a category (part of speech = POS):

  • words combine into phrases with categories like NP(noun phrase) and PP(prep.phrase):

  • Phrases can combine into bigger phrases recursively:

⇒ forms a tree structure:

Dependency Structure

Different from CFGs, instead of having concepts of NP/PP/etc, dependency structure shows which word depend on which other word.

Prepositional Phrase Attachment Ambiguity

example of ambiguties:

multiplied ambiguities: many PPs in a row

⇒ exp number of possible dep trees,

Dependency Grammar - Structure and Parsing

  • Dependency syntax: syntactic structure consists of relations between lexical items, normally binary asymmetric relations (“arrows”) called dependencies.
  • The arrows are commonly typed with the name of grammatical relations (subject, prepositional object, apposition, etc.)
  • Usually, dependencies form a tree (connected, acyclic, single-rooted graph)


Universal Dependencies treebanks: human-annotated dep trees

treebank vs.grammar:

  • cons:
  • slow
  • pros:
  • Reusability of the labor
  • Broad coverage, not just a few intuitions
  • Frequencies and distributional information
  • A way to evaluate systems

More on Dependency Parsing

Dep parsing: A sentence is parsed by choosing for each word what other word (including ROOT) is it a dependent of. constraints:

  • Only one word is a dependent of ROOT
  • no cycle

pb: whether arrows can cross (non-projective)

Transition-based Dependency Parsing

greedy discriminative dependency parser, a seq of bottom up actions.


  • stack alpha
  • buffer beta
  • dependencies A

Possible actions:

  • SHIFT : removes the first word from the buffer and pushes it onto the stack.
  • LEFT-ARC : marks the second (second most recently added) item on the stack as a dependent of

the first item and removes the second item from the stack.

  • RIGHT-ARC : marks the first (most recently added) item on the stack as a dependent of the second

item and removes the first item from the stack.


Pb: how to choose the actions (shift/left-arc/right-arc) ? searching all possible actions or DP → cubical complexity❌️ ⇒ use ML to predict actions✔️

  • classes: 3 actions (for untyped choices)
  • features: stack word, buffer word, POS
  • can also do beam search: keep k good parse prefixes at each time step.

⇒ provides very fast linear time parsing, with great performance QUESTION: what creteria to select best path?

Conventional features: hand-engineered, binary (indicator) features

(from assignement) Four types of parsing errors:

  • Prepositional Phrase Attachment Error:

e.g. wrong: Moscow sent [troops into Afghanistan] right: Moscow sent [troops] [into Afghanistan] ⇒ prep phrase="into Afghanistan", correct head word = "sent", wrong head word = "troops"

  • Verb Phrase Attachment Error

e.g.[Leaving the store unattended], I went outside to watch the parade ⇒ verb phrase = "Leaving the store unattended", head word="went"

  • Modifier Attachment Error

e.g.I am [extremely] short ⇒ modifier="extremely", head word="short"

  • Coordination Attachment Error

e.g.Would you like brown rice or garlic naan? ⇒ conjuncts="rown rice" and "garlic naan", coordinating conjunction="or" The second conjunct (here "garlic naan") should be attached to the first conjunct (here "brown rice").

Evaluation of Dependency Parsing

eval metrics: dependecy accuracy

Neural Dependency Parsing

problem with indicator features:

  • sparse
  • incomplete
  • expensive computation: most time are wasted computing the features

neural dependency parser

  • represent each word as a d -dimensional dense vector (word vectors)
  • POS and dependency labels are also represented as dense vectors
  • rational: some POS tags are similar,
  • e.g. NNS(plural nouns) is similar to NN(singular noun), NUM(numbers) similar to AMOD(adj. modifier).

⇒ concat the embeddings of features, feed into a feed forward NN:

⇒ The dense representations let it outperform other greedy parsers in both accuracy and speed

comments powered by Disqus