Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound

• The paper addresses the need to estimate effective combinations of voter predictions because known error probabilities and independent-voter assumptions usually do not hold.Source: §1 · p. 1
• PAC-Bayesian methods optimize voter weightings through expected-risk guarantees involving a prior, a data-dependent posterior, and their KL divergence.These guarantees apply in expectation over the hypothesis set rather than as worst-case bounds over all hypotheses.Source: §1 · pp. 1–2
• The proposed stochastic majority vote treats voter weightings as draws from a posterior distribution, enabling PAC-Bayesian bounds directly on its expected risk.The paper contrasts this with prior work that randomized evaluations to upper-bound the deterministic majority vote's risk.Source: §1 · p. 2
• Dirichlet posteriors provide an analytical, differentiable empirical-risk objective, while Monte Carlo optimization supports arbitrary posterior forms.The experiments compare these optimization approaches across regimes before evaluating real benchmarks.Source: §1 · p. 2

Weighted majority votes

• A weighted majority vote combines dictionary classifiers using a weight vector θ, while W_θ measures the total weight assigned to classifiers that err on an example.For binary classification, the vote errs when W_θ ≥ 0.5, so its true risk is P(W_θ ≥ 0.5); the same probability is a surrogate upper bound in multiclass settings.Source: §2.1 · pp. 2–3

PAC-Bayesian majority-vote learning

• The PAC-Bayesian framework treats θ as parameters of a categorical voter distribution and provides risk certificates that can support self-bounding learning algorithms.The paper studies PAC-Bayesian learning of majority votes using this distributional interpretation of the ensemble weights.Source: §2.2 · p. 3

PAC-Bayesian bounds

• The first-order bound controls vote risk through the expected risk of one sampled base classifier, but it ignores correlations that can let ensembles succeed despite individually weak voters.Its factor-two form is close to zero only when the single-voter expected risk is close to zero, unlike ensemble effects observed in methods such as Boosting.Source: §2.2 · pp. 3–4
• The binomial approach approximates vote risk using N sampled hypotheses, but increasing N tightens the approximation while worsening the KL term and retaining a factor-two oracle bound.It does not yield generalization bounds directly on the true risk, and its oracle bound is R(f_θ) ≤ 2 E[W_θ^N].Source: §2.2 · p. 4
• Second-order and C-Bounds incorporate voter agreement or disagreement through the second moment of W_θ, with tightness depending on correlations among base classifiers.The second-order bound can be worse than the first-order bound for identical classifiers but substantially tighter for perfectly decorrelated classifiers; the C-Bound is tighter than the second-order bound when disagreement exceeds R_2(θ) [Masegosa et al., 2020].Source: §2.2 · p. 4

Motivation

• Minimizing PAC-Bayesian bounds can produce sub-optimal majority votes when base classifiers are weak, motivating the paper’s focus on stochastic weight distributions.Figure 3 compares decision surfaces for Bayesian Naive Bayes, several PAC-Bayesian methods, and the proposed method using decision stumps on two-moons data; Dirichlet distributions assign probabilities to vote weights on the simplex, as illustrated in Figure 2.Source: Figure 2 · p. 3, §2.2 · p. 4, Figure 3 · p. 5

• A stochastic majority vote treats each weighting vector as a realization drawn from a posterior distribution, so its risk averages over the entire distribution of majority votes.This directly targets the expected risk of stochastic majority votes rather than randomized evaluations of a deterministic vote.Source: §3 · p. 5
• Under Dirichlet weights, the expected error aggregates wrong and correct voters through a Beta distribution and the regularized incomplete beta function.The Dirichlet aggregation property yields a closed-form expression for the expected risk.Source: §3.1 · pp. 5–6
• The resulting exact risk is differentiable, allowing direct optimization with gradient-based methods.This makes the stochastic-risk objective usable as a training loss.Source: §3.1 · p. 6
• For distributions without analytical risk, the relaxed Monte Carlo scheme samples weight vectors, estimates a softened risk, and updates the concentration parameters by gradient descent.The method uses reparameterized samples and a tempered sigmoid because the discrete 01-loss has zero gradients.Source: §3.2 · p. 6
• The exact formulation is constant in the number of voters M, whereas the Monte Carlo approximation scales linearly with both the number of draws T and M.The paper studies this trade-off empirically when comparing training time and accuracy.Source: §3.2 · p. 7

