Explanation-Based Learning of Data-Oriented Parsing

Explanation-Based Learning of Data-Oriented Parsing K. Sima'an Research Institute for Language and Speech, Utrecht University, Trans 10, 3512 JK Utrecht, The Netherlands khalil.simaan~let.ruu.nl Abstract This paper presents a new view of ExplanatiomBased Learning (EBL) of nat- ural language parsing. Rather than em- ploying EBL for specializing parsers by in- ferring new ones, this paper suggests em- ploying EBL for learning how to reduce ambiguity only partially.We exemplify this by presenting a new EBL method that learns parsers that avoid spurious over- generation, and we show how the same method can be used for reducing the sizes of stochastic: grammars learned from tree- banks, e.g. (Bod, 1995, Charniak, 1996, Sekine and Grishman, 1995). The present method consists of an EBL al- gorithm for learning partial-parsers, and a parsing algorithm which combines partial- parsers with existing "full-parsers". The learned partial-parsers, implementable as Cascades of Finite State Transducers (CF- STs), recognize and combine constituents efficiently, prohibiting spurious overgener- ation. The parsing algorithm combines a learned partial-parser with a given full- parser such that the role of the full-parser is limited tO combining the constituents, recognized by the partial-parser, and to recognizing unrecognized portions of the input sentence. Besides the reduction of the parse-space prior to disambiguation, the present method provides a way for re- fining existing disambiguation models that learn stochastic grammars from tree-banks e.g. (Bod, 1995, Charniak, 1996, Sekine and Grishman, 1995). We exhibit encouraging empirical results using a pilot implementation: parse-space is reduced substantially with minimal loss of coverage. The speedup gain for disam- biguation models is exemplified by experi- ments with the DOP model (Bod, 1995). 1 Introduction Current work on natural language parsing is in large part directed towards eliminating overgeneration of grammars by employing stochastic models for dis- ambiguation (e.g. (Bod, 1995, Sekine and Grish- man, 1995, Charniak, 1996)). For many applications (e.g. Speech Understanding), probabilistic evalua- tion of the full parse-space using such models is NP- hard (Sima'an, 1996b), and even when it is deter- ministic polynomial-time, then grammar size is pro- hibitive. Therefore, it is necessary to develop meth- ods that, on the one hand, reduce the space of anal- yses, as much as possible prior to disambiguation, and on the other hand, reduce the sizes of gram- mars used for disambiguation. This paper presents a method aimed at these two forms of reduction of time and space costs. In recent work on speeding up parsing, effort is directed towards specializing broad-coverage gram- mar by EBL (e.g. (Rayner, 1988, Samuelsson, 1994, Rayner and Carter, 1996, Srinivas and Joshi, 1995)). Grammar-specialization, in these works, amounts to replacing a given parser by a fresh effi- cient parser learned from the tree-bank. The learned parser trades coverage for efficiency. Inspired by these works, we present a new method based on EBL for learning efficient parsers. Rather than special- izing a given full-parser by inferring a new one, the present method learns a partial-parser and combines it with the full-parser in a way that reduces ambi- guity. The combination is …

Content truncated to 500 words