acl acl2013 acl2013-133 acl2013-133-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yoav Goldberg ; Kai Zhao ; Liang Huang
Abstract: Beam search incremental parsers are accurate, but not as fast as they could be. We demonstrate that, contrary to popular belief, most current implementations of beam parsers in fact run in O(n2), rather than linear time, because each statetransition is actually implemented as an O(n) operation. We present an improved implementation, based on Tree Structured Stack (TSS), in which a transition is performed in O(1), resulting in a real lineartime algorithm, which is verified empiri- cally. We further improve parsing speed by sharing feature-extraction and dotproduct across beam items. Practically, our methods combined offer a speedup of ∼2x over strong baselines on Penn Treeb∼a2nxk sentences, a bnads are eosrd oenrs P eofn magnitude faster on much longer sentences.
Eugene Charniak. 2000. A maximum-entropyinspired parser. In Proceedings of NAACL. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL. Michael Collins. 1999. Head-Driven Statistical Mod- els for Natural Language Parsing. University of Pennsylvania. Ph.D. thesis, Yoav Goldberg and Michael Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency parsing. In Proceedings of HLT-NAACL, pages 742–750. Liang Huang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL 2010. Liang Huang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In Proceedings of EMNLP. Philipp Koehn. 2004. Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Proceedings of AMTA, pages 115– 124. Marco Kuhlmann, Carlos Gmez-Rodrguez, and Giorgio Satta. 2011. Dynamic programming algorithms for transition-based dependency parsers. In Proceedings of ACL. Joakim Nivre and Mario Scholz. 2004. Deterministic dependency parsing of english text. In Proceedings of COLING, Geneva. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. Chris Okasaki. 1999. Purely functional data structures. Cambridge University Press. Brian Roark. 2001. Probabilistic top-down parsing and language modeling. Computational Linguistics, 27(2):249–276. Masaru Tomita. 1985. An efficient context-free parsing algorithm for natural languages. In Proceedings of the 9th international joint conference on Artificial intelligence - Volume 2, pages 756–764. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: investigating and combining graphbased and transition-based dependency parsing using beam-search. In Proceedings of EMNLP. Yue Zhang and Stephen Clark. 2011. Shift-reduce ccg parsing. In Proceedings of ACL. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proceedings of ACL, pages 188–193. 633