Non-monotonic feature selection

ABSTRACT

We consider the problem of selecting a subset of m most informative features where m is the number of required features. This feature selection problem is essentially a combinatorial optimization problem, and is usually solved by an approximation. Conventional feature selection methods address the computational challenge in two steps: (a) ranking all the features by certain scores that are usually computed independently from the number of specified features m, and (b) selecting the top m ranked features. One major shortcoming of these approaches is that if a feature f is chosen when the number of specified features is m, it will always be chosen when the number of specified features is larger than m. We refer to this property as the "monotonic" property of feature selection. In this work, we argue that it is important to develop efficient algorithms for non-monotonic feature selection. To this end, we develop an algorithm for non-monotonic feature selection that approximates the related combinatorial optimization problem by a Multiple Kernel Learning (MKL) problem. We also present a strategy that derives a discrete solution from the approximate solution of MKL, and show the performance guarantee for the derived discrete solution when compared to the global optimal solution for the related combinatorial optimization problem. An empirical study with a number of benchmark data sets indicates the promising performance of the proposed framework compared with several state-of-the-art approaches for feature selection.

REFERENCES

• 1: Francis R. Bach , Gert R. G. Lanckriet , Michael I. Jordan, Multiple kernel learning, conic duality, and the SMO algorithm, Proceedings of the twenty-first international conference on Machine learning, p.6, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015424]
• 2: Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Inc., New York, NY, 1995
• 3: Paul S. Bradley , O. L. Mangasarian, Feature Selection via Concave Minimization and Support Vector Machines, Proceedings of the Fifteenth International Conference on Machine Learning, p.82-90, July 24-27, 1998
• 4: Antoni B. Chan , Nuno Vasconcelos , Gert R. G. Lanckriet, Direct convex relaxations of sparse SVM, Proceedings of the 24th international conference on Machine learning, p.145-153, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273515]
• 5: Cortes, C., Mohri, M., & Rostamizadeh, A. (2008). Learning sequence kernels. IEEE Workshop on Machine Learning for Signal Processing (pp. 2--8).
• 6: Cristianini, N., Shawe-Taylor, J., Elisseeff, A., & Kandola, J. S. (2001). On kernel-target alignment. Proc. Neur. Info. Proc. Sys. (pp. 367--373).
• 7: Efron, B., Hastie, T., Johnstone, L., & Tibshirani, R. (2004). Least angle regression. Annals of Statistics, 32, 407--499.
• 8: Glenn Fung , Olvi L. Mangasarian, Data selection for support vector machine classifiers, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.64-70, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347105]
• 9: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 10: Isabelle Guyon , Jason Weston , Stephen Barnhill , Vladimir Vapnik, Gene Selection for Cancer Classification using Support Vector Machines, Machine Learning, v.46 n.1-3, p.389-422, 2002 [doi>10.1023/A:1012487302797]
• 11: Koller, D., & Sahami, M. (1996). Toward optimal feature selection. Proc. Int. Conf. Mach. Learn. (pp. 284--292).
• 12: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 13: Julia Neumann , Christoph Schnörr , Gabriele Steidl, Combined SVM-Based Feature Selection and Classification, Machine Learning, v.61 n.1-3, p.129-150, November 2005 [doi>10.1007/s10994-005-1505-9]
• 14: Andrew Y. Ng, Feature selection, L₁ vs. L₂ regularization, and rotational invariance, Proceedings of the twenty-first international conference on Machine learning, p.78, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015435]
• 15: Alain Rakotomamonjy, Variable selection using svm based criteria, The Journal of Machine Learning Research, 3, 3/1/2003
• 16: Alain Rakotomamonjy , Francis Bach , Stéphane Canu , Yves Grandvalet, More efficiency in multiple kernel learning, Proceedings of the 24th international conference on Machine learning, p.775-782, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273594]
• 17: Bernhard Schölkopf , Alex J. Smola , Robert C. Williamson , Peter L. Bartlett, New Support Vector Algorithms, Neural Computation, v.12 n.5, p.1207-1245, May 2000 [doi>10.1162/089976600300015565]
• 18: Le Song , Alex Smola , Arthur Gretton , Karsten M. Borgwardt , Justin Bedo, Supervised feature selection via dependence estimation, Proceedings of the 24th international conference on Machine learning, p.823-830, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273600]
• 19: Sören Sonnenburg , Gunnar Rätsch , Christin Schäfer , Bernhard Schölkopf, Large Scale Multiple Kernel Learning, The Journal of Machine Learning Research, 7, p.1531-1565, 12/1/2006
• 20: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B, 58, 267--288.
• 21: Vapnik, V. N. (1998). Statistical learning theory. John Wiley & Sons.
• 22: Jason Weston , André Elisseeff , Bernhard Schölkopf , Mike Tipping, Use of the zero norm with linear models and kernel methods, The Journal of Machine Learning Research, 3, 3/1/2003
• 23: Weston, J., Mukherjee, S., Chapelle, O., Pontil, M., Poggio, T., & Vapnik, V. (2000). Feature selection for SVMs. Proc. Neur. Info. Proc. Sys. (pp. 668--674).
• 24: Xu, Z., Jin, R., King, I., & Lyu, M. R. (2009). An extended level method for efficient multiple kernel learning. Proc. Neur. Info. Proc. Sys. (pp. 1825--1832).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory