Managing Domain Knowledge and Multiple Models with Boosting

1 Introduction

Recent efforts in ensemble learning methods have shown empirically that the use of many methods and models is more powerful than using any single method alone. For example, Caruana [2004] shows how constructing an ensemble classifier from a library of around 2000 models ranging from decision trees to SVMs produces classifiers that outperform the best of any single model. Oddly, Boosting [Schapire, 1990]- a particularly popular ensemble technique with strong theoretical and empirical support-is rarely used in such a fashion. In principle, Boosting should be able to handle multiple learning methods automatically simply by using a learner that itself chooses among multiple weak learners. On the other hand, such a learner introduces additional complexity and may compound overfitting effects.

In this paper, we present a new boosting algorithm, MBoost, that incorporates multiple models into Boosting explicitly. In particular, we extend AdaBoost [Schapire and Singer, 1999; Freund and Schapire, 1995] to act as an arbitrator between multiple models. Our contributions are:

• A principled technique for extending Boosting to enable explicit use of multiple weak learners.
• A technique for controlling weak learners that overfit or are poorly matched to the data (e.g., embody poor domain knowledge).

In the sections that follow we first present MBoost itself, comparing it to AdaBoost. We analyze the theoretical and practical consequences of MBoost, and validate our analysis by presenting several empirical results, including a comparison of MBoost to model selection via cross validation. Finally, we situate our work in the literature and conclude with some discussion.

Charles Isbell

College of Computing Georgia Tech Atlanta, GA 30332

isbell@cc.gatech.edu

2 MBoost

AdaBoost [Schapire and Singer, 1999; Freund and Schapire, 1995] is an ensemble learning technique that iteratively constructs an ensemble of hypotheses by applying a weak learner repeatedly on different distributions of data. Distributions are chosen to focus on the "hard" parts of the data space, that is, where the hypotheses generated thus far perform poorly. If h1,h2, . . . ,hT is a set of hypotheses generated by AdaBoost, the final boosted hypothesis is then: H(x) = sign( f (x)) = sign(∑T t=1 αtht(x)), where αt denotes the weighting coefficient for ht .

Although described as a single learner, the weak learner could be a "bag" of several learning models. For example, rather than choosing between a decision tree and a perceptron as the weak learner, one could use a learner that contained both, presumably choosing the better for any given iteration.

Using such a composite weak learner requires some attention to detail. Whether the bag chooses the best model or combines the models in some way, it introduces additional inductive bias: one is no longer boosting over a decision tree and a perceptron, but over a potentially complex ensemble learner that happens to include a decision tree and perceptron. To ensure that no additional inductive bias is introduced, we propose that the boosting algorithm itself should be the arbitrator, acting as the mechanism for choosing which model to use.

The MBoost algorithm explicitly supports multiple weak learners and formalizes the notion of boosting as the arbitrator. In each round, each weak learner proposes a hypothesis and MBoost selects the "best" one. Here, "best" is determined by how boosting would reweight the distribution from round to round, allowing MBoost to arbitrate among the weak learners without introducing any inductive bias not already intrinsic to the boosting framework.

Boosting is known to be susceptible to overfitting when its weak learner overfits. Imagine for example, that the weak learner is a rote learner such as a hash table. The training error will be zero, but there will also be no generalization. No matter how many rounds are run, the rote learner will generate the same hypothesis (assuming there is no noise in the labels). As a result, the final Boosting classifier would show the same (lack of) generalization capabilities. Using multiple weak learners can only compound this problem.

Boosting's susceptibility to this kind of overfitting lies in Require: Weak learners b1, . . . , bm Data (x1, y1), . . . , (xn, yn) where xi ∈ χ, yi ∈ {-1,+1}

1. Initialize D0(i) =1/n
2. for t =1, . . . ,T -1 do
3. Split the data randomly into two parts Dtraint and Dvalt .
4. Train learners b1 . . .bn with Dtraint , generating hypotheses h1 . . . hn.
5. Choose hypothesis ht =argminZt (hi, . . . ,hn)
6. Choose αt for ht per usual
7. Update: Dvalt+1(i) =Dvalt (i)e-αtyiht (xi)

1. end for

Where χ is the input space and Zt is the normalization constant.

