Incremental Feature Selection and l1 Regularization for Relaxed Maximum-Entropy Modeling

Incremental Feature Selection and ℓ1 Regularization for Relaxed Maximum-Entropy Modeling Stefan Riezler and Alexander Vasserman Palo Alto Research Center 3333 Coyote Hill Road, Palo Alto, CA 94304 Abstract We present an approach to bounded constraint- relaxation for entropy maximization that corre- sponds to using a double-exponential prior or ℓ1 reg- ularizer in likelihood maximization for log-linear models. We show that a combined incremental fea- ture selection and regularization method can be es- tablished for maximum entropy modeling by a nat- ural incorporation of the regularizer into gradient- based feature selection, following Perkins et al. (2003). This provides an efficient alternative to stan- dard ℓ1 regularization on the full feature set, and a mathematical justification for thresholding tech- niques used in likelihood-based feature selection. Also, we motivate an extension to n-best feature selection for linguistic features sets with moderate redundancy, and present experimental results show- ing its advantage over ℓ0, 1-best ℓ1, ℓ2 regularization and over standard incremental feature selection for the task of maximum-entropy parsing.1 1 Introduction The maximum-entropy (ME) principle, which pre- scribes choosing the model that maximizes the en- tropy out of all models that satisfy given feature constraints, can be seen as a built-in regularization mechanism that avoids overfitting the training data. However, it is only a weak regularizer that cannot avoid overfitting in situations where the number of training examples is significantly smaller than the number of features. In such situations some fea- tures will occur zero times on the training set and receive negative infinity weights, causing the as- signment of zero probabilities for inputs including those features. Similar assignment of (negative) in- finity weights happens to features that are pseudo- minimal (or pseudo-maximal) on the training set (see Johnson et al. (1999)), that is, features whose value on correct parses always is less (or greater) 1This research has been funded in part by contract MDA904-03-C-0404 of the Advanced Research and Develop- ment Activity, Novel Intelligence from Massive Data program. than or equal to their value on all other parses. Also, if large features sets are generated automatically from conjunctions of simple feature tests, many fea- tures will be redundant. Besides overfitting, large feature sets also create the problem of increased time and space complexity. Common techniques to deal with these problems are regularization and feature selection. For ME models, the use of an ℓ2 regularizer, corresponding to imposing a Gaussian prior on the parameter val- ues, has been proposed by Johnson et al. (1999) and Chen and Rosenfeld (1999). Feature selection for ME models has commonly used simple frequency- based cut-off, or likelihood-based feature induction as introduced by Della Pietra et al. (1997). Whereas ℓ2 regularization produces excellent generalization performance and effectively avoids numerical prob- lems, parameter values almost never decrease to zero, leaving the problem of inefficient computa- tion with the full feature set. In contrast, feature se- lection methods effectively decrease computational complexity by selecting a fraction of the feature set for computation; however, generalization per- formance suffers from the ad-hoc character …

Content truncated to 500 words