• Seeger’s bound provides a high-probability upper bound on stochastic-majority-vote risk through empirical risk, KL divergence between posterior and prior, and inverse binary KL.The bound is optimized numerically by evaluating the inverse binary-KL function and using gradient descent.Source: §4 · p. 7
• Data-dependent priors are constructed by splitting the training data, learning separate hypothesis spaces on each split, and evaluating each posterior on the other split.The resulting theorem bounds convex combinations of the two posteriors while preserving the required independence between each prior and its evaluation data.Source: §4 · p. 7
• Figure 4 compares exact and Monte Carlo variants across training-set size n and voter count M, reporting error, generalization bound, and training time for different draw counts T.The figure uses logarithmic scales and averages results over 10 trials.Source: Figure 4 · p. 8
• The KL term grows with the number of base classifiers M, making certificates increasingly conservative and unable to reflect redundancy among highly correlated voters.Learning a smaller hypothesis space is proposed as an expedient for retaining tight bounds without degrading majority-vote performance.Source: §4 · p. 8

Experimental setup

• The experiments compare exact and Monte Carlo STOCMV variants with FO, SO, and Bin baselines under uniform priors and a 0.95 confidence level.The exact variant optimizes the exact risk, whereas MC optimizes an approximation; MC uses T=10 samples in the reported setup.Source: §5 · p. 9
• The real-benchmark study uses UCI, LIBSVM, and Zalando datasets with decision stumps for data-independent priors and Random Forest voters for data-dependent priors.Models are trained with Adam-based stochastic gradient descent, early stopping, and dataset-specific preprocessing described in the appendix.Source: §5.2 · p. 9

Real-dataset comparison

• STOCMV produces consistently tighter and non-vacuous PAC-Bayesian bounds than the baselines across the evaluated datasets.The comparison covers binary datasets with data-independent priors and multi-class datasets with data-dependent priors.Source: §5 · p. 8, §5.2 · p. 9, Figure 5 · p. 10
• STOCMV’s test errors are generally aligned with the baselines, but are significantly lower than FO and SO on the perfectly separable two-moons dataset.The two-moons experiment uses gradient descent to optimize Seeger’s bound over 1,000 iterations.Source: §5.2 · p. 9, §5.1 · p. 9

Voter-strength analysis

• All methods improve as voter strength increases, while STOCMV maintains test errors comparable to the best baselines and consistently tighter bounds.Voter strength is varied by constraining Random Forest tree depth between 1 and 10; SO is particularly sensitive to weak voters and FO improves more slowly.Source: §5.2 · p. 10, Figure 6 · p. 10

Bound tightness

• The paper also targets looseness of its generalization bounds as the number of base predictors increases by accounting for redundancy in the hypothesis space.Source: §6 · p. 10

A Derivation details under Dirichlet assumptions

• Gradient-based optimization requires derivatives involving the Dirichlet parameters, KL divergence, and generalized hyper-geometric functions.The hyper-geometric evaluation can be slow because its convergence rate depends on the Dirichlet parameters.Source: §A.3 · p. 15
• The expected majority vote is parameterized by the Dirichlet mean weighting vector, enabling an oracle bound on its risk.This oracle bound supports empirical PAC-Bayesian bounds for the expected majority vote.Source: §A.4 · pp. 15–16
• The Dirichlet formulation yields an analytical, differentiable risk for the stochastic majority vote.The expected misclassification probability is expressed through the regularized incomplete beta function.Source: §A.4 · p. 16

B Proof of Theorem 2