part in its use of training error for hypothesis evaluation. Training error can be an overly-optimistic and poor measure of true performance. Rather than avoid "stronger" learners, MBoost divides the data every round into training and validation sets, using the latter to evaluate generated hypotheses. This approach yields a more accurate measure of the hypotheses' performance which in turn is used to choose the best hypothesis and its weight. Additionally, MBoost only reweights the distribution on data from the validation set. Points from the training set are suspect as their prediction may be due to overfitting causes. Reweighting these points may incorrectly imply that they have been learned. Reweighting only the validation set avoids making such a mistake. Note that the convergence of the algorithm does not change. All points will eventually be reweighted since points in the training set of one round may very well be in the validation set of the next.

The combination of these two techniques means MBoost has a much more accurate measure of the hypotheses' generalization errors. Further, by being "inside" the bag of competing models, MBoost can choose the hypothesis that directly minimizes the loss function. The net effect is that users can insert a variety of models into boosting to take advantage of the empirical power of using multiple models while mitigating the effects of poor weak learners that either overfit or embody incorrect domain knowledge.

Algorithm 1 shows pseudo-code for MBoost. We note that while MBoost as shown is derived from AdaBoost, any boosting scheme can be similarly adapted.

3 Analysis and Implications

3.1 Using multiple weak learners

Boosting can be viewed as a coordinate gradient descent method that searches for the set of hypotheses which, when combined with their weights, minimizes some loss. In each round of AdaBoost, a hypothesis ht (the coordinate) is given, and AdaBoost optimizes the weight αt for that coordinate to minimize the loss function. An interpretation of this process is that given the coordinate, AdaBoost is taking the largest possible loss-minimizing step along that coordinate.

When Boosting is extended to multiple weak learners, not only must the optimal weight be chosen, but the optimal hypothesis (among a set of proposed hypotheses) must be chosen as well. In other words, we must find the best coordinate (the one with the largest component in the direction of the gradient) in addition to optimizing the loss-minimizing step.

Because we do not know our learning models a priori, we are precluded from analytical optimizations that find the best hypothesis. Instead, we perform an exhaustive search. For each hypothesis proposed by the different models, we find its optimal weight and calculate the resulting loss. The hypothesis with the lowest loss is chosen. Because the number of weak learners is typically small and computation of the loss requires only hypothesis predictions and not training, the cost of this step is low.

Applying this technique to AdaBoost, we see that the best hypothesis is the one minimizing G( f ) = ∑N i=1 e-yi f (xi) , where yi is the true label and f (x) =∑T t=1 αtht (x) is the hypotheses ensemble classifier. The cost of this minimization grows linearly with the number of rounds run. Over many rounds, it can become expensive. Fortunately, minimizing G( f ) is equivalent to minimizing Zt , the normalization constant in AdaBoost, in that round.

Proof. In any particular round t, the update rule gives us:

Because Zt must normalize Dt+1(i) = 1, we have:

Thus

We note that in the MBoost formulation, Zt is defined somewhat differently than in AdaBoost. This is because MBoost's use of a validation set changes the loss function; however, the difference is slight and the proof still applies.

Finally, it is worth noting that because MBoost is choosing among multiple hypotheses, the weak learner requirement (in the PAC sense) can be relaxed. The ensemble of learners must act as a weak learner but no individual learner must.

3.2 Using an internal validation set

MBoost needs an accurate error estimate for candidate hypotheses each round. Following [Langford, 2005], we model hypothesis error as a biased coin flip where the bias is the true error, the number of tails is the number of correct predictions and the number of heads is the number of incorrect predictions.

The probability that one makes k or fewer mistakes in n predictions given that the true error rate is ε is given by the binomial cumulative distribution function: CDF(k,n,ε) = ∑k i=0 (n i )ε i (1 - ε)n-i .

The largest true error rate r such that the probability of having k or fewer mistakes in those n predictions is at least δ, is then: maxr(r : CDF(k,n,r) ≥ δ). We will refer to this as the maximum reasonable true error: mrte(k, n, δ). A bound on the true error can then be formed as: P(ε ≤ mrte(k, n, δ)) ≥ 1 - δ.

In MBoost, a hypothesis is only used if its mrte(k,n,δ) is less than 0.5. That is, a hypothesis is only used if the upper bound of its true error is less than 0.5, suggesting with high confidence that the hypothesis is better than random.

