{'fraction_non_alphanumeric': 0.03882657463330457, 'fraction_numerical': 0.014870831853017307, 'mean_word_length': 4.227779251790926, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Second Order PAC-Bayesian Bounds for the Weighted Majority Vote

We present a novel analysis of the expected risk of weighted majority vote in multiclass classification. The analysis takes correlation of predictions by ensemble members into account and provides a bound that is amenable to efficient minimization, which yields improved weighting for the majority vote. We also provide a specialized version of our bound for binary classification, which allows to exploit additional unlabeled data for tighter risk estimation. In experiments, we apply the bound to improve weighting of trees in random forests and show that, in contrast to the commonly used first order bound, minimization of the new bound typically does not lead to degradation of the test error of the ensemble.


Introduction
Weighted majority vote is a fundamental technique for combining predictions of multiple classifiers. In machine learning, it was proposed for neural networks by Hansen and Salomon [1990] and became popular with the works of Breiman [1996Breiman [ , 2001 on bagging and random forests and the work of Freund and Schapire [1996] on boosting. Zhu [2015] surveys the subsequent development of the field. Weighted majority vote is now part of the winning strategies in many machine learning competitions [e.g., Chen and Guestrin, 2016, Hoch, 2015, Puurula et al., 2014, Stallkamp et al., 2012. Its power lies in the cancellation of errors effect [Eckhardt and Lee, 1985]: when individual classifiers perform better than a random guess and make independent errors, the errors average out and the majority vote tends to outperform the individual classifiers.
A central question in the design of a weighted majority vote is the assignment of weights to individual classifiers. This question was resolved by Berend and Kontorovich [2016] under the assumptions that the expected error rates of the classifiers are known and their errors are independent. However, neither of the two assumptions is typically satisfied in practice.
When the expected error rates are estimated based on a sample, the common way of bounding the expected error of a weighted majority vote is by twice the error of the corresponding randomized classifier [Langford and Shawe-Taylor, 2002]. A randomized classifier, a.k.a. Gibbs classifier, associated with a distribution (weights) ρ over classifiers draws a single classifier at random at each prediction round according to ρ and applies it to make the prediction. The error rate of the randomized classifier is bounded using PAC-Bayesian analysis [McAllester, 1998, Seeger, 2002, Langford and Shawe-Taylor, 2002. We call this a first order bound. The factor 2 bound on the gap between the error of the weighted majority vote and the corresponding randomized classifier follows from the observation that an error by the weighted majority vote implies an error by at least a weighted half of the base classifiers. The bound is derived using Markov's inequality. While the PAC-Bayesian bounds for the randomized classifier are remarkably tight [Germain et al., 2009, Thiemann et al., 2017, the factor 2 gap is only tight in the worst-case, but loose in most real-life situations, where the weighted majority vote typically performs better than the randomized classifier rather than twice worse. The reason for looseness is that the approach does not take the correlation of errors into account.
In order to address the weakness of the first order bound, Lacasse et al. [2007] have proposed PAC-Bayesian C-bounds, which are based on Chebyshev-Cantelli inequality (a.k.a. one-sided Chebyshev's inequality) and take correlations into account. The idea was further developed by Laviolette et al. [2011], Germain et al. [2015], and Laviolette et al. [2017]. However, the C-bounds have two severe limitations: (1) They are defined in terms of classification margin and the second moment of the margin is in the denominator of the bound. The second moment is difficult to estimate from data and significantly weakens the tightness of the bounds [Lorenzen et al., 2019]. (2) The C-bounds are difficult to optimize. Germain et al. [2015] were only able to minimize the bounds in a highly restrictive case of self-complemented sets of voters and aligned priors and posteriors. In binary classification a set of voters is self-complemented if for any hypothesis h ∈ H the mirror hypothesis −h, which always predicts the opposite label to the one predicted by h, is also in H. A posterior ρ is aligned on a prior π if ρ(h) + ρ(−h) = π(h) + π(−h) for all h ∈ H. Obviously, not every hypothesis space is self-complemented and such sets can only be defined in binary, but not in multiclass classification. Furthermore, the alignment requirement only allows to shift the posterior mass within the mirror pairs (h, −h), but not across pairs. If both h and −h are poor classifiers and their joint prior mass is high, there is no way to remedy this in the posterior.
Lorenzen et al. [2019] have shown that for standard random forests applied to several UCI datasets the first order bound is typically tighter than the various forms of C-bounds proposed by Germain et al. [2015]. However, the first order approach has its own limitations. While it is possible to minimize the bound [Thiemann et al., 2017], it ignores the correlation of errors and minimization of the bound concentrates the weight on a few top classifiers and reduces the power of the ensemble. Our experiments show that minimization of the first order bound typically leads to deterioration of the test error.
We propose a novel analysis of the risk of weighted majority vote in multiclass classification, which addresses the weaknesses of previous methods. The new analysis is based on a second order Markov's inequality, P(Z ≥ ε) ≤ E Z 2 /ε 2 , which can be seen as a relaxation of the Chebyshev-Cantelli inequality. We use the inequality to bound the expected loss of weighted majority vote by four times the expected tandem loss of the corresponding randomized classifier: The tandem loss measures the probability that two hypotheses drawn independently by the randomized classifier simultaneously err on a sample. Hence, it takes correlation of errors into account. We then use PAC-Bayesian analysis to bound the expected tandem loss in terms of its empirical counterpart and provide a procedure for minimizing the bound and optimizing the weighting. We show that the bound is reasonably tight and that, in contrast to the first order bound, minimization of the bound typically does not deteriorate the performance of the majority vote on new data, but rather improves it.
We also present a specialized version of the bound for binary classification, which takes advantage of unlabeled data. It expresses the expected tandem loss in terms of a difference between the expected loss and half the expected disagreement between pairs of hypotheses. In the binary case the disagreements do not depend on the labels and can be estimated from unlabeled data, whereas the loss of a randomized classifier is a first order quantity, which is easier to estimate than the tandem loss. We note, however, that the specialized version only gives advantage over the general one when the amount of unlabeled data is considerably larger than the amount of labeled data. the empirical loss by E h∼ρ [L(h, S)]. To simplify the notation we use E D [·] as a shorthand for E (X,Y )∼D [·] and E ρ [·] as a shorthand for E h∼ρ [·].
Ensemble classifiers and majority vote Ensemble classifiers predict by taking a weighted aggregation of predictions by hypotheses from H. The ρ-weighted majority vote MV ρ predicts MV ρ (X) = arg max Y ∈Y h∈H∧(h(X)=Y ) ρ(h), where ties can be resolved arbitrarily.
If majority vote makes an error, we know that at least a ρ-weighted half of the classifiers have made an error and, therefore, This observation leads to the well-known first order oracle bound for the loss of weighted majority vote. Theorem 1 (First Order Oracle Bound).
PAC-Bayesian analysis can be used to bound E ρ [L(h)] in Theorem 1 in terms E ρ [L(h, S)], turning the oracle bound into an empirical one. The disadvantage of the first order approach is that E ρ [L(h)] ignores correlations of predictions, which is the main power of the majority vote.

New second order oracle bounds for the majority vote
The key novelty of our approach is using a second order Markov's inequality: for a non-negative random variable Z and ε > 0, we have P(Z ≥ ε) = P Z 2 ≥ ε 2 ≤ ε −2 E Z 2 . We define the tandem loss of two hypotheses h and h by The tandem loss counts an error on a sample (X, Y ) only if both h and h err on (X, Y ). The following lemma relates the expectation of the second moment of the standard loss to the expected tandem loss. We use the shorthand A proof is provided in Appendix A. A combination of second order Markov's inequality with Lemma 2 leads to the following result. Theorem 3 (Second Order Oracle Bound). In multiclass classification (1) Proof. By second order Markov's inequality applied to Z = E ρ [1(h(X) = Y )] and Lemma 2:

A specialized bound for binary classification
We provide an alternative form of Theorem 3, which can be used to exploit unlabeled data in binary classification. We denote the expected disagreement between hypotheses h and h by D(h, h ) = E D [1(h(X) = h (X))] and express the tandem loss in terms of standard loss and disagreement.
Lemma 4. In binary classification A proof of the lemma is provided in Appendix A. The lemma leads to the following result.
Theorem 5 (Second Order Oracle Bound for Binary Classification). In binary classification (2) Proof. The theorem follows by plugging the result of Lemma 4 into Theorem 3.
The advantage of the alternative way of writing the bound is the possibility of using unlabeled data for estimation of D(h, h ) in binary prediction (see also Germain et al., 2015). We note, however, that estimation of E ρ 2 [D(h, h )] has a slow convergence rate, as opposed to E ρ 2 [L(h, h )], which has a fast convergence rate. We discuss this point in Section 4.4.

Comparison with the first order oracle bound
From Theorems 1 and 5 we see that in binary classification the second order bound is tighter when Below we provide a more detailed comparison of Theorems 1 and 3 in the worst, the best, and the independent cases. The comparison only concerns the oracle bounds, whereas estimation of the oracle quantities, In this case the second order bound is an order of magnitude tighter than the first order.

The independent case
Assume that all hypotheses in H make independent errors and have the same error rate, ) and the first order bound is 2E ρ [L(h)] = 2L(h). Assuming that M is large, so that we can ignore the second term in the second order bound, we obtain that it is tighter for L(h) < 1/2 and looser otherwise. The former is the interesting regime, especially in binary classification.

Comparison with the oracle C-bound
The C-bound [Germain et al., 2015] is an alternative second order bound based on Chebyshev-Cantelli inequality (Theorem C.13 in the appendix). Germain et al. [2015, Theorem 11] and Laviolette et al.
[2017] write their bounds in terms of the margin of the majority vote classifier. In order to facilitate the comparison with our results we provide an alternative form of a C-bound in terms of the tandem loss.
In Appendix D we provide a direct derivation of Theorem 6 from Chebyshev-Cantelli inequality. In Appendix C we show that the second order Markov's inequality behind Theorem 3 is a relaxation of Chebyshev-Cantelli inequality. Therefore, the oracle C-bounds in Theorem 6 and by Germain et al. [2015] are always at least as tight as the second order bound in Theorem 3. In particular, Germain et al. show that if the classifiers make independent errors and their error rate is identical and below 1/2, the C-bound converges to zero with the growth of the number of classifiers, whereas, as we have shown above, the bound in Theorem 3 only converges to 4L(h) 2 . However, the C-bound has E ρ 2 [L(h, h )] in the denominator, which comes as a significant disadvantage in its estimation from data and minimization [Lorenzen et al., 2019], as we also show in our empirical evaluation.

Second order PAC-Bayesian bounds for the weighted majority vote
We apply PAC-Bayesian analysis to transform oracle bounds from the previous section into empirical bounds. The results are based on the following two theorems, where we use KL(ρ π) to denote the Kullback-Leibler divergence between distributions ρ and π and kl(p q) to denote the Kullback-Leibler divergence between two Bernoulli distributions with biases p and q.
Theorem 7 (PAC- Bayes-kl Inequality, Seeger, 2002). For any probability distribution π on H that is independent of S and any δ ∈ (0, 1), with probability at least 1 − δ over a random draw of a sample S, for all distributions ρ on H simultaneously: The next theorem provides a relaxation of PAC-Bayes-kl inequality, which is more convenient for optimization. The upper bound is due to Thiemann et al. [2017] and the lower bound follows by an almost identical derivation, see Appendix E. Both results are based on the refined Pinsker's bound of the kl-divergence. Since both the upper and the lower bound are deterministic relaxations of PAC-Bayes-kl, they hold simultaneously with no need to take a union bound over the two statements.
Theorem 8 (PAC-Bayes-λ Inequality, Thiemann et al., 2017). For any probability distribution π on H that is independent of S and any δ ∈ (0, 1), with probability at least 1 − δ over a random draw of a sample S, for all distributions ρ on H and all λ ∈ (0, 2) and γ > 0 simultaneously:

A general bound for multiclass classification
We define the empirical tandem losŝ and provide a bound on the expected loss of ρ-weighted majority vote in terms of the tandem losses.
It is also possible to use PAC-Bayes-kl to bound E ρ 2 [L(h, h )] in Theorem 3, which actually gives a tighter bound, but the bound in Theorem 9 is more convenient for minimization. Tolstikhin and Seldin [2013] have shown that for a fixed ρ the expression in Theorem 9 is convex in λ and has a closed-form minimizer. In Appendix F we show that for fixed λ and S the bound is convex in ρ. Although in our applications S is not fixed and the bound is not necessarily convex in ρ, a local minimum can still be efficiently achieved by gradient descent. A bound minimization procedure is provided in Appendix G.

A specialized bound for binary classification
We define the empirical disagreement where S = {X 1 , . . . , X m }. The set S may overlap with the labeled set S, however, S may include additional unlabeled data. The following theorem bounds the loss of weighted majority vote in terms of empirical disagreements. Due to possibility of using unlabeled data for estimation of disagreements in the binary case, the theorem has the potential of yielding a tighter bound when a considerable amount of unlabeled data is available.
Theorem 10. In binary classification, for any probability distribution π on H that is independent of S and S and any δ ∈ (0, 1), with probability at least 1 − δ over a random draw of S and S , for all distributions ρ on H and all λ ∈ (0, 2) and γ > 0 simultaneously: Proof. The theorem follows by using the upper bound in equation (4) to bound E ρ [L(h)] and the lower bound in equation (5) to bound E ρ 2 [D(h, h )] in Theorem 5. We replace δ by δ/2 in the upper and lower bound and take a union bound over them.
in Theorem 5 gives a tighter bound, but the bound in Theorem 10 is more convenient for minimisation. The minimization procedure is provided in Appendix G.

Ensemble construction
Thiemann et al. [2017] have proposed an elegant way of constructing finite data-dependent hypothesis spaces that work well with PAC-Bayesian bounds. The idea is to generate multiple splits of a data set S into pairs of subsets For pairs of hypotheses (h, h ) we use the overlaps of their validation sets S h ∩ S h to calculate an unbiased estimate of their tandem loss,L(h, h , S h ∩ S h ), which replacesL(h, h , S) in the bounds. The sample size n is then replaced by n min = min h,h (S h ∩ S h ).

Comparison of the empirical bounds
We provide a high-level comparison of the empirical first order bound (FO), the new empirical second order bound based on the tandem loss (TND, Theorem 9), and the new empirical second order bound based on disagreements (DIS, Theorem 10). The two key quantities in the comparison are the sample size n in the denominator of the bounds and fast and slow convergence rates for the standard (first order) loss, the tandem loss, and the disagreements. Tolstikhin and Seldin [2013] have shown that if we optimize λ for a given ρ, the PAC-Bayes-λ bound in equation (4) can be written as n .
This form of the bound, used by McAllester [2003], is convenient for explanation of fast and slow rates. If E ρ [L(h, S)] is large, then the middle term on the right hand side dominates the complexity and the bound decreases at the rate of 1/ √ n, which is known as a slow rate. If E ρ [L(h, S)] is small, then the last term dominates and the bound decreases at the rate of 1/n, which is known as a fast rate.
FO vs. TND The advantage of the FO bound is that the validation sets S h available for estimation of the first order lossesL(h, S h ) are larger than the validation sets S h ∩ S h available for estimation of the tandem losses. Therefore, the denominator n min = min h |S h | in the FO bound is larger than the denominator n min = min h,h (S h ∩ S h ) in the TND bound. The TND disadvantage can be reduced by using data splits with large validation sets S h and small training sets T h , as long as small training sets do not overly impact the quality of base classifiers h. Another advantage of the FO bound is that its complexity term has KL(ρ π), whereas the TND bound has 2 KL(ρ π). The advantage of the TND bound is that and, therefore, the convergence rate of the tandem loss is typically faster than the convergence rate of the first order loss. The interplay of the estimation advantages and disadvantages, combined with the advantages and disadvantages of the underlying order oracle bounds discussed in Section 3.2, depends on the data and the hypothesis space.
TND vs. DIS The advantage of the DIS bound relative to the TND bound is that in presence of a large amount of unlabeled data the disagreements D(h, h ) can be tightly estimated (the denominator m is large) and the estimation complexity is governed by the first order term, E ρ [L(h)], which is "easy" to estimate, as discussed above. However, the DIS bound has two disadvantages. A minor one is its reliance on estimation of two quantities, , which requires a union bound, e.g., replacement of δ by δ/2. A more substantial one is that the disagreement term is desired to be large, and thus has a slow convergence rate. Since slow convergence rate relates to fast convergence rate as 1/ √ n to 1/n, as a rule of thumb the DIS bound is expected to outperform TND only when the amount of unlabeled data is at least quadratic in the amount of labeled data, m > n 2 .

Empirical evaluation
We studied the empirical performance of the bounds using standard random forests [Breiman, 2001] on a subset of data sets from the UCI and LibSVM repositories [Dua andGraff, 2019, Chang andLin, 2011]. An overview of the data sets is given in Table H.1 in the appendix. The number of points varied from 3000 to 70000 with dimensions d < 1000. For each data set we set aside 20% of the data for a test set S test and used the remaining data, which we call S, for ensemble construction and computation of the bounds. Forests with 100 trees were trained until leaves were pure, using the Gini criterion for splitting and considering √ d features in each split. We made 50 repetitions of each experiment and report the mean and standard deviation. In all our experiments π was uniform and δ = 0.05. We present two experiments: (1) a comparison of tightness of the bounds applied to uniform weighting, and (2) a comparison of weighting optimization the bounds. Additional experiments, where we explored the effect of using splits with increased validation and decreased training subsets, as suggested in Section 4.4, and where we compared the TND and DIS bounds in presence of unlabeled data, are described in Appendix H.
Uniform weighting In Figure 1 we compare tightness of FO, C1 and C2 (the two forms of C-bound by Germain et al., 2015), the C-tandem bound (CTD, Theorem 6), and TND applied to uniformly weighted random forests on a subset of data sets. The right three plots are multiclass datasets, where C1 and C2 are inapplicable. The outcomes for the remaining datasets are reported in Figures H.4 and H.5 in the appendix. Since no optimization was involved, we used the PAC-Bayes-kl in the first and second order bounds, which is tighter than using PAC-Bayes-λ. The TND bound was the tightest for 5 out of 16 data sets, and provided better guarantees than the C-bounds for 4 out of 7 binary data sets. In most cases, the FO-bound was the tightest.
Optimization of the weighting We compared the loss on the test set S test and tightness after using the bounds for optimizing the weighting ρ. As already discussed, the C-bounds are not suitable for  Figure 1: Test risk (black) and the bounds for a uniformly weighted random forest on a subset of binary (left) and multiclass (right) datasets. Plots for the remaining datasets are provided in Figures H.4 and H.5 in the appendix.   Table H.6 in the appendix. While both bounds tighten with optimization, we observed that optimization of FO considerably weakens the performance on S test for all datasets, whereas optimization of TND did not have this effect and in some cases even improved the outcome. Figure 2b shows optimized distributions for two sample data sets. It is clearly seen that FO placed all the weight on a few top trees, while TND hedged the bets on multiple trees. The two figures demonstrate that the new bound correctly handled interactions between voters, as opposed to FO.

Discussion
We have presented a new analysis of the weighted majority vote, which provides a reasonably tight generalization guarantee and can be used to guide optimization of the weights. The analysis has been applied to random forests, where the bound can be computed using out-of-bag samples with no need for a dedicated hold-out validation set, thus making highly efficient use of the data. We have shown that in contrary to the commonly used first order bound, minimization of the new bound does not lead to deterioration of the test error, confirming that the analysis captures the cancellation of errors, which is the core of the majority vote.

A Proof of Lemmas 2 and 4
Proof of Lemma 2.
Proof of Lemma 4. Picking from (A.6), we have By taking expectation with respect to D on both sides and applying Lemma 2 to the left hand side, we obtain: B An alternative derivation of Theorems 1 and 3 using relaxations of the indicator function In this section, we provide an alternative derivation of Theorems 1 and 3 using relaxations of the indicator function. The alternative derivation may provide additional intuition about the method and this is how we initially have arrived to the results.
As explained in Section 2, if majority vote makes an error, then at least a ρ-weighted half of the classifiers have made an error. Therefore, we have (MV ρ (X), Y ) ≤ 1(E ρ [1(h(X) = Y )] ≥ 0.5).
The first order bound can be derived from a first order relaxation of the indicator function. For any w ∈ [0, 1] we have 1(w ≥ 0.5) ≤ 2w, see Figure B.
which gives the result in Theorem 1.
The second order bound can be derived from a second order relaxation of the indicator function. We use the inequality 1(w ≥ 0.5) ≤ 4w 2 , which holds for all w ∈ [0, 1], see Figure B.3. As before, we where the last equality is by Lemma 2.

C Relation between second order Markov's and Chebyshev-Cantelli inequalities
In this section we show that second order Markov's inequality is a relaxation of Chebyshev-Cantelli inequality. In order to emphasize the relation between the proofs of Theorems 1 and 3 in the body and in the previous section, we provide a direct derivation of Markov's and second order Markov's inequalities using relaxations of the indicator function. For any non-negative random variable X and ε > 0 we have: We use these inequalities to recover the well-known Markov's inequality and prove the second order Markov's inequality. Theorem C.11 (Markov's Inequality). For a non-negative random variable X and ε > 0 ε .
Theorem C.12 (Second order Markov's inequality). For a non-negative random variable X and ε > 0 Proof.
We also cite Chebyshev-Cantelli inequality without a proof. For a proof see, for example, Devroye et al. [1996]. Theorem C.13 (Chebyshev-Cantelli inequality). For a real-valued random variable X and ε > 0 Finally, we show that second order Markov's inequality is a relaxation of Chebyshev-Cantelli inequality.
Proof. We show that inequality (C.8) is always at least as tight as inequality (C.7). The inequality (C.7) is only non-trivial when E [X] < ε, so for the comparison we can assume that E [X] < ε. By (C.8) we then have: Thus, we need to compare This is equivalent to the following row of comparisons: which completes the proof.

D A proof of Theorem 6
We provide a direct proof of Theorem 6 using Chebyshev-Cantelli inequality.
Proof. We apply Chebyshev-Cantelli inequality to E ρ [h(X) = Y ]: Note that by applying Lemma 4 we can also write the bound in terms of the first order loss and disagreements:

F Positive semi-definiteness of the matrix of empirical tandem losses
In Lemma F.15 below we show that if the empirical tandem losses are evaluated on the same set S, then the matrix of empirical tandem lossesL tnd with entries (L tnd ) h,h =L(h, h , S) is positive semi-definite. This implies that for a fixed λ the bound in Theorem 9 is convex in ρ, because in this case E 2 ρ [L(h, h , S)] = ρ TL tnd ρ is convex in ρ and KL(ρ π) is always convex in ρ. (We note, however, that the bound is not necessarily jointly convex in ρ and λ and, therefore, alternating minimization of the bound may still converge to a local minimum. While Thiemann et al. [2017] derive conditions under which the PAC-Bayes-λ bound for the first order loss is quasiconvex, such analysis of the bound for the second order loss would be more complicated.) In Section F.1 we then provide an example showing that if the tandem losses are evaluated on different sets, as it happens in our case, where the entries are (L tnd ) h,h =L(h, h , S h ∩ S h ), then the matrix of tandem losses is not necessarily positive semi-definite. Therefore, in our case alternating minimization of the bound is only expected to converge to a local minimum. Lemma F.15. Given M hypotheses and data S = {(X 1 , Y 1 ), . . . , (X n , Y n )}, the M × M matrix of empirical tandem lossesL tnd with entries (L tnd ) h,h =L(h, h , S) is positive semi-definite.

Proof. Define a vector of empirical losses by hypotheses in H on a sample
Thus, the matrix of empirical tandem losses can be written as a mean of outer productŝ and is, therefore, positive semi-definite.

F.1 Non positive semi-definite example
When the empirical tandem losses are estimated on different subsets of the data rather than a common set S, as in the case of out-of-bag samples, where we takeL(h, h , S h ∩ S h ), the resulting matrix of empirical tandem losses is not necessarily positive semi-definite. Consider the following example with 2 points, 3 hypotheses, and the following losses: If we the compute tandem loss for h 1 and h 2 on the first point and the tandem loss for h 1 and h 3 and for h 2 and h 3 on the second point, and the tandem losses of hypotheses with themselves on all the points, then we haveL This matrix is not positive semi-definite. It has eigenvalues −0.5, 0.5, and 1.5.

G Gradient-based minimization of the bounds
This section gives details on the optimization of the bounds in Theorems 9 and 10. First, we consider the bound in Theorem 9 and provide a closed form solution for the parameter λ given ρ as well as the gradient of the bound w.r.t. ρ for fixed λ. Then we give the closed form solutions for the parameters λ and γ given ρ and the gradient w.r.t. ρ for fixed λ and γ for the bound in Theorem 10. After that, we describe the alternating minimization procedure we applied for optimization in our experiments.

G.1 Minimization of the bound in Theorem 9
Optimal λ given ρ Given ρ, the optimal λ in Theorem 9 can be computed following Tolstikhin and Seldin [2013] and Thiemann et al. [2017], because the optimization problem is the same: Gradient with respect to ρ given λ Next we calculate the gradient for minimizing the bound in Theorem 9 with respect to ρ under fixed λ. The minimization is equivalent to minimizing f (ρ) = E ρ 2 [L(h, h , S)] + 2 λn KL(ρ π) under the constraint that ρ is a probability distribution. Let (∇f ) h for h ∈ H denote the component of the gradient corresponding to hypothesis h. We also useL tnd to denote the matrix of empirical tandem losses and ln ρ π to denote the vector with entry corresponding to hypothesis h being ln ρ(h) π(h) . We have:

G.2 Minimization of the bound in Theorem 10
Optimal λ and γ given ρ The optimal λ can be computed as above, because the optimization problem is the same. The only difference is that we have δ/2 instead of δ: KL(ρ π)+ln 4 √ n δ + 1 + 1 .
Minimization of the bound in Theorem 10 with fixed ρ with respect to γ is equivalent to minimizing Gradient with respect to ρ Minimization of the bound with respect to ρ for fixed λ and γ is equivalent to constrained minimization of f (ρ) = 2aE ρ [L(h, S)]−bE ρ 2 [D(h, h , S )]+2c KL(ρ π), where a = 1 1−λ/2 , b = 1 − γ/2, and c = 1 λ(1−λ/2)n + 1 γm , and the constraint is that ρ is a probability distribution. We useL to denote the vector of empirical losses of h ∈ H andD to denote the matrix of empirical disagreements. We have:

G.3 Alternating optimization procedure
In our experiments, we applied an alternating optimization procedure to improve the weighting ρ of the ensemble members as well as the parameters λ and, when considering the disagreement, γ.
Let M = |H| denote the number of ensemble members. We parameterize ρ byρ ∈ R M with ρ = softmax(ρ), where ρ i = expρi M j=1 expρj for i = 1, . . . , M . This ensures that ρ is a proper probability distribution and allows us to apply unconstrained optimization in the adaption of ρ. Because we are using uniform priors π and due to the regularization in terms of the Kullback-Leibler divergence between ρ and π in the bounds, excluding ρ i ∈ {0, 1} for each i = 1, . . . , B is not a limitation.
Starting from uniform ρ and the corresponding optimal λ and, if applicable, γ, we looped through the following steps: We applied iterative gradient-based optimization of ρ parameterized byρ until the bound did not improve for 10 iterations. Then we computed the optimal λ and, in the case of the DIS bound, γ for the optimized ρ. We stopped if the change in the bound was smaller than 10 −9 . We applied iRProp + for the gradient based optimization, a first order method with adaptive individual step sizes [Igel andHüsken, 2003, Florescu andIgel, 2018].

H Experiments
This section provides details on the data sets used in the experiments and provides details, additional figures, and numerical values for the empirical evaluations: empirical evaluation of the bounds using a standard random forest with uniform weighting (Section H.2, expanding the first experiment and Figure 1 in the body), and optimization of the weighting of the trees (Section H.3, expanding the second experiment and Figure 2 in the body). We also include additional experiments with reduced bagging, where we use less data for construction of each tree in order to leave larger out-of-bag sets for improved estimation of the second order quantities. The diagram below provides an overview of the experiments with references to the relevant subsections.  For each experiment, we report the mean and standard deviations of 50 runs. We used standard random forests trained on S (80% of the data) and evaluated on test set S test (20%). 100 trees were used for each data set, and √ d features were considered in each split. The bounds were evaluated on the OOB data, with uniform π and δ = 0.05.
Furthermore, Section H.5 presents an empirical evaluation of the DIS bound in the setting with only a small amount of labeled data available and large amounts of unlabeled data. For this experiment, we reserved part of S as unlabeled data and evaluated FO, TND and DIS. We varied the split between labeled training data and unlabeled data and report the means and standard deviations of 20 runs for each split.

H.1 Data sets
As mentioned, we considered data sets from the UCI and LibSVM repositories [Dua andGraff, 2019, Chang andLin, 2011], as well as FASHION-MNIST from Zalando Research 2 . We used data sets with size 3000 ≤ N ≤ 70000 and dimension d ≤ 1000. These relatively large data sets were chosen in order to provide meaningful bounds in the standard bagging setting, where individual trees are trained on n = 0.8N randomly subsampled points with replacement and the size of the overlap of out-of-bag sets is roughly n/9. An overview of the data sets is given in Table H.1. For all experiments, we removed patterns with missing entries and made a stratified split of the data set. For data sets with a training and a test set (SVMGUIDE1, SPLICE, ADULT, W1A, MNIST, SHUTTLE, PENDIGITS, PROTEIN, SATIMAGE, USPS) we combined the training and test sets and shuffled the entire set before splitting.

H.2 Standard uniformly weighted random forests
This section provides additional figures and numerical values of the bounds computed for the standard uniformly weighted random forest using bagging ( Figure 1 in the body), as well as additional statistics for the experiments.  TND is tightest for 2 out of 7 binary data sets and 3 out of 10 multiclass data sets, while FO is tightest for the rest. Figure H.6 plots the ratio between the empirical disagreement E ρ 2 [D(h, h , S h ∩ S h )] and the empirical randomized loss E ρ [L(h, S h )] versus the ratio between the TND and FO bounds. This figure shows that TND bound tends to be tighter than FO when the disagreement is large in relation to the randomized loss. Since the amounts of data |S h ∩ S h | available for estimation of the tandem losses are considerably smaller than the amounts of data |S h | available for estimation of the first order losses, the empirical disagreement has to be considerably larger than the empirical loss for TND to take the advantage over FO. This is in agreement with the discussion provided in Sections 3.2 and 4.4.
Comparing TND to the other second order bounds, we see that TND is tighter (or almost as tight) in all cases, except for MUSHROOM, where C1 is tighter. This is due to C1 being given in terms of an upper bound on E ρ [L(h)] and a lower bound on E ρ 2 [D(h, h )]. With the lower bound being almost zero, we have C1 ≈ 2 FO and since the disagreement is very low, TND ≈ 4 FO. We note that even though C1 is tighter than TND in this case, it is still much weaker than FO, because, as it has been discussed in Section 3.2, problems with low disagreement are not well-suited for second order bounds.  and Hüsken, 2003], see Appendix G. We denote the weights after optimization of FO and TND by ρ * FO and ρ * TND , respectively. Figures H.7 and H.8 show the bounds before and after optimization for binary and multiclass data sets respectively. The FO bound achieves higher reduction after minimization, however, as illustrated in both figures and Figure 2 in the body, this improvement comes at the cost of considerable increase of the test loss L(M V ρ * FO , S test ). The latter happens because FO places most of the posterior mass on a few top classifiers and diminishes the power of the ensemble, see Figure 2b. The improvement of the TND after minimization is more modest, but on a highly positive side it does not degrade the classifier. Table H.6 shows the numerical values used in Figure 2a.

H.4 Random forests with reduced bagging vs. full bagging with uniform and optimized weights
The TND bound depends on the size of overlaps S h ∩ S h , which are used to estimate the tandem losses and define the denominator of the bound. In order to ensure that the overlaps S h ∩ S h are not too small, it might be beneficial to generate splits with |S h | of at least (2/3)n, so that |S h ∩ S h | is at least n/3. In our application to random forests we reduce the number of sampled points in bagging from n to n/2, which increases the number of out-of-bag samples |S h | from roughly n/3 to roughly (2/3)n and the overlaps from roughly n/9 to n/3. We show that the corresponding decrease in |T h | leads to a relatively small decrease of prediction quality of individual trees and improves the bounds.
We call the bagging procedure that samples n points with replacement a standard bagging or full bagging and the procedure that samples n/2 points reduced bagging. This section presents results for random forests trained with reduced bagging, including comparisons to the full bagging setting. Figure H.13 compares the test risk in the full bagging and the reduced bagging settings with uniform and optimized weights. In both uniform and optimized weights we see a limited increase (and in a few cases even a small decrease) in test risk when reducing the amount of data sampled in bagging, indicating that reduced bagging has relatively minor impact on the quality of a uniformly weighted ensemble. At the same time, Figures H. 14, H.9, H.10, H.11, and H.12 show that the bounds are improved in most cases, sometimes considerably.

H.5 DIS bound vs. TND bound in presence of unlabeled data
In this section we compare the tightness of the TND and DIS bounds in a setting, where a lot of unlabeled data is available.
We considered the largest binary data sets (N > 8000) from  Figure H.15 plots the test risk and FO, TND and DIS bounds as a function of r. For each data set, the mean and standard deviation over 20 runs are plotted. In agreement with the discussion in Section 4.4, DIS had the highest advantage over TND when the amount of unlabeled data relative to labeled data was the largest. As the amount of unlabeled data relative to labeled data was decreasing the difference between the bounds became smaller, with TND eventually overtaking DIS in most cases. 1.8 Figure H.13: Median, 25%, and 75% quantiles of the ratio between the test risk in the reduced and full bagging settings with uniform and optimized weights ρ * TND . Results on MUSHROOM and SHUTTLE are left out, as the test risk is 0 in some cases.   Figure H.14: Median, 25%, and 75% quantiles of the ratio between the TND bound in the reduced and full bagging settings with uniform and optimized weights ρ * TND .    Table H.3: Statistics for each data set when using bagging. We use the following short-hand:     Table H.7: Test risks computed when using different bounds for optimizing ρ for random forest trained using reduced bagging. Best risk achieved overall is marked in bold, while best risk achieved by optimization is marked with underline.