Learning Efficient Parsing

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 817–825, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Learning Efficient Parsing Gertjan van Noord University of Groningen G.J.M.van.noord@rug.nl Abstract A corpus-based technique is described to improve the efficiency of wide-coverage high-accuracy parsers. By keeping track of the derivation steps which lead to the best parse for a very large collection of sentences, the parser learns which parse steps can be filtered without significant loss in parsing accuracy, but with an im- portant increase in parsing efficiency. An interesting characteristic of our approach is that it is self-learning, in the sense that it uses unannotated corpora. 1 Introduction We consider wide-coverage high-accuracy pars- ing systems such as Alpino, a parser for Dutch which contains a grammar based on HPSG and a maximum entropy disambiguation component trained on a treebank. Even if such parsing sys- tems now obtain satisfactory accuracy for a vari- ety of text types, a drawback concerns the compu- tational properties of such parsers: they typically require lots of memory and are often very slow for longer and very ambiguous sentences. We present a very simple, fairly general, corpus-based method to improve upon the prac- tical efficiency of such parsers. We use the accu- rate, slow, parser to parse many (unannotated) in- put sentences. For each sentence, we keep track of sequences of derivation steps that were required to find the best parse of that sentence (i.e., the parse that obtained the best score, highest probability, according to the parser itself). Given a large set of successful derivation step sequences, we experimented with a variety of simple heuristics to filter unpromising derivation steps. A heuristic that works remarkably well simply states that for a new input sentence, the parser can only consider derivation step sequences in which any sub-sequence of length N has been observed at least once in the training data. Exper- imental results are provided for various heuristics and amounts of training data. It is hard to compare fast, accurate, parsers with slow, slightly more accurate parsers. In section 3 we propose both an on-line and an off-line appli- cation scenario, introducing a time-out per sen- tence, which leads to metrics for choosing be- tween parser variants. In the experimental part we show that, in an on- line scenario, the most successful heuristic leads to a parser that is more accurate than the baseline system, except for unrealistic time-outs per sen- tence of more than 15 minutes. Furthermore, we show that, in an off-line scenario, the most suc- cessful heuristic leads to a parser that is more than four times faster than the base-line variant with the same accuracy. 2 Background: the Alpino parser for Dutch The experiments are performed using the Alpino parser for Dutch. The Alpino system is a linguis- tically motivated, wide-coverage grammar and parser for Dutch in the tradition of HPSG. It con- sists of about 800 grammar rules and a large lexi- con …

Content truncated to 500 words