Efficient Approximation of Cross-Validation for Kernel Methods using Bouligand Influence Function
Published 21 June 2014
Yong Liu, Shali Jiang, Shizhong Liao
Citations37
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 novel strategy for approximating the cross-validation based on the Bouligand influence function (BIF), which only requires the solution of the algorithm once to be trained, and is sound and efficient.
Abstract
Model selection is one of the key issues both in recent research and application of kernel meth-ods. Cross-validation is a commonly employed and widely accepted model selection criterion. However, it requires multiple times of train-ing the algorithm under consideration, which is computationally intensive. In this paper, we present a novel strategy for approximating the cross-validation based on the Bouligand influ-ence function (BIF), which only requires the so-lution of the algorithm once. The BIF measures the impact of an infinitesimal small amount of contamination of the original distribution. We first establish the link between the concept of BIF and the concept of cross-validation. The BIF is related to the first order term of a Taylor expan-sion. Then, we calculate the BIF and higher or-der BIFs, and apply these theoretical results to approximate the cross-validation error in prac-tice. Experimental results demonstrate that our approximate cross-validation criterion is sound and efficient. 1.
Keywords
Computer ScienceEngineeringPhysics and Astronomy
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
Neural Processing LettersLeast Squares Support Vector Machine Classifiers
9,375 Citations1999Johan A. K. Suykens, Joos Vandewalle
A least squares version for support vector machine (SVM) classifiers that follows from solving a set of linear equations, instead of quadratic programming for classical SVM's.
Transactions of the American Mathematical SocietyTheory of reproducing kernels
5,435 Citations1950N. Aronszajn
Journal of the American Statistical AssociationSpline Models for Observational Data.
5,025 Citations1991Hans‐Georg Müller, Grace Wahba
TechnometricsRobust Statistics: The Approach Based on Influence Functions
3,793 Citations1987David Ruppert, Frank R. Hampel +3 more
This paper presents a meta-modelling framework for estimating the values of Covariance Matrices and Multivariate Location using one-Dimensional and Multidimensional Estimators.
TechnometricsGeneralized Cross-Validation as a Method for Choosing a Good Ridge Parameter
3,770 Citations1979Gene H. Golub, Michael T. Heath +1 more
The method of generalized cross-validation (GCV) for choosing a good value for λ from the data is studied, which can be used in subset selection and singular value truncation methods for regression, and even to choose from among mixtures of these methods.
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.
Lecture notes in computer scienceRademacher and Gaussian Complexities: Risk Bounds and Structural Results
2,111 Citations2001Peter L. Bartlett, Shahar Mendelson
This work investigates the use of certain data-dependent estimates of the complexity of a function class called Rademacher and Gaussian complexities and proves general risk bounds in terms of these complexities in a decision theoretic setting.
Cambridge University Press eBooksSupport Vector Machines
1,479 Citations2020Mohammed J. Zaki, Wagner Meira
Mathematics of Operations ResearchAn Implicit-Function Theorem for a Class of Nonsmooth Functions
240 Citations1991Stephen M. Robinson
This paper introduces the concept of strong approximation of functions, and a related concept ofstrong Bouligand (B-) derivative, and employs these ideas to prove an implicit-function theorem for nonsmooth functions, applicable to a considerably wider class of functions than is the classical theorem.
Journal of Machine Learning ResearchPreventing Over-Fitting during Model Selection via Bayesian Regularisation of the Hyper-Parameters
227 Citations2007Gavin C. Cawley, Nicola L. C. Talbot
This paper investigates the novel use of Bayesian regularisation at the second level of inference, adding a regularisation term to the model selection criterion corresponding to a prior over the hyper-parameter values, where the additional regularisation parameters are integrated out analytically.
The 2006 IEEE International Joint Conference on Neural Network ProceedingsLeave-One-Out Cross-Validation Based Model Selection Criteria for Weighted LS-SVMs
197 Citations2006Gavin C. Cawley
A simple and efficient approach to model selection for weighted least-squares support vector machines, and compares a variety of model selection criteria based on leave-one-out cross-validation.
Technische Universität Dortmund Eldorado (Technische Universität Dortmund)On Robustness Properties of Convex Risk Minimization Methods for Pattern Recognition
117 Citations2003Andreas Christmann, Ingo Steinwart
The paper argues that robustness is an important aspect and shows that many existing machine learning methods based on the convex risk minimization principle have - besides other good properties - also the advantage of being robust.
Journal of Machine Learning ResearchSome Properties of Regularized Kernel Methods
95 Citations2004Ernesto De Vito, Lorenzo Rosasco +3 more
A quantitative version of the representer theorem holding for both regression and classification, for both differentiable and non-differentiable loss functions, and for arbitrary offset terms is proved.
SSRN Electronic JournalModel Selection and Error Estimation
94 Citations2000Peter L. Bartlett, Stéphane Boucheron +1 more
Model Selection in Kernel Based Regression using the Influence Function
63 Citations2008Michiel Debruyne, Mia Hubert +1 more
It is shown how to evaluate influence functions at a specific sample distribution to obtain an approximation of the leave-one-out error and a specific implementation is proposed using a L1 loss in the selection of the hyperparameters and a Huber loss inThe estimation procedure.
The MIT Press eBooksGACV for Support Vector Machines
52 Citations2000Grace Wahba, Yi Lin +1 more
A look at the SVM paradigm from the point of view of a regularization problem, which allows a comparison with penalized log likelihood methods, as well as the application of model selection and tuning approaches which have been used with those and other regularization-type algorithms to choose tuning parameters in nonparametric statistical models.
Statistics and Its InterfaceOn consistency and robustness properties of support vector machines for heavy-tailed distributions
50 Citations2009Andreas Christmann, Ingo Steinwart +1 more
Ghent University Academic Bibliography (Ghent University)Bouligand Derivatives and Robustness of Support Vector Machines for Regression
45 Citations2008Andreas Christmann, Arnout Van Messem
It is shown that many support vector machines based on a Lipschitz continuous loss function and a bounded kernel have a bounded BIF and are thus robust in the sense of robust statistics based on influence functions.
Technische Universität Dortmund Eldorado (Technische Universität Dortmund)Consistency and robustness of kernel based regression
39 Citations2005Andreas Christmann, Ingo Steinwart
Eigenvalues perturbation of integral operator for kernel selection
11 Citations2013Yong Liu, Shali Jiang +1 more
This paper introduces new kernel selection criteria based on the eigenvalues perturbation of the integral operator, and establishes the connection between eigen values perturbations and generalization error.
Advances in Data Analysis and ClassificationA review on consistency and robustness properties of support vector machines for heavy-tailed distributions
5 Citations2010Arnout Van Messem, Andreas Christmann
It is proved that SVMs based on a bounded continuous kernel and on a convex and Lipschitz continuous, but not necessarily differentiable, shifted loss function have a bounded Bouligand influence function for all distributions, even for heavy-tailed distributions including extreme value distributions and Cauchy distributions.