Accurate Context-Free Parsing with Combinatory Categorial Grammar

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 335–344, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Accurate Context-Free Parsing with Combinatory Categorial Grammar Timothy A. D. Fowler and Gerald Penn Department of Computer Science, University of Toronto Toronto, ON, M5S 3G4, Canada {tfowler, gpenn}@cs.toronto.edu Abstract The definition of combinatory categorial grammar (CCG) in the literature varies quite a bit from author to author. How- ever, the differences between the defini- tions are important in terms of the lan- guage classes of each CCG. We prove that a wide range of CCGs are strongly context-free, including the CCG of CCG- bank and of the parser of Clark and Cur- ran (2007). In light of these new results, we train the PCFG parser of Petrov and Klein (2007) on CCGbank and achieve state of the art results in supertagging ac- curacy, PARSEVAL measures and depen- dency accuracy. 1 Introduction Combinatory categorial grammar (CCG) is a vari- ant of categorial grammar which has attracted in- terest for both theoretical and practical reasons. On the theoretical side, we know that it is mildly context-sensitive (Vijay-Shanker and Weir, 1994) and that it can elegantly analyze a wide range of linguistic phenomena (Steedman, 2000). On the practical side, we have corpora with CCG deriva- tions for each sentence (Hockenmaier and Steed- man, 2007), a wide-coverage parser trained on that corpus (Clark and Curran, 2007) and a system for converting CCG derivations into semantic repre- sentations (Bos et al., 2004). However, despite being treated as a single uni- fied grammar formalism, each of these authors use variations of CCG which differ primarily on which combinators are included in the grammar and the restrictions that are put on them. These differences are important because they affect whether the mild context-sensitivity proof of Vijay-Shanker and Weir (1994) applies. We will provide a gen- eralized framework for CCG within which the full variation of CCG seen in the literature can be de- fined. Then, we prove that for a wide range of CCGs there is a context-free grammar (CFG) that has exactly the same derivations. Included in this class of strongly context-free CCGs are a grammar including all the derivations in CCGbank and the grammar used in the Clark and Curran parser. Due to this insight, we investigate the potential of using tools from the probabilistic CFG com- munity to improve CCG parsing results. The Petrov parser (Petrov and Klein, 2007) uses la- tent variables to refine the grammar extracted from a corpus to improve accuracy, originally used to improve parsing results on the Penn treebank (PTB). We train the Petrov parser on CCGbank and achieve the best results to date on sentences from section 23 in terms of supertagging accuracy, PARSEVAL measures and dependency accuracy. These results should not be interpreted as proof that grammars extracted from the Penn treebank and from CCGbank are equivalent. Bos’s system for building semantic representations from CCG derivations is only possible due to the categorial …

Content truncated to 500 words