Recall that we can view Boosting as a coordinate gradient descent method optimizing a particular loss function. Use of the validation set for hypothesis selection, weighting and distribution reweighting essentially amounts to a different loss function: ∑N i=1 e-yi ∑t ht (x)I(xi /∈Dtraint ) . MBoost's loss function reflects our understanding that the real goal of interest is the ensemble's generalization error. We want to avoid being misled by atypical results on training data. Use of the test set for evaluation allows MBoost to effectively apply weak learners prone to overfitting (as a "strong" learner may do).

One could easily imagine extending the use of a single internal validation set to perform full 10-fold cross-validation per round of boosting. We note however, that such a treatment aims towards finding the best weak learner, not the best hypothesis. In building an ensemble of hypotheses, our goal is to find the best hypothesis per round.

Finally, we note that internal validation is also mildly helpful when overfitting is due to noise. Such error is a side effect of boosting's emphasis on "hard" examples, or in noisy situations, noise. If noise is non-systematic, MBoost should determine that the generated hypotheses cannot predict the noise better than random. As we note in the next section, this will cause MBoost to halt.

3.3 Automatic stopping condition

It is natural for MBoost to stop when none of its weak learners perform better than random. Standard boosting uses training data for evaluation so it may be easier for weak learners to perform better than random than in MBoost. In running our experiments, MBoost usually stops due to this condition.

For MBoost to determine that none of its weak learners can perform better than random, a single round in which no generated hypotheses perform is insufficient as the training and validation sets are chosen randomly. To determine that the learners are indeed "exhausted", many consecutive rounds in which no hypothesis beats random is required.

We note that in these rounds, the distribution is static. MBoost is essentially performing an internal Monte-Carlo cross-validation on each of its weak learners. As we run more rounds, we acquire tighter bounds on each learner's true error. Eventually, this will either show that at least one of the weak learners does better than random, in which case MBoost will continue, or that none of the weak learners can do better than random (with some confidence), in which case MBoost halts.

3.4 Error bounds

MBoost can be approximately reduced to AdaBoost. To see this, consider the weak learner L which when trained on data set Dt in round t does the following:

• Splits the data set into a training set and a validation set, Dtraint and Dvalt .
• Trains each of its member learners b1 . . .bm on Dtraint , generating hypotheses h1 . . . hm.
• Simulates for each hypothesis the boosting reweighting on Dvalt and chooses the hypothesis hbest,t with the lowest hypothetical normalization constant Z.
• Returns h′ t (x) = hbest,t (x)I(x /∈ Dtraint), where I(p) ∈ 0, 1 is the indicator function that returns 1 when the predicate p is true, and 0 otherwise. In other words, return h′ t(x) as a copy of hbest,t (x) except that when asked to predict on data it has been trained on it abstains.

Applying AdaBoost to the weak learner L, we construct a learner Lada. This is essentially MBoost. The sole difference is that MBoost's final hypothesis is H(x) = sign(∑T t=1 αt hbest ,t (x)) instead of H ′ (x) = sign(∑T t=1 αt h′ t (x)); however, h′ t(x) and hbest,t (x) differ only in predictions on a randomly-drawn finite set, namely, Dtraint . Thus, H ′ (x) and H(x) can differ only on points in the union of Dtrain1 . . .DtrainT , a subset of the overall training data D. In the limit, as the size of the instance space approaches infinity, the probability of predicting on a data point seen in training is vanishingly small. More formally, lim |χ|→∞ Pr(x ∈ D) = 0

and therefore lim |χ|→∞ |H ′ (x)-H(x)| = 0 where χ is the instance space and x is a point randomly drawn from χ. Further:

• The sum of all errors is bounded by the size of the training set: ∑ x∈χ |H ′ (x) -H(x)| < |D|.
• H ′ (x) and H(x) differ only on a randomly drawn, finite set, and the errors |H ′ (x)-H(x)|, are not systematic. In other words, ∑|H ′ (x)-H(x)| ≈ 0. H ′ (x) and H(x) represent the same decision boundary.

H ′ (x) ≈H(x) and thus, Lada is approximatelyMBoost.

This reduction now allows us to inherit the generalization error bounds that have been derived for AdaBoost. In particular, both the VC-theory based generalization error bound found in [Freund and Schapire, 1995], as well as the marginbased generalization bounds in [Schapire et al., 1997] and [Schapire and Singer, 1999] can be applied straightforwardly.

4 Empirical evaluation

