Sparseness of support vector machines
Published 1 December 2003
Ingo Steinwart
Citations228
SJR quartileQ1
SJR score2.02
SNIP3.07
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
Lower (asymptotical) bounds on the number of support vectors are established and several results are proved which are of great importance for the understanding of SVMs.
Abstract
Support vector machines (SVMs) construct decision functions that are linear combinations of kernel evaluations on the training set. The samples with non-vanishing coefficients are called support vectors. In this work we establish lower (asymptotical) bounds on the number of support vectors. On our way we prove several results which are of great importance for the understanding of SVMs. In particular, we describe to which “limit” SVM decision functions tend, discuss the corresponding notion of convergence and provide some results on the stability of SVMs using subdifferential calculus in the associated reproducing kernel Hilbert space.
Keywords
Computer ScienceMathematicsEngineering
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
Transactions of the American Mathematical SocietyTheory of reproducing kernels
5,435 Citations1950N. Aronszajn
ePrints Soton (University of Southampton)An Introduction to Support Vector Machines
4,120 Citations2000Nello Cristianini, John Shawe‐Taylor
WORLD SCIENTIFIC eBooksLeast Squares Support Vector Machines
3,640 Citations2002Johan A. K. Suykens, Tony Van Gestel +3 more
Neural ComputationNew Support Vector Algorithms
2,816 Citations2000Bernhard Schölkopf, Alex Smola +2 more
A new class of support vector algorithms for regression and classification that eliminates one of the other free parameters of the algorithm: the accuracy parameter in the regression case, and the regularization constant C in the classification case.
Lecture notes in computer scienceA Generalized Representer Theorem
1,587 Citations2001Bernhard Schölkopf, Ralf Herbrich +1 more
The result shows that a wide range of problems have optimal solutions that live in the finite dimensional span of the training examples mapped into feature space, thus enabling us to carry out kernel algorithms independent of the (potentially infinite) dimensionality of the feature space.
Journal of Mathematical Analysis and ApplicationsSome results on Tchebycheffian spline functions
1,255 Citations1971George Kimeldorf, Grace Wahba
Lecture notes in mathematicsConvex Functions, Monotone Operators and Differentiability
1,019 Citations1989R. R. Phelps
Journal of the American Statistical AssociationConvexity, Classification, and Risk Bounds
1,019 Citations2006Peter L. Bartlett, Michael I. Jordan +1 more
A general quantitative relationship between the risk as assessed using the 0–1 loss and the riskAs assessed using any nonnegative surrogate loss function is provided, and it is shown that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function.
Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions
419 Citations1984Christian Berg, Jens Peter Christensen +1 more
Lecture notes in mathematicsIntegral functionals, normal integrands and measurable selections
363 Citations1976R. T. Rockafellar
Lecture notes in mathematicsAverage-Case Analysis of Numerical Problems
259 Citations2000Klaus Ritter
This chapter discusses Linear Problems for Univariate Functions with Noisy Data Integration and Approximation of Multivariate Functions Nonlinear Methods for Linear Problems Nonlinear Problems.
Data Mining and Knowledge DiscoverySupport Vector Machines and the Bayes Rule in Classification
228 Citations2002Yi Lin
It is shown that the asymptotic target of SVMs are some interesting classification functions that are directly related to the Bayes rule, and helps understand the success of SVM in many classification studies, and makes it easier to compare SVMs and traditional statistical methods.
Applied Physics Letters10.1162/153244302760185252
225 Citations2000
It is shown that the soft margin algorithms with universal kernels are consistent for a large class of classification problems including some kind of noisy tasks provided that the regularization parameter is chosen well.
The Annals of StatisticsAsymptotic Analysis of Penalized Likelihood and Related Estimators
204 Citations1990Dennis D. Cox, Finbarr O’Sullivan
Journal of Machine Learning ResearchExact simplification of support vector solutions
201 Citations2002T. Downs, K. E. Gates +1 more
An algorithm is presented that allows unnecessary support vectors to be recognized and eliminated while leaving the solution otherwise unchanged, and in most cases the procedure leads to a reduction in the number of support vectors.
Journal of ComplexitySupport Vector Machines are Universally Consistent
167 Citations2002Ingo Steinwart
It is shown that the 1-norm soft margin classifier with Gaussian RBF kernel on a compact subset X of Rd and regularization parameter cn = nβ-1 is universally consistent, if n is the training set size and 0 >β> 1/d.
Sparseness of Support Vector Machines---Some Asymptotically Sharp Bounds
74 Citations2003Ingo Steinwart
This work derives asymptotically sharp lower and upper bounds on the number of support vectors for several standard types of SVM's, showing for the Gaussian RBF kernel that the fraction of support vector tends to twice the Bayes risk for the L1-SVM, to the probability of noise for the SVM, and to 1 for the LS-S VM.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn the optimal parameter choice for v-support vector machines
48 Citations2003Ingo Steinwart
It turns out that /spl nu/ should be a close upper estimate of twice the optimal Bayes risk provided that the classifier uses a so-called universal kernel such as the Gaussian RBF kernel.
Applied Mathematics & OptimizationNew results in subdifferential calculus with applications to convex optimization
21 Citations1995Giovanni Romano
Chain and addition rules of subdifferential calculus are revisited in the paper and new proofs, providing local necessary and sufficient conditions for their validity, are presented.
Convergence of Large Margin Separable Linear Classification
16 Citations2000Tong Zhang
It is shown that for a large margin separable linear classification problem, the expected misclassification error may converge exponentially in the number of training sample size.