A PAC-Bayes Risk Bound for General Loss Functions

Pascal Germain, Alexandre Lacasse, François Laviolette, Mario MarchandNeurIPS 2006 · OpenReview

This paper addresses a long-standing limitation in PAC-Bayesian theory: providing tight risk bounds for ensemble methods like Adaboost and Bagging. By deriving a new PAC-Bayesian risk bound for convex combinations of classifiers using general loss functions (such as exponential or sigmoid loss), the authors successfully predict the behavior of majority vote ensembles. Notably, this approach works even when individual ensemble members are "weak," producing bounds that track true test performance with remarkable parallelism.

The Blind Spot in PAC-Bayesian Theory

In machine learning, "risk bounds" provide mathematical guarantees that a model's performance on training data will generalize to unseen data. The PAC-Bayes framework is a powerful tool for establishing these bounds, but it has historically struggled with certain ensemble methods.

Traditionally, PAC-Bayes bounds the risk of a Gibbs classifier—a stochastic model that picks one classifier from an ensemble at random. It then relates this to the majority vote (the ensemble's collective decision). However, for methods like Adaboost, the individual classifiers (e.g., decision stumps) are often only slightly better than random guessing. In these cases, the Gibbs risk hovers near 0.5, making the standard theoretical guarantee ("majority vote error $\le 2 \times$ Gibbs error") practically useless. The authors set out to bypass this limitation by bounding the risk of the majority vote directly using more flexible loss functions.

Bridging the Gap: The "Super-Gibbs" Mapping

The researchers bridge the gap between general loss functions and zero-one loss through a clever mathematical construction:

  1. Taylor Expansion: They represent general loss functions (like the exponential loss used in boosting) as a Taylor series expansion around the point where a classifier is undecided (margin = 0).
  2. Product Classifiers: They define a new "super-ensemble" consisting of products of the original classifiers (e.g., $h_1(x) \cdot h_2(x) \dots h_k(x)$).
  3. The "Super-Gibbs" Mapping: They demonstrate that the expected general loss of the original ensemble is mathematically equivalent to the simple zero-one loss of a specific Gibbs classifier defined over these newly constructed product classifiers.
  4. PAC-Bayes Application: By applying the standard PAC-Bayes theorem to this "super-Gibbs" classifier, they derive a formal bound for the original ensemble's general loss (Theorem 2).

Key Insights and Empirical Tracking

The authors evaluated their bounds using Adaboost with decision stumps on several datasets from the UCI Machine Learning Repository, including Mushroom, Sonar, and Breast Cancer.

Capturing Higher Moments

Unlike standard PAC-Bayes, which typically only considers the first moment (the mean) of the error distribution, this Taylor-expansion approach implicitly accounts for all moments of the margin distribution. This provides a much richer characterization of the ensemble's performance.

The Parallelism Phenomenon

The most striking insight from the empirical evaluation is that the proposed bound's curve is almost perfectly parallel to the true test loss curve.

Exponential loss bound tracking the true test loss over boosting rounds.

While the bound might be numerically higher than the actual error, it accurately predicts the trend. If the bound decreases during training, the test error almost certainly decreases as well. The authors note that Adaboost's strategy of increasing weights on hard examples effectively increases the entropy of the ensemble, which is reflected in how the bound evolves over boosting rounds.

Sigmoid vs. Exponential Loss

The researchers compared bounds derived from different loss functions. They found that the sigmoid loss (tanh) provided a tighter upper bound to the zero-one loss of the majority vote than the exponential loss.

Sigmoid loss bound tracking the true test loss, showing a tighter upper bound.

However, the sigmoid loss is mathematically more restricted. Its Taylor expansion only converges within a specific range ($|x| < \pi/2$), limiting the "sharpness" (denoted as $\beta$) of the sigmoid that can be used in practice.

Limitations and Future Work

While a significant step forward, the proposed bounds have limitations:

  • The Scaling Factor $c$: The bound includes a scaling constant $c$, which is the sum of the absolute values of the Taylor coefficients. If the loss function requires a very large $c$ (for example, using a very high $\beta$ in exponential loss to tightly approximate zero-one loss), the bound becomes loose and less useful.
  • Absolute Tightness: Although the curves exhibit strong parallelism, there remains a gap in absolute value between the bound and the true risk.

Future work could focus on narrowing this absolute gap to produce bounds that are not just qualitatively predictive, but quantitatively tight across all boosting rounds.

Summary updated

Abstract

We provide a PAC-Bayesian bound for the expected loss of convex combinations of classifiers under a wide class of loss functions (which includes the exponential loss and the logistic loss). Our numerical experiments with Adaboost indicate that the proposed upper bound, computed on the training set, behaves very similarly as the true loss estimated on the testing set.
BibTeX
@inproceedings{germain2006pac,
  author = {Pascal Germain and Alexandre Lacasse and François Laviolette and Mario Marchand},
  title = {{A PAC-Bayes Risk Bound for General Loss Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=r1-KXD-_WB},
}

Loading related content...

Figure