• The proof derives the informed-prior result by applying separate PAC-Bayesian bounds to the two data-split hypothesis spaces.The theorem uses prior and posterior distributions defined on each space.Source: B Proof of Theorem 2 · pp. 16–17
• Joint convexity of the binary KL divergence supplies the key inequality used in the proof.The resulting bounds are combined across the two spaces.Source: B Proof of Theorem 2 · p. 17
• A union-bound argument combines the component inequalities and yields the stated 1−δ guarantee.The final result holds simultaneously for the relevant posterior distributions.Source: B Proof of Theorem 2 · p. 17

Analysis of the role of bound regularization on the posterior

• Without bound regularization, posterior parameters diverge; optimizing the bound keeps them smaller and near the prior while fitting empirical risk.The gradients smoothly approach zero in both cases, indicating that divergence is not attributed to optimization instability.Source: §C.1 · pp. 17–18

Comparison with baselines

• Our method produces tighter PAC-Bayesian bounds than FO, SO, and Bin for every tested number of predictors M.The tighter bounds reflect both lower error rates and the absence of an oracle upper bound on true risk.Source: §C.1 · p. 18, Figure 10 · p. 18

Sensitivity to noise

• Increasing input noise worsens all methods, and the benefits of exact and Bin vanish for noise variance σ2 > 0.35.Their test errors deteriorate fastest in the noise experiment.Source: §C.1 · p. 18, Figure 11 · p. 18
• On two-moons, the proposed method outperforms the baselines in error rate, whereas on real benchmarks its test errors are generally aligned with theirs.The authors investigate input-noise sensitivity as a possible explanation for this difference.Source: §C.1 · p. 18

C.2 Additional results on real benchmarks

• The benchmark study uses classification datasets from UCI, LIBSVM, and Zalando with 80%/20% training-test splits and no validation set.PAC-Bayesian bounds are used as estimates of test error for model selection.Source: §C.2 · p. 19
• The prior’s concentration substantially affects performance: sparse posteriors help Protein, whereas concentrated posteriors help MNIST.These patterns suggest that tuning prior concentration can improve results.Source: §C.2 · p. 19

C.3 Impact of voter strength

• Limiting Random Forest tree depth between 1 and 10 controls voter strength, measured by the expected accuracy of a random voter.The study evaluates 100-tree Random Forest hypothesis sets.Source: §C.3 · pp. 19–20
• Across tree depths from 1 to 10, our method has error rates comparable with the best baselines and tight, non-vacuous guarantees.Increasing voter strength generally improves ensembles except on Protein, where decision trees are unsuitable base predictors.Source: §C.3 · pp. 19–20

Summary of main results

• The real-benchmark comparison evaluates entropy, KL divergence, training error, test error, and PAC-Bayes bound values across datasets and methods.Figure 14 compares FO, SO, Bin, and the exact and MC variants; Tables 1 and 2 summarize binary and multi-class results.Source: §C.4 · pp. 20–21, Figure 14 · p. 25, Table 1

Model entropy and complexity

• Our models generally have the highest posterior entropy, whereas FO generally has the lowest, indicating greater posterior diversity for our approach.Higher entropy corresponds to a higher number of selected base classifiers.Source: §C.4 · p. 20
• Figure 12 varies the common Dirichlet prior parameter β, where smaller β encourages a sparser posterior, and reports averages and standard deviations over four trials.This experiment studies how prior sparsity affects posterior performance.Source: Figure 12 · p. 21
• The exact and MC posteriors do not necessarily have low KL divergence relative to the prior, so their results are not explained by uniformly reduced model complexity.The reported analysis explicitly separates optimization of the 0-1 loss from obtaining lower-complexity models.Source: §C.4 · p. 21

Summary of main results

• Figure 13 compares voter strength, training error, test error, and Seeger’s bound across tree maximal depths, marking the threshold above which bounds become vacuous.Results are averaged over four trials.Source: Figure 13 · p. 22