acl acl2013 acl2013-362 acl2013-362-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Andre Martins ; Miguel Almeida ; Noah A. Smith
Abstract: We present fast, accurate, direct nonprojective dependency parsers with thirdorder features. Our approach uses AD3, an accelerated dual decomposition algorithm which we extend to handle specialized head automata and sequential head bigram models. Experiments in fourteen languages yield parsing speeds competitive to projective parsers, with state-ofthe-art accuracies for the largest datasets (English, Czech, and German).
S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In International Conference on Natural Language Learning. X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In International Conference on Natural Language Learning. Y. J. Chu and T. H. Liu. 1965. On the shortest arbores- cence of a directed graph. Science Sinica, 14: 1396– 1400. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585. J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233–240. J. M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. of International Conference on Computational Linguistics, pages 340–345. H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan. 1986. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2): 109–122. 621 L. Huang and K. Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proc. of Annual Meeting of the Association for Computational Linguistics, pages 1077–1086. N. Komodakis, N. Paragios, and G. Tziritas. 2007. MRF optimization via dual decomposition: Message-passing revisited. In Proc. of International Conference on Computer Vision. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of Annual Meeting of the Association for Computational Linguistics, pages 1– 11. T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and D. Sontag. 2010. Dual decomposition for parsing with non-projective head automata. In Proc. of Empirical Methods for Natural Language Processing. S. K ¨ubler, R. McDonald, and J. Nivre. 2009. Dependency parsing. Morgan & Claypool Publishers. A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proc. of Annual Meeting of the Association for Computational Linguistics. A. F. T. Martins, N. A. Smith, E. P. Xing, M. A. T. Figueiredo, and P. M. Q. Aguiar. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Proc. of Empirical Methods for Natural Language Processing. A. F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and M. A. T. Figueiredo. 2011. Dual decomposition with many overlapping components. In Proc. of Empirical Methods for Natural Language Processing. A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar, N. A. Smith, and E. P. Xing. 2012. Alternating directions dual decomposition. Arxiv preprint arXiv: 1212.6550. R. T. McDonald and F. C. N. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. of Annual Meeting of the European Chapter of the Association for Computational Linguistics. R. McDonald and G. Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proc. of International Conference on Parsing Technologies. R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of Empirical Methods for Natural Language Processing. R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage dis- criminative parser. In Proc. of International Conference on Natural Language Learning. J. Nivre, J. Hall, J. Nilsson, G. Eryi gˇit, and S. Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Procs. of International Conference on Natural Language Learning. J. Nocedal and S. J. Wright. mization. Springer-Verlag. 1999. Numerical opti- Alexander M Rush and Slav Petrov. 2012. Vine pruning for efficient multi-pass dependency parsing. In Proc. of Conference of the North American Chapter of the Association for Computational Linguistics. A. Rush, D. Sontag, M. Collins, and T. Jaakkola. 2010. On dual decomposition and linear programming relaxations for natural language processing. In Proc. of Empirical Methods for Natural Language Processing. D. Smith and J. Eisner. 2008. Dependency parsing by belief propagation. In Proc. of Empirical Methods for Natural Language Processing. M. Surdeanu, R. Johansson, A. Meyers, L. M `arquez, and J. Nivre. 2008. The CoNLL-2008 shared task on joint parsing of syntactic and semantic dependencies. Proc. of International Conference on Natural Language Learning. R.E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25–36. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of International Conference on Parsing Technologies. H. Zhang and R. McDonald. 2012. Generalized higher-order dependency parsing with cube pruning. In Proc. of Empirical Methods in Natural Language Processing. Y. Zhang and J. Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proc. of the Annual Meeting of the Association for Computational Linguistics. 622