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

Abstract:
We investigate a stochastic counterpart of majority votes over finite ensembles of classifiers, and study its generalization properties. While our approach holds for arbitrary distributions, we instantiate it with Dirichlet distributions: this allows for a closed-form and differentiable expression for the expected risk, which then turns the generalization bound into a tractable training objective. The resulting stochastic majority vote learning algorithm achieves state-of-the-art accuracy and benefits from (non-vacuous) tight generalization bounds, in a series of numerical experiments when compared to competing algorithms which also minimize PACBayes objectives – both with uninformed (data-independent) and informed (datadependent) priors.

heading: 1 Introduction
text: By combining the outcomes of several predictors, ensemble methods [Dietterich, 2000] have been shown to provide models that are more accurate and more robust than each predictor taken singularly. The key to their success lies in harnessing the diversity of the set of predictors [Kuncheva, 2004]. Among ensemble methods, weighted Majority Votes (MV) classifiers assign a score to each base classifier (a.k.a. voter) and output the most common prediction, given by the weighted majority. When voters have known probabilities of making an error and make independent predictions, the optimal weighting is given by the so-called Naive Bayes rule [Berend and Kontorovich, 2015]. However, in most situations these assumptions are not satisfied, giving rise to the need for techniques that estimate the optimal combination of voter predictions from the data.
Among them, PAC-Bayesian based methods are well-grounded approaches for optimizing the voter weighting. Indeed, PAC-Bayes theory (introduced by Shawe-Taylor and Williamson, 1997, McAllester, 1999 – we refer to Guedj, 2019 for a recent survey and references therein) provides not only bounds on the true error of a MV through Probably Approximately Correct (PAC) generalization bounds (see e.g. Catoni [2007], Seeger [2002], Maurer [2004], Langford and Shawe-Taylor [2002], Germain et al. [2015]), but is also suited to derive theoretically grounded learning algorithms (see e.g. Germain et al. [2009], Roy et al. [2011], Parrado-Hernández et al. [2012], Alquier et al. [2016]). Contrary to the most classical PAC bounds [Valiant, 1984], as VC-dimension [Vapnik, 2000] or Rademacher-based bounds [Mohri et al., 2012], PAC-Bayesian guarantees do not stand for all hypotheses (i.e. are not expressed as a worst-case analysis) but stand in expectation over the hypothesis set. They involve a hypothesis space (formed by the base predictors), a prior distribution on it (i.e. an a priori weighting) and a posterior distribution (i.e. an a posteriori weighting) evaluated on a learning sample. The prior brings some prior knowledge on the combination of predictors, and the posterior
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
distribution is learned (adjusted) to lead to good generalization guarantees; the deviation between the prior and the posterior distributions plays a role in generalization guarantee and is usually captured by the Kullback-Leibler (KL) divergence. In their essence, PAC-Bayesian results do not bound directly the risk of the deterministic MV, but bound the expected risk of one (or several) base voters randomly drawn according to the weight distribution of the MV [Langford and Shawe-Taylor, 2002, Lacasse et al., 2006, 2010, Germain et al., 2015, Masegosa et al., 2020]. This randomization scheme leads to upper bounds on the true risk of the MV that are then used as a proxy to derive PAC-Bayesian generalization bounds. However, the obtained risk certificates are generally not tight, as they depend on irreducible constant factors, and when optimized they can lead to sub-optimal weightings. Indeed, by considering a random subset of base predictors, state-of-the-art methods do not fully leverage the diversity of the whole set of voters. This is especially a problem when the voters are weak, and learning to combine their predictions is critical for good performance.
Our contributions. In this paper, we propose a new randomization scheme. We consider the voter weighting associated to a MV as a realization of a distribution of voter weightings. More precisely, we analyze with the PAC-Bayesian framework the expected risk of a MV drawn from the posterior distribution of MVs. The main difference with the literature is that we propose a stochastic MV, while previous works aim at studying randomized evaluations of the true risk of the deterministic MV. Doing so, we are able to derive tight empirical PAC-Bayesian bounds for our model directly on its expected risk, in Section 4. We further propose, in Section 3 two approaches for optimizing the generalization bounds, hence learning the optimal posterior: the first optimizes an analytical and differentiable form of the empirical risk that can be derived when considering Dirichlet distributions; the second optimizes a Monte Carlo approximation of the expected risk and can be employed with any form of posterior. In our experiments, reported in Section 5, we first compare these two approaches, highlighting in which regimes one is preferable to the other. Finally, we assess our method’s performance on real benchmarks w.r.t. the performance of PAC-Bayesian approaches also learning MV classifiers. These results indicate that our models enjoy generalization bounds that are consistently tight and non-vacuous both when studying ensembles of data-independent predictors and when studying ensembles of data-dependent ones.
Societal impact. Our work abides by the ethical guidelines enforced in contemporary research in machine learning. Given the theoretical nature of our contributions we do not foresee immediate potentially negative societal impact.

