Learning Non-Linear Combinations of Kernels
Published 7 December 2009
Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh
Citations277
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A projection-based gradient descent algorithm is given for solving the optimization problem of learning kernels based on a polynomial combination of base kernels and it is proved that the global solution of this problem always lies on the boundary.
Abstract
This paper studies the general problem of learning kernels based on a polynomial combination of base kernels. We analyze this problem in the case of regression and the kernel ridge regression algorithm. We examine the corresponding learning kernel optimization problem, show how that minimax problem can be reduced to a simpler minimization problem, and prove that the global solution of this problem always lies on the boundary. We give a projection-based gradient descent algorithm for solving the optimization problem, shown empirically to converge in few iterations. Finally, we report the results of extensive experiments with this algorithm using several publicly available datasets demonstrating the effectiveness of our technique. 1
Keywords
Computer ScienceEngineering
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
Neural ComputationNonlinear Component Analysis as a Kernel Eigenvalue Problem
8,078 Citations1998Bernhard Schölkopf, Alexander J. Smola +1 more
A new method for performing a nonlinear form of principal component analysis by the use of integral operator kernel functions is proposed and experimental results on polynomial feature extraction for pattern recognition are presented.
Cambridge University Press eBooksKernel Methods for Pattern Analysis
6,598 Citations2004John Shawe‐Taylor, Nello Cristianini
This book provides an easy introduction for students and researchers to the growing field of kernel-based pattern analysis, demonstrating with examples how to handcraft an algorithm or a kernel for a new specific application, and covering all the necessary conceptual and mathematical tools to do so.
Machine LearningChoosing Multiple Parameters for Support Vector Machines
2,182 Citations2002Olivier Chapelle, Vladimir Vapnik +2 more
The problem of automatically tuning multiple parameters for pattern recognition Support Vector Machines (SVMs) is considered by minimizing some estimates of the generalization error of SVMs using a gradient descent algorithm over the set of parameters.
Biographies, Bollywood, Boom-boxes and Blenders: Domain Adaptation for Sentiment Classification
2,026 Citations2007John Blitzer, Mark Dredze +1 more
This work extends to sentiment classification the recently-proposed structural correspondence learning (SCL) algorithm, reducing the relative error due to adaptation between domains by an average of 30% over the original SCL algorithm and 46% over a supervised baseline.
MPG.PuRe (Max Planck Society)Large Scale Multiple Kernel Learning
1,212 Citations2006Sören Sonnenburg, Gunnar Rätsch +2 more
It is shown that the proposed multiple kernel learning algorithm can be rewritten as a semi-infinite linear program that can be efficiently solved by recycling the standard SVM implementations, and generalize the formulation and the method to a larger class of problems, including regression and one-class classification.
Graduate texts in mathematicsHarmonic Analysis on Semigroups
1,125 Citations1984Christian Berg, Jens Peter Christensen +1 more
ePrints Soton (University of Southampton)Ridge Regression Learning Algorithm in Dual Variables
802 Citations1998Craig Saunders, Alex Gammerman +1 more
A regression estimation algorithm which is a combination of the dual version of Ridge Regression is applied to the ANOVA enhancement of the infinitenode splines and the use of kernel functions, as used in Support Vector methods is introduced.
Journal of Machine Learning ResearchLearning the Kernel Function via Regularization
404 Citations2005Charles A. Micchelli, Massimiliano Pontil
It is shown that, although K may be an uncountable set, the optimal kernel is always obtained as a convex combination of at most m+2 basic kernels, where m is the number of data examples.
More generality in efficient multiple kernel learning
403 Citations2009Manik Varma, Bodla Rakesh Babu
It is observed that existing MKL formulations can be extended to learn general kernel combinations subject to general regularization while retaining all the efficiency of existing large scale optimization algorithms.
arXiv (Cornell University)L2 Regularization for Learning Kernels
361 Citations2012Corinna Cortes, Mehryar Mohri +1 more
ANU Open Research (Australian National University)Learning the Kernel with Hyperkernels
322 Citations2003Cheng Soon Ong, Alexander J. Smola +1 more
Multi-task feature and kernel selection for SVMs
221 Citations2004Tony Jebara
A multi-task representation learning approach using the maximum entropy discrimination formalism is derived and the resulting convex algorithms maintain the global solution properties of support vector machines.
arXiv (Cornell University)Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
175 Citations2008Francis Bach
A DC-programming algorithm for kernel selection
114 Citations2006Andreas A. Argyriou, Raphael Hauser +2 more
This work builds upon a formulation involving a minimax optimization problem and a recently proposed greedy algorithm for learning the kernel to create a new algorithm which outperforms a previously proposed method.
Lecture notes in computer scienceLearning Convex Combinations of Continuously Parameterized Basic Kernels
108 Citations2005Andreas A. Argyriou, Charles A. Micchelli +1 more
There always exists an optimal kernel which is the convex combination of at most m + 1 basic kernels, where m is the sample size, and provide a necessary and sufficient condition for a kernel to be optimal.
Lecture notes in computer scienceLearning Bounds for Support Vector Machines with Learned Kernels
84 Citations2006Nathan Srebro, Shai Ben-David
This work bounds the estimation error of a large margin classifier when the kernel, relative to which this margin is defined, is chosen from a family of kernels based on the training sample, and gives simple bounds on the pseudodimension for families of Gaussian kernels.
Learning sequence kernels
43 Citations2008Corinna Cortes, Mehryar Mohri +1 more
A general formulation of the problem of learning rational kernels is given and it is proved that a large family of rational kernels can be learned efficiently using a simple quadratic program both in the context of support vector machines and kernel ridge regression.