Sample Selection for Statistical Grammar Induction

Sample Selection for Statistical Grammar Induction Rebecca Hwa Division of Engineering and Applied Sciences • Harvard University Cambridge, MA 02138 USA rebecca@eecs.harvard.edu Abstract Corpus-based grz.mmar induction relies on us- ing many hand-parsed sentences as training examples. However, the construction of a training corpus with detailed syntactic analy- sis for every sentence is a labor-intensive task. We propose to use sample selection methods to minimize the amount of annotation needed in the training data, thereby reducing the workload of the human annotators. This pa- per shows that the amount of annotated train- ing data can be reduced by 36% without de- grading the quality of the induced grammars. 1 Introduction: Many learning problems in the domain of natural language processing need supervised training. For instance, it is difficult to induce a grammar from a corpus of raw text; but the task becomes much easier when the training sentences are supplemented with their parse trees. However, appropriate supervised train- ing data may be difficult to obtain. Existing corpora might not contain the relevant type of supervision, and the data might not be in the domain of interest. For example, one might need morphological analyses of the lex- icon in addition to the parse trees for inducing a grammar, or one might be interested in pro- cessing non-English languages for which there is no annotated corpus. Because supervised training typically demands significant human involvement (e.g., annotating the parse trees of sentences by hand), building a new corpus is a labor-intensive task. Therefore, it is worth- while to consider ways of minimizing the size of the corpus to reduce the effort spent by an- notators. * This material is based upon work supported by the National Science Foundation under Grant No. IRI 9712068. We thank Wheeler Rural for his plotting tool; and Stuart Shieber, Lillian Lee, Ric Crabbe, and the anonymous reviewers for their comments on the paper. There are two possible directions: one might attempt to reduce the amount of anno- tations in each sentence, as was explored by Hwa (1999); alternatively, one might attempt to reduce the number of training sentences. In this paper, we consider the latter approach using sample selection, an interactive learning method in which the machine takes the initia- tive of selecting potentially beneficial train- ing examples for the humans to annotate. If the system could accurately identify a subset of examples with high Training Utility Values (TUV) out of a pool of unlabeled data, the annotators would not need to waste time on processing uninformative examples. We show that sample selection can be applied to grammar induction to produce high quality grammars with fewer annotated training sentences. Our approach is to use uncertainty-based evaluation functions that estimate the TUV of a sentence by quantify- ing the grammar's uncertainty about assign- ing a parse tree to this sentence. We have considered two functions. The first is a sire- • ple heuristic that approximates the grammar's uncertainty in terms of sentence lengths. The second computes uncertainty in terms of …

Content truncated to 500 words