International Conference on Machine Learning · 2014 · 27 citations · 39 references
ComputingComputer ScienceAlgorithmsMachine LearningOptimizationApproximation AlgorithmsFeature SelectionKernel MethodsOptimization For Machine LearningPattern RecognitionRepresentation LearningApproximation GuaranteesClassification AccuracyClassification Accuracy AnalysisClassification Accuracy AssessmentFeature Set OptimizationKernel LearningMultiple Kernel LearningPath Generation
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
39
Clustering with Bregman Divergences
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon et al. · 2004 · 1.5K citations
Jason Weston, Sayan Mukherjee, Olivier Chapelle et al. · 2000 · 979 citations
1-norm Support Vector Machines
Ji Zhu, Saharon Rosset, Robert Tibshirani et al. · 2003 · 833 citations
Multiple kernels for object detection
Andrea Vedaldi, Varun Gulshan, Manik Varma et al. · 2009 · 767 citations