heading: 2 Notation and background
text: In this section, we formally define weighted Majority Vote (MV) classifiers and review the principal PAC-Bayesian approaches for learning them.

heading: 2.1 Weighted majority vote classifiers
text: Consider the data random variable pX,Y q, taking values in XˆY with X Ď Rd a d-dimensional representation space and Y the set of labels. We denote P the (unknown) data distribution of pX,Y q. We define a set (dictionary) of base classifiers D“thj : X Ñ YuMj“1. The weighted majority vote classifier is a convex combination of the base classifiers from D. Formally, a MV is parameterized by a weight vector θ P r0, 1sM , such that
řM j“1 θj “ 1 hence lying in the (M -1)-simplex ∆M´1, as
follows:
fθpxq “ argmax yPY
M ÿ j“1 θj 1phjpxq “ yq, (1)
where 1p¨q is the indicator function. Let WθpX,Y q be the random variable corresponding to the total weight assigned to base classifiers that predict an incorrect label on pX,Y q, that is
WθpX,Y q “ M ÿ
j“1 θj1phjpXq ‰ Y q. (2)
In binary classification with |Y|“2, the MV errs whenever WθpX,Y q ě 0.5 [Lacasse et al., 2010, Masegosa et al., 2020]. Hence the true risk (w.r.t. 01-loss) of the MV classifier can be expressed as
Rpfθq fi EP 1pWθpX,Y q ě 0.5q “ PpWθ ě 0.5q. (3)
Similarly, the empirical risk of fθ on a n-sample S“tpxi, yiq„Puni“1 is given by
R̂pfθq “ n ÿ
i“1 1pWθpxi, yiq ě 0.5q.
Note that the results we introduce in the following are stated for binary classification, but are valid also in the multi-class setting (|Y|ą2). Indeed, in this context Equation (3) becomes a surrogate of the risk: we have Rpfθq ď PpWθ ě 0.5q (see the notion of ω-margin with ω “ 0.5 proposed by Laviolette et al. [2017]).

