A Progressive Feature Selection Algorithm for Ultra Large Feature Spaces

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 561–568, Sydney, July 2006. c⃝2006 Association for Computational Linguistics A Progressive Feature Selection Algorithm for Ultra Large Feature Spaces Qi Zhang Computer Science Department Fudan University Shanghai 200433, P.R. China qi_zhang@fudan.edu.cn Fuliang Weng Research and Technology Center Robert Bosch Corp. Palo Alto, CA 94304, USA fuliang.weng@rtc.bosch.com Zhe Feng Research and Technology Center Robert Bosch Corp. Palo Alto, CA 94304, USA zhe.feng@rtc.bosch.com Abstract Recent developments in statistical modeling of various linguistic phenomena have shown that additional features give consistent per- formance improvements. Quite often, im- provements are limited by the number of fea- tures a system is able to explore. This paper describes a novel progressive training algo- rithm that selects features from virtually unlimited feature spaces for conditional maximum entropy (CME) modeling. Experi- mental results in edit region identification demonstrate the benefits of the progressive feature selection (PFS) algorithm: the PFS algorithm maintains the same accuracy per- formance as previous CME feature selection algorithms (e.g., Zhou et al., 2003) when the same feature spaces are used. When addi- tional features and their combinations are used, the PFS gives 17.66% relative im- provement over the previously reported best result in edit region identification on Switchboard corpus (Kahn et al., 2005), which leads to a 20% relative error reduction in parsing the Switchboard corpus when gold edits are used as the upper bound. 1 Introduction Conditional Maximum Entropy (CME) modeling has received a great amount of attention within natural language processing community for the past decade (e.g., Berger et al., 1996; Reynar and Ratnaparkhi, 1997; Koeling, 2000; Malouf, 2002; Zhou et al., 2003; Riezler and Vasserman, 2004). One of the main advantages of CME modeling is the ability to incorporate a variety of features in a uniform framework with a sound mathematical foundation. Recent improvements on the original incremental feature selection (IFS) algorithm, such as Malouf (2002) and Zhou et al. (2003), greatly speed up the feature selection process. However, like many other statistical modeling algorithms, such as boosting (Schapire and Singer, 1999) and support vector machine (Vap- nik 1995), the algorithm is limited by the size of the defined feature space. Past results show that larger feature spaces tend to give better results. However, finding a way to include an unlimited amount of features is still an open research prob- lem. In this paper, we propose a novel progressive feature selection (PFS) algorithm that addresses the feature space size limitation. The algorithm is implemented on top of the Selective Gain Com- putation (SGC) algorithm (Zhou et al., 2003), which offers fast training and high quality mod- els. Theoretically, the new algorithm is able to explore an unlimited amount of features. Be- cause of the improved capability of the CME algorithm, we are able to consider many new features and feature combinations during model construction. To demonstrate the effectiveness of our new algorithm, we conducted a number of experi- ments on the task of identifying …

Content truncated to 500 words