Feature selection, L1 vs. L2 regularization, and rotational invariance

ABSTRACT

We consider supervised learning in the presence of very many irrelevant features, and study two different regularization methods for preventing overfitting. Focusing on logistic regression, we show that using L1 regularization of the parameters, the sample complexity (i.e., the number of training examples required to learn "well,") grows only logarithmically in the number of irrelevant features. This logarithmic rate matches the best known bounds for feature selection, and indicates that L1 regularized logistic regression can be effective even if there are exponentially many irrelevant features as there are training examples. We also give a lower-bound showing that any rotationally invariant algorithm---including logistic regression with L2 regularization, SVMs, and neural networks trained by backpropagation---has a worst case sample complexity that grows at least linearly in the number of irrelevant features.

REFERENCES

• 1: Bertsekas, D. P. (1982). Constrained optimization and lagrange multiplier methods. New York: Academic Press.
• 2: Bordley, R. (1982). A multiplicative formula for aggregating probability assessments. Management Science, 28, 1137--1148.
• 3: Breese, J. S., Heckerman, D., & Kadie, C. (1998). Empirical Analysis of Predictive Algorithms for Collaborative Filtering. Proceedings of UAI 14 (pp. 43--52).
• 4: John Canny, Collaborative filtering with privacy via factor analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564419]
• 5: Tom Heskes, Selecting weighting factors in logarithmic opinion pools, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.266-272, July 1998, Denver, Colorado, United States
• 6: Geoffrey E. Hinton, Training products of experts by minimizing contrastive divergence, Neural Computation, v.14 n.8, p.1771-1800, August 2002 [doi>10.1162/089976602760128018]
• 7: Thomas Hofmann, Learning What People (Don't) Want, Proceedings of the 12th European Conference on Machine Learning, p.214-225, September 05-07, 2001
• 8: Marlin, B. (2003). Modeling user rating profiles for collaborative filtering. Proceedings of NIPS 17.
• 9: Marlin, B. (2004). Collaborative filtering: A machine learning perspective. Master's thesis, University of Toronto.
• 10: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 11: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]