{'fraction_non_alphanumeric': 0.03603838871841745, 'fraction_numerical': 0.009401318796108898, 'mean_word_length': 4.27842866988284, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, '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}}
Ensemble Validation: Selectivity has a Price, but Variety is Free

Suppose some classifiers are selected from a set of hypothesis classifiers to form an equally-weighted ensemble that selects a member classifier at random for each input example. Then the ensemble has an error bound consisting of the average error bound for the member classifiers, a term for selectivity that varies from zero (if all hypothesis classifiers are selected) to a standard uniform error bound (if only a single classifier is selected), and small constants. There is no penalty for using a richer hypothesis set if the same fraction of the hypothesis classifiers are selected for the ensemble.


I. INTRODUCTION
In machine learning, ensemble methods combine multiple classifiers into a single classifier. Ensemble methods include bagging [1], boosting [2], [3], forests (of decision trees) [4], [5], [6], and stacking [7]. In this paper, we focus on the Gibbs ensemble classifier with a uniform distribution over its member classifiers. To classify an example, a Gibbs classifier chooses one of the classifiers from its ensemble at random and applies that classifier to the example. Our goal is to develop out-ofsample error bounds for Gibbs classifiers.
The PAC-Bayes technique [8], [9], [10] bounds the average out-of-sample error rate over a set of classifiers. It applies to the following setup: start with a prior distribution over a set of hypothesis classifiers, use a set of in-sample data to select a posterior distribution over classifiers, and use that posterior as the basis for an ensemble classifier. PAC-Bayes error bounds include a term for selectivity that grows as the Kullback-Leibler (KL) divergence [11] (or another divergence [10]) between the posterior and prior grows and a term that grows with the number of in-sample examples.
For equally-weighted Gibbs ensemble classifiers and a uniform prior, the bounds in this paper remove the term that grows with sample size, showing that those ensembles have essentially the same error bound (up to small constants) as single classifiers selected from hypothesis sets. So, for example, essentially the same error bound applies to selecting 100 classifiers for an ensemble from a set of 10,000 classifiers as to selecting a single classifier from a set of 100, even though there are 10 000 100 ways to choose in the first case and only 100 in the second. In fact, the same bounds apply to selecting 1% of the classifiers for an ensemble from an arbitrarily large hypothesis class.
The bounds in this paper allow validation of ensemble classifiers using training data for other ensemble classifiers.
For example, suppose we have a set of in-sample data, form different train-validation splits, for each split use its training data to select a classifier from a very large or even infinite class and use its validation data to estimate the classifier's error rate, then use validation error rate or other criteria to select an ensemble. Then we can apply the bounds from this paper, setting hypothesis class size to the number of splits and data set size to the number of validation examples in each split.
Section II briefly reviews uniform and nearly uniform error bounds. Section III shows how to infer ensemble error bounds from uniform and nearly uniform error bounds. Section IV shows how to expand nearly uniform error bounds into telescoping error bounds. Section V shows how to select parameters for telescoping error bounds to make the price of variety independent of the hypothesis set size and the number of in-sample examples. Section VI concludes with a discussion of how to apply the error bounds we derive.

II. UNIFORM AND NEARLY UNIFORM VALIDATION
Let's begin with a brief review of uniform validation. Let m be the number of classifiers in the hypothesis class. Let n be the number of validation examples, with known inputs and labels, available for each classifier in the hypothesis class. Assume the validation examples for each classifier are drawn independently of any data used to choose the classifier for the class and are drawn i.i.d. from an unknown input-label distribution D. (The validation data may be the same, partially overlap, or not overlap at all for different classifiers in the class.) For each classifier i ∈ {1, . . . , m} in the hypothesis class, let p i be the error rate of classifier i over its validation data. Let p * i be the (unknown) error rate of classifier i over D. Call p * i the actual error rate or out-of-sample error rate of classifier i. Applying Hoeffding bounds [12], for each classifier i, for δ > 0: Substitute δ m for δ: Use the sum bound for the probability of a union to derive a uniform bound: This is the standard PAC error bound for uniform convergence of classifier validation error rates to their actual error rates, from Vapnik and Chervonenkis (VC) [13]. Uniform validation requires that, with probability at least 1 − δ, every classifier in the class has a successful validation in the sense that its validation error rate is close to its actual error rate. In contrast, nearly uniform validation [14] allows some classifiers to have validation error rates far from their actual error rates. Call these misvalidations.
To derive nearly uniform error bounds, select a number j of misvalidations to allow. The probability of more than j misvalidations is maximized if there are exactly j + 1 misvalidations in each case of any misvalidations. For j = 0, this is just the sum bound for the union of probabilities: the probability of at least one misvalidation is maximized if there is exactly one misvalidation when there is any misvalidationany more and the probability of misvalidation will be less than the sum of individual classifier misvalidation probabilities. For j = 1, which allows a single misvalidation, the greatest probability of two or more misvalidations is achieved if any misvalidation that occurs is accompanied by exactly one more.
So the probability of more than j misvalidations is at most 1 j+1 of the probability of one or more misvalidations. Apply this rule to produce a nearly uniform version of Inequality 1: We will use some non-integer values for j. If we allow a non-integer number j of misvalidations, then the worst case is for ⌊j + 1⌋ misvalidations to occur simultaneously if there are more than zero misvalidations. Since j < ⌊j + 1⌋, we can use j in place of j +1 on the RHS of Inequality 2 to accommodate non-integer j values.
Substitute δj for δ: This is a nearly uniform PAC error bound. Comparing it to the uniform error bound in Inequality 1, in exchange for allowing j misvalidations, we can subtract ln j from the numerator in the square root.
III. VALIDATION FOR AN ENSEMBLE Let S be a subset of the m hypothesis classifiers. Refer to S as the selected classifiers or the ensemble. Classifiers may be selected for the ensemble based on their validation error rates. Let s = |S|.
Our goal is to derive an error bound for the average out-ofsample error rate over the ensemble classifiers. Let E S be the expectation over ensemble classifiers. Specifically, let E S p i be the average validation error rate, and let E S p * i be the average out-of-sample error rate. (Then E s p * i is the out-of-sample error rate of a Gibbs classifier based on a uniform distribution over the ensemble classifiers.) For an average bound based on uniform bounds, multiply both sides of the inequality in the probability from Inequality 1 by 1 s : and Now consider an average bound based on nearly uniform bounds. In the worst case (with the nearly uniform bound holding), the j allowed misvalidations occur; they are all for classifiers in the ensemble, and those classifiers have the least validation error rates in the ensemble and out-of-sample error rates of one. In that case, each misvalidation adds 1 s to the average error bound, minus the contribution it would have made to the bound if not for misvalidation: Let L index the j classifiers in S with the least validation error rates. Then we have: Separate the terms in sums and collect the terms in square roots to get: To produce a bound on the difference between average validation error rate and average out-of-sample error rate before observing the validation error rates, consider that in the worst case ∀i ∈ L : p i = 0, so E L p i = 0: Then we can rewrite Inequality 5 as

IV. TELESCOPING BOUNDS
In the bound in Inequality 6, we have assumed that misvalidated classifiers have error rate one, regardless of their validation error rates, because one is a trivial upper bound on outof-sample error rate. Instead, we could use a loose bound for the misvalidations that is tighter than the trivial bound. Since this "backstop" uniform bound must hold simultaneously with our original nearly uniform bound, we have to split δ between them and appeal to a sum bound on the probability of either of these bounds failing. Let δ 1 + δ 2 = δ. Then we have: whereǫ(0, δ 2 ) is the backstop uniform bound. Extending this idea produces "telescoping" bounds: a uniform bound and a sequence of nearly uniform bounds, each one tighter but allowing more misvalidations than the previous one. Each bound'sǫ applies to the misvalidations allowed by the next bound but not by the present one. The final bound applies to the classifiers that are not misvalidated. Listing the bounds from right to left (it is math, after all) gives the telescoping bound: We can optimize this bound by selecting j 1 , . . . , j t and δ 1 , . . . , δ t+1 through dynamic programming. For details, refer to Appendix A.

V. THE PRICE OF SELECTIVITY
Now we apply telescoping bounds to ensembles to prove that for all c > 0, there is an ensemble error bound with ǫ at most 1 √ 2n ln m s + ln 1 δ e c e c − 1 For c = 3, for example, this gives The term ln m s can be viewed as a price for selectivity: for a single classifier (s = 1), it gives the ln m term from the standard VC error bounds [13] for selecting one classifier from a size-m hypothesis class (our Inequality 1). For an average over all classifiers in the hypothesis class (s = m), it gives ln m m = ln 1 = 0, which is consistent with a VC error bound for a hypothesis class consisting of a single hypothesis -the Gibbs classifier composed of all hypothesis classifiers. (For more details refer to Bax [15].) To prove the result, begin with the telescoping bound range from Inequality 7: Recall thatǫ For convenience, define j 0 = s. Now use i as the index of summation over terms in ǫ t (instead of over j values within each term). Then Let c > 0 be a constant we select. Let t be the minimum integer such that e tc ≥ √ 2n, in other words, t = ⌈ 1 2c ln 2n⌉.
Substitute these values into Inequality 10 to get a bound range, and call it ǫ * : By the definition of t, the last term is at most 1 Substituting these values into Equation 11, For the first sum, apply the standard inequality: ∀0 ≤ x < 1 : The second sum is: 1 + 2x + 3x 2 + . . .
Substitute these values for the sums in Expression 12 to show that

VI. DISCUSSION
The error bounds developed in this paper allow the validation data for one classifier to be used to choose or train other classifiers for the hypothesis class. So we can apply these bounds to a Gibbs classifier based on classifiers trained on different splits of the same in-sample data set, with each classifier's validation data the data withheld from its training. Then we can extend an error bound for this holdout Gibbs classifier to an error bound for the single "full" classifier based on all in-sample examples, if we can bound the rate of disagreement between the holdout Gibbs classifier and the full classifier, since the error rate of the full classifier is at most the error rate of the holdout Gibbs classifier plus the rate of disagreement. (For more details, see Bax and Le [16].) For local classifiers, like nearest neighbor classifiers, we can use statistics to bound the rate of disagreement. For example, suppose we split the in-sample data into 10 subsets; use each subset as the validation data for a one-nearest neighbor classifier consisting of the other nine subsets; use those ten classifiers in a Gibbs classifier, and use the results in this paper to compute an error bound for the Gibbs classifier. To get an error bound for the one-nearest neighbor classifier based on all in-sample examples, we also need to bound the rate of disagreement between that classifier and the Gibbs classifier. The rate of disagreement is at most 10%, because with probability 90%, the Gibbs classifier selects one of the nine classifiers that includes the nearest neighbor to the example being classified. (In the other 10% of cases, the Gibbs classifier selects the one classifier with the nearest neighbor in its withheld validation data.) For the Gibbs classifier based on only m = 10 classifiers, we should use the average bound based on uniform validation, from Inequality 4. Alternatively, to reduce variance, we could use a Gibbs classifier based on all subsets of 90% of the data. It would also have a 10% bound on its rate of disagreement with the full classifier, because this Gibbs classifier also has a 10% probability of selecting a classifier that does not include the nearest neighbor from the full classifier. For this Gibbs classifier, it is important to use error bounds that have a low cost for variety, because there are m = 10n In the future, it would be interesting to determine whether nearly uniform bounds can improve PAC-Bayesian bounds that are based on arbitrary prior and posterior distributions and on change of measure with respect to divergences. A first step would be to show how nearly uniform bounds apply to arbitrary distributions. Then we would need to show that those improvements can be maintained through a change of measure.
We will begin with the terms on the right of the RHS of Equality 14 and work to the left. Let The base cases are: The general recurrence is: (Use a discrete set of candidate values for δ i+1 in [0, Σ δ ], for example increments of 0.0001.) The last step is:

B. How to Compute Average Validation Error Rate over Splits for k-Nearest Neighbors
We can use dynamic programming to compute the average validation error rate over all splits of the in-sample E (x,y)∈F E H⊆F , |H|=n, (x,y)∈H I(g H (x) = y).
Convert the inner expectation to a probability of error on (x, y) over classifiers g H that have (x, y) ∈ H: where the probability is over H ⊆ F such that |H| = n and (x, y) ∈ H.
For each in-sample example (x, y), we can use dynamic programming to compute the probability of error over classifiers g H that have (x, y) ∈ H. Let a i,h,v be the probability that h of the i nearest neighbors to (x, y) in F − {(x, y)} are in H, and v of the remaining i − h nearest neighbors have a different label than y, so that there are v incorrect votes. The base case is i = 0. Let a 0,0,0 = 1, and let a 0,h,v = 0 for all other h and v.
For the general case, let (x i , y i ) be the ith nearest neighbor to (x, y) in F − {(x, y)}. Let p H (i, h) be the probability that the ith nearest neighbor to (x, y) is in H, given that h of the i − 1 nearest neighbors are in H and (x, y) ∈ H too. Then If y i = y, then H (i, h)).
If y i = y, then So the average validation error rate over the r+n n splits is: