Feature Selection for a Rich HPSG Grammar Using Decision Trees

Feature Selection for a Rich HPSG Grammar Using Decision Trees Kristina Toutanova and Christopher D. Manning Computer Science Department Stanford University Stanford, CA 94305-9040, USA Abstract This paper examines feature selection for log linear models over rich constraint-based grammar (HPSG) representations by building decision trees over fea- tures in corresponding probabilistic context free grammars (PCFGs). We show that single decision trees do not make optimal use of the available in- formation; constructed ensembles of decision trees based on different feature subspaces show signifi- cant performance gains (14% parse selection error reduction). We compare the performance of the learned PCFG grammars and log linear models over the same features. 1 Introduction Hand-built NLP grammars frequently have a depth of linguistic representation and constraints not present in current treebanks, giving them poten- tial importance for tasks requiring deeper process- ing. On the other hand, these manually built gram- mars need to solve the disambiguation problem to be practically usable. This paper presents work on the problem of prob- abilistic parse selection from among a set of al- ternatives licensed by a hand-built grammar in the context of the newly developed Redwoods HPSG treebank (Oepen et al., 2002). HPSG (Head-driven Phrase Structure Grammar) is a modern constraint- based lexicalist (unification) grammar, described in Pollard and Sag (1994). The Redwoods treebank makes available syntac- tic and semantic analyses of much greater depth than, for example, the Penn Treebank. Therefore there are a large number of features available that could be used by stochastic models for disambigua- tion. Other researchers have worked on extracting features useful for disambiguation from unification grammar analyses and have built log linear mod- els a.k.a. Stochastic Unification Based Grammars (Johnson et al., 1999; Riezler et al., 2000). Here we also use log linear models to estimate condi- tional probabilities of sentence analyses. Since fea- ture selection is almost prohibitive for these mod- els, because of high computational costs, we use PCFG models to select features for log linear mod- els. Even though this method may be expected to be suboptimal, it proves to be useful. We select fea- tures for PCFGs using decision trees and use the same features in a conditional log linear model. We compare the performance of the two models using equivalent features. Our PCFG models are comparable to branching process models for parsing the Penn Treebank, in which the next state of the model depends on a his- tory of features. In most recent parsing work the his- tory consists of a small number of manually selected features (Charniak, 1997; Collins, 1997). Other researchers have proposed automatically selecting the conditioning information for various states of the model, thus potentially increasing greatly the space of possible features and selectively choosing the best predictors for each situation. Decision trees have been applied for feature selection for statistical parsing models by Magerman (1995) and Haruno et al. (1998). Another example of automatic feature selection for parsing is in the context of a determin- istic parsing model that chooses parse …

Content truncated to 500 words