emnlp emnlp2012 emnlp2012-57 emnlp2012-57-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hao Zhang ; Ryan McDonald
Abstract: State-of-the-art graph-based parsers use features over higher-order dependencies that rely on decoding algorithms that are slow and difficult to generalize. On the other hand, transition-based dependency parsers can easily utilize such features without increasing the linear complexity of the shift-reduce system beyond a constant. In this paper, we attempt to address this imbalance for graph-based parsing by generalizing the Eisner (1996) algorithm to handle arbitrary features over higherorder dependencies. The generalization is at the cost of asymptotic efficiency. To account for this, cube pruning for decoding is utilized (Chiang, 2007). For the first time, label tuple and structural features such as valencies can be scored efficiently with third-order features in a graph-based parser. Our parser achieves the state-of-art unlabeled accuracy of 93.06% and labeled accuracy of 91.86% on the standard test set for English, at a faster speed than a reimplementation ofthe third-ordermodel of Koo et al. (2010).
N. Bodenstab, A. Dunlop, K. Hall, and B. Roark. 2011. Beam-width prediction for efficient context-free parsing. In Proc. ACL. S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proc. of CoNLL. X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proc. of the CoNLL Shared Task Session of EMNLP-CoNLL. E. Charniak and M. Johnson. 2005. Coarse-to-fine nbest parsing and maxent discriminative reranking. In Proc. ACL. D. Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2). K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research. M. De Marneffe, B. MacCartney, and C.D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proc. of LREC. X. Duan, J. Zhao, and B. Xu. 2007. Probabilistic parsing action models for multi-lingual dependency parsing. In Proc. of EMNLP-CoNLL. J. Eisner. 1996. Three new probabilistic models for dependency parsing: an exploration. In Proc. of COLING. K. Gimpel and N.A. Smith. 2009. Cube summing, approximate inference with non-local features, and dynamic programming without semirings. In Proc. EACL. C. G ´omez-Rodr ı´guez, M. Kuhlmann, G. Satta, and D. Weir. 2009. Optimal reduction ofrule length in linear context-free rewriting systems. In Proc. NAACL. C. G ´omez-Rodr ı´guez, M. Kuhlmann, and G. Satta. 2010. Efficient parsing of well-nested linear context-free rewriting systems. In Proc. NAACL. K. Hall. 2007. K-best spanning tree parsing. In Proc. of ACL. L. Huang and S. Fayong. 2012. Structured perceptron with inexact search. In Proc. of NAACL. L. Huang and K. Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proc. of ACL. L. Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proc. of ACL. R. Johansson and P. Nugues. 2007. Incremental dependency parsing using online learning. In Proc. of EMNLP-CoNLL. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of ACL. T. Koo, A. Rush, M. Collins, T. Jaakkola, and D. Son- tag. 2010. Dual decomposition for parsing with nonprojective head automata. In Proc. of EMNLP. 330 M. Kuhlmann and G. Satta. 2009. Treebank grammar techniques for non-projective dependency parsing. In Proc. EACL. A. F. T. Martins, N. Smith, and E. P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proc. of ACL. A. F. T. Martins, N. Smith, E. P. Xing, P. M. Q. Aguiar, and M. A. T. Figueiredo. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Proc. of EMNLP. A. F. T. Martins, N. Smith, M. A. T. Figueiredo, and P. M. Q. Aguiar. 2011. Dual decomposition with many overlapping components. In Proc of EMNLP. R. McDonald and J. Nivre. 2007. Characterizing the errors of data-driven dependency parsing models. In Proc. of EMNLP-CoNLL. R. McDonald and F. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. of EACL. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. of ACL. T. Nakagawa. 2007. Multilingual dependency parsing using global features. In Proc. of EMNLP-CoNLL. J. Nivre and R. McDonald. 2008. Integrating graphbased and transition-based dependency parsers. In Proc. of ACL. J. Nivre, J. Hall, S. K ¨ubler, R. McDonald, J. Nilsson, S. Riedel, and D. Yuret. 2007. The CoNLL 2007 shared task on dependency parsing. In Proc. of EMNLP-CoNLL. S. Petrov and D. Klein. 2007. Improved inference for unlexicalized parsing. In Proc. NAACL. S. Riedel and J. Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. of EMNLP. B. Roark and K. Hollingshead. 2008. Classifying chart cells for quadratic complexity context-free inference. In Proc. COLING. B. Roark and K. Hollingshead. 2009. Linear complexity context-free parsing pipelines via chart constraints. In Proce. NAACL. A. Rush and S. Petrov. 2012. Efficient multi-pass dependency pruning with vine parsing. In Proc. of NAACL. D. Smith and J. Eisner. 2008. Dependency parsing by belief propagation. In Proc. of EMNLP. I. Titov and J. Henderson. 2007. Fast and robust multilingual dependency parsing with a generative latent variable model. In Proc. of EMNLP-CoNLL. D. Weiss and B. Taskar. 2010. Structured prediction cas- cades. In Proc. of AISTATS. Y. Zhang and S. Clark. 2008. A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing. In Proc. of EMNLP. Y. Zhang and J. Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proc. of ACL-HLT, volume 2. 331