On p-norm Path Following in Multiple Kernel Learning for Non-linear Feature Selection

Abstract

Our objective is to develop formulations and al-gorithms for efficiently computing the feature se-lection path – i.e. the variation in classification accuracy as the fraction of selected features is varied from null to unity. Multiple Kernel Learn-ing subject to lp≥1 regularization (lp-MKL) has been demonstrated to be one of the most effective techniques for non-linear feature selection. How-ever, state-of-the-art lp-MKL algorithms are too computationally expensive to be invoked thou-sands of times to determine the entire path. We propose a novel conjecture which states that, for certain lp-MKL formulations, the number of features selected in the optimal solution mono-tonically decreases as p is decreased from an initial value to unity. We prove the conjecture, for a generic family of kernel target alignment based formulations, and show that the feature weights themselves decay (grow) monotonically once they are below (above) a certain threshold at optimality. This allows us to develop a path fol-lowing algorithm that systematically generates optimal feature sets of decreasing size. The pro-posed algorithm sets certain feature weights di-rectly to zero for potentially large intervals of p thereby reducing optimization costs while simul-taneously providing approximation guarantees. We empirically demonstrate that our formula-tion can lead to classification accuracies which are as much as 10 % higher on benchmark data sets not only as compared to other lp-MKL for-mulations and uniform kernel baselines but also