acl acl2010 acl2010-93 acl2010-93-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Liang Huang ; Kenji Sagae
Abstract: Incremental parsing techniques such as shift-reduce have gained popularity thanks to their efficiency, but there remains a major problem: the search is greedy and only explores a tiny fraction of the whole space (even with beam search) as opposed to dynamic programming. We show that, surprisingly, dynamic programming is in fact possible for many shift-reduce parsers, by merging “equivalent” stacks based on feature values. Empirically, our algorithm yields up to a five-fold speedup over a state-of-the-art shift-reduce depen- dency parser with no loss in accuracy. Better search also leads to better learning, and our final parser outperforms all previously reported dependency parsers for English and Chinese, yet is much faster.
Alfred V. Aho and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling, volume I: Parsing of Series in Automatic Computation. Prentice Hall, Englewood Cliffs, New Jersey. S. Billot and B. Lang. 1989. The structure of shared forests in ambiguous parsing. In Proceedings of the 27th ACL, pages 143–15 1. Eugene Charniak and Mark Johnson. 2005. Coarseto-fine-grained n-best parsing and discriminative reranking. In Proceedings of the 43rd ACL, Ann Arbor, MI. 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. 2000. Discriminative reranking for natural language parsing. In Proceedings of ICML, pages 175–182. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP. Xiangyu Duan, Jun Zhao, and Bo Xu. 2007. Probabilistic models for action-based chinese dependency parsing. In Proceedings of ECML/PKDD. Jay Earley. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94– 102. Jason Eisner and Giorgio Satta. 1999. Efficient parsing for bilexical context-free grammars and headautomaton grammars. In Proceedings of ACL. Jason Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING. Lyn Frazier and Keith Rayner. 1982. Making and correcting errors during sentence comprehension: Eye movements in the analysis of structurally ambiguous sentences. Cognitive Psychology, 14(2): 178 210. – Liang Huang and David Chiang. 2005. Better k-best Parsing. In Proceedings of the Ninth International Workshop on Parsing Technologies (IWPT-2005). Liang Huang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In Proceedings of EMNLP. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of the ACL: HLT, Columbus, OH, June. Mark Johnson. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24:613–632. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In Proceedings of ACL. B. Lang. 1974. Deterministic techniques for efficient non-deterministic parsers. In Automata, Languages and Programming, 2nd Colloquium, volume 14 of Lecture Notes in Computer Science, pages 255–269, Saarbr¨ ucken. Springer-Verlag. Lillian Lee. 2002. Fast context-free grammar parsing requires fast Boolean matrix multiplication. Journal of the ACM, 49(1): 1–15. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online large-margin training of dependency parsers. In Proceedings of the 43rd ACL. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Haji cˇ. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT- EMNLP. Mark-Jan Nederhof. 2003. Weighted deductive parsing and Knuth’s algorithm. Computational Linguistics, pages 135–143. Joakim Nivre. 2004. Incrementality in deterministic dependency parsing. In Incremental Parsing: Bringing Engineering and Cognition Together. Workshop at ACL-2004, Barcelona. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Proceedings of HLTNAACL. Brian Roark and Kristy Hollingshead. 2009. Linear complexity context-free parsing pipelines via chart constraints. In Proceedings of HLT-NAACL. Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2): 165–201. Masaru Tomita. 1988. Graph-structured stack and natural language parsing. In Proceedings of the 26th annual meeting on Association for Computational Linguistics, pages 249–257, Morristown, NJ, USA. Association for Computational Linguistics. Masaru Tomita, editor. 1991 . Generalized LR Parsing. Kluwer Academic Publishers. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT. 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. 1086