We performed four sets of experiments to examine MBoost's performance.

4.1 Effects of domain knowledge

This set of experiments focus on exploring MBoost's basic ability to exploit multiple domain knowledge sets, as encoded by the weak learners; the validation set is not used. We used a 2D synthetic dataset composed of three Gaussians whose points are labeled according to three different lines, one for each Gaussian. Two weak learners were used. The first is a simple perceptron. The second is a Gaussian estimator combined with a perceptron. This represents the accurate domain knowledge case.

As we can see in Figures 1a and 1b, this is an easy dataset and both AdaBoost and MBoost are able to approach perfect classification. MBoost, however, by leveraging the additional domain knowledge in the second weak learner, is able to do so five times faster.

To explore the effect of inaccurate domain knowledge, we replace the second weak learner with one that learns vertical bands of width 0.1. This hypothesis class can yield no helpful hypotheses, simulating poor domain knowledge. In this case, MBoost discards the hypotheses generated by the second weak learner. MBoost and AdaBoost perform identically from round to round.

4.2 MBoost versus AdaBoost on individual learners

In this set of experiments, we explore the effect of boosting multiple models together, versus boosting each model individually. We want to determine if heterogeneous ensembles are superior to homogeneous ones. We performed the experiments on five of the largest binary classification UCI datasets 1 . A set of twenty-five weak learners were used:

• Five Naive Bayes learners. One uses empirical probabilities, the other four use m-estimates with m at 4, 16, 64, and 256. We used the Naive Bayes learner provided in the Orange data mining package.
• Five kNN learners with k at 1, 4, 16, 64, and 256. We used the kNN learner provided in the Orange data mining package.
• Five C4.5 decision tree learners with minOb js, the minimum number of examples in a leaf, set at 1, 4, 16, 64 and 256. All other options were set to defaults. We used R8 of Quinlan's implementation.
• Ten SVM learners with C, the parameter for the cost of misclassification, set at 0.125, 0.5, 2, 8, 32, 128, 512, 2048, 8192, and 32768. The SVMs used a RFB kernel. All other options were set to defaults. We used the libsvm library by Chih-Chung Chang and Chih-Jen Lin.

We compared two learners. The first, MBoost10, is given all twenty-five weak learners and set to run for ten rounds. The second is a learner that runs AdaBoost for 10 rounds with each of the weak learners in turn (for a total of twenty-five runs). The best AdaBoosted model (according to their reported training error) is chosen and used. We call this second learner BestAda. Note that the computational complexity of the two learners are equivalent, they are O(nm) where n is the number of rounds and m is the number of weak learners.

1 The full ADULT data set is quite large, we used a subsample of 1000 examples.

Table 1 shows the accuracy results on the five datasets. All reported accuracy scores use subsample cross-validation 50 times; that is, in each cross validation round we randomly split the data into training and validation sets with 90% in the training set. We use this variation of cross validation throughout our evaluation because it can be performed any number of times. We find that 50 rounds typically produce enough samples for our significance tests.

We used one-way ANOVA tests to determine if the reported accuracies are statistically significant, pvalue = F(1,98). All datasets show MBoost performing statistically significantly better.

These results are quite surprising. Detailed analysis shows that BestAda suffered from significant overfitting. For example, AdaBoosted SVM would report a higher accuracy rate than AdaBoosted C4.5 when in fact AdaBoosted C4.5 generalized better.

One might imagine using cross-validation to avoid this problem. To this end, we create a third learner, BestCV-Ada, that is the same as BestAda but uses ten-fold cross validation to select the best AdaBoosted weak learner. Note that this increases the computational cost of BestCV-Ada by a factor 10. We present results comparing BestCV-Ada and MBoost10 in Table 2.

These results are in line with expectations. As commonly reported in the literature, the best single-model booster is quite effective. Nevertheless, we see that MBoost, using one tenth of the computational cost, can perform better on three of the five data sets and as good on the rest. Heterogeneous ensembles appear to perform better than homogeneous ones. MBoost is able to take advantage of this effect and combine the ensembles appropriately.

2 Additional CV rounds were performed to ascertain statistical significance.

4.3 MBoost as weak learner arbitrator

Here, we perform a set of experiments to explore the effects of using MBoost's loss function as a weak learner arbitrator. We compare two versions of MBoost. The first is standard MBoost using its exponential loss function as the arbitrator, the second, MBoostAcc using validation accuracy of the weak learners. Both boosters are run for 10 rounds.

