An efficient algorithm for easy-first non-directional dependency parsing

ABSTRACT

We present a novel deterministic dependency parsing algorithm that attempts to create the easiest arcs in the dependency structure first in a non-directional manner. Traditional deterministic parsing algorithms are based on a shift-reduce framework: they traverse the sentence from left-to-right and, at each step, perform one of a possible set of actions, until a complete tree is built. A drawback of this approach is that it is extremely local: while decisions can be based on complex structures on the left, they can look only at a few words to the right. In contrast, our algorithm builds a dependency tree by iteratively selecting the best pair of neighbours to connect at each parsing step. This allows incorporation of features from already built structures both to the left and to the right of the attachment point. The parser learns both the attachment preferences and the order in which they should be performed. The result is a deterministic, best-first, O(nlogn) parser, which is significantly more accurate than best-first transition based parsers, and nears the performance of globally optimized parsing models.

References

1. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proc. of CoNLL.
2. Xavier Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proc. of CoNLL Shared Task, EMNLP-CoNLL.
3. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proc of EMNLP.
4. Markus Dreyer, David A. Smith, and Noah A. Smith. 2006. Vine parsing and minimum risk reranking for speed and precision. In Proc. of CoNLL, pages 201--205, Morristown, NJ, USA. Association for Computational Linguistics.
5. Jason Eisner and Noah A. Smith. 2005. arsing with soft and hard constraints on dependency length. In Proc. of IWPT.
6. Liang Huang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In Proc of EMNLP.
7. Richard Johansson and Pierre Nugues. 2007. Extended constituent-to-dependency conversion for english. In Proc of NODALIDA.
8. Ryan McDonald and Joakim Nivre. 2007. Characterizing the errors of data-driven dependency parsing models. In Proc. of EMNLP.
9. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc of EACL.
10. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proc of ACL.
11. Tetsuji Nakagawa. 2007. Multilingual dependency parsing using global features. In Proc. of EMNLP-CoNLL.
12. Joakim Nivre and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proc. of ACL, pages 950--958, Columbus, Ohio, June. Association for Computational Linguistics.
13. Joakim Nivre, Johan Hall, and Jens Nillson. 2006. Malt-Parser: A data-driven parser-generator for dependency parsing. In Proc. of LREC.
14. Joakim Nivre, Johan Hall, Sandra Kübler, Ryan Mcdonald, Jens Nilsson, Sebastian Riedel, and Deniz Yuret. 2007. The CoNLL 2007 shared task on dependency parsing. In Proc. of EMNLP-CoNLL.
15. Joakim Nivre. 2004. Incrementality in deterministic dependency parsing. In Incremental Parsing: Bringing Engineering and Cognition Together, ACL-Workshop.
16. Sebastian Riedel and James Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. of EMNLP 2006, July.
17. Kenji Sagae and Alon Lavie. 2006a. A best-first probabilistic shift-reduce parser. In Proc of ACL.
18. Kenji Sagae and Alon Lavie. 2006b. Parser combination by reparsing. In Proc of NAACL.
19. Federico Sangati and Chiara Mazza. 2009. An english dependency treebank à la tesnière. In Proc of TLT8.
20. Libin Shen and Aravind K. Joshi. 2008. Ltag dependency parsing with bidirectional incremental construction. In Proc of EMNLP.
21. Libin Shen, Giorgio Satta, and Aravind K. Joshi. 2007. Guided learning for bidirectional sequence classification. In Proc of ACL.
22. Ivan Titov and James Henderson. 2007. Fast and robust multilingual dependency parsing with a generative latent variable model. In Proc. of EMNLP-CoNLL.
23. Yamada and Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT.
24. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beam-search. In Proc of EMNLP.