Efficient Combinatory Categorial Grammar Parsing

Proceedings of the 2006 Australasian Language Technology Workshop (ALTW2006), pages 3–10. Efficient Combinatory Categorial Grammar Parsing Bojan Djordjevic and James R. Curran School of Information Technologies University of Sydney NSW 2006, Australia {bojan,james}@it.usyd.edu.au Abstract Efficient wide-coverage parsing is integral to large-scale NLP applications. Unfortu- nately, parsers for linguistically motivated formalisms, e.g. HPSG and TAG, are often too inefficient for these applications. This paper describes two modifications to the standard CKY chart parsing algo- rithm used in the Clark and Curran (2006) Combinatory Categorial Grammar (CCG) parser. The first modification extends the tight integration of the supertagger and parser, so that individual supertags can be added to the chart, which is then repaired rather than rebuilt. The second modifica- tion adds constraints to the chart that re- strict which constituents can combine. Parsing speed is improved by 30–35% without a significant accuracy penalty and a small increase in coverage when both of these modifications are used. 1 Introduction Parsing is the process of determining the syntactic structure of a sentence. It is an integral part of the deep semantic analysis that any sophisticated Nat- ural Language Processing (NLP) system, such as Question Answering and Information Extraction systems, must perform. The sentences Bob killed Alice, Alice was killed by Bob and Bob was the man who killed Alice convey the same information. If we treat the sentence as a bag or sequence of words by assuming limited structure, the sentences appear to be very differ- ent. These examples demonstrate that full parsing is necessary for accurate semantic interpretation. Further, sophisticated linguistic analysis capable of modelling a wider range of phenomena should give us the most information. Unfortunately, parsing is very inefficient be- cause of the large degree of ambiguity present in natural language. This is particularly true for wide-coverage grammars in linguistically expres- sive formalisms, especially those automatically extracted from a treebank. Many NLP systems use shallow parsing be- cause full parsing is too slow (Grishman, 1997). To improve the approximate structure identified by shallow parsers, many systems use domain- specific knowledge to extract dependencies (Gr- ishman, 1997; Cole et al., 1997). Ciravegna et al. (1997) show that the accuracy can be improved by using a better parser. The ability of NLP systems to extract useful and correct information could there- fore be improved substantially if the speed of full parsing was acceptable. The C&C CCG parser (Clark and Curran, 2006) is the fastest linguistically motivated parser in the literature, but it is still limited to about 25 sen- tences per second on commodity hardware. This paper describes two modifications to the C&C parser that significantly improve parsing ef- ficiency without reducing accuracy or coverage. The first involves chart repair, where the CKY chart is repaired when new categories are added, instead of rebuilt from scratch. This allows an even tighter integration of the parser and supertag- ger (described below) which results in an 11% speed improvement over the original parser. The second modification involves parsing with constraints, that is, requiring certain …

Content truncated to 500 words