acl acl2011 acl2011-282 acl2011-282-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yue Zhang ; Stephen Clark
Abstract: CCGs are directly compatible with binarybranching bottom-up parsing algorithms, in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG, the shift-reduce method has been little explored. In this paper, we develop a shift-reduce CCG parser using a discriminative model and beam search, and compare its strengths and weaknesses with the chart-based C&C; parser. We study different errors made by the two parsers, and show that the shift-reduce parser gives competitive accuracies compared to C&C.; Considering our use of a small beam, and given the high ambiguity levels in an automatically-extracted grammar and the amount of information in the CCG lexical categories which form the shift actions, this is a surprising result.
A. E. Ades and M. Steedman. 1982. On the order of words. Linguistics and Philosophy, pages 5 17 558. Johan Bos, Stephen Clark, Mark Steedman, James R. Curran, and Julia Hockenmaier. 2004. Wide-coverage semantic representations from a CCG parser. In Proceedings of COLING-04, pages 1240–1246, Geneva, Switzerland. Stephen Clark and James R. Curran. 2007. Widecoverage efficient statistical parsing with CCG and log-linear models. Computational Linguistics, 33(4):493–552. Stephen Clark and James R. Curran. 2009. Comparing the accuracy of CCG and Penn Treebank parsers. In Proceedings of ACL-2009 (short papers), pages 53– 56, Singapore. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 111–1 18, Barcelona, Spain. Michael Collins. 2002. Discriminative training meth– ods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP, pages 1–8, Philadelphia, USA. Jenny Rose Finkel, Alex Kleeman, and Christopher D. Manning. 2008. Feature-based, conditional random field parsing. In Proceedings of the 46th Meeting of the ACL, pages 959–967, Columbus, Ohio. Timothy A. D. Fowler and Gerald Penn. 2010. Accurate context-free parsing with Combinatory Categorial Grammar. In Proceedings of ACL-2010, Uppsala, Sweden. H. Hassan, K. Sima’an, and A. Way. 2008. A syntactic language model based on incremental CCG parsing. In Proceedings of the Second IEEE Spoken Language Technology Workshop, Goa, India. Julia Hockenmaier and Mark Steedman. 2007. CCGbank: A corpus of CCG derivations and dependency structures extracted from the Penn Treebank. Computational Linguistics, 33(3):355–396. Julia Hockenmaier. 2003. Data and Models for Statistical Parsing with Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh. Liang Huang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In Proceedings of the 2009 EMNLP Conference, pages 1222–123 1, Singapore. Richard Johansson and Pierre Nugues. 2007. Incre- mental dependency parsing using online learning. In Proceedings of the CoNLL/EMNLP Conference, pages 1134–1 138, Prague, Czech Republic. Takuya Matsuzaki, Yusuke Miyao, and Jun ichi Tsujii. 2007. Efficient HPSG parsing with supertagging and CFG-filtering. In Proceedings of IJCAI-07, pages 1671–1676, Hyderabad, India. Ryan McDonald and Joakim Nivre. 2007. Characterizing the errors of data-driven dependency parsing models. In Proceedings of EMNLP/CoNLL, pages 122– 13 1, Prague, Czech Republic. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of the 43rd Meeting of the ACL, pages 91–98, Michigan, Ann Arbor. Yusuke Miyao and Jun’ichi Tsujii. 2005. Probabilistic disambiguation models for wide-coverage HPSG parsing. In Proceedings of the 43rd meeting of the ACL, pages 83–90, University of Michigan, Ann Arbor. Takashi Ninomiya, Takuya Matsuzaki, Nobuyuki Shimizu, and Hiroshi Nakagawa. 2009. Deterministic shift-reduce parsing for unification-based grammars by using default unification. In Proceedings of EACL-09, pages 603–61 1, Athens, Greece. Takashi Ninomiya, Takuya Matsuzaki, Nobuyuki Shimizu, and Hiroshi Nakagawa. 2010. Deterministic shift-reduce parsing for unification-based grammars. Journal of Natural Language Engineering, DOI: 10.1017/S1351324910000240. J. Nivre and M. Scholz. 2004. Deterministic dependency parsing of English text. In Proceedings of COLING04, pages 64–70, Geneva, Switzerland. Joakim Nivre, Johan Hall, Jens Nilsson, G ¨ul s¸en Eryi gˇit, and Svetoslav Marinov. 2006. Labeled pseudoprojective dependency parsing with support vector machines. In Proceedings of CoNLL, pages 221–225, New York, USA. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Proceedings of HLT/NAACL, pages 404–41 1, Rochester, New York, April. Stefan Riezler, Tracy H. King, Ronald M. Kaplan, Richard Crouch, John T. Maxwell III, and Mark Johnson. 2002. Parsing the Wall Street Journal using a Lexical-Functional Grammar and discriminative estimation techniques. In Proceedings of the 40th Meeting of the ACL, pages 271–278, Philadelphia, PA. Laura Rimell, Stephen Clark, and Mark Steedman. 2009. Unbounded dependency recovery for parser evaluation. In Proceedings of EMNLP-09, pages 8 13–821, Singapore. 692 Kenji Sagae and Alon Lavie. 2005. A classifier-based parser with linear run-time complexity. In Proceedings of IWPT, pages 125–132, Vancouver, Canada. Kenji Sagae and Alon Lavie. 2006a. A best-first probabilistic shift-reduce parser. In Proceedings of COLING/ACL poster session, pages 691–698, Sydney, Australia, July. Kenji Sagae and Alon Lavie. 2006b. Parser combination by reparsing. In Proceedings of HLT/NAACL, Companion Volume: Short Papers, pages 129–132, New York, USA. Mark Steedman. 2000. The Syntactic Process. The MIT Press, Cambridge, Mass. David Weir. 1988. Characterizing Mildly ContextSensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylviania. Michael White and Rajakrishnan Rajkumar. 2009. Perceptron reranking for CCG realization. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 410–419, Singapore. H Yamada and Y Matsumoto. 2003. Statistical dependency analysis using support vector machines. In Proceedings of IWPT, Nancy, France. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beamsearch. In Proceedings of EMNLP-08, Hawaii, USA. Yue Zhang and Stephen Clark. 2009. Transition-based parsing of the Chinese Treebank using a global discriminative model. In Proceedings of IWPT, Paris, France, October. Yi Zhang, Valia Kordoni, and Erin Fitzgerald. 2007. Partial parse selection for robust deep processing. In Proceedings of the ACL 2007 Workshop on Deep Linguistic Processing, Prague, Czech Republic.