Log-Linear Models for Wide-Coverage CCG Parsing

Log-Linear Models for Wide-Coverage CCG Parsing Stephen Clark and James R. Curran School of Informatics University of Edinburgh 2 Buccleuch Place, Edinburgh. EH8 9LW fstephenc,jamesc g@cogsci.ed.ac.uk Abstract This paper describes log-linear pars- ing models for Combinatory Categorial Grammar (CCG). Log-linear models can easily encode the long-range dependen- cies inherent in coordination and extrac- tion phenomena, which CCG was designed to handle. Log-linear models have pre- viously been applied to statistical pars- ing, under the assumption that all possible parses for a sentence can be enumerated. Enumerating all parses is infeasible for large grammars; however, dynamic pro- gramming over a packed chart can be used to efficiently estimate the model parame- ters. We describe a parellelised implemen- tation which runs on a Beowulf cluster and allows the complete WSJ Penn Treebank to be used for estimation. 1 Introduction Statistical parsing models have recently been de- veloped for Combinatory Categorial Grammar (CCG, Steedman (2000)) and used in wide-coverage parsers applied to the WSJ Penn Treebank (Clark et al., 2002; Hockenmaier and Steedman, 2002). An attraction of CCG is its elegant treatment of coor- dination and extraction, allowing recovery of the long-range dependencies inherent in these construc- tions. We would like the parsing model to include long-range dependencies, but this introduces prob- lems for generative parsing models similar to those described by Abney (1997) for attribute-value gram- mars; hence Hockenmaier and Steedman do not in- clude such dependencies in their model, and Clark et al. include the dependencies but use an incon- sistent model. Following Abney, we propose a log- linear framework which incorporates long-range de- pendencies as features without loss of consistency. Log-linear models have previously been ap- plied to statistical parsing (Johnson et al., 1999; Toutanova et al., 2002; Riezler et al., 2002; Os- borne, 2000). Typically, these approaches have enu- merated all possible parses for model estimation and finding the most probable parse. For gram- mars extracted from the Penn Treebank (in our case CCGbank (Hockenmaier, 2003)), enumerating all parses is infeasible. One approach to this prob- lem is to sample the parse space for estimation, e.g. Osborne (2000). In this paper we use a dynamic pro- gramming technique applied to a packed chart, simi- lar to those proposed by Geman and Johnson (2002) and Miyao and Tsujii (2002), which efficiently esti- mates the model parameters over the complete space without enumerating parses. The estimation method is similar to the inside-outside algorithm used for es- timating a PCFG (Lari and Young, 1990). Miyao and Tsujii (2002) apply their estimation technique to an automatically extracted Tree Adjoin- ing Grammar using Improved Iterative Scaling (IIS, Della Pietra et al. (1997)). However, their model has significant memory requirements which limits them to using 868 sentences as training data. We use a parallelised version of Generalised Iterative Scal- ing (GIS, Darroch and Ratcliff (1972)) on a Beowulf cluster which allows the complete WSJ Penn Tree- bank to be used as training data. This paper assumes a basic knowledge of CCG; see Steedman (2000) and …

Content truncated to 500 words