acl acl2010 acl2010-99 acl2010-99-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Terry Koo ; Michael Collins
Abstract: We present algorithms for higher-order dependency parsing that are “third-order” in the sense that they can evaluate substructures containing three dependencies, and “efficient” in the sense that they require only O(n4) time. Importantly, our new parsers can utilize both sibling-style and grandchild-style interactions. We evaluate our parsers on the Penn Treebank and Prague Dependency Treebank, achieving unlabeled attachment scores of 93.04% and 87.38%, respectively.
Giuseppe Attardi. 2006. Experiments with a Multilanguage Non-Projective Dependency Parser. In Proceedings of the 10th CoNLL, pages 166–170. Asso- ciation for Computational Linguistics. James Baker. 1979. Trainable Grammars for Speech Recognition. In Proceedings of the 97th meeting of the Acoustical Society of America. Xavier Carreras, Michael Collins, and Terry Koo. 2008. TAG, Dynamic Programming, and the Perceptron for Efficient, Feature-rich Parsing. In Proceedings of the 12th CoNLL, pages 9–16. Association for Computational Linguistics. Xavier Carreras. 2007. Experiments with a HigherOrder Projective Dependency Parser. In Proceedings of the CoNLL Shared Task Session of EMNLPCoNLL, pages 957–961. Association for Computational Linguistics. Eugene Charniak and Mark Johnson. 2005. Coarseto-fine N-best Parsing and MaxEnt Discriminative Reranking. In Proceedings of the 43rd ACL. Y.J. Chu and T.H. Liu. 1965. On the Shortest Arborescence of a Directed Graph. Science Sinica, 14: 1396–1400. John Cocke and Jacob T. Schwartz. 1970. Programming Languages and Their Compilers: Preliminary Notes. Technical report, New York University. Michael Collins, Amir Globerson, Terry Koo, Xavier Carreras, and Peter L. Bartlett. 2008. Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks. Journal of Machine Learning Research, 9: 1775–1822, Aug. Michael Collins. 2002. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. In Proceedings of the 7th EMNLP, pages 1–8. Association for Computational Linguistics. Jack R. Edmonds. 1967. Optimum Branchings. Journal of Research of the National Bureau of Standards, 71B:233–240. Jason Eisner. 1996. Three New Probabilistic Models for Dependency Parsing: An Exploration. In Proceedings of the 16th COLING, pages 340–345. Association for Computational Linguistics. Jason Eisner. 2000. Bilexical Grammars and Their Cubic-Time Parsing Algorithms. In Harry Bunt and Anton Nijholt, editors, Advances in Probabilistic and Other Parsing Technologies, pages 29–62. Kluwer Academic Publishers. Yoav Freund and Robert E. Schapire. 1999. Large Margin Classification Using the Perceptron Algo- rithm. Machine Learning, 37(3):277–296. Jan Haji cˇ, Eva Haji cˇov a´, Petr Pajas, Jarmila Panevova, and Petr Sgall. 2001 . The Prague Dependency Treebank 1.0, LDC No. LDC2001T10. Linguistics Data Consortium. Jan Haji cˇ. 1998. Building a Syntactically Annotated Corpus: The Prague Dependency Treebank. In Eva Haji cˇov a´, editor, Issues of Valency and Meaning. Studies in Honor of Jarmila Panevov a´, pages 12–19. Mark Johnson. 1998. PCFG Models of Linguistic Tree Representations. Computational Linguistics, 24(4):613–632. Tadao Kasami. 1965. An Efficient Recognition and Syntax-analysis Algorithm for Context-free Languages. Technical Report AFCRL-65-758, Air Force Cambridge Research Lab. Terry Koo, Amir Globerson, Xavier Carreras, and Michael Collins. 2007. Structured Prediction Models via the Matrix-Tree Theorem. In Proceedings of EMNLP-CoNLL, pages 141–150. Association for Computational Linguistics. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple Semi-supervised Dependency Pars- ing. In Proceedings of the 46th ACL, pages 595–603. Association for Computational Linguistics. Terry Koo. 2010. Advances in Discriminative Dependency Parsing. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, June. John Lafferty, Andrew McCallum, and Fernando Pereira. 2001 . Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proceedings of the 18th ICML, pages 282–289. Morgan Kaufmann. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics, 19(2):3 13–330. David A. McAllester. 1999. On the Complexity Analysis of Static Analyses. In Proceedings of the 6th Static Analysis Symposium, pages 3 12–329. Springer-Verlag. Ryan McDonald and Joakim Nivre. 2007. Characterizing the Errors ofData-Driven Dependency Parsers. In Proceedings of EMNLP-CoNLL, pages 122–13 1. Association for Computational Linguistics. Ryan McDonald and Fernando Pereira. 2006. Online Learning of Approximate Dependency Parsing Algorithms. In Proceedings of the 11th EACL, pages 81–88. Association for Computational Linguistics. Ryan McDonald and Giorgio Satta. 2007. On the Complexity of Non-Projective Data-Driven Dependency Parsing. In Proceedings of IWPT. 10 Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online Large-Margin Training of Dependency Parsers. In Proceedings of the 43rd ACL, pages 91–98. Association for Computational Linguistics. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Haji cˇ. 2005b. Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of HLT-EMNLP, pages 523–530. Association for Computational Linguistics. Ryan McDonald. 2006. Discriminative Training and Spanning Tree Algorithms for Dependency Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA, USA, July. Joakim Nivre, Johan Hall, Jens Nilsson, G ¨ul s¸en Eryi gˇit, and Svetoslav Marinov. 2006. Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines. In Proceedings of the 10th CoNLL, pages 221–225. Association for Computational Linguistics. Slav Petrov and Dan Klein. 2007. Improved Inference for Unlexicalized Parsing. In Proceedings of HLTNAACL, pages 404–41 1. Association for Computational Linguistics. Adwait Ratnaparkhi. 1996. A Maximum Entropy Model for Part-Of-Speech Tagging. In Proceedings of the 1st EMNLP, pages 133–142. Association for Computational Linguistics. Libin Shen, Jinxi Xu, and Ralph Weischedel. 2008. A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model. In Proceedings of the 46th ACL, pages 577– 585. Association for Computational Linguistics. David A. Smith and Noah A. Smith. 2007. Probabilistic Models of Nonprojective Dependency Trees. In Proceedings of EMNLP-CoNLL, pages 132–140. Association for Computational Linguistics. 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 EMNLP, pages 551–560. Association for Computational Linguistics. Ben Taskar, Carlos Guestrin, and Daphne Koller. 2003. Max margin markov networks. In Sebastian Thrun, Lawrence K. Saul, and Bernhard Sch o¨lkopf, editors, NIPS. MIT Press. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical Dependency Analysis with Support Vector Machines. In Proceedings of the 8th IWPT, pages 195– 206. Association for Computational Linguistics. David H. Younger. 1967. Recognition and parsing of context-free languages in time n3. Information and Control, 10(2): 189–208. 11