DIMACS TR: 2004-08

Simultaneous Feature Selection And Margin Maximization Using Saddle Point Approach

Authors: Yuri Goncharov, Ilya Muchnik and Leonid Shvartser


A new SVM wrapper method, which simultaneously maximizes margin and minimizes feature space is introduced. For these purposes we modify the standard criterion by adding to the basic objective function a third term, which directly penalizes a chosen set of variables. The new criterion divided the set of all variables into three subsets: deleted, selected and weighted features. We are showing that the question can be formulated as a particular min-max problem for convex-concave functions, which in turn can be solved by saddle point polynomial algorithms. We analyzed a set of such algorithms and realized one, which is taking to account specificity of our problem. The algorithm is examined on a classification Benchmark and its ability to improve the recognition results is shown. We also show that the developed method can be easily transfered to the Support Vector Regression case.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-08.ps.gz
DIMACS Home Page