Dependency Parsing

20.2 Transition-based parsing

1. What are the components of a transition-based dependency parser?
   A stack on which the parse is built, a buffer of input tokens, a set of relations, and an oracle (a predictor) that chooses the next transition given the configuration. It derives from shift-reduce parsing for programming languages.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 454
2. What three intuitive actions does transition-based parsing formalize?
   Make the current word the head of a previously seen word; make a previously seen word the head of the current word; or postpone the current word for later.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 454
3. Define the arc-standard transitions LEFTARC, RIGHTARC and SHIFT.
   LEFTARC: the top of the stack becomes head of the second word; pop the second. RIGHTARC: the second word becomes head of the top; pop the top. SHIFT: move the next buffer word onto the stack. LEFTARC can’t apply when ROOT is second; both arcs need two stack elements.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, pp. 454–455
4. What characterizes arc-standard parsing?
   Transitions only relate the top two stack elements, and once a word is assigned its head it is removed from the stack and unavailable for further processing.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 455
5. What are the initial and final configurations of a transition-based parse?
   Initial: stack [ROOT], buffer = all words, no relations. Final: buffer empty and only ROOT on the stack; the relations form the parse.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 455
6. Why is transition-based parsing efficient, and what is its weakness?
   It is linear in sentence length: one left-to-right pass, each word shifted once and reduced once. But it is greedy: one choice per step, no backtracking, so a wrong decision can’t be undone.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 455
7. Trace an arc-standard parse of “Book me the morning flight”.

   stack	buffer	action
   root	book me the morning flight	SHIFT
   root book	me the morning flight	SHIFT
   root book me	the morning flight	RIGHTARC (book → me)
   root book	the morning flight	SHIFT ×3
   root book the morning flight		LEFTARC (morning ← flight)
   root book the flight		LEFTARC (the ← flight)
   root book flight		RIGHTARC (book → flight)
   root book		RIGHTARC (root → book)

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, pp. 456–457
8. How does a transition-based parser produce labeled trees?
   Parameterize the arc transitions by relation, e.g. LEFTARC(nsubj), RIGHTARC(obj), giving one LEFTARC and RIGHTARC per label plus SHIFT; the oracle’s choice becomes harder.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 457
9. How is training data for the oracle obtained from a treebank?
   Treebanks give sentences with trees, not configurations, so simulate the parser on each training sentence with a training oracle that consults the reference parse to pick the correct transition at each configuration, recording (configuration, transition) pairs.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 457
10. What rules does the training oracle follow for arc-standard parsing?
    Choose LEFTARC if it creates a correct relation in the reference parse; otherwise RIGHTARC if it creates a correct relation and all dependents of the top word have already been attached; otherwise SHIFT.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 458
11. Why must RIGHTARC wait until the top word has all its dependents?
    RIGHTARC pops the dependent off the stack; popping it early (e.g. attaching flight to book before through Houston) would make it unavailable as the head of later words.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 458
12. What features does a feature-based transition oracle use?
    Word forms, lemmas, POS tags, heads and relations of the top stack elements and front buffer words, via templates like ⟨s1.w, op⟩, ⟨b1.t, op⟩, ⟨s1.wt, op⟩, and combinations like s1.t ∘ s2.t (e.g. NNS∘VBD); any classifier (logistic regression, SVM) can be used.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 459
13. How does a neural oracle for transition-based parsing work?
    Encode the sentence, take the encodings of the top two stack words and the first buffer word, concatenate them, and feed a feedforward network with a softmax over transitions, trained with cross-entropy.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 460
14. What problem does the arc-eager transition system solve?
    In arc-standard, a word can only be attached to its head after all its dependents are found, so attachments wait long (e.g. book → flight waits for through Houston), and long waits invite errors. Arc-eager attaches words to heads as early as possible.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 461
15. How do arc-eager transitions differ from arc-standard ones?
    LEFTARC and RIGHTARC relate the top of the stack and the front of the buffer. RIGHTARC shifts the dependent onto the stack (so it can still take dependents), and a new REDUCE operator pops the stack.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 461
16. How can beam search improve transition-based parsing?
    Instead of one greedy choice, apply all valid transitions to each configuration on an agenda, score the new configurations, and keep the best \(k\) (beam width). A configuration’s score is its predecessor’s score plus the transition’s score.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.2, p. 462