Normal-form parsing for Combinatory Categorial Grammars with generalized composition and type-raising

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 465–473, Beijing, August 2010 Normal-form parsing for Combinatory Categorial Grammars with generalized composition and type-raising Julia Hockenmaier Yonatan Bisk University of Illinois at Urbana-Champaign {juliahmr, bisk1}@illinois.edu Abstract We propose and implement a modifica- tion of the Eisner (1996) normal form to account for generalized composition of bounded degree, and an extension to deal with grammatical type-raising. 1 Introduction Combinatory Categorial Grammar (Steedman, 2000) is a linguistically expressive grammar for- malism that has been used for many NLP appli- cations, including wide-coverage parsing (Clark and Curran, 2007; Hockenmaier, 2003) and se- mantic interpretation (Curran et al., 2007), se- mantic role-labeling (Gildea and Hockenmaier, 2003; Boxwell et al., 2009), semantic parsing (Zettlemoyer and Collins, 2005) and natural lan- guage generation (Espinosa et al., 2008). An essential feature of CCG is its flexible constituent structure, licensed by type-raising and composition rules which can create “non- standard” constituents such as “John saw”, or “Mary talked to”, required in constructions in- volving non-local dependencies, such as wh- extraction (Fig. 1) or right-node raising. Since “John saw” can now also be a constituent in “John saw Mary”, this leads to a combinato- rial explosion of spurious ambiguities, i.e. mul- tiple syntactic derivations of the same seman- tic interpretation (Wittenburg, 1986). This can create problems for applications based on CCG, e.g. for the induction of stochastic CCGs from text annotated with logical forms (Zettlemoyer and Collins, 2007), where spreading probabil- ity mass over equivalent derivations should be avoided. A number of normal-form (NF) parsing algorithms that aim to produce only one deriva- tion per interpretation have been proposed (Wit- tenburg, 1986; Niv, 1994; Pareschi and Steed- man, 1987; Hepple and Morrill, 1989; Eis- ner, 1996). Computationally, such algorithms are very attractive since they do not require costly semantic equivalence checks (Karttunen, 1989; Komagata, 2004) during parsing. Eis- ner’s (1996) normal form is the most devel- oped and well-known of these approaches, but is only defined for a variant of CCG where type-raising is a lexical operation and where the degree of composition is unbounded. There- fore, it and its equivalent reformulation by Hoyt and Baldridge (2008) in a multimodal variant of CCG are not safe (preserve all interpretations) and complete (remove all spurious ambiguities) for more commonly used variants of CCG. In particular, this NF is not safe when the degree of composition is bounded,1 and not complete when type-raising is a grammatical operation. This paper defines a NF for CCG with bounded composition and grammatical type-raising. 2 Combinatory Categorial Grammar In CCG, every constituent (“John saw”) has a syntactic category (S/NP) and a semantic in- terpretation (λx.saw(john′, x)).2 Constituents combine according to a small set of language- 1Although Eisner (1996, section 5) also provides a safe and complete parsing algorithm which can return non-NF derivations when necessary to preseve an interpretation if composition is bounded or the grammar is restricted in other (arbitrary) ways. 2More complex representations than simple predicate- argument structures are equally …

Content truncated to 500 words