A Scatter-Based Prototype Framework and Multi-Class Extension of Support Vector Machines

Robert Jenssen, Marius Kloft, Alexander Zien, Sören Sonnenburg, Klaus‐Robert MüllerPLoS 2012 · DOI

Abstract

We provide a novel interpretation of the dual of support vector machines (SVMs) in terms of scatter with respect to class prototypes and their mean. As a key contribution, we extend this framework to multiple classes, providing a new joint Scatter SVM algorithm, at the level of its binary counterpart in the number of optimization variables. This enables us to implement computationally efficient solvers based on sequential minimal and chunking optimization. As a further contribution, the primal problem formulation is developed in terms of regularized risk minimization and the hinge loss, revealing the score function to be used in the actual classification of test patterns. We investigate Scatter SVM properties related to generalization ability, computational efficiency, sparsity and sensitivity maps, and report promising results.

Introduction

Support Vector Machines (SVMs) are foundational tools in machine learning, yet their extension to multi-class problems often relies on heuristic decompositions like One-vs-Rest (OVR) or One-vs-One (OVO). While joint optimization methods exist, they typically suffer from high computational complexity, scaling with the number of classes. This paper introduces a novel "Scatter-Based" framework that reinterprets the SVM dual problem, allowing for a joint multi-class algorithm that is as efficient as its binary predecessor.

The Scatter Interpretation

The core innovation lies in viewing the SVM objective through the lens of geometric scatter. In the binary case, the standard SVM seeks to maximize the margin between two classes. The authors demonstrate that this is mathematically equivalent to minimizing the "between-class scatter"—the squared distance between class prototypes and their collective arithmetic mean.

Binary SVM reinterpreted as scatter between class prototypes and their mean.

In this view, a "class prototype" is a weighted combination of data points. Unlike a simple centroid, these prototypes are learned to reside on the decision boundaries, specifically targeting the most difficult samples (support vectors) to define the optimal separation.

Multi-Class Extension: The Scatter SVM

By extending this scatter-based objective to $C$ classes, the authors derive the Scatter SVM. Unlike traditional joint methods (e.g., Crammer-Singer) which require $n \times C$ optimization variables, the Scatter SVM requires only $n$ variables—the same as a binary SVM. This reduction is achieved by referencing all class prototypes to a single "global mean," introducing a form of global regularization or "stiffness."

The Scatter SVM framework extended to three classes using a global mean.

This formulation allows the use of high-performance solvers like Sequential Minimal Optimization (SMO) and chunking, which were previously difficult to apply to complex joint multi-class models.

Experimental Results

The Scatter SVM was evaluated against OVR, OVO, and standard joint methods across various datasets, including UCI benchmarks, USPS/MNIST digits, and Caltech101 images.

Computational Efficiency

The most striking result is the speedup in high-cardinality problems. On a synthetic "Circle" dataset with 10,000 classes, Scatter SVM was nearly five times faster than the OVR approach using LIBSVM. This efficiency makes joint optimization feasible for large-scale multi-class problems where it was previously prohibitive.

Accuracy and Sparsity

Across standard benchmarks like the "Segment" dataset, Scatter SVM achieved competitive accuracy (97.62%) compared to OVR (97.49%). Furthermore, the model maintains high sparsity, producing a number of support vectors comparable to or lower than OVR, ensuring fast inference times.

Interpretability and Sensitivity Maps

The framework also facilitates the generation of "sensitivity maps." By calculating the derivative of the score function with respect to input features, researchers can visualize which parts of an input (e.g., specific pixels in a digit) drive the classification decision. For instance, in MNIST classification, the maps clearly highlight the characteristic strokes of digits like "0" or "1."

Conclusion

Scatter SVM offers a theoretically elegant and computationally practical bridge between simple binary SVMs and complex joint multi-class models. By leveraging the concept of scatter relative to a global mean, it achieves significant speedups without sacrificing accuracy. While the assumption of class homogeneity (via the global mean) may be a limitation for highly heterogeneous data, the framework provides a robust new tool for large-scale classification tasks in fields ranging from image recognition to computational biology.

Summary updated

Abstract

We provide a novel interpretation of the dual of support vector machines (SVMs) in terms of scatter with respect to class prototypes and their mean. As a key contribution, we extend this framework to multiple classes, providing a new joint Scatter SVM algorithm, at the level of its binary counterpart in the number of optimization variables. This enables us to implement computationally efficient solvers based on sequential minimal and chunking optimization. As a further contribution, the primal problem formulation is developed in terms of regularized risk minimization and the hinge loss, revealing the score function to be used in the actual classification of test patterns. We investigate Scatter SVM properties related to generalization ability, computational efficiency, sparsity and sensitivity maps, and report promising results.
BibTeX
@inproceedings{jenssen2012scatter,
  author = {Robert Jenssen and Marius Kloft and Alexander Zien and Sören Sonnenburg and Klaus‐Robert Müller},
  title = {{A Scatter-Based Prototype Framework and Multi-Class Extension of Support Vector Machines}},
  booktitle = {PLoS},
  year = {2012},
  doi = {10.1371/journal.pone.0042947},
}
Figure