A Linear-Time Transition System for Crossing Interval Trees

Emily Pitler, Ryan T. McDonaldNAACL 2015 · OpenReview

Abstract

We define a restricted class of non-projective trees that 1) covers many natural language sentences; and 2) can be parsed exactly with a generalization of the popular arc-eager system for projective trees (Nivre, 2003). Crucially, this generalization only adds constant overhead in run-time and space keeping the parser’s total run-time linear in the worst case. In empirical experiments, our proposed transition-based parser is more accurate on average than both the arc-eager system or the swap-based system, an unconstrained nonprojective transition system with a worst-case quadratic runtime (Nivre, 2009).
BibTeX
@inproceedings{pitler2015linear,
  author = {Emily Pitler and Ryan T. McDonald},
  title = {{A Linear-Time Transition System for Crossing Interval Trees}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  url = {https://openreview.net/forum?id=rkZeS7ZuZS},
}

Loading related content...

Figure