A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes
Organizations: Université Laval
Abstract
PAC-Bayes is a popular and efficient framework for obtaining generalization guarantees in situations involving uncountable hypothesis spaces. Unfortunately, in its classical formulation, it only provides guarantees on the expected risk of a randomly sampled hypothesis. This requires stochastic predictions at test time, making PAC-Bayes unusable in many practical situations where a single deterministic hypothesis must be deployed. We propose a unified framework for extracting guarantees for a single hypothesis from PAC-Bayesian guarantees. We present a general derandomization framework, and derive from it a numerical bound for majority votes and for three different probability distributions over the posterior space. We study the empirical behaviour of our approach, showing that it consistently outperforms popular baselines in terms of generalization bounds for single classifiers (by up to a factor of 2), but sometimes requires a sacrifice in accuracy.
Figures & tables
| Distribution | First Order | Second Order | Binomial Bound | C-Bound | Partition Bound | |
| Categorical | ✓ | ✓ | ✓ | ✓ | ||
| Dirichlet | ||||||
| Gaussian | ✓ | ✓ | ✓ | |||
| Categorical | ✓ | ✓ | ✓ | |||
| Dirichlet | ||||||
| Gaussian |
| Task | First Order | Second Order | Binomial Bound | C-Bound | VC-dimension | Partition Bound | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bound | Test error | Bound | Test error | Bound | Test error | Bound | Test error | Bound | Test error | Bound | Test error | |
| ADULT | 46.9 0.0 | 22.2 0.1 | 52.9 0.1 | 15.8 0.2 | 51.4 0.0 | 24.1 0.0 | 74.5 0.4 | 21.0 1.6 | 78.9 0.0 | 17.2 0.3 | 23.2 2.4 | 21.7 2.5 |
| CODRNA | 40.2 0.1 | 12.0 0.1 | 47.4 0.1 | 11.7 0.1 | 42.8 5.2 | 15.2 4.5 | 63.7 1.0 | 23.1 1.3 | 38.8 1.6 | 23.1 1.5 | 24.7 0.3 | 23.6 0.3 |
| HABER | 75.2 0.9 | 26.5 1.8 | 110.5 1.1 | 26.1 2.1 | 84.7 0.8 | 26.1 0.7 | 100.0 0.0 | 27.1 1.8 | 112.0 1.0 | 28.4 1.8 | 37.8 0.5 | 26.5 1.8 |
| MUSH | 12.2 0.3 | 4.8 0.5 | 20.6 1.2 | 0.5 0.3 | 12.6 0.4 | 1.1 0.1 | 22.0 0.5 | 4.8 0.5 | 59.1 0.1 | 4.8 0.5 | 6.1 0.1 | 4.8 0.5 |
| PHIS | 25.8 0.3 | 11.1 0.6 | 33.6 0.2 | 6.4 0.5 | 27.5 0.2 | 6.8 0.5 | 37.1 0.5 | 10.4 1.3 | 85.2 0.2 | 11.1 0.6 | 24.9 1.0 | 11.1 0.6 |
| Task | Categorical Distribution | Dirichlet Distribution | Gaussian Distribution | |||
|---|---|---|---|---|---|---|
| Partition Bound | Test error | Partition Bound | Test error | Partition Bound | Test error | |
| ADULT | 46.4 0.4 | 22.2 0.1 | 23.2 2.4 | 21.7 2.5 | 51.0 0.0 | 24.1 0.0 |
| CODRNA | 24.7 0.3 | 23.6 0.3 | 29.4 4.8 | 28.4 4.6 | 39.1 1.4 | 17.1 7.2 |
| HABER | 37.8 0.5 | 26.5 1.8 | 73.6 7.9 | 34.2 7.2 | 71.7 4.2 | 25.8 3.0 |
| MUSH | 6.1 0.1 | 4.8 0.5 | 8.0 1.0 | 4.1 1.8 | 19.0 0.5 | 2.6 0.6 |
| PHIS | 24.9 1.0 | 11.1 0.6 | 26.8 0.2 | 6.7 0.4 | 27.5 0.2 | 6.6 0.5 |
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
| # | Dataset | Full name | Source | |||
|---|---|---|---|---|---|---|
| 1 | ADULT | Adult | LIBSVM | 123 | 2 | 32 561 |
| 2 | CODRNA | CodRNA | LIBSVM | 8 | 2 | 59 535 |
| 3 | HABER | Haberman | UCI | 3 | 2 | 306 |
| 4 | MUSH | Mushroom | UCI | 22 | 2 | 8124 |
| 5 | PHIS | Phishing | LIBSVM | 68 | 2 | 2456 |
| 6 | SVMG | Svmguide1 | LIBSVM | 4 | 2 | 7089 |
| # | Dataset | Partition problem solving (ms) | Heuristic #1 (s) | Heuristic #2 (s) | Heuristic #3 (s) |
|---|---|---|---|---|---|
| 1 | ADULT | 124.4 11.2 | 12.3 2.3 | 67.1 20.8 | 16.7 1.0 |
| 2 | CODRNA | 23.7 7.5 | 14.2 4.6 | 1.9 0.2 | 10.2 1.8 |
| 3 | HABER | 17.3 4.3 | 2.3 0.1 | 0.4 0.1 | 1.9 0.3 |
| 4 | MUSH | 42.1 8.8 | 2.9 0.4 | 1.1 0.2 | 3.1 0.3 |
| 5 | PHIS | 12.3 4.0 | 4.1 1.0 | 6.2 1.1 | 3.4 0.7 |
| 6 | SVMG | 16.0 4.6 | 2.8 0.1 | 0.4 0.0 | 2.1 0.4 |
| Task | First Order | Second Order | Binomial Bound | C-Bound | VC-dimension | Partition Bound |
| C , or G | C , or G | C , or G | C | C | C , D , or G | |
| ADULT | Categorical | Gaussian | Categorical | Categorical | Categorical | Dirichlet |
| CODRNA | Gaussian | Gaussian | Categorical | Categorical | Categorical | Categorical |
| HABER | Categorical | Categorical | Categorical | Categorical | Categorical | Categorical |
| MUSH | Categorical | Categorical | Categorical | Categorical | Categorical | Categorical |
| PHIS | Categorical | Gaussian | Categorical | Categorical | Categorical | Categorical |
PAC-Bayesian Generalization Bounds
PAC-Bayesian Generalization Bounds use prior-to-posterior complexity to certify how well learned predictors perform beyond training data.
See all 39 papers