Regularization Networks and Support Vector Machines
Advances in Computational MathematicsPublished 1 April 2000
Theodoros Evgeniou, Massimiliano Pontil, Tomaso Poggio
Citations1,223
SJR quartileQ1
SJR score0.94
SNIP1.20
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
Both formulations of regularization and Support Vector Machines are reviewed in the context of Vapnik's theory of statistical learning which provides a general foundation for the learning problem, combining functional analysis and statistics.
Abstract
Regularization Networks and Support Vector Machines are techniques for solving certain problems of learning from examples – in particular, the regression problem of approximating a multivariate function from sparse data. Radial Basis Functions, for example, are a special case of both regularization and Support Vector Machines. We review both formulations in the context of Vapnik's theory of statistical learning which provides a general foundation for the learning problem, combining functional analysis and statistics. The emphasis is on regression: classification is treated as a special case.
Keywords
Computer ScienceEngineering
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
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.
Neural Networks: A Comprehensive Foundation
29,816 Citations1998Simon Haykin
Thorough, well-organized, and completely up to date, this book examines all the important aspects of this emerging technology, including the learning process, back-propagation learning, radial-basis function networks, self-organizing systems, modular networks, temporal processing and neurodynamics, and VLSI implementation of neural networks.
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.
Data Mining and Knowledge DiscoveryA Tutorial on Support Vector Machines for Pattern Recognition
16,433 Citations1998Christopher J. C. Burges
There are several arguments which support the observed high accuracy of SVMs, which are reviewed and numerous examples and proofs of most of the key theorems are given.
Computers in PhysicsTen Lectures on Wavelets
15,386 Citations1992Ingrid Daubechies, Christopher Heil
This paper presents a meta-analyses of the wavelet transforms of Coxeter’s inequality and its applications to multiresolutional analysis and orthonormal bases.
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Neural ComputationAn Information-Maximization Approach to Blind Separation and Blind Deconvolution
9,194 Citations1995Anthony J. Bell, Terrence J. Sejnowski
It is suggested that information maximization provides a unifying framework for problems in "blind" signal processing and dependencies of information transfer on time delays are derived.
IEEE Transactions on Signal ProcessingMatching pursuits with time-frequency dictionaries
9,115 Citations1993Stéphane Mallat, Zhifeng Zhang
The authors introduce an algorithm, called matching pursuit, that decomposes any signal into a linear expansion of waveforms that are selected from a redundant dictionary of functions, chosen in order to best match the signal structures.
Methods of Mathematical Physics
8,096 Citations1989R. Courant, David Hilbert
SIAM Journal on Scientific ComputingAtomic Decomposition by Basis Pursuit
6,899 Citations1998Scott Shaobing Chen, David L. Donoho +1 more
Basis Pursuit (BP) is a principle for decomposing a signal into an "optimal" superposition of dictionary elements, where optimal means having the smallest l1 norm of coefficients among all such decompositions.
AutomaticaModeling by shortest data description
5,944 Citations1978J. Rissanen
The number of digits it takes to write down an observed sequence x1,...,xN of a time series depends on the model with its parameters that one assumes to have generated the observed data.
NatureEmergence of simple-cell receptive field properties by learning a sparse code for natural images
5,840 Citations1996Bruno A. Olshausen, David J. Field
It is shown that a learning algorithm that attempts to find sparse linear codes for natural scenes will develop a complete family of localized, oriented, bandpass receptive fields, similar to those found in the primary visual cortex.
Transactions of the American Mathematical SocietyTheory of reproducing kernels
5,435 Citations1950N. Aronszajn
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Stochastic modelling and applied probabilityA Probabilistic Theory of Pattern Recognition
3,277 Citations1996Luc Devroye, László Györfi +1 more
The Bayes Error and Vapnik-Chervonenkis theory are applied as guide for empirical classifier selection on the basis of explicit specification and explicit enforcement of the maximum likelihood principle.
Proceedings of the IEEENetworks for approximation and learning
3,257 Citations1990Tomaso Poggio, Federico Girosi
Regularization theory and a theoretical framework for approximation that leads to a class of three-layer networks called regularization networks are discussed, generalized to a formulation that includes task-dependent clustering and dimensionality reduction.
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
IEEE Transactions on Information TheoryEntropy-based algorithms for best basis selection
3,173 Citations1992Ronald R. Coifman, Mladen Victor Wickerhauser
Adapted waveform analysis uses a library of orthonormal bases and an efficiency functional to match a basis to a given signal or family of signals, and relies heavily on the remarkable orthogonality properties of the new libraries.
Neural ComputationNatural Gradient Works Efficiently in Learning
2,700 Citations1998Шун-ичи Амари
The dynamical behavior of natural gradient online learning is analyzed and is proved to be Fisher efficient, implying that it has asymptotically the same performance as the optimal batch estimation of parameters.
Choice Reviews OnlineApplied nonparametric regression
2,613 Citations1991
Applied Nonparametric Regression is the first book to bring together in one place the techniques for regression curve smoothing involving more than one variable and argues that all smoothing methods are based on a local averaging mechanism and can be seen as essentially equivalent to kernel smoothing.
Mathematics of ComputationSpline Functions: Basic Theory.
2,493 Citations1982Philip W. Smith, Larry L. Schumaker
The material covered provides the reader with the necessary tools for understanding the many applications of splines in such diverse areas as approximation theory, computer-aided geometric design, curve and surface design and fitting, image processing, numerical solution of differential equations, and increasingly in business and the biosciences.
Information science and statisticsEstimation of Dependences Based on Empirical Data
2,238 Citations2006Vladimir Vapnik
A New Learning Algorithm for Blind Signal Separation
1,888 Citations1995Шун-ичи Амари, Andrzej Cichocki +1 more
A new on-line learning algorithm which minimizes a statistical dependency among outputs is derived for blind separation of mixed signals and has an equivariant property and is easily implemented on a neural network like model.
NatureComputational vision and regularization theory
1,414 Citations1985Tomaso Poggio, Vincent Torre +1 more
Descriptions of physical properties of visible surfaces, such as their distance and the presence of edges, must be recovered from the primary image data and algorithms and parallel analog circuits that can solve ‘ill-posed problems’ and which are suggestive of neural equivalents in the brain are proposed.
TechnometricsThe Relationship Between Variable Selection and Data Agumentation and a Method for Prediction
1,361 Citations1974David M. Allen
It is shown that data augmentation provides a rather general formulation for the study of biased prediction techniques using multiple linear regression and a way to obtain predictors given a credible criterion of good prediction is proposed.
Neural ComputationRegularization Theory and Neural Networks Architectures
1,355 Citations1995Federico Girosi, Michael Jones +1 more
This paper shows that regularization networks encompass a much broader range of approximation schemes, including many of the popular general additive models and some of the neural networks, and introduces new classes of smoothness functionals that lead to different classes of basis functions.
Interpolation of Scattered Data: Distance Matrices and Conditionally Positive Definite Functions
1,307 Citations1984Charles A. Micchelli
Learning from Data: Concepts, Theory, and Methods
1,293 Citations1998Vladimir Cherkassky, Filip Mulier
Constructive ApproximationInterpolation of scattered data: Distance matrices and conditionally positive definite functions
1,213 Citations1986Charles A. Micchelli
IEEE Transactions on Information TheoryThe sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network
1,187 Citations1998Peter L. Bartlett
Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights.
Approximation of functions
1,171 Citations2017
The Annals of Mathematical StatisticsA Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
950 Citations1970George Kimeldorf, Grace Wahba
Acta NumericaNonlinear approximation
859 Citations1998Ronald DeVore
This is a survey of nonlinear approximation, especially that part of the subject which is important in numerical computation, and emphasis will be placed on approximation by piecewise polynomials and wavelets as well as their numerical implementation.
Proceedings of the IEEEIll-posed problems in early vision
729 Citations1988M. Bertero, Tomaso Poggio +1 more
A Theory of Networks for Approximation and Learning
716 Citations1989Tomaso Poggio, Federico Girosi
Journal of the American Statistical AssociationProbabilistic Solution of Ill-Posed Problems in Computational Vision
698 Citations1987José L. Marroquín, Sanjoy K. Mitter +1 more
This work derives efficient algorithms and describes parallel implementations on digital parallel SIMD architectures, as well as a new class of parallel hybrid computers that mix digital with analog components.
Advances in Numerical AnalysisThe Theory of Radial Basis Function Approximation in 1990
570 Citations1992M. J. D. Powell
Neural ComputationLocal Learning Algorithms
544 Citations1992Léon Bottou, Vladimir Vapnik
A single analysis suggests that neither kNN or RBF, nor nonlocal classifiers, achieve the best compromise between locality and capacity.
IEEE Transactions on Information TheoryStructural risk minimization over data-dependent hierarchies
527 Citations1998John Shawe‐Taylor, Peter L. Bartlett +2 more
A result is presented that allows one to trade off errors on the training sample against improved generalization performance, and a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets.
The Annals of StatisticsA Comparison of GCV and GML for Choosing the Smoothing Parameter in the Generalized Spline Smoothing Problem
523 Citations1985Grace Wahba
Neural ComputationAn Equivalence Between Sparse Approximation and Support Vector Machines
505 Citations1998Federico Girosi
If the data are noiseless, the modified version of basis pursuit denoising proposed in this article is equivalent to SVM in the following sense: if applied to the same data set, the two techniques give the same solution, which is obtained by solving the same quadratic programming problem.
Transactions of the American Mathematical SocietyTheory of Reproducing Kernels
483 Citations1950N. Aronszajn
Asilomar Conference on Signals, Systems and ComputersBasis pursuit
471 Citations1994Shaobing Chen, David L. Donoho
Birkhäuser Boston eBooksContributions to the Problem of Approximation of Equidistant Data by Analytic Functions
465 Citations1988I. J. Schoenberg
Neural Information Processing SystemsEfficient Pattern Recognition Using a New Transformation Distance
464 Citations1992Patrice Simard, Yann LeCun +1 more
A new distance measure which can be made locally invariant to any set of transformations of the input and can be computed efficiently is proposed.
The Annals of StatisticsSpline Smoothing: The Equivalent Variable Kernel Method
444 Citations1984Bernard W. Silverman
SIAM Journal on Scientific and Statistical ComputingNumerical Procedures for Surface Fitting of Scattered Data by Radial Functions
400 Citations1986Nira Dyn, David I. W. Levin +1 more
The major theme of this work is the development of an iterative scheme for the construction of a smooth surface, presented by global basis functions, which approximates only the smooth components of a set of scattered noisy data.
Journal of Computer and System SciencesEfficient distribution-free learning of probabilistic concepts
377 Citations1994Michael Kearns, Robert E. Schapire
Journal of the American Statistical AssociationProbabilistic Solution of Ill-Posed Problems in Computational Vision
367 Citations1987José L. Marroquín, Sanjoy K. Mitter +1 more
Computers & Mathematics with ApplicationsA unifying information-theoretic framework for independent component analysis
360 Citations2000Te-Won Lee, Mark Girolami +2 more
It is shown that different theories recently proposed for independent component analysis (ICA) lead to the same iterative learning algorithm for blind separation of mixed independent sources and that information theory can be used to unify several lines of research.
Model Selection for Support Vector Machines
347 Citations1999Olivier Chapelle, Vladimir Vapnik
New functionals for parameter (model) selection of Support Vector Machines are introduced based on the concepts of the span of support vectors and rescaling of the feature space and it is shown that using these functionals one can both predict the best choice of parameters of the model and the relative quality of performance for any value of parameter.
Proceedings of the IEEEIncorporating prior information in machine learning by creating virtual examples
311 Citations1998Partha Niyogi, Federico Girosi +1 more
It is shown that in some contexts this idea of using prior knowledge by creating virtual examples and thereby expanding the effective training-set size is mathematically equivalent to incorporating the prior knowledge as a regularizer, suggesting that the strategy is well motivated.
AlgorithmicaOn a Kernel-Based Method for Pattern Recognition, Regression, Approximation, and Operator Inversion
297 Citations1998Alexander J. Smola, Bernhard Schölkopf
A kernel-based framework for pattern recognition, regression estimation, function approximation, and multiple operator inversion is presented, adopting a regularization-theoretic framework.
Prior Knowledge in Support Vector Kernels
293 Citations1997Bernhard Schölkopf, Patrice Simard +2 more
It is shown that both invariances under group transformations and prior knowledge about locality in images can be incorporated by constructing appropriate kernel functions by exploring methods for incorporating prior knowledge in Support Vector learning machines.
TechnometricsThe Relationship between Variable Selection and Data Agumentation and a Method for Prediction
251 Citations1974David M. Allen
NeurocomputingThe nonlinear PCA learning rule in independent component analysis
219 Citations1997Erkki Oja
It has been verified experimentally that when nonlinear Principal Component Analysis (PCA) learning rules are used for the weights of a neural layer, the neurons have signal separation capabilities and can be used for image and speech signal separation.
Probabilistic Kernel Regression Models
207 Citations1999Tommi Jaakkola, David Haussler
A class of exible conditional probability models and techniques for classi cation regression problems that comes from the use of kernel functions as in support vector machines and the generality from dual formulations of stan dard regression models is introduced.
Neural ComputationOn the Relationship between Generalization Error, Hypothesis Complexity, and Sample Complexity for Radial Basis Functions
175 Citations1996Partha Niyogi, Federico Girosi
This article shows that the generalization error can be decomposed into two terms: the approximation error, due to the insufficient representational capacity of a finite sized network, and the estimation error,due to insufficient information about the target function because of the finite number of samples.
An experimental and theoretical comparison of model selection methods
170 Citations1995Michael Kearns, Yishay Mansour +2 more
IEEE Transactions on Information TheoryGeneralization performance of regularization networks and support vector machines via entropy numbers of compact operators
169 Citations2001Robert C. Williamson, Alex Smola +1 more
New bounds for the generalization error of kernel machines, such as support vector machines and related regularization networks, are derived by obtaining new bounds on their covering numbers by using the eigenvalues of an integral operator induced by the kernel function used by the machine.
Constructive ApproximationMultivariate cardinal interpolation with radial-basis functions
166 Citations1990Martin Buhmann
Biological CyberneticsOn optimal nonlinear associative recall
139 Citations1975Tomaso Poggio
The problem of determining the nonlinear function (“blackbox”) which optimally associates two sets of data is considered and an iteration method based on the concept of the generalized inverse of a matrix provides the polynomial mapping of degreek onX by whichY is retrieved in an optimal way in the least squares sense.
Fat-shattering and the learnability of real-valued functions
118 Citations1994Peter L. Bartlett, Philip M. Long +1 more
It is shown that, given some restrictions on the noise, a function class is learnable in this model if and only if its fat-shattering function is finite, and analogous results in an agnostic setting, where there is no assumption of an underlying function class.
Journal of Theoretical ProbabilityUniform and universal Glivenko-Cantelli classes
100 Citations1991R. M. Dudley, E. Gin� +1 more
Quasiinterpolants and Approximation Power of Multivariate Splines
93 Citations1990Carl de Boor
Network Computation in Neural SystemsDevelopment of low entropy coding in a recurrent network
87 Citations1996George Harpur, Richard W. Prager
An unsupervised neural network which exhibits competition between units via inhibitory feedback is presented, and it is shown how the assignment of prior probabilities to network outputs can help to reduce entropy.
Neural ComputationA Sparse Representation for Function Approximation
84 Citations1998Tomaso Poggio, Federico Girosi
A new general representation for a function is derived as a linear combination of local correlation kernels at optimal sparse locations (and scales) and its relation to principal component analysis, regularization, sparsity principles, and support vector machines is characterized.
Learning Nonlinear Overcomplete Representations for Efficient Coding
73 Citations1997Michael S. Lewicki, Terrence J. Sejnowski
The utility of overcomplete representations on natural speech is demonstrated and it is shown that compared to the traditional Fourier basis the inferred representations potentially have much greater coding efficiency.
Lecture notes in computer scienceOn the Noise Model of Support Vector Machines Regression
57 Citations2000Massimiliano Pontil, Sayan Mukherjee +1 more
This work can be extended to justify nonquadratic loss functions in any Maximum Likelihood or Maximum AP osteriori approach, and applies not only to the ILF, but to a much broader class of loss functions.
Journal of Computer and System SciencesFat-Shattering and the Learnability of Real-Valued Functions
54 Citations1996Peter L. Bartlett, Philip M. Long +1 more
Scale-sensitive dimensions, uniform convergence, and learnability
52 Citations2002Noga Alon, Shalev Ben-David +2 more
This paper proves, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes, the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension.
Journal of Approximation TheoryOn Quasi-interpolation with Radial Basis Functions
47 Citations1993Martin Buhmann
Israel Journal of MathematicsOn multivariate approximation by integer translates of a basis function
43 Citations1992Nira Dyn, I. R. H. Jackson +2 more
DSpace@MIT (Massachusetts Institute of Technology)Learning linear, sparse, factorial codes
41 Citations1996Bruno A. Olshausen
Journal of Approximation TheoryPolyharmonic cardinal splines: A minimization property
33 Citations1990W. R. Madych, S. A. Nelson
Computers & Mathematics with ApplicationsAn introduction to schoenberg's approximation
29 Citations1992Christophe Rabut
DSpace@MIT (Massachusetts Institute of Technology)Extensions of a Theory of Networks for Approximation and Learning: Outliers and Negative Examples
29 Citations1990Federico Girosi, Tomaso Poggio +1 more
Neural networks for localized approximation of real functions
25 Citations2002H. N. Mhaskar
It is demonstrated that, using standard ideas from the theory of spline approximation, it is possible to construct such networks to provide localized approximation and can be used for the simultaneous approximation of a function and its derivative.
DSpace@MIT (Massachusetts Institute of Technology)From Regression to Classification in Support Vector Machines
25 Citations1998Massimiliano Pontil, Ryan Rifkin +1 more
It is shown that for a given SVMC solution there exists a SVMR solution which is equivalent for a certain choice of the parameters, and SVMC can be seen as a special case of SVMR.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Models of Noise and Robust Estimation
23 Citations1991Federico Girosi
This paper shows that using robust least squares estimators corresponds to assuming that data are corrupted by Gaussian noise whose variance fluctuates according to some given probability distribution, that uniquely determines the estimator.
Lecture notes in computer scienceOn the V γ Dimension for Regression in Reproducing Kernel Hilbert Spaces
23 Citations1999Theodoros Evgeniou, Massimiliano Pontil
Finiteness of the Vγ dimension is shown, which also proves uniform convergence in probability for regression machines in RKHS subspaces that use the LƐ or general Lp loss functions.
Bounds on the Generalization Performance of Kernel Machine Ensembles
21 Citations2000Theodoros Evgeniou, Luis Perez-Breva +2 more
New theoretical bounds on the generalization performance of voting ensembles ofkernel machines of kernel machines are presented and it is shown how such ensembleles can be used for fast training with very large datasets.
Lecture notes in computer scienceA Note on Support Vector Machine Degeneracy
15 Citations1999Ryan Rifkin, Massimiliano Pontil +1 more
It is shown that an SVM training problem can always be made degenerate by the addition of a single data point belonging to a certain unbounded polyhedron, which is characterized in terms of its extreme points and rays.
Elsevier eBooksHow to Build Quasi-Interpolants: Application to Polyharmonic B-Splines
10 Citations1991Christophe Rabut
It is shown that B h may be defined by considering it as some regularisation of the Dirac distribution, and that it is better to determine B h by using some least square criterion than by using a “ ‘ P κ reproducing” criterion.
Lecture notes in computer scienceA note on the generalization performance of kernel classifiers with margin
6 Citations2000Theodoros Evgeniou, Massimiliano Pontil
Distribution independent bounds on the generalization misclassification performance of a family of kernel classifiers with margin of Support Vector Machine classifiers stem out of this class of machines.
From Regression to Classication in Support Vector Machines
3 Citations1999Massimiliano Pontil, Ryan Rifkin +1 more
It is shown that for a given SVMC solution there exists a SVMR solution which is equivalent for a certain choice of the parameters, and SVMC can be seen as a special case of SVMR.
…