Constraining robust constructions for broad-coverage parsing with precision grammars

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 223–231, Beijing, August 2010 Constraining robust constructions for broad-coverage parsing with precision grammars Bart Cramer† and Yi Zhang†‡ Department of Computational Linguistics & Phonetics, Saarland University† LT-Lab, German Research Center for Artificial Intelligence (DFKI)‡ {bcramer,yzhang}@coli.uni-saarland.de Abstract This paper addresses two problems that commonly arise in parsing with precision- oriented, rule-based models of grammar: lack of speed and lack of robustness. First, we show how we can reduce parsing times by restricting the number of tasks the parser will carry out, based on a gener- ative model of rule applications. Sec- ond, we show that a combination of search space restriction and radically overgen- erating robustness rules lead to a more robust parser, with only a small penalty in precision. Applying both the robust- ness rules and a fragment fallback strat- egy showed better recall than just giving fragment analyses, with equal precision. Results are reported on a medium-sized HPSG grammar for German. 1 1 Introduction In the field of natural language processing, it is common wisdom that handwritten, rule-based models generally perform poorly on complex problems, mainly due to the knowledge acquisi- tion bottleneck: it is hard for the human modeller to conceive of all possible scenarios the model has to cope with. In parsing, many approaches have relied on hand-written grammars, and their fragility is one of their largest weaknesses. Such models can fail due to insufficiency of lexical en- tries or grammatical constructions, but also due 1The research reported on in this paper has been carried out with financial support from the Deutsche Forschungs- gemeinschaft and the German Excellence Cluster of Multi- modal Computing & Interaction. to creative or ungrammatical input. In any case, the parser should always return a reasonable out- put. A very simple technique is partial or fragment parsing (Kiefer et al., 1999; Riezler et al., 2001; Zhang et al., 2007a): if there is no item in the chart that both spans the complete sentence and fulfills the root condition, several chunks that do conform to a root condition are combined by minimising a certain cost function (for instance to favour larger chunks, or more probable chunks). A second problem with deep parsers is their rel- atively low efficiency. For online applications, it is impermissible to wait for longer than a minute be- fore the system responds. Apart from studies that were aimed at increasing the efficiency of deep parsers by using smarter algorithms (e.g. using left-corner relations (Van Noord, 1997)), several studies in recent years have suggested that search space restriction can offer a beneficial balance be- tween speed and accuracy as well. Techniques that have been proposed are, among others, su- pertagging (Clark and Curran, 2007), CFG filter- ing (Matsuzaki et al., 2007) and beam threshold- ing (Ninomiya et al., 2005). A potential disadvantage of the latter technique is that the unifications have taken place by the time the value of the resulting chart item is in- vestigated. One strategy that …

Content truncated to 500 words