Multiple Incremental Decremental Learning of Support Vector Machines

Masayuki Karasuyama, Ichiro Takeuchi

Introduction

Support Vector Machines (SVMs) are powerful classifiers, but retraining them from scratch every time new data arrives is computationally expensive. To solve this, researchers previously developed "incremental/decremental" algorithms that update the model by adding or removing a single data point.

However, in many real-world scenarios—like online learning with a sliding window—you often need to add a batch of new points and remove a batch of old ones simultaneously. Using existing single-update methods requires repeating the process for every single point in the batch. This "coordinate-wise" approach is slow because the computational cost is tied to the number of "breakpoints" (moments when the set of support vectors changes) encountered along the path to the new solution.

This paper introduces MID-SVM (Multiple Incremental Decremental SVM), an algorithm that allows SVMs to be updated by adding or removing multiple data points simultaneously. By leveraging multi-parametric programming to find a "shortcut" through the model's parameter space, the authors achieve significant speedups over traditional methods that process updates one point at a time.

Methods: Multi-Parametric Programming

The authors transition from parametric programming (used for single updates) to multi-parametric programming to handle batch updates efficiently.

  1. Path Following: Instead of updating one coefficient ($\alpha$) at a time, the algorithm defines a direction in the multi-dimensional space of all coefficients being added or removed.
  2. Shortest Path Logic: By moving toward the new optimal values in a direct line rather than following the axes of the parameter space, the algorithm traverses a much shorter total path.
Comparison of path trajectories in parameter space for MID-SVM (diagonal) versus SID-SVM (coordinate-wise)
  1. Breakpoint Tracking: The algorithm monitors the Karush-Kuhn-Tucker (KKT) conditions. It moves along the path until a "breakpoint" is hit—for example, when a data point enters or leaves the margin. At each breakpoint, it solves a linear system to adjust the update direction.
  2. Empty Margin Handling: The paper includes a specific strategy for cases where the "margin" (the area where points have $y f(x) = 1$) becomes empty, ensuring the bias term ($b$) remains correctly bounded.

Key Insights

  • The Geometry of Efficiency: The core "aha moment" is that the number of expensive linear system calculations is proportional to the length of the path taken in the parameter space. Moving diagonally through the space of $m$ parameters is significantly shorter than moving along each axis sequentially.
  • Theoretical Speedup: For adding $m$ points, the authors show that the ratio of breakpoints (and thus computational effort) between their method and the single-update method is roughly $\sqrt{m} : m$.
  • Online Learning Synergy: The method is particularly effective for "sliding window" applications where the number of points added equals the number of points removed, as it can handle both operations in a single mathematical pass.

Datasets and Results

The authors evaluated MID-SVM using both synthetic and real-world data:

  • Artificial Data: A synthetic 2D dataset generated from Gaussian mixtures was used to visualize path lengths and count breakpoints.
  • Fisher River Data: A real-world dataset for online time-series learning, predicting river flow changes based on 21-dimensional input vectors.

Key Results: * Significant Speedups: In artificial tests, MID-SVM was consistently faster than the single-update version (SID-SVM). As the number of points in the update batch ($m$) increased, the performance gap widened. * Breakpoint Reduction: The number of breakpoints encountered by MID-SVM closely followed the theoretical $\sqrt{m}$ prediction, confirming that the multi-parametric approach successfully finds a more efficient route to the solution. * Comparison to Batch Solvers: When compared to LIBSVM (a state-of-the-art batch solver), MID-SVM was much faster for updates, especially when the regularization parameter $C$ was large—a scenario where traditional batch solvers often struggle.

Limitations and Future Work

  • Degeneracy Issues: Like many path-following algorithms, MID-SVM can struggle if the kernel matrix becomes singular (e.g., if there are multiple identical data points). The authors currently use a small constant (jitter) on the diagonal to bypass this, but a more robust theoretical solution remains an open problem.
  • Path Direction: The current algorithm uses a simple linear path toward the target. The authors suggest that using more advanced optimization techniques (like Newton's method) to determine the update direction could potentially yield even shorter paths, though this would introduce its own computational overhead.
  • Generalization: While focused on SVMs, the authors note that this multi-parametric framework could be extended to other kernel-based machines.

Summary updated

Abstract

We propose a multiple incremental decremental algorithm of Support Vector Machine (SVM). Conventional single cremental decremental SVM can update the trained model efficiently when single data point is added to or removed from the training set. When we add and/or remove multiple data points, this algorithm is time-consuming because we need to repeatedly apply it to each data point. The roposed algorithm is computationally more efficient when multiple data points are added and/or removed simultaneously. The single incremental decremental algorithm is built on an optimization technique called parametric programming. We extend the idea and introduce multi-parametric programming for developing the proposed algorithm. Experimental results on synthetic and real data sets indicate that the proposed algorithm can significantly reduce the computational cost of multiple incremental decremental operation. Our approach is especially useful for online SVM learning in which we need to remove old data points and add new data points in a short amount of time.
BibTeX
@inproceedings{karasuyama2009multiple,
  author = {Masayuki Karasuyama and Ichiro Takeuchi},
  title = {{Multiple Incremental Decremental Learning of Support Vector Machines}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=B1-IfPZu-H},
}

Loading related content...

Figure