heading: 2.2 A PAC-Bayesian perspective on the majority vote
text: The current paper stands in the context of PAC-Bayesian MV learning. The PAC-Bayesian framework has been employed to study the generalization guarantees of randomized classifiers. It is known to provide tight risk certificates that can be used to derive self-bounding learning algorithms [e.g. Germain et al., 2009, Dziugaite and Roy, 2017, Pérez-Ortiz et al., 2020]. In the PAC-Bayes literature of the analysis of MV, θ is interpreted as the parameter of a categorical distribution Cpθq over the set of base classifiers D [e.g. Germain et al., 2015, Lorenzen et al., 2019, Masegosa et al., 2020]. In this sense, fθ corresponds to the MV predictor fθpxq“ argmaxyPY Eh„Cpθq1phpxq“yq and Wθ corresponds to the expected ratio of wrong predictors WθpX,Y q “ Eh„Cpθq1phpXq ‰ Y q. The PAC-Bayesian analysis provides a sensible way to find such a categorical distribution, called posterior distribution, that leads to a model with low true risk Rpfθq. However, an important caveat is that the PAC-Bayesian generalization bounds cannot be derived directly on the true risk Rpfθq, without making assumptions on the distribution of Wθ and raising fidelity problems. Thus, a common approach is to consider oracle1 upper bounds on the true risk in terms of quantities from which PAC-Bayesian bounds can be derived, that are typically related to the statistical moments of Wθ. By doing so, oracle bounds act as a proxy for estimating the cumulative density function for Wθ ě 0.5 [Langford and Shawe-Taylor, 2002, Germain et al., 2006, Lacasse et al., 2010, Masegosa et al., 2020]. Generalization guarantees for Rpfθq are hence derived, involving the empirical counterpart of the oracle bound, the KL-divergence between the posterior categorical distribution Cpθq and a prior one. An overview of the existing oracle bounds described below is represented in Figure 1.
First order bound. The most classical “factor two” oracle bound [Langford and Shawe-Taylor, 2002] is derived considering the relation between MV’s risk and the first moment of Wθ, a.k.a. the expected risk of the randomized classifier:
R1pθq fi Eh„Cpθq1phpXq‰Y q “ EP Wθ.
1Oracle bounds are expressed in terms of the unknown data distribution; their exact value cannot be computed.
By applying Markov’s inequality, we have Rpfθq ď 2R1pθq. This “factor two” bound is close to zero only if the expectation of the risk of a single base classifier drawn according to Cpθq is itself close to zero. Therefore, it does not take into account the correlation between base predictors, which is key to characterize how a MV classifier can achieve strong predictions even when its base classifiers are individually weak (as observed when performing e.g. Boosting [Schapire and Singer, 1999]). This explains why R1pθq can be a very loose estimate of Rpfθq when the base classifiers are adequately decorrelated.
Binomial bound. A generalization of the first order approach was proposed in Shawe-Taylor and Hardoon [2009], Lacasse et al. [2010], where the true risk of the MV is estimated by drawing multiple (N ) base hypotheses and computing the probability that at least N2 make an error (which is given by the binomial with parameter Wθ):
WθN pX,Y q fi N ÿ
k“N2
ˆ
N
k
˙
W kθ p1´WθqpN´kq.
The higher N , the better WθN pX,Y q approximates the true risk, but the looser the bound, as the KL term worsens by a factor of N . Moreover, with this approach it is not possible to derive generalization bounds directly on the true risk, and the corresponding oracle bound still presents a factor two: Rpfθq ď 2 EPWθN .
Second order bound. A parallel line of works focuses on improving the bounds by accounting for voter correlations, i.e. considering the agreement and/or disagreement of two random voters. Masegosa et al. [2020] recently proposed a new upper bound for the true risk depending on the second moment of Wθ, a.k.a. tandem loss or joint error, the risk that two predictors make a mistake on the same point: R2pθqfiEP Eh„Cpθq,h1„Cpθq1phpXq‰Y ^h1pXq‰Y q“EP W 2θ . By applying the second order Markov’s inequality, we have Rpfθqď4R2pθq. Masegosa et al. [2020] show that in the worst case (i.e. when the base classifiers are identical) the second order bound could be twice worse than the first order bound (R2pθq«2R1pθq), while in the best case (i.e. the M base classifiers are perfectly decorrelated), the second order bound could be an order of magnitude tighter (R2pθq« 1MR1pθq).
C-bound. Originally proposed by Breiman [2001] in the context of Random Forest, a bound known as the C-Bound in the PAC-Bayesian literature [Lacasse et al., 2006, Roy et al., 2011, Germain et al., 2015, Laviolette et al., 2017, Viallard et al., 2021b] is derived by considering explicitly the joint error and disagreement between two base predictors. Using Chebyshev-Cantelli’s inequality, the C-Bound can be written in terms of the first and second moments of Wθ:
Rpfθq ď R2pθq ´ Eh„Cpθq pEP1phpXq ‰ Y qq
2
R2pθq ´R1pθq ` 14 .
This bound is tighter than the second order one if the disagreement Eh,h1EPp1phpxq ‰ h1pXqqq is greater than R2pθq [Masegosa et al., 2020].
From a practical point of view, one could minimize the generalization bounds of one of the above methods to learn a weight distribution over an ensemble of predictors. However, this could lead to suboptimal MV classifiers. To illustrate this behavior we plot in Figure 3 the decision surfaces learnt by the minimization of a PAC-Bayesian bound on each of the aforementioned oracle bounds. These plots provide evidence that, when the base classifiers are weak, state-of-the-art PAC-Bayesian methods do not necessarily build powerful ensembles (failing to improve upon a Naive Bayes approach [Berend and Kontorovich, 2015]). First Order concentrates on few base classifiers, as previously observed by Lorenzen et al. [2019] and Masegosa et al. [2020], while Second Order and C-Bound fail to leverage the diversity in the whole set of classifiers. Indeed, in this setting the base classifiers are weak, but diverse enough so that there exists an optimal combination of them that perfectly splits the two classes without error. However, the optimization of the PAC-Bayes guarantees over Second Order and C-Bound are shown to select a small subset of base classifiers which is not enough to achieve good performance. On the contrary, Binomial is able to fit the problem by drawing more than 2 voters, but it provides generalization bounds that are loose even when the learned model exhibits good generalization capabilities, as in this case.

heading: 3 Our approach: stochastic weighted majority vote
text: In our framework for deriving generalization bound for Majority Vote classifiers, we consider fθ as a realization of a distribution of majority vote classifiers, with parameter θ P Θ Ď RM and probability measure ρ, as represented in Figure 2. The main advantage of considering a stochastic majority vote is that it allows to derive and optimize PAC-Bayesian generalization bounds directly on its true risk and to fully leverage the set of base classifiers. The true risk of the proposed stochastic weighted majority vote takes into account the whole distribution of MVs ρpθq, as follows: ż
Θ
Rpfθqρpdθq “ ż
Θ
EP 1pWθpX,Y q ě 0.5qρpdθq “ EP ż
Θ
1pWθpX,Y q ě 0.5qρpdθq. (4)
Given its stochastic nature, in order to evaluate and/or minimize Equation (4) we can either (i) compute its closed form or (ii) approximate it (e.g. through Monte Carlo methods). In both cases, assumptions have to be made on the form of ρ. As the components of θ are constrained to sum to one, θ lies in the (M -1)-simplex: Θ “ ∆pM -1q, hence natural choices for its probability measure are e.g. the Dirichlet or the Logit Normal distributions. In the following, we show that under Dirichlet assumptions, we can derive an analytical and differentiable form of the risk of a stochastic MV.

heading: 3.1 Exact risk under Dirichlet assumptions
text: First of all, we recall that the probability density function of the Dirichlet distribution is defined by:
θ „ Dpα1, . . . , αM q, ρpθq “ 1
Bpαq
M ź j“1 pθjqαj´1, (5)
with α “ rαj P R`sMj“1 the vector of concentration parameters and Bpαq a normalization factor (see App A for its definition). Notice that by taking α as the vector of all ones, the distribution corresponds to a uniform distribution over the (M -1)-simplex ∆M´1.
Under these assumptions for the MV distribution, a closed form can be derived for the expected risk:
Lemma 1. For a given px, yq „ P , let w “ tj|hjpxq ‰ yu be the set of indices of the base classifiers that misclassify px, yq and c “ tj|hjpxq “ yu be the set of indices of the base classifiers that correctly classify px, yq. The expected error (or 01-loss) for px, yq of the stochastic majority vote under θ „ Dpα1, . . . , αM q is equal to
ż
Θ
1pWθpx, yq ě 0.5qρpdθq “ I0.5
˜
ÿ jPc αj , ÿ jPw αj
¸
, (6)
with I0.5p¨q the regularized incomplete beta function evaluated at 0.5.
Proof. We rewrite Wθ as Wθpx, yq “ řM j“1 θj1phjpxq ‰ yq “ ř
jPw θj , and use the aggregation property of Dirichlet distributions to show that Wθ follows a bivariate Dirichlet distribution (a.k.a. Beta distribution):
Lemma 2. If θ „ Dpα1, . . . , αM q, then for any j P rM s and j1 P r1,M sztju the variable θ1 formed by dropping θj and θj1 and adding their sum also follows a Dirichlet distribution
pθ1, . . . , θM , θj ` θj1q „ Dpα1, . . . , αM , αj ` αj1q.
A proof of this property can be found in https://vannevar.ece.uw.edu/techsite/papers/ documents/UWEETR-2010-0006.pdf. Hence Wθ follows a Beta distribution over the two sets of wrong and correct base classifiers:
PrWθpx, yq “ ωs “ P « ÿ
jPw θj “ ω
ff
P
«
ÿ jPc θj “ 1´ ω
ff
ùñWθpx, yq „ D ˜ ÿ
jPw αj ,
ÿ jPc αj
¸
by aggregation. (7)
Finally, notice that the expected error is related to the cumulative probability function of Wθ, the incomplete beta function Ip : R` ˆ R` Ñ r0, 1s:
ż
Θ
1pWθpx, yq ě 0.5qρpdθq “ ż 1
0.5
PrdWθpx, yqs (8)
“ 1´ I0.5
˜
ÿ jPw αj , ÿ jPc αj
¸
“ I0.5
˜
ÿ jPc αj , ÿ jPw αj
¸
. (9)
Equation (9) follows by symmetry of the incomplete beta function: Ippa, bq “ 1´ I1´ppb, aq.
The expected risk Rpρq can be then expressed as follows:
Rpρq “ EP ż
Θ
1pWθpx, yq ě 0.5qρpdθq “ EPI0.5
˜
ÿ jPc αj , ÿ jPw αj
¸
. (10)
Importantly, this exact form of the risk is differentiable, hence can be directly optimized by gradientbased methods.

heading: 3.2 Monte Carlo approximated risk
text: We now propose a relaxed Monte Carlo (MC) optimization scheme for those distributions that do not admit an analytical form of the expected risk, unlike the Dirichlet one. This second strategy is also suited to speed up training, in some cases, as the derivatives of the exact risk depend on the hyper-geometric function and can be slow to evaluate (see App. A.3). With the approximated scheme, in order to update α by gradient descent we need to relax the true risk as the gradients of the 01-loss are always null for discrete Wθ. In practice, we make use of a tempered sigmoid loss σcpxq “ 11`expp´cxq with slope parameter c P R
`. De facto this corresponds to solving a relaxation of the problem and not its exact form [Nesterov, 2005]. At each iteration of the MC optimization algorithm we perform:
1. Draw a sample tθt „ ρpαquTt“1 using the implicit reparameterization trick [Figurnov et al., 2018, Jankowiak and Obermeyer, 2018];
2. Compute the relaxed empirical risk řT t“1 R̂σcpθq “ řT t“1 řn i“1 σcpWθtpxi, yiq ´ 0.5q;
3. Update α by gradient descent.
Notice that when considering Dirichlet distributions for the posterior and the prior, at inference time the empirical PAC-Bayesian bounds can still be evaluated using the exact form of Lemma 1.
A drawback of the approximated scheme is that it has a complexity linear in the number of MC draws T , but also linear in the number of predictors M , as sampling over the simplex requires sampling from OpMq distributions, one per base classifier. As an example, sampling from a Dirichlet over the (M -1)-simplex is usually implemented as sampling from M Gamma distributions and normalizing the samples so that they lie on the simplex. In contrast, the exact formulation’s complexity is constant in M as it depends only on the sets of wrong and of correct predictors, hence on a constant number of variables (2) no matter the number of predictors M . In Section 5.1 we empirically study the trade-off between training time and accuracy, showing in which regimes it is more convenient to optimize the relaxed MC risk than optimizing the exact one, and viceversa.

