acl acl2013 acl2013-358 acl2013-358-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jinho D. Choi ; Andrew McCallum
Abstract: We present a novel approach, called selectional branching, which uses confidence estimates to decide when to employ a beam, providing the accuracy of beam search at speeds close to a greedy transition-based dependency parsing approach. Selectional branching is guaranteed to perform a fewer number of transitions than beam search yet performs as accurately. We also present a new transition-based dependency parsing algorithm that gives a complexity of O(n) for projective parsing and an expected linear time speed for non-projective parsing. With the standard setup, our parser shows an unlabeled attachment score of 92.96% and a parsing speed of 9 milliseconds per sentence, which is faster and more accurate than the current state-of-the-art transitionbased parser that uses beam search.
Bernd Bohnet and Joakim Nivre. 2012. A TransitionBased System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP’ 12, pages 1455–1465. Sabine Buchholz and Erwin Marsi. 2006. CoNLLX shared task on multilingual dependency parsing. In Proceedings of the Tenth Conference on Computational Natural Language Learning, CoNLL’06, pages 149–164. Xavier Carreras, Michael Collins, and Terry Koo. 2008. TAG, Dynamic Programming, and the Perceptron for Efficient, Feature-rich Parsing. In Proceedings of the 12th Conference on Computational Natural Language Learning, CoNLL’08, pages 9–16. Daniel Cer, Marie-Catherine de Marneffe, Daniel Jurafsky, and Christopher D. Manning. 2010. Parsing to Stanford Dependencies: Trade-offs between speed and accuracy. In Proceedings of the 7th International Conference on Language Resources and Evaluation, LREC’ 10. Jinho D. Choi and Martha Palmer. 2011. Getting the Most out of Transition-based Dependency Parsing. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, ACL:HLT’ 11, pages 687– 692. Jinho D. Choi and Martha Palmer. 2012a. Fast and Robust Part-of-Speech Tagging Using Dynamic Model Selection. In Proceedings of the 50th Annual Meeting ofthe Associationfor Computational Linguistics, ACL’ 12, pages 363–367. Jinho D. Choi and Martha Palmer. 2012b. Guidelines for the Clear Style Constituent to Dependency Conversion. Technical Report 01-12, University of Colorado Boulder. Michael Collins. 2002. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. In Proceedings of the conference on Empirical methods in natural language processing, EMNLP’02, pages 1–8. Marie-Catherine de Marneffe and Christopher D. Manning. 2008. The Stanford typed dependencies representation. In Proceedings of the COLING workshop on Cross-Framework and Cross-Domain Parser Evaluation. 1060 Paramveer S. Dhillon, Jordan Rodu, Michael Collins, Dean P. Foster, and Lyle H. Ungar. 2012. Spectral Dependency Parsing with Latent Variables. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP’ 12, pages 205–213. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. The Journal of Machine Learning Research, 12(39):2121–2159. Daniel Fernández-González and Carlos GómezRodríguez. 2012. Improving Transition-Based Dependency Parsing with Buffer Transitions. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP’ 12, pages 308–319. Yoav Goldberg and Michael Elhadad. 2010. An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT:NAACL’ 10, pages 742–750. Yoav Goldberg and Joakim Nivre. 2012. A Dynamic Oracle for Arc-Eager Dependency Parsing. In Proceedings of the 24th International Conference on Computational Linguistics, COLING’ 12. Johan Hall, Joakim Nivre, and Jens Nilsson. 2006. Discriminative Classifiers for Deterministic Dependency Parsing. In In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, COLING-ACL’06, pages 3 16– 323. Cho-Jui Hsieh, Kai-Wei Chang, Chih-Jen Lin, S. Sathiya Keerthi, and S. Sundararajan. 2008. A Dual Coordinate Descent Method for Large-scale Linear SVM. In Proceedings of the 25th international conference on Machine learning, ICML’08, pages 408–415. Liang Huang and Kenji Sagae. 2010. Dynamic Programming for Linear-Time Incremental Parsing. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL’ 10. Liang Huang, Suphan Fayong, and Yang Guo. 2012. Structured Perceptron with Inexact Search. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT’ 12, pages 142–151. Terry Koo and Michael Collins. 2010. Efficient Thirdorder Dependency Parsers. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL’ 10. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple Semi-supervised Dependency Parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, ACL:HLT’08, pages 595–603. Sandra Kübler, Ryan T. McDonald, and Joakim Nivre. 2009. Dependency Parsing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool Publishers. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics, 19(2):3 13–330. André F. T. Martins, Noah A. Smith, Eric P. Xing, Pe- dro M. Q. Aguiar, and Mário A. T. Figueiredo. 2010. Turbo Parsers: Dependency Parsing by Approximate Variational Inference. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, EMNLP’ 10, pages 34–44. Ryan Mcdonald and Fernando Pereira. 2006. Online Learning ofApproximate Dependency Parsing Algorithms. In Proceedings of the Annual Meeting of the European American Chapter of the Association for Computational Linguistics, EACL’06, pages 81–88. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online Large-Margin Training of Dependency Parsers. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, pages 91–98. Ryan McDonald, Kevin Lerman, and Fernando Pereira. 2006. Multilingual Dependency Analysis with a Two-Stage Discriminative Parser. In Proceedings of the Tenth Conference on Computational Natural Language Learning, CoNLL’06, pages 216–220. Joakim Nivre and Ryan McDonald. 2008. Integrating Graph-based and Transition-based Dependency Parsers. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, ACL:HLT’08, pages 950–958. Joakim Nivre and Jens Nilsson. 2005. PseudoProjective Dependency Parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics, ACL’05, pages 99–106. Joakim Nivre, Johan Hall, Jens Nilsson, Gül s¸en Eryi gˇit, and Svetoslav Marinov. 2006. Labeled pseudoprojective dependency parsing with support vector machines. In Proceedings of the 10th Conference on Computational Natural Language Learning, CoNLL’06, pages 221–225. Joakim Nivre. 2003. An Efficient Algorithm for Projective Dependency Parsing. In Proceedings of the 8th International Workshop on Parsing Technologies, IWPT’03, pages 149–160. 1061 Joakim Nivre. 2004. Incrementality in Deterministic Dependency Parsing. In Proceedings of the ACL’04 Workshop on Incremental Parsing: Bringing Engineering and Cognition Together, pages 50–57. Joakim Nivre. 2006. Inductive Dependency Parsing. Springer. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. Joakim Nivre. 2009. Non-Projective Dependency Parsing in Expected Linear Time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, ACLIJCNLP’09, pages 351–359. Alexander M. Rush and Slav Petrov. 2012. Vine Pruning for Efficient Multi-Pass Dependency Parsing. In Proceedings of the 12th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolo- Yue Zhang and Joakim Nivre. 2011. Transition-based Dependency Parsing with Rich Non-local Features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, ACL’ 11, pages 188–193. gies, NAACL:HLT’ 12. Alexander M. Rush, David Sontag, Michael Collins, and Tommi Jaakkola. 2010. On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, EMNLP’ 10, pages 1–1 1. Kenji Sagae and Alon Lavie. 2006. Parser Combination by Reparsing. In In Proceedings of the Human Language Technology Conference of the NAACL, NAACL’06, pages 129–132. Jun Suzuki, Hideki Isozaki, Xavier Carreras, and Michael Collins. 2009. An Empirical Study of Semi-supervised Structured Conditional Models for Dependency Parsing. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, EMNLP’09, pages 55 1–560. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machine. In Proceedings of the 8th International Workshop on Parsing Technologies, IWPT’03, pages 195– 206. 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 the Conference on Empirical Methods in Natural Language Processing, EMNLP’08, pages 562–571. Hao Zhang and Ryan McDonald. 2012. Generalized Higher-Order Dependency Parsing with Cube Pruning. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP-CoNLL’ 12, pages 320–331. 1062