A Compression Approach to Support Vector Model Selection

Ulrike von Luxburg, Olivier Bousquet, Bernhard SchölkopfJMLR 2004 · OpenReview

Abstract

This paper explores the application of the Minimum Description Length (MDL) principle to the problem of model selection in Support Vector Machines (SVMs). By treating the selection of hyperparameters—such as kernel width and soft-margin penalty—as a data compression task, the authors derive several "compression coefficients." These metrics quantify the number of bits required to encode training labels given the data patterns. Experimental results across various benchmark datasets demonstrate that these coefficients, particularly those accounting for the data's spectral properties, provide accurate error estimates and effective parameter selection, often outperforming traditional statistical learning theory bounds.

Introduction

When building a Support Vector Machine (SVM), practitioners must choose critical hyperparameters like the kernel width ($\sigma$) and the soft-margin penalty ($C$). Traditionally, these are selected via cross-validation, which is computationally intensive, or through generalization bounds from Statistical Learning Theory (SLT). However, many SLT bounds are either too loose for practical use or mathematically prohibitive.

This research investigates whether the Minimum Description Length (MDL) principle—the idea that the best model is the one providing the shortest description of the data—can serve as a robust framework for model selection. To achieve this, the authors translate geometric concepts like margins and feature spaces into the language of bits and binary strings.

Methodology: The Five Compression Codes

The core contribution is the construction of five different compression schemes (Codes). These schemes represent a hypothetical scenario where a sender transmits training labels to a receiver who already possesses the data patterns.

Code 1: The Sphere and Margin Quantization

The most significant conceptual breakthrough is the realization that the SVM margin acts as a natural quantization parameter. A large margin $\rho$ allows the separating hyperplane $H$ to be rotated by an angle $\alpha$ without changing the classification of points within a sphere of radius $R$. This "wobble" room means the normal vector $\omega$ can be represented with lower precision (fewer bits).

Geometric interpretation of hyperplane quantization. A larger margin $\rho$ allows for a larger rotation angle $\alpha$, reducing the precision required to encode the normal vector $\omega$.

Advanced Codes (2-5)

  • Code 2 (The Ellipsoid): Recognizes that high-dimensional data is rarely spherical. By utilizing the eigenvalues of the kernel matrix, this code adapts its precision to the actual ellipsoidal shape of the data distribution.
  • Code 3 & 4 (Subspace & PCA): These refine the encoding by focusing on the subspace spanned by Support Vectors or by using Kernel PCA to ignore dimensions with negligible variance.
  • Code 5 (The Sparse Code): A simpler approach that transmits the indices and labels of the Support Vectors themselves.

The resulting "Compression Coefficient" is the total number of bits used by the code divided by the number of training examples.

Experimental Results

The authors evaluated these coefficients on a massive battery of benchmark datasets, including artificial sets (Banana, Ringnorm) and real-world data (Breast cancer, USPS digits).

Key Findings

  • Superiority of Code 2: The ellipsoid-based coefficient ($C_2$) was the standout performer. It consistently outperformed the classic "radius-margin" bound and performed comparably to the Span Bound, the current gold standard for SVM error estimation.
  • Parameter Prediction: The coefficients were remarkably effective at identifying the optimal $(\sigma, C)$ pairs that minimized actual test error across 16 different datasets.
  • Complexity Trade-offs: Interestingly, the most complex code (Code 4) did not always perform best. The bits required to describe the PCA projection often outweighed the savings from dimension reduction, illustrating the MDL principle's inherent penalty for over-parameterization.

Discussion and Limitations

While the compression approach bridges the gap between geometry and information theory, some hurdles remain. The theoretical bounds used are strictly valid for finite hypothesis sets, requiring a "quantization trick" to apply to continuous SVM spaces. Additionally, calculating eigenvalues for very large kernel matrices can be computationally demanding. Future work may extend this framework to Support Vector Regression (SVR).

In summary, this research demonstrates that the best way to learn a model is often to find the most efficient way to compress the data it describes.

Summary updated

BibTeX
@article{luxburg2004compression,
  author = {Ulrike von Luxburg and Olivier Bousquet and Bernhard Schölkopf},
  title = {{A Compression Approach to Support Vector Model Selection}},
  journal = {J. Mach. Learn. Res.},
  year = {2004},
  url = {https://openreview.net/forum?id=zjFpZmFM-29},
}
Figure