heading: 4 PAC-Bayesian generalization guarantees
text: We now derive PAC-Bayesian generalization upper bounds for the proposed stochastic MV. In our context, upper bounds can be derived for studying the gap between true and empirical risk considering a prior distribution π over the hypothesis space Θ. In this paper, we make use of one of the tightest classical PAC-Bayesian bound [Seeger, 2002, Maurer, 2004]: Theorem 1 (Seeger’s bound). For any π over Θ and δ P p0, 1q with probability at least 1´δ over samples S “ tpxi, yiq„Puni“1 of size n we have simultaneously for any posterior ρ over Θ:
ż
Θ
Rpfθqρpdθq ď kl´1 ¨ ˝ ż
Θ
R̂pfθqρpdθq , KLpρ, πq ` ln
´ 2 ? n δ ¯
n
˛
‚, (11)
with R̂pfθq “ 1n řn i“1 1pWθpxi, yiq ě 0.5q the empirical risk on sample S, KLpρ, πq “ ş
Θ ρpθq log ρpθqπpθq dθ the KL divergence and kl ´1pq, q the inverse of the binary KL divergence defined as kl´1pq, q “ maxtp P r0, 1s | klpq, pq ď u.
A proof of Theorem 1 can be found in Seeger [2002]. The kl´1 function can be evaluated via the bisection method and optimized by gradient descent, as proposed in Reeb et al. [2018]. Note that our contributions do not restrict the choice of generalization bound.
Importantly, Theorem 1 is valid when the prior π is independent from the data. Thus it cannot be evaluated with base classifiers learned from the training sample. However, it is known that considering a data-dependent prior can lead to tighter PAC-Bayes bounds [Dziugaite et al., 2021]. Following recent works on PAC-Bayesian bounds with data-dependent priors [Thiemann et al., 2017, Mhammedi et al., 2019], we derive a cross-bounding certificate that allows us to learn and evaluate the set of base classifiers without held-out data. More precisely, we split the training data S into two subsets (Sďm“tpxi, yiq P Sumi“1 and Sąm“tpxi, yiq P Suni“m`1) and we learn a set of base classifiers on each data split independently (determining the hypothesis spaces Θďm and Θąm). We refer to the prior distribution over Θďm as πďm and to the prior distribution over Θąm as πąm. In the same way, we can then define a posterior distribution per hypothesis space: ρďm and ρąm. The following theorem shows that we can bound the expected risk of any convex combination of the two posteriors, as long as their empirical risks are evaluated on the data split that was not used for learning their respective priors. Theorem 2 (Seeger’s bound with informed priors). Let πďm and ρďm be the prior and posterior distributions on Θďm, and πąm and ρąm the prior and posterior distributions on Θąm. For any pPp0, 1q and δ P p0, 1q with probability at least 1´δ over samples S“tpxi, yiq„Puni“1 we have
kl ´ pR̂pρąmq ` p1´ pqR̂pρďmq › › › pRďmpρąmq ` p1´ pqąmpρďmq ¯
ď p KLpρąm, πąmq m ` p1´ pq KLpρďm, πďmq n´m `
ln 4 ? mpn´mq δ
n ,
with Rpρąmq “ ş Θąm Rpfθqρpdθq, and Rpρďmq “ ş Θďm Rpfθqρpdθq, and R̂ďmpρąmq“ ş
Θąm R̂pfθqρpdθq, and R̂ďmpρąmq“
ş
Θďm R̂pfθqρpdθq.
The result follows by kl’s convexity. The complete proof is reported in App. B. In practice, following Mhammedi et al. [2019] we set m “ n2 and p “ m n , and we learn the base classifiers by empirical risk minimization.
Comparison with existing bounds. Until now, we considered bounds for the expected risk over the space of MVs but not for a single realization fθ, unlike state-of-the-art methods. Under Dirichlet assumptions, we can bound the risk of the expected MV fθ̂ by twice the expected risk (see App A.4): Rpfθ̂q “ RpEρpθqfθq ď 2EρpθqRpfθq. The obtained oracle bound would comprise an irreducible factor, but its KL term would not degrade, unlike state-of-the-art bounds that account for voter correlation [Lacasse et al., 2006, 2010, Masegosa et al., 2020]. Indeed, the empirical bound does not introduce additional factors on the KL term, such as Second Order which has a 2 KLpq term and Binomial which has a N KLpq term. The empirical bound on the deterministic MV could be also refined leveraging works on the disintegration of PAC-Bayesian guarantees [Blanchard and Fleuret, 2007, Catoni, 2007, Rivasplata et al., 2020, Viallard et al., 2021a].
A downside of our method is that the complexity of the KL term grows with the number of base classifiers M , unlike the KL on categoricals that tends to 0 in its limit. This results in making the generalization bounds increasingly looser and conservative with growing M , even for low empirical risks. From a generalization perspective, our guarantees are hence able to reflect the complexity of the model, expressed as the size of the hypothesis space M . However, our risk certificates do not account for redundancy in the voter set. For instance, they are not able to distinguish scenarios where base classifiers are highly correlated (hence less complex hypothesis space) from scenarios where base classifiers are independent (more complex). An expedient for ensuring that generalization bounds are tight consists in learning the hypothesis space: the number of base predictors can then be limited without degrading the performance of the majority vote.

