Parsing the WSJ Using CCG and Log-Linear Models

Parsing the WSJ using CCG and Log-Linear Models Stephen Clark School of Informatics University of Edinburgh 2 Buccleuch Place, Edinburgh, UK stephen.clark@ed.ac.uk James R. Curran School of Information Technologies University of Sydney NSW 2006, Australia james@it.usyd.edu.au Abstract This paper describes and evaluates log-linear parsing models for Combinatory Categorial Grammar (CCG). A parallel implementation of the L-BFGS optimisation algorithm is described, which runs on a Beowulf cluster allowing the complete Penn Treebank to be used for estima- tion. We also develop a new efficient parsing algorithm for CCG which maximises expected recall of dependencies. We compare models which use all CCG derivations, including non- standard derivations, with normal-form models. The performances of the two models are com- parable and the results are competitive with ex- isting wide-coverage CCG parsers. 1 Introduction A number of statistical parsing models have recently been developed for Combinatory Categorial Gram- mar (CCG; Steedman, 2000) and used in parsers ap- plied to the WSJ Penn Treebank (Clark et al., 2002; Hockenmaier and Steedman, 2002; Hockenmaier, 2003b). In Clark and Curran (2003) we argued for the use of log-linear parsing models for CCG. However, estimating a log-linear model for a wide- coverage CCG grammar is very computationally ex- pensive. Following Miyao and Tsujii (2002), we showed how the estimation can be performed effi- ciently by applying the inside-outside algorithm to a packed chart. We also showed how the complete WSJ Penn Treebank can be used for training by de- veloping a parallel version of Generalised Iterative Scaling (GIS) to perform the estimation. This paper significantly extends our earlier work in a number of ways. First, we evaluate a number of log-linear models, obtaining results which are competitive with the state-of-the-art for CCG pars- ing. We also compare log-linear models which use all CCG derivations, including non-standard deriva- tions, with normal-form models. Second, we find that GIS is unsuitable for estimating a model of the size being considered, and develop a parallel ver- sion of the L-BFGS algorithm (Nocedal and Wright, 1999). And finally, we show that the parsing algo- rithm described in Clark and Curran (2003) is ex- tremely slow in some cases, and suggest an efficient alternative based on Goodman (1996). The development of parsing and estimation algo- rithms for models which use all derivations extends existing CCG parsing techniques, and allows us to test whether there is useful information in the addi- tional derivations. However, we find that the perfor- mance of the normal-form model is at least as good as the all-derivations model, in our experiments to- date. The normal-form approach allows the use of additional constraints on rule applications, leading to a smaller model, reducing the computational re- sources required for estimation, and resulting in an extremely efficient parser. This paper assumes a basic understanding of CCG; see Steedman (2000) for an introduction, and Clark et al. (2002) and Hockenmaier (2003a) for an introduction to statistical parsing with CCG. 2 Parsing Models for CCG CCG is unusual among grammar formalisms in that, for each …

Content truncated to 500 words