Monte Carlo Theory as an Explanation of Bagging and Boosting

1 Introduction

Ensemble Learning aims at combining learned hypothe­ ses for classification tasks instead of choosing one. It has proved to be a valuable learning approach, and it is ac­ tively investigated in the Machine Learning community [Freund 1995; Freund & Schapire 1997; Breiman, 1996; Wolpert, 1992].

In addition to the advantages pointed out by Dietterich [2000], what really attracts the great interest to ensemble learning is its amazing effectiveness and robustness to overfitting. In fact, ensemble classifiers, and specifically AdaBoost, often show a drop in generalization error far beyond the point in which the training error reaches zero.

In this paper we concentrate on two approaches, namely Bagging [Breiman, 1996], and Boosting, as implemented in the AdaBoost algorithm [Freund & Schapire, 1997], and we propose an analysis of these two approaches by exploiting links with Monte Carlo theory. This parallel allows a deeper understanding of the basic process un­ derlying hypothesis combination. In particular:

• it suggests the conditions under which Bagging is likely to be better than single hypothesis learning,
• it explains why reducing the margin [Schapire eta/., 1998] increases the performances,
• it allows some reasons for robustness to overfitting to be conjectured.

The article is organized as follows: in Section 2 we briefly review Bagging and AdaBoost algorithms, and in Section 3 we introduce basic terminology and results

Lorenza Saitta

Universita del Piemonte Orientale Spalto Marengo 33, Alessandria, Italy saitta@mfn. unipmn. it

from Monte Carlo theory. Section 4 is the core of the paper: it introduces the link between Monte Carlo theory and Ensemble Learning algorithms, and analyzes the two algorithms in the ideal situation of having access to the whole example and hypothesis spaces. Section 5 relaxes the hypotheses of Section 4. In particular, it focuses on AdaBoost's case offering an intuitive accounting of the generalization performances of the algorithm. Finally, Section 6 concludes the paper and proposes future work.

2 Bagging and AdaBoost

Bagging [Breiman, 1996] is one among the most studied Ensemble Learning algorithms. It takes in input a learn­ ing set L0, an integer number T, and a (possibly weak) induction algorithm A. At each iteration step t the algo­ rithm creates a bootstrap replicate L [Efron & Tibshirani, 1993] of the original learning set, and uses it in conjunc­ tion with A to form a new hypothesis h1. When T hy­ potheses have been learned, they are combined using a simple majority voting rule.

Breiman [1996] found a significant increase of classifi­ cation accuracy, when the hypotheses are bagged, on dif­ ferent datasets from the UCI repository, for both regres­ sion and classification tasks . Moreover, in the same pa­ per, a theoretical analysis is carried on . The notion of order correct classifier is introduced, and it is shown that when A is order correct, then Bagging is expected to behave almost optimally (i.e., it behaves like the Bayes classifier) . Throughout the paper it is claimed that "bag­ ging stable classifiers is not a good idea". A "stable" classifier is qualitatively defined as one that does not show large variations in the learned hypotheses when the training set undergoes small variations. Experimental analysis of Bagging's performances is provided by Bauer and Kohavi [1999], Quinlan [1996], and Dietterich [2000].

The simplest version of AdaBoost [Freund & Schapire, 1997] deals with binary classification problems, and this is the one we refer to. AdaBoost maintains a weight dis­ tribution over the training examples, and adjusts it at each iteration. The adjusted weights are chosen so that higher values are associated to previously misclassified examples. As a main effect, the weighting scheme forces A to focus on "more difficult" examples, ensuring thus that all the examples will be, sooner or later, taken into account by the weak learner. The hypothesis combination rule is a weighted majority vote that puts more weight on successful hypotheses (i.e., hypotheses that incur a low weighted training error) .

