Margin based feature selection - theory and algorithms

ABSTRACT

Feature selection is the task of choosing a small set out of a given set of features that capture the relevant properties of the data. In the context of supervised classification problems the relevance is determined by the given labels on the training data. A good choice of features is a key for building compact and accurate classifiers. In this paper we introduce a margin based feature selection criterion and apply it to measure the quality of sets of features. Using margins we devise novel selection algorithms for multi-class classification problems and provide theoretical generalization bound. We also study the well known Relief algorithm and show that it resembles a gradient ascent over our margin criterion. We apply our new algorithm to various datasets and show that our new Simba algorithm, which directly optimizes the margin, outperforms Relief.

REFERENCES

• 1: Bartlett, P. (1998). The size of the wieghts is more important than the size of the network. IEEE Transactions on Information Theory, 44, 525--536.
• 2: Bellman, R. (1961). Adaptive control processes: A guided tour. Princeton University Press.
• 3: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 4: Cover, T., & Hart, P. (1967). Nearest neighbor pattern classifier. IEEE Trans. on Information Theory, 13.
• 5: Crammer, K., Gilad-Bachrach, R., Navot, A., & Tishby, N. (2002). Margin analysis of the lvq algorithm. Proc. 17'th Conference on Neural Information Processing Systems.
• 6: Fix, E., & Hodges, j. (1951). Discriminatory analysis. nonparametric discrimination: Consistency properties (Technical Report 4). USAF school of Aviation Medicine.
• 7: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 8: Amir Globerson , Naftali Tishby, Sufficient dimensionality reduction, The Journal of Machine Learning Research, 3, 3/1/2003
• 9: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 10: Guyon, I., & Gunn, S. (2003). Nips feature selection challenge. http://www.nipsfsc.ecs.soton.ac.uk/.
• 11: Jolliffee, I. (1986). Principal component analysis. Springer Varlag.
• 12: Kenji Kira , Larry A. Rendell, A practical approach to feature selection, Proceedings of the ninth international workshop on Machine learning, p.249-256, July 1992, Aberdeen, Scotland, United Kingdom
• 13: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• 14: Teuvo Kohonen, Self-organizing maps, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 15: Martinez, A., & Benavente, R. (1998). The ar face database (Technical Report). CVC Tech. Rep. #24.
• 16: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 17: Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290.
• 18: Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. Annals of Statistics.
• 19: Shawe-Taylor, J., Bartlett, P., Williamson, R., & Anthony, M. (1998). Structural risk minimization over data-dependent hierarchies. IEEE transactions on Information Theory, 44, 1926--1940.
• 20: Tishby, N., Pereira, F., & Bialek, W. (1999). The information bottleneck method. Proc. of the 37-th Annual Allerton Conference on Communication, Control and Computing (pp. 368--377).
• 21: Weston, J., Mukherjee, S., Chapelle, O., Pontil, M., Poggio, T., & Vapnik, V. (2000). Feature selection for SVMs. Proc. 15th Conference on Neural Information Processing Systems (NIPS) (pp. 668--674).