Algorithms for Deterministic Incremental Dependency Parsing

1 Introduction

1. Why had deterministic parsing been considered inadequate for natural language, and what changed?
   Natural language grammars are massively ambiguous, so mainstream parsers derive many analyses in parallel (charts, dynamic programming) and rank them. But treebank-induced classifiers that predict the next derivation step can make a single left-to-right derivation highly accurate, especially for dependency parsing.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §1, pp. 513–514
2. What is the trade-off of pseudo-deterministic, classifier-based parsing?
   It is an extreme form of pruning: parse selection happens incrementally and only one analysis is ever built, making parsing very simple and efficient, at the risk of losing accuracy through early commitment in greedy search. In practice it reached state-of-the-art accuracy, e.g. tying for top results at CoNLL-X 2006.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §1, pp. 513–514
3. What are the three components of a deterministic classifier-based parser?
   A parsing algorithm (derivations as sequences of elementary actions), a feature model (a feature vector representation of the parser state), and a classifier mapping parser states to actions. Nivre (2008) focuses on the algorithms.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §1, pp. 513–514