A PAC-Bayesian Margin Bound for Linear Classifiers: Why SVMs work

Ralf Herbrich, Thore GraepelNeurIPS 2000 · OpenReview

Introduction

In the late 1990s, Support Vector Machines (SVMs) were taking the machine learning world by storm, yet their theoretical justification remained a puzzle. Standard Statistical Learning Theory, such as Vapnik-Chervonenkis (VC) dimension, suggested that a model's "complexity" should be fixed before seeing the data. However, SVMs find a "maximum margin" hyperplane that is inherently data-dependent.

Existing bounds at the time were often too loose to explain why SVMs performed so well in practice, especially in scenarios where the number of features exceeded the number of training samples. This paper introduces a new, exponentially tighter generalization error bound for linear classifiers using a PAC-Bayesian framework. The authors demonstrate that the "normalized margin"—which accounts for the length of feature vectors—is the true driver of performance, leading to a crucial practical recommendation: always normalize your data in feature space when using SVMs.

A PAC-Bayesian Approach to Margins

The authors move away from traditional worst-case VC-dimension analysis and embrace the PAC-Bayesian framework, which evaluates an average over a distribution of hypotheses rather than a single worst-case scenario.

The Normalized Margin ($\Gamma$)

The core innovation of this work is the definition of a "refined" or "normalized" margin. While the classical margin only considers the distance to the decision boundary relative to the weight vector's norm, the authors' normalized margin ($\Gamma$) also divides by the norm of the feature vectors:

$$\Gamma_z(w) = \min_{(x_i, y_i) \in z} \frac{y_i \langle w, x_i \rangle}{\|w\| \|x_i\|}$$

By normalizing the margin by the length of the feature vectors, the measure becomes invariant to rescaling. This dimensionless margin is a much more robust indicator of how well a model will generalize.

Geometric Arguments and the Volume Ratio

The authors treat the space of linear classifiers as a unit sphere. They show that a classifier with a large normalized margin effectively "summarizes" a large volume of neighboring classifiers on that sphere.

Geometric representation of the hypothesis space as a unit sphere.

The critical insight here is that generalization isn't just about the distance to the nearest point (the margin); it is fundamentally about the volume ratio between the entire hypothesis space and the subset of hypotheses consistent with the training data. If the volume of consistent hypotheses is large, the probability of accidentally picking a "bad" classifier that merely memorized the training data is extremely low. This geometric perspective yields a new bound that scales logarithmically with the inverse margin, representing an exponential improvement over previous theoretical results.

Experimental Validation and Key Results

A surprising theoretical gap highlighted by the authors is that standard SVM algorithms maximize the classical margin, whereas their tighter bound suggests we should maximize the normalized margin. These two objectives only align perfectly if all feature vectors have the exact same length.

To validate this, the authors tested their findings on two classic benchmarks from the UCI Machine Learning Repository:

  • Thyroid dataset: ($d=5$ features, $m=140$ training samples).
  • Sonar dataset: ($d=60$ features, $m=124$ training samples).

They compared standard SVM performance against SVMs trained on normalized feature vectors across different polynomial kernel degrees.

Generalization error comparison across polynomial degrees for standard and normalized SVMs.

The experimental trials confirmed the theory: normalizing feature vectors in the feature space led to a statistically significant improvement in generalization performance on both datasets. Furthermore, the new theoretical bound remained non-trivial even when there were fewer training examples than input dimensions ($m < n$), a scenario where older bounds typically failed.

Limitations and Future Work

While this paper provides a massive leap forward in understanding SVMs, it notes a few limitations:

  • Dimensionality Dependence: The bound still depends on the dimensionality of the space ($d = \min(m, n)$). In infinite-dimensional feature spaces (like RBF kernels), the bound relies heavily on the margin being large enough to offset the complexity.
  • Computational Optimization: Standard SVM solvers are optimized for the classical margin. While normalizing data is an easy preprocessing fix, developing algorithms that directly optimize for the volume ratio in more complex, non-uniform scenarios remains an open challenge.
  • Assumption of Separability: The derivation assumes the realizable case—that a "true" hypothesis exists which perfectly labels the data. Extending this framework to noisy or non-separable data (the agnostic case) is a distinct future hurdle.

Conclusion

By bridging the gap between empirical success and theoretical guarantees, this paper reshaped how practitioners approach linear classifiers. It leaves us with a definitive, theoretically backed rule of thumb that remains standard practice today: When training an SVM, always normalize your data in feature space.

Summary updated

Abstract

We present a bound on the generalisation error of linear classifiers in terms of a refined margin quantity on the training set. The result is obtained in a PAC- Bayesian framework and is based on geometrical arguments in the space of linear classifiers. The new bound constitutes an exponential improvement of the so far tightest margin bound by Shawe-Taylor et al. [8] and scales logarithmically in the inverse margin. Even in the case of less training examples than input dimensions sufficiently large margins lead to non-trivial bound values and - plexity term. Furthermore, the classical margin is too coarse a measure for the essential quantity that controls the generalisation error: the volume ratio between the whole hypothesis space and the subset of consistent hypotheses. The practical relevance of the result lies in the fact that the well-known support vector machine is optimal w.r.t. the new bound only if the feature vectors are all of the same length. As a consequence we recommend to use SVMs on normalised feature vectors only - a recommendation that is well supported by our numerical experiments on two benchmark data sets. for maximum margins - to a vanishing com(cid:173)
BibTeX
@inproceedings{herbrich2000pac,
  author = {Ralf Herbrich and Thore Graepel},
  title = {{A PAC-Bayesian Margin Bound for Linear Classifiers: Why SVMs work}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2000},
  url = {https://openreview.net/forum?id=S1NcauWOZS},
}
Figure