Incremental and Decremental Support Vector Machine Learning

Published 1 January 2000

Gert Cauwenberghs, Tomaso Poggio

Citations1,158

TL;DR

An on-line recursive algorithm for training support vector machines, one vector at a time, is presented and interpretation of decremental unlearning in feature space sheds light on the relationship between generalization and geometry of the data.

Abstract

An on-line recursive algorithm for training support vector machines, one vector at a time, is presented. Adiabatic increments retain the KuhnTucker conditions on all previously seen training data, in a number of steps each computed analytically. The incremental procedure is reversible, and decremental &quot;unlearning&quot; offers an efficient method to exactly evaluate leave-one-out generalization performance. Interpretation of decremental unlearning in feature space sheds light on the relationship between generalization and geometry of the data. 1

Keywords

Computer Science

The Nature of Statistical Learning Theory

39,279 Citations1995Vladimir Vapnik

International Conference on Neural Information ProcessingAdvances in kernel methods: support vector learning

5,815 Citations1999Bernhard Schölkopf, Christopher J. C. Burges +1 more

Support vector machines for dynamic reconstruction of a chaotic system, Klaus-Robert Muller et al pairwise classification and support vector machines, Ulrich Kressel.

The MIT Press eBooksFast Training of Support Vector Machines Using Sequential Minimal Optimization

5,462 Citations1998John Platt

An improved training algorithm for support vector machines

1,066 Citations2002E. Osuna, Robert M. Freund +1 more

This paper presents a decomposition algorithm that is guaranteed to solve the QP problem and that does not make assumptions on the expected number of support vectors.

Incremental learning with support vector machines

530 Citations2002Stefan Rüping

An approach for incremental learning with support vector machines is presented, that improves the existing approach of Syed et al. (1999), and an insight into the interpretability of support vectors is given.

Query Learning with Large Margin Classifiers

348 Citations2000Colin Campbell, Nello Cristianini +1 more

This paper proposes an algorithm for the training of support vector machines using instance selection, a theoretical justification for the strategy and experimental results on real and artificial data demonstrating its effectiveness.

The Kernel-Adatron Algorithm: A Fast and Simple Learning Procedure for Support Vector Machines

246 Citations1998Thilo-Thomas Frieß, Nello Cristianini +1 more

This paper proposes an adaptation of the Adatron algorithm for clas-siication with kernels in high dimensional spaces that can find a solution very rapidly with an exponentially fast rate of convergence towards the optimal solution.

Neural ComputationProperties of Support Vector Machines

231 Citations1998Massimiliano Pontil, Alessandro Verri

View PDF

Sparse Representation for Gaussian Process Models

128 Citations2000Lehel Csató, Manfred Opper

An approach for a sparse representation for Gaussian Process models in order to overcome the limitations of GPs caused by large data sets is developed based on a combination of a Bayesian online algorithm together with a sequential construction of a relevant subsample of the data which fully specifies the prediction of the model.

Generalization Bounds via Eigenvalues of the Gram matrix

40 Citations1999Bernhard Schölkopf, Smola Shawe-Taylor J +1 more

A new crite rion taking the distribution within that sphere of the data into account by considering the Gram matrix makes use of the eigen value distribution of the matrix.