Despite its apparent simplicity AdaBoost solves a diffi­ cult problem: choosing example and hypothesis weights in such a way to ensure an exponential decrease in the training error committed by the boosted committee. Moreover, the choice is made without any knowledge or assumption on the weak learner itself (except that the weak learner is always able to outperform random guessing). In contrast, Bagging only works when "be­ nign" weak learners are used. On the other hand, AdaBoost seems to be more sensitive to noise than Bag­ ging [Quinlan, 1996].

As mentioned earlier, AdaBoost shows the characteristic of being robust with respect to overfitting [Schapire et a!., 1998; Drucker & Cortes, 1996; Quinlan, 1996; Bre­ iman, 1998; Freund & Schapire, 1998]. A rather con­ vincing account of this behavior imputes to AdaBoost the ability to be very successful in increasing the final classifier's margin over the training examples [Schapire eta!., 1998].

In the effort of understanding and/or explaining AdaBoost's behavior, boosting has been related to other existing theories, such as Game Theory [Schapire, 2001], logistic regression [Friedman et a!., 1998; Collins et a!., 2000], optimization [Ratsch et a!., 2002], and Brownian motion [Freund, 1995] .

3 Monte Carlo Algorithms

In this section we recall some basic notions from Monte Carlo algorithms theory. In the literature, the name Monte Carlo often denotes a generic stochastic algo­ rithm; in this paper we will refer to the more restrictive definition given by Brassard and Bratley [ 1988]. Let fi be a class of problems, Y a finite set of answers for the problems in fl, and c : rr ~ 2y be a function that maps each problem into the set of its correct answers.

Definition 1 - A stochastic algorithm A, mapping fi into Y, is said to be a Monte Carlo algorithm, if, when applied to an instance n of fl, it always terminates, providing an answer to n, which may be occasionally incorrect.

Two properties of Monte Carlo algorithms turn out to be relevant:

Definition 2 - A Monte Carlo algorithm is consistent if it never outputs two distinct correct answers when run two times on the same problem instance n:.

Definition 3 - A Monte Carlo algorithm is p-correct if the probability that it gives a correct answer to n is at least p, independently of the specific problem instance n considered.

The great interest in Monte Carlo algorithms resides in their amplification ability: given a problem instance n:, and a Monte Carlo algorithm MC, if MC is run multiple times on n; and the majority answer is taken as the result, then, under mild assumptions, the probability of a correct answer exponentially increases. The conditions are that MC must be consistent for n and that p must be greater than random guess . We note that, whenever c(n) reduces to a mapping from rr to y (instead of 2y ), the algorithm is consistent. Let us denote by MCr the algorithm ob­ tained by combining with a majority vote the answers given by multiple runs of a Monte Carlo MC.

4 Complete Information Case

In this section we provide a theoretical account of the links between Monte Carlo theory and bagging or boost­ ing, in the case we have complete information on the learning/classification problem. More precisely, let X be a finite set of examples 1 , w a target concept (binary clas­ sification), A a (weak) learner. Let lXI = N and w be a probability distribution over X. Let moreover 'I' be the power set of X. Any intensional concept description, be­ longing to a given language L, will be mapped to an element ljJ of '1', i.e., ljJ is the set of examples classified by that description as belonging to w. In this way, we can reduce ourselves to a finite set of (extensional) hypothe­ ses. Let <I> ~'I' be any subset of '1'. Let 1<1>1 = K. A prob­ ability distribution q is associated to the elements of <1>. The set <I> can be thought of as the collection of the hypotheses generated by a learning algorithm A applied to a number of training sets, or a set of hypotheses pro­ vided by an oracle. Learning can then be simulated by extracting with replacement elements from <I> according to q (each extraction corresponds to a run of A on some training set).

