Efficient CCG Parsing: A* versus Adaptive Supertagging

Michael Auli, Adam Lopez

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a systematic comparison and combination of two orthogonal techniques for efficient parsing of Combinatory Categorial Grammar (CCG). First we consider adaptive supertagging, a widely used approximate search technique that prunes most lexical categories from the parser’s search space using a separate sequence model. Next we consider several variants on A*, a classic exact search technique which to our knowledge has not been applied to more expressive grammar formalisms like CCG. In addition to standard hardware-independent measures of parser effort we also present what we believe is the first evaluation of A* parsing on the more realistic but more stringent metric of CPU time. By itself, A* substantially reduces parser effort as measured by the number of edges considered during parsing, but we show that for CCG this
does not always correspond to improvements in CPU time over a CKY baseline. Combining A* with adaptive supertagging decreases CPU time by 15% for our best model.
Original languageEnglish
Title of host publicationProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies
Place of PublicationPortland, Oregon, USA
PublisherAssociation for Computational Linguistics
Number of pages9
Publication statusPublished - 1 Jun 2011

Fingerprint Dive into the research topics of 'Efficient CCG Parsing: A* versus Adaptive Supertagging'. Together they form a unique fingerprint.

Cite this