A Fast Algorithm for Feature Selection in Conditional Maximum Entropy Modeling

A Fast Algorithm for Feature Selection in Conditional Maximum Entropy Modeling Yaqian Zhou Computer Science Department Fudan University Shanghai 200433, P.R. China archzhou@yahoo.com Fuliang Weng Research and Technology Center Robert Bosch Corp. Palo Alto, CA 94304, USA Fuliang.weng@rtc.bosch.com Lide Wu Computer Science Department Fudan University Shanghai 200433, P.R. China ldwu@fudan.edu.cn Hauke Schmidt Research and Technology Center Robert Bosch Corp. Palo Alto, CA 94304, USA hauke.schmidt@rtc.bosch.com Abstract This paper describes a fast algorithm that se- lects features for conditional maximum en- tropy modeling. Berger et al. (1996) presents an incremental feature selection (IFS) algo- rithm, which computes the approximate gains for all candidate features at each selection stage, and is very time-consuming for any problems with large feature spaces. In this new algorithm, instead, we only compute the approximate gains for the top-ranked features based on the models obtained from previous stages. Experiments on WSJ data in Penn Treebank are conducted to show that the new algorithm greatly speeds up the feature selec- tion process while maintaining the same qual- ity of selected features. One variant of this new algorithm with look-ahead functionality is also tested to further confirm the good quality of the selected features. The new algo- rithm is easy to implement, and given a fea- ture space of size F, it only uses O(F) more space than the original IFS algorithm. 1 Introduction Maximum Entropy (ME) modeling has received a lot of attention in language modeling and natural language processing for the past few years (e.g., Rosenfeld, 1994; Berger et al 1996; Ratnaparkhi, 1998; Koeling, 2000). One of the main advantages using ME modeling is the ability to incorporate various features in the same framework with a sound mathematical foundation. There are two main tasks in ME modeling: the feature selection process that chooses from a feature space a subset of good features to be included in the model; and the parameter estimation process that estimates the weighting factors for each selected feature in the exponential model. This paper is primarily con- cerned with the feature selection process in ME modeling. While the majority of the work in ME modeling has been focusing on parameter estimation, less effort has been made in feature selection. This is partly because feature selection may not be neces- sary for certain tasks when parameter estimate al- gorithms are fast. However, when a feature space is large and complex, it is clearly advantageous to perform feature selection, which not only speeds up the probability computation and requires smaller memory size during its application, but also shortens the cycle of model selection during the training. Feature selection is a very difficult optimization task when the feature space under investigation is large. This is because we essentially try to find a best subset from a collection of all the possible feature subsets, which has a size of 2|W|, where |W| is the size of the feature space. In the past, most researchers resorted to a sim- ple count cutoff technique for selecting features (Rosenfeld, 1994; …

Content truncated to 500 words