Let us represent the described situation by means of Ta­ ble I. Here, let pj(x.J E { 1,0} 2 be the probability that hy­ pothesis cp 1 correctly classifies example xk. Let p(x.J be the average of such probabilities for xk. Let r 1 be the ac­ curacy of hypothesis cp 1 over the whole X.

By using the given probability distributions, we can compute the average accuracy for the whole table:

1 The finiteness of X is not essential; it is only assumed for the sake of simplicity.

2 This assumption implies that the Bayes error is zero.

~iven a subset Z of X, let IIZII the measure of Z w.r.t. w, I.e.:

Analogously, if <I>'~ <l>, we define:

Clearly the measures IIZII and 11<1>'11 reduce to IZI/N and I<I>'I/K, respectively, if q and ware uniform distributions.

4.1 Monte Carlo and Bagging

We will now establish a link between Monte Carlo algo­ rithms and Bagging. Let L0 be a training set, and T an integer; let L be a generic bootstrap replicate of L0· In this case, <l> is the set of all the different hypotheses that can be obtained by applying A to L0's replicates. The frequencies with which each <pi is generated determine q.

If we look at Table 1, Bagging proceeds, so to say, by columns, by extracting T columns from <l> and using them to obtain a majority vote on each xk. Considering the global average accuracy r, or even the exact distribution of the r 1 , it is not easy to say how many of the xk will be correctly classified by the majority voting procedure, and, then, whether to perform Bagging will be rewarding. It is generally said [Breiman, 1996] that bagging is useful when A is "unstable". We will show later that this notion of "instability" can be made more precise.

Let us consider now a Monte Carlo interpretation of Ta­ ble I. To the contrary of Bagging, a Monte Carlo algo­ rithm MCr proceeds by rows: for each Xk (problem to be solved), it extracts T hypotheses cp 1 from <l> and classifies xk bf majority voting. This process is repeated for each row . This procedure is necessary, because the compo­ nents of the Monte Carlo voting must be independent, but the entries in each column are not. Monte Carlo theory tells us that the correctness of MCr on xk can be amplified if:

1. The T trials are independent
2. MC is consistent
3. p(xk) > 1/2

Condition (I) is true by construction of the process (ex­ traction with replacement of T hypotheses for each row) .

3 Let us set apart, for the moment, the computational issues.

Condition (2) is true as long as the Bayes error is zero. Condition (3) may or may not be true, depending on the set <l> .

Let Xa be the set of examples for which p(xJ > 112. Ac­ cording to the Monte Carlo theory, all these examples will be "amplified", i.e., they will be correctly classified in the limit (for T -+ oo) . The application of MCr to all the rows yields an asymptotic accuracy:

By denoting by PT the expected Monte Carlo accuracy when only a finite number T of extractions is performed, we obtain:

Let now <l>b be the set of hypotheses whose accuracy is greater than Pooo The value

is. th~ prob~bilit~ that . a hypothesis "better" than bag­ gmg IS obtamed m a smgle extraction. Then, in an infi­ nite number of trials, such a hypothesis will occur with a frequency 't.., . It is clear that, in the limit, Bagging is surely convenient only when when <l>b = 0, because, in t~is case, there is no single hypothesis better than Bag­ gmg. When <l>b f: 0 a better hypothesis will surely ap­ pear, soon or later. The interesting case, however, occurs when only a finite number T of extractions is performed. Before approaching this case, let us make some consid­ erations on what has been described so far.

Let us first notice that ensemble learning claims that am­ plification occurs when the r;'s (accuracy of each of the combined hypotheses) are greater than 1/2 (condition on the columns). Actually it may not be the case. What is really required is that, for each example xk> more than 1/2 of the learned hypotheses are correct on it (condition on t~e rows). Then, Monte Carlo Theory suggests that Bag­ gmg would be successful when it is possible to find a subset of <l> such that Xa=X. Before looking with more details into the relationship between the r·'s and the p(xJ's, let us consider some extreme cases . 1

Let A ?e a weak learner that always returns the same hy­ pothesis <p, regardless of the training set. The lucky situation in which that single hypothesis <p is quite accu­ rate over the training set does not imply anything about the occurrence of Monte Carlo amplification. In fact, all the p(xk) are equal to 1 on those examples which are cor­ rectly classified by <p, and 0 otherwise. In other words, whatever the accuracy of <p, no amplification at all oc­ curs. This is an example of a perfectly stable Ieamer.

Let us consider a situation in which the global average r of the accuracy is a little more than 112. This value is at the same time the average of the last column and on the last row in Table I, according to (I). For the sake of il­ lustration, let q and w be uniform distributions. Let us consider the following three extreme situations (a detailed analysis of several other interesting cases is pro­ vided by Esposito [2003]) :

• (a) The p(xk)'s in the last column are distributed in such a way that one half of the examples have p(xk) val­ ues close to one, and one half of the examples have p(xk) values close to zero. The r/s in the last row, on the contrary, have all almost the same value around 112. (All hypotheses show the same per­ formances and they cover almost the same exam­ ples)
• (b) The p(xk)'s in the last column have all almost the same value around 112, whereas the r/s in the last row have, for one half, values close to one, and for the other half close to zero. (Some hypotheses are very good and other are very bad, but their coverage is uniformly distributed on the examples).
• (c) Both distributions are uniformly valued around 112 (All the hypotheses are uncertain on all examples).

In case (a) half of the examples are amplifiable, but Bag­ ging is not useful, because any single hypothesis classi­ fies correctly half of the examples, so that nothing can be gained by the Bagging process.

In case (b), the number of amplifiable examples depends on how many of them have actually values a little over 112. But, even in the best case (Xa =X, i.e., p.., = 1), Bag­ ging is again not convenient. In fact, half of the single hypotheses have rj = 1; then, in one over two extractions (on average) a perfect hypothesis is extracted.

In case (c), if the p(xk) values in the last columns are all a little greater than 112, then p.., = 1. This is the case in which Bagging is convenient, because the single hy­ pothesis have all accuracy close to 112. Actually, case (c) is the ideal case for Bagging, because amplification can be obtained with the minimum effort (with "bad" hy­ potheses we may obtain a large amplification).

The following theorem summarizes the above consid­ erations and establishes a link between Bagging and Monte Carlo amplification (proof is provided by Esposito [2003]):

Theorem 1 - The amplified accuracy p.., cannot be greater than 2r, where r is the average accuracy of the bagged hypotheses. 0

Then, even by bagging single hypotheses with accuracy less then 112 it is possible to obtain higher accuracies by Monte Carlo amplification. However, in order to reach p.., = I, the value of r must be at least 112. Even in this case, some of the combined hypotheses are allowed to have a accuracy less than 112, without hindering amplification, provided that Xa =X and that r does not go below 1/2.

4.2 Monte Carlo and AdaBoost

Let us notice that, if the set <I> of hypotheses coincides with the power set 2x (all possible hypotheses are con­ sidered), we are in the situation in which all p(x,J = 112, r = 1/2, and p.., = 1/2, so that no amplification is possible. This means that the learning procedure was not able to make any useful selection inside the hypothesis space. On the contrary, we would like that the weak learner has the nice property of focusing on the best hypotheses. In the previous section we showed that the basic Monte Carlo approach, implemented by Bagging, may fail due to a number of reasons; this happens, for instance, in the cases (a) and (b) of Section 4.1. Even if not explicitly stated, the underling problem is that the weak learner may not be suited enough for this kind of procedure. The question we are now trying to investigate is what to do when such a situation occurs, in particular when we do not want or can modify the weak learner. Then, is it pos­ sible to convert case (a) or (b) into case (c)? Or, said in other words, is it possible to convert a learning problem in which the Monte Carlo assumptions for amplification do not hold into one in which they do?

The solution to this problem can be found by thinking again of the role of the weak learner in the Monte Carlo process. As mentioned earlier, the learner has the duty to modify the distribution from which the hypotheses are drawn (i.e., the qj of the columns) in such a way that "better" hypotheses are more likely to be drawn. Moreo­ ver, we can actually change the behavior of the weak learner through its input, i.e., by modifying the training set. In particular, we have to force the weak learner to extract hypotheses that make the minimum value of the p(x,J 's grow larger than 112 (in order to satisfy the Monte Carlo conditions of amplifiability for all the examples) . Since the weak learner is influenced by the training set, the solution is to modify the training set in such a way that examples with low p(x,J values are more represented, in the attempt to make the weak learner try harder to be successful on them. What we obtain with this reasoning is an AdaBoost-like algorithm. In other words, when the weak learner is unable to satisfy Monte Carlo conditions for amplification, AdaBoost forces it to satisfy them by weighting the examples. More precisely, AdaBost tries to increase the minimum p(x,J with the unconscious goal of extending X0 . In fact, when the weak learner satisfies relatively mild conditions, it has been shown by Schapire et al. [ 1998] that AdaBoost is actually effective in in­ creasing the minimal margin:

Definition 4 - For any particular example xk. the classifi­ cation margin Jl(Xk) for xk is the difference between the weight assigned to the correct label and the maximal weight assigned to any single incorrect label.

In the case of binary classification, the margin is the dif­ ference between the weight assigned to the correct label and the weight assigned to the incorrect one.

Theorem 2 - In the case of binary classification, the fol­ lowing relation holds between the margin and the Monte Carlo p(x,J-correctness value:

The proof of Theorem 2 derives immediately from the definition of margin and p(xk). Formula (7) explains why increasing the margin improves the performances of boosting: in fact, increasing the minimum margin lets the cardinality of the set Xa increase, augmenting the number of examples for which the Monte Carlo conditions for amplifiability hold.

4.3 Non-Asymptotic Case

Let us consider a finite integer T. Let 'tR denote the prob­ ability that a hypothesis "better" than Bagging is ob­ tained in R extractions. In order to compare Bagging with hypothesis selection, let . us consider a classification accu­ racy a . Given Table I , and given a number o close to 0, let T(a) be the minimum number of components of the bagged hypothesis such that:

If a> p"", then probability (8) is zero.

Analogously, let <I> a be the set of hypotheses with r 1 > a and R(a) be the minimum number of hypothesis extrac­ tions such that:

Again, if <I> a= 0, probability (9) is zero.

We can draw a graph of T (ordinate) vs . R (abscissa), parameterized by a . The graph is problem dependent. What we can say in general is that points in the graph above the diagonal correspond to situation for which se­ lection is better than Bagging (for the same accuracy a, Bagging requires more trials), points below the diagonal correspond to situation for which selection is worse than Bagging (for the same accuracy a, Bagging requires less trials), and points on the diagonal correspond to situa­ tions of indifference.

5 Problems with Partial Information

The setting discussed in Section 4 is useful for under­ standing the functioning of ensemble learning, but we need to extend it to the case· of real learning problems. In concrete situation, neither the set <l> nor the example space X is available a priori. What we have is a training set Lo (ILol = M) and a test set T0, both subsets of X, and a learning algorithm A for generating hypotheses. We learn hypotheses, possibly consistent with L0, and estimate the generalization error on T/

If we consider the problem from the Monte Carlo per­ spective and we go back to Table 1, we can think to pro­ ceed as follows. At the beginning we have, on the rows, the training and the test examples, but the columns are empty. Let us consider the first example x1 E L0· Let A run on T replicates of L0 and let us compute Pe(x1), which is an unbiased estimate of the Bernoulli probability p(x1). Even though the T hypotheses generated are only used to classify x1, and could then be discarded, nothing hinders from recording them in the first T (or less, if there is du­ plication) columns of Table 1. When we consider x2, we repeat the whole procedure, running again A on T new replicates of L0 and classifying x2. Again we record the new generated hypotheses (or update the probability dis­ tribution q in case of repetitions). When we finish exam­ ining L0, we have also filled the part of the table corre­ sponding to the test set, which allows estimates p. (x;) for the examples in the test set to be computed. Each pe(x;) is based on T M experimental values, which is the number of runs necessary to estimate the generalization accuracy using the leave-one-out method on a number M of train­ ing examples.

4 In this paper we do not consider to use cross-validation or leave-one-out.

What is interesting is that, during learning, we also learn whether it is convenient or not to exploit Bagging for classifying future unseen examples . It also turns out, ex­ perimental!/, that a much lower number of runs than T·M is very often sufficient to obtain a stable estimate of the sought probabilities.

5.1 AdaBoost's generalization behavior

In this section we discuss AdaBoost's generalization ca­ pabilities and their interpretation in the Monte Carlo framework. Having related the margin of an example xk with the average probability that it is correctly classified by the hypotheses learned via the weak learner allows us to transfer results provided by Schapire et a!. [ 1998] to the Monte Carlo framework . Interestingly enough, the link may be used to give a new, more intuitive, interpre­ tation of the margin explanation of AdaBoost's generali­ zation capabilities. Moreover a nice explanation of why the test error is often observed to decrease even after the training error reaches zero can be suggested.

To understand how generalization error can be inter­ preted in the Monte Carlo framework it is necessary to deepen a little the discussion about the link between en­ semble learning and Monte Carlo algorithms. Let us choose the randomization procedure (whatever it is). Once this is done, the choice of the weak learner deter­ mines the distribution of the p(xk)'s. In other words, when the two major parameters of the ensemble algo­ rithm are fixed, we can think of p(xk) as a theoretical property of the examples.

Once the ensemble process starts, we compute the esti­ mations p ,(xk) . The accuracy of the estimates increases with the number of iterations performed. Whether the final rule will classify correctly or not any example, is a matter of two things: the value of the underlying exact probability p(xk), and how lucky we were in the choice of the rules used to perform the actual estimation.

5 The datasets used, as well as part of the experimental results, can be found at the URL:

http://www.di.unito.it/-esposito/mcandboost

The above argument might explain the finding of the test error decreasing, for AdaBoost, beyond the point in which training error reaches zero. In fact, as an effect of the learning bias introduced by the weak algorithm, it is likely that the p( xk) 's corresponding to examples in the training set would be greater than the ones corresponding to the other examples. It is then likely that those exam­ ples would be correctly classified with high probability after a moderate number of iterations. On the contrary, other examples would require a greater number of itera­ tions, and thus they may start to be correctly labelled well beyond the point where the training error reaches zero. In fact, even though any example with p(xk) > 112 will eventually be correctly classified, the number of it­ erations necessary to see this effect to emerge strongly depends on T. The observed effect of the test error de­ creasing is hence due to those examples for which p(xk) is only slightly greater than 112. Initially, their p(xd is pos­ sibly underestimated by the observed pe(xJ. For small values of T, Pe(xk) can be quite different from p(xJ and greater values of T are necessary to let the choice of hy­ potheses converge toward a set for which Pe(xJ ... p(xJ and, hence, to obtain a stable correct classification of Xk in the test set.

6 Conclusions and Further Work

In this paper we have proposed to analyze ensemble learning (in particular Bagging and, partly, AdaBoost) from the perspective of Monte Carlo algorithm theory. We have shown that this theory can shed light on some basic aspects of Bagging and boosting, and, also offers a new way to actually perform ensemble learning and error estimation. More research is nevertheless needed to deepen our understanding of the presented framework. In particular, it would be very interesting to investigate the relationships between the Monte Carlo explanation of Ensemble Learning and other well known ones (for in­ stance, the bias-variance decomposition). Moreover, it would be very interesting to investigate how a particu­ larly aggressive class of Monte Carlo algorithms, namely the one of biased Monte Carlos, relates to ensemble learning.