We present a new cubic-time algorithm to calculate the optimal next step in shift-reduce dependency parsing, relative to ground truth, commonly referred to as dynamic oracle. Unlike existing algorithms, it is applicable if the training corpus contains non-projective structures. We then show that for a projective training corpus, the time complexity can be improved from cubic to linear.
|Number of pages
|Transactions of the Association for Computational Linguistics
|Published - 31 May 2019
- Formal language theory
- Automata theory