emnlp emnlp2011 emnlp2011-134 emnlp2011-134-reference knowledge-graph by maker-knowledge-mining

134 emnlp-2011-Third-order Variational Reranking on Packed-Shared Dependency Forests


Source: pdf

Author: Katsuhiko Hayashi ; Taro Watanabe ; Masayuki Asahara ; Yuji Matsumoto

Abstract: We propose a novel forest reranking algorithm for discriminative dependency parsing based on a variant of Eisner’s generative model. In our framework, we define two kinds of generative model for reranking. One is learned from training data offline and the other from a forest generated by a baseline parser on the fly. The final prediction in the reranking stage is performed using linear interpolation of these models and discriminative model. In order to efficiently train the model from and decode on a hypergraph data structure representing a forest, we apply extended inside/outside and Viterbi algorithms. Experimental results show that our proposed forest reranking algorithm achieves significant improvement when compared with conventional approaches.


reference text

X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proc. the CoNLLEMNLP, pages 957–961. E. Charniak and M. Johnson. 2005. Coarse-to-fine nbest parsing and maxent discriminative reranking. In Proc. the 43rd ACL, pages 173–180. D. Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33:201–228. M. Collins. 2000. Discriminative reranking for natural language parsing. In Proc. the ICML. J. M. Eisner. 1996a. An empirical comparison of prob- ability models for dependency grammar. In Technical Report, pages 1–18. J. M. Eisner. 1996b. Three new probabilistic models for dependency parsing: An exploration. In Proc. the 16th COLING, pages 340–345. Y. Goldberg and M. Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency parsing. In Proc. the HLT-NAACL, pages 742–750. L. Huang and D. Chiang. 2005. Better k-best parsing. In Proc. the IWPT, pages 53–64. L. Huang and K. Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proc. the ACL, pages 1077–1086. L. Huang. 2006. Dynamic programming algorithms in semiring and hypergraph frameworks. Qualification Exam Report, pages 1–19. http://www.cis.upenn.edu/ lhuang3/wpe2/. L. Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proc. the 46th ACL, pages 586–594. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. the 48th ACL, pages 1–1 1. T. Koo, X. Carreras, and M. Collins. 2008. Simple semisupervised dependency parsing. In Proc. the ACL, pages 595–603. S. Kumar, W. Macherey, C. Dyer, and F. Och. 2009. Efficient minimum error rate training and minimum bayesrisk decoding for translation hypergraphs and lattices. In Proc. the 47th ACL, pages 163–171 . Z. Li, J. Eisner, and S. Khudanpur. 2009. Variational decoding for statistical machine translation. In Proc. the 47th ACL, pages 593–601. T. Matsuzaki, Y. Miyao, and J. Tsujii. 2005. Probabilistic cfg with latent annotations. In Proc. the ACL, pages 75–82. R. McDonald and F. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. EACL, pages 81–88. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. the 43rd ACL, pages 91–98. 1488 H. Mi and L. Huang. 2008. Forest-based translation rule extraction. In Proceedings of EMNLP, pages 206– 214. M. Mohri. 2002. Semiring framework and algorithms for shortest-distance problems. Automata, Languages and Combinatorics, 7:321–350. F. J. Och. 2003. Minimum error rate training in statistical machine translation. In Proc. the 41st ACL, pages 160–167. F. Sangati, W. Zuidema, and R. Bod. 2009. A generative re-ranking model for dependency parsing. In Proc. the 11th IWPT, pages 238–241. J. Suzuki, H. Isozaki, X. Carreras, and M. Collins. 2009. An empirical study of semi-supervised structured con- ditional models for dependency parsing. In Proc. the EMNLP, pages 551–560. I. Titov and J. Henderson. 2006. Bayes risk minimization in natural language parsing. In Technical Report, pages 1–9. Z. Tu, Y. Liu, Y. Hwang, Q. Liu, and S. Lin. 2010. Dependency forest for statistical machine translation. In Proc. the 23rd COLING, pages 1092–1 100. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. the IWPT, pages 195–206.