heading: 5 Experiments
text: In this section, we empirically evaluate STOCMV, and we compare its generalization bounds and test errors to those obtained with PAC-Bayesian methods learning majority votes. We show that our method allows to derive generalization bounds that are consistently tight (i.e. close to the test errors) and non-vacuous (i.e. smaller than 1) both when studying ensembles of weak predictors and when studying ensembles of strong ones.
In the following, we consider Dirichlet distributions for the prior and the posterior of our method, and refer to the model obtained by optimizing the exact risk as exact and the one obtained by optimizing the approximated one as MC. We consider as baselines the PAC-Bayesian methods described in Section 2.1: We refer to the methods optimizing the First Order, Second Order and Binomial empirical bound as FO, SO and Bin respectively. We do not compare with the C-Bound, as it is hard to optimize on large-scale datasets and existing algorithms are suited only for binary classification. All generalization bounds are evaluated with a probability 1´δ“0.95 and all prior distributions are set to the uniform (we provide a study for different priors in App. C.2). The posterior parameters (α for our method, θ for the others) are initialized uniformly in r0.01, 2s (and normalized to sum to 1 for SO, FO and Bin). Finally, for MC the sigmoid’s slope parameter c is set to 100 and for Bin the number of voters drawn at each iteration is set to N“100. Code, available at https://github.com/vzantedeschi/StocMV, was implemented in pytorch [Paszke et al., 2019] and all experiments were run on a virtual machine with 8 vCPUs and 128Gb of RAM.

