Amir Globerson
ABSTRACT
When constructing a classifier from labeled data, it is important not to assign too much weight to any single input feature, in order to increase the robustness of the classifier. This is particularly important in domains with nonstationary feature distributions or with input sensor failures. A common approach to achieving such robustness is to introduce regularization which spreads the weight more evenly between the features. However, this strategy is very generic, and cannot induce robustness specifically tailored to the classification task at hand. In this work, we introduce a new algorithm for avoiding single feature over-weighting by analyzing robustness using a game theoretic formalization. We develop classifiers which are optimally resilient to deletion of features in a minimax sense, and show how to construct such classifiers using quadratic programming. We illustrate the applicability of our methods on spam filtering and handwritten digit recognition tasks, where feature deletion is indeed a realistic noise model.
- Bovik, A. C., Gibson, J. D., & Bovik, A. (Eds.). (2000). Handbook of image and video processing. Orlando, FL, USA: Academic Press, Inc. Google Scholar
Digital Library
- Boyd, S., & Vandenberghe, L. (2004). Convex optimization. New York, NY, USA: Cambridge University Press. Google ScholarCross Ref
- Cohen, S., Ruppin, E., & Dror, G. (2005). Feature selection based on the shapley value. IJCAI (pp. 665--670). Professional Book Center. Google ScholarDigital Library
- El Ghaoui, L., Lanckriet, G., & Natsoulis, G. (2003). Robust classification with interval data (Technical Report UCB/CSD-03-1279). EECS Department, University of California, Berkeley.Google Scholar
- Gilad-Bachrach, R., Navot, A., & Tishby, N. (2004). Margin based feature selection - theory and algorithms. ICML 21 (pp. 43--50). ACM Press. Google ScholarDigital Library
- Kim, S., Magnani, A., & Boyd, S. (2006). Robust fisher discriminant analysis. NIPS 18 (pp. 659--666). MIT Press.Google Scholar
- Krupka, E., & Tishby, N. (2006). Generalization in clustering with unobserved features. NIPS 18 (pp. 683--690). MIT Press.Google Scholar
- Lanckriet, G., Cristianini, N., Bartlett, P., El Ghaoui, L., & Jordan, M. (2004). Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5, 27--72. Google ScholarDigital Library
- LeCun, Y., Jackel, L., Bottou, L., Brunot, A., Cortes, C., Denker, J., Drucker, H., Guyon, I., Müller, U., Sackinger, E., Simard, P., & Vapnik, V. (1995). Comparison of learning algorithms for handwritten digit recognition. ICANN (pp. 53--60).Google Scholar
- Schölkopf, B., & Smola, A. J. (Eds.). (2002). Learning with kernels. Cambridge, MA: MIT Press.Google Scholar
- Weston, J., Mukherjee, S., Chapelle, O., Pontil, M., Poggio, T., & Vapnik, V. (2000). Feature selection for SVMs. NIPS 13 (pp. 668--674). MIT Press.Google Scholar
- Yang, Y., & Pedersen, J. O. (1997). A comparative study on feature selection in text categorization. ICML 14 (pp. 412--420). Morgan Kaufmann. Google ScholarDigital Library
Index Terms
- Nightmare at test time: robust learning by feature deletion
Recommendations
Test-retest reliability and feature selection in physiological time series classification
Feature test-retest reliability is proposed as a useful criterion for the selection/exclusion of features in time series classification tasks. Three sets of physiological time series are examined, EEG and ECG recordings together with measurements of ...
An efficient Concealed Information Test: EEG feature extraction and ensemble classification for lie identification
EEG-based lie detectors have become popular over polygraphs because it cannot be controlled by human intentions. Various studies have performed "Guilty Knowledge Test" or "Concealed Information Test" by creating a mock crime scenario to identify changes ...
Hindrances for robust multi-objective test problems
Five hindrances are employed to improve and propose challenging robust multi-objective test problems.12 robust multi-objective test problems have been proposed.Five robust multi-objective algorithms have been compared on the proposed test ...
Comments