Table 3 shows that the two versions' performance are quite similar. Only one dataset shows any difference that might be statistically significant with MBoost outperforming MBoostAcc. In further exploration, we ran the same experiment but allowed both versions to run until exhaustion. In this experiment, all performance differences disappeared. This is unsurprising as the performance difference should be in terms of speed of convergence, not final asymptomatic performance. The exponential loss function is more aggressive, so it is reasonable that it might show some early gains.

4.4 MBoost versus the best individual learners

Here we perform a series of experiments comparing MBoost with the best individual model as selected via 10 fold cross validation (BestCV-Ind). We ran two versions of MBoost, one running for 10 rounds and one with the automatic stopping condition, though never more than 50 rounds. MBoost10 has the same computational complexity as selecting the best individual model via 10-fold cross validation. MBoost-Auto typically requires two to five times the computational cost.

Table 4 shows MBoost10 performing better on one of the five datasets and equivalently on the rest. Further, as we can see in Table 5, the accuracy scores do not degrade even as we run MBoost to exhaustion. MBoost is quite resistant to overfitting. These factors combined with MBoost's low computational complexity lead us to suggest it as an alternative to cross-validation for model selection. Instead of trying many models and finding the best, we suggest Boosting the models together and synthesizing an ensemble whole.

5 RelatedWork

MBoost's use of multiple weak learners is similar to a boosting extension known as localized or dynamic boosting ([Moerland and Mayoraz, 1999; Meir et al., 2000; Avnimelech and Intrator, 1999; Maclin, 1998]) where αt-the weight on the hypothesis in round t-is generalized to be a function dependent on the data, x. Localized boosting can be viewed as a way to boost across two weak learners: one in the hypothesis and one in the αt (x). Our work aims to explicitly enable multiple weak learners in general, where any number of weak learners are allowable. MBoost can emulate localized boosting by treating αt (x)ht (x) as one weak learner, but we point out that-ignoringMBoost's use of internal validation-both extensions are mathematically reducible back to boosting. The difference lies in that MBoost makes boosting across multiple learners explicit. We hope that this formulation is easier to reason about, and that at the very least, provides a clearer mechanism for the user to apply multiple weak learners and the domain knowledge they embody.

We know of no other work in boosting for controlling weak learner overfitting that is similar to our use of internal validation; however, there is general work in ensemble learning (again, see [Caruana et al., 2004]). Our work differs in that it is integrated into the boosting framework, and so we leverage boosting's distribution perturbation and the use of hypotheses trained on different parts of the data space.

MBoost's ability to mitigate the effects of poor weak learners also makes it suitable for arbitrating between and merging different sets domain knowledge embodied in the weak learners. There has been some prior work focused on incorporating knowledge into Boosting, eg. [Schapire et al., 2002]. Their approach is to add a prior model, informed by domain knowledge, mapping each instance of the data to a probability over the possible label values. The Boosting process is modified to also fit the prior. Requiring a prior can be burdensome. Further, if the prior is incorrect, performance will suffer. Priors also offer no way to reconcile different sets of domain knowledge. MBoost relaxes these constraints. Weak learners provide a very flexible domain knowledge insertion point. MBoost can further mitigate any negative effects should incorporated knowledge be inaccurate. Finally, MBoost can merge the knowledge sets into an ensemble whole.

6 Conclusion

We have introduced a novel boosting algorithm, MBoost, that explicitly chooses among multiple models, controlling for those weak learners that overfit or are otherwise poor model fits for the data. MBoost takes advantage of results in ensemble learning while retaining the theoretical and empirical strengths of boosting. It provides us an effective way to manage and use multiple models and the domain knowledge they embody.

Empirical evaluations show MBoost can outperform any single model and any boosted single model on some data sets and performs at least as well on the rest. Furthermore, MBoost provides a natural stopping criterion that appears robust to overfitting. Favorable performance and MBoost's low computational complexity also lead us to suggest it as an alternative to model selection via cross validation.

Acknowledgments

We thank Alex Gray and John Cassel who both provided useful pointers to hunch.net among other helpful discussions. Special thanks to Andrew Watts for his help editing and proofing this paper. The breast cancer databases used in our benchmarks was obtained from the University of Wisconsin Hospitals, Madison from Dr. William H. Wolberg.