Algorithms for Deterministic Incremental Dependency Parsing

3 Deterministic Incremental Dependency Parsing

1. What is a transition system for dependency parsing?
   A quadruple \(S = (C, T, c_s, C_t)\): configurations \(C\) (at least a buffer \(\beta\) of remaining nodes and an arc set \(A\)), transitions \(T\) (partial functions \(C \to C\)), an initialization \(c_s\) putting \([1, \ldots, n]\) in the buffer, and terminal configurations \(C_t\). The parse is the arc set of the terminal configuration.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §3, pp. 517–520
2. What is an oracle, and how does it make parsing deterministic?
   A function \(o: C \to T\) choosing one transition in every configuration. The parser starts in \(c_s(x)\) and applies \(o(c)\) until a terminal configuration is reached. In data-driven parsing the oracle is approximated by a classifier trained on treebank data.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §3, pp. 517–520
3. Why does Nivre separate the oracle from the transition system?
   To separate the abstract machine, which determines formal properties like correctness and complexity, from the search mechanism. If oracle and transitions take constant time, time complexity is bounded by the maximum length of a transition sequence, and space by the size of one configuration.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §3, pp. 517–520
4. What does it mean for a transition system to be sound, complete and correct for a class of dependency graphs?
   Sound: every transition sequence yields a graph in the class. Complete: every graph in the class is the result of some transition sequence. Correct: both.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §3, pp. 517–520