heading: 5.1 Comparison of exact and MC variants
text: For this set of experiments, we optimize Seeger’s Bound (Equation (1)) by (batch) Gradient Descent, for 1, 000 iterations and with learning rate equal to 0.1. We study the performance of our method on the binary classification two-moons dataset, with 2 features, 2 classes and N p0, 0.05q Gaussian noise, for which we draw n points for training, and 1, 000 points for testing. Figure 4 reports a comparison of exact and MC variants in terms of error, generalization bound and training time (in seconds). Increasing the number of MC draws T unsurprisingly allows to recover exact’s performance, and at lower computational cost for reasonable values ofM and T . In general, as MC is easily parallelizable, its training time has better dependence on n than exact’s one, however it increases with M at a worse rate. When the training sample is large enough (here for n ą 102), MC achieves exact’s errors and bounds even for T “ 1. We also observe that the error rates and bounds gradually degrade for higher values of M for both methods. This is due to the KL term increasing with M , as highlighted in Section 4, becoming a too strong regularization during training and making the bound looser.

heading: 5.2 Experiments on real benchmarks
text: We now compare the considered methods on real datasets and on two different scenarios, depending on the type of PAC-Bayesian bounds that are evaluated: When making use of data-independent priors, we chose as voters axis-aligned decision stumps, with thresholds evenly spread over the input space (10 per feature); When making use of data-dependent priors, we build Random Forests [Breiman, 2001] as set of voters, each with M“100 trees learned bagging n2 points and sampling ? d random features to ensure voter diversity, optimizing Gini impurity score and, unless stated otherwise, without bounding their maximal depth.
We consider several classification datasets from UCI [Dua and Graff, 2017], LIBSVM2 and Zalando [Xiao et al., 2017], of different number of features and of instances. Their descriptions and details on any pre-processing are provided in App. C.2. We train the models by Stochastic Gradient Descent (SGD) using Adam [Kingma and Ba, 2015] with p0.9, 0.999q running average coefficients, batch size equal to 1024 and learning rate equal to 0.1 with a scheduler reducing this parameter of a factor of 10 with 2 epochs patience. We fix the maximal number of epochs to 100 and patience equal to 25 for early stopping, and for MC we fix T “ 10 to increase randomness. We report the test errors and generalization bounds in Figure 5 (additional results are reported in the appendix, in Tables 1 and 2 and Figure 14): We compare the different methods on binary datasets and with data-independent priors in Figure 5a, and on multi-class datasets and with data-dependent priors in Figure 5b. First we notice that the bounds obtained by our method are consistently non vacuous and tighter than those obtained by the baselines on all datasets. Regarding the error rates, our method’s performance is generally aligned with the baselines, while it achieved error rates significantly lower than FO and SO on the perfectly separable two-moons dataset. Sensitivity to noise could explain why our method does not outperform the baselines on the studied real problems, as these usually present label and input noise. Indeed our learning algorithm optimizes the 01-loss, which does not distinguish points with margins close or far from 0.5 because of its discontinuity in Wθ “ 0.5. Preliminary results reported in App C.1 seem to confirm this supposition.
2https://www.csie.ntu.edu.tw/~cjlin/libsvm/
Finally, to gain a better understanding of the relation between base classifier strength and performance of the models obtained with the different methods, we further study their performance and generalization guarantees with varying voter strength. As hypothesis set, we learn Random Forests with 200 decision trees in total, as before, but for this experiment we bound their maximal depth between 1 and 10. Constraining the tree depth allows to indirectly control how well the voters fit the training set (as shown in Appendix, Figure 13). Following Lorenzen et al. [2019], we assess the voter strength by computing the expected accuracy of a random voter. All methods’ results improve overall when voters get stronger, even though FO at a slower pace. Notice that on the considered datasets SO is the most sensitive method, particularly suffering from weak base predictors. Our method generally provides test errors comparable with the best baselines and consistently tighter bounds.

heading: 6 Future work
text: We propose a stochastic version of the classical majority vote classifier, and we directly analyze and optimize its expected risk through the PAC-Bayesian framework. The benefits on the model accuracy of this direct optimization are however reduced in presence of input noise, and fostering robustness in noisy contexts is the subject of future work. Another potential improvement would consist in tackling the discussed looseness of our generalization bounds with increasing number of base predictors, by accounting for redundancy in the hypothesis space.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their constructive feedback and support. This work was partially funded by the French Project APRIORI ANR-18-CE23-0015. Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr). Pascal Germain is supported by the Canada CIFAR AI Chair Program, and the NSERC Discovery grant RGPIN-2020-07223. Benjamin Guedj acknowledges partial support by the U.S. Army Research Laboratory and the U.S. Army Research Office, and by the U.K. Ministry of Defence and the U.K. Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/R013616/1. Benjamin Guedj acknowledges partial support from the French National Agency for Research, grants ANR-18-CE40-0016-01 and ANR-18-CE23-0015-02.

Review summaries:
The authors propose an algorithm for learning a *stochastic* weighted majority vote classifier, by optimizing a (PAC-Bayesian) generalization bound. They consider Dirichlet distributions over classifiers as well as general measures, and derive analytical and numerical schemes, respectively, for optimizing both. They empirically evaluate the algorithm for several datasets and model classes (decision stumps and random forest). They also compare against deterministic weighted majority vote classifiers learned by optimizing Gibbs classifiers via existing PAC-Bayes bounds (first order, secord order, C-bounds, etc). The resulting stochastic predictor achieves competitive performance and bound tightness compared to ones obtained by minimizing alternative bounds.

This paper studies the generalization properties of the stochastic weighted majority vote (MV) classifiers, where the weight of the MV follows another distribution over MVs. The proposal allows a direct analysis of the risk of the stochastic MV instead of analyzing through other empirical quantities, which leads to tighter bounds. By taking the distribution over MVs to be Dirichlet distributions, the authors also provide an exact and an approximation method to optimize the parameters of the distribution.