Constructing Diverse Classifier Ensembles using Artificial Training Examples

1 Introduction

One of the major advances in inductive learning in the past decade was the development of ensemble or committee ap­ proaches that learn and retain multiple hypotheses and com­ bine their decisions during classification [Dietterich, 2000]. For example, boosting [Freund and Schapire, 1996], an en­ semble method that learns a series of "weak" classifiers each one focusing on correcting the errors made by the previous one, has been found to be one of the currently best generic inductive classification methods [Hastie et al., 2001].

Constructing a diverse committee in which each hypothesis is as different as possible (decorrelated with other members of the ensemble) while still maintaining consistency with the training data is known to be a theoretically important property of a good committee [Krogh and Vedelsby, 1995]. Although all successful ensemble methods encourage diversity to some extent, few have focused directly on the goal of maximizing diversity. Existing methods that focus on achieving diversity [Opitz and Shavlik, 1996; Rosen, 1996] are fairly complex and are not general meta-learners like bagging [Breiman, 1996] and boosting that can be applied to any base learner to produce an effective committee [Witten and Frank, 1999].

We present a new meta-learner (DECORATE, Diverse En­ semble Creation by Oppositional Relabeling of Artificial Training Examples) that uses an existing "strong" learner (one that provides high accuracy on the training data) to build an effective diverse committee in a fairly simple, straightfor­ ward manner. This is accomplished by adding different ran­ domly constructed examples to the training set when building new committee members. These artificially constructed ex­ amples are given category labels that disagree with the cur­ rent decision of the committee, thereby easily and directly increasing diversity when a new classifier is trained on the augmented data and added to the committee.

Boosting and bagging provide diversity by sub-sampling or re-weighting the existing training examples. If the train­ ing set is small, this limits the amount of ensemble diversity that these methods can obtain. DECORATE ensures diversity on an arbitrarily large set of additional artificial examples. Therefore, one hypothesis is that it will result in higher gen­ eralization accuracy when the training set is small. This pa­ per presents experimental results on a wide range of UCI data sets comparing boosting, bagging, and DECORATE, all using 148 decision-tree induction (a Java implementation of C4.5 [Quinlan, 1993] introduced in [Witten and Frank, 1999]) as a base learner. Cross-validated learning curves support the hy­ pothesis that "DECORATEd trees" generally result in greater classification accuracy for small training sets.

2 Ensembles and Diversity

In an ensemble, the combination of the output of several classifiers is only useful if they disagree on some inputs [Krogh and Vedelsby, 1995]. We refer to the measure of disagreement as the diversity of the ensemble. There have been several methods proposed to measure ensemble diver­ sity [Kuncheva and Whitaker, 2002] - usually dependent on the measure of accuracy. For regression, where the mean squared error is commonly used to measure accuracy, vari­ ance can be used as a measure of diversity. So the diver­ sity of the ith classifier on example x can be defined as di(x) = [Ci(x) - C*(x)J2, where Ci(x) and C*(x) are the predictions of the ith classifier and the ensemble respec­ tively. For this setting Krogh et al [1995] show that the gen­ eralization error, E, of the ensemble can be expressed as E = E-D, where E and Dare the mean error and diversity of the ensemble respectively.

For classification problems, where the 011 loss function is most commonly used to measure accuracy, the diversity of the ith classifier can be defined as:

However, in this case the above simple linear relationship does not hold between E, E and b. But there is still strong reason to believe that increasing diversity should decrease en­ semble error [Zenobi and Cunningham, 2001]. The underly­ ing principle of our approach is to build ensembles of classi­ fiers that are consistent with the training data and maximize diversity as defined in ( 1 ).

3 DECORATE: Algorithm Definition

In DECORATE (see Algorithm 1), an ensemble is generated iteratively, learning a classifier at each iteration and adding it to the current ensemble. We initialize the ensemble to contain the classifier trained on the given training data. The classifiers in each successive iteration are trained on the original training data and also on some artificial data. In each iteration artifi­ cial training examples are generated from the data distribu­ tion; where the number of examples to be generated is spec­ ified as a fraction, Rsize, of the training set size. The labels for these artificially generated training examples are chosen so as to differ maximally from the current ensemble's predic­ tions. The construction of the artificial data is explained in greater detail in the following section. We refer to the labeled artificially generated training set as the diversity data. We train a new classifier on the union of the original training data and the diversity data. If adding this new classifier to the cur­ rent ensemble increases the ensemble training error, then we reject this classifier, else we add it to the current ensemble. This process is repeated until we reach the desired committee size or exceed the maximum number of iterations.

To classify an unlabeled example, x, we employ the fol­ lowing method. Each base classifier, C;, in the ensemble C* provides probabilities for the class membership of x. If Pc, ,y(x) is the probability of example x belonging to class y according to the classifier C;, then we compute the class membership probabilities for the entire ensemble as:

where Py(x) is the probability of x belonging to class y. We then select the most probable class as the label for x i.e. C*(x) = argmaxyEY Py(x)

3.1 Construction of Artificial Data

We generate artificial training data by randomly picking data points from an approximation of the training-data distribu­ tion. For a numeric attribute, we compute the mean and stan­ dard deviation from the training set and generate values from the Gaussian distribution defined by these. For a nominal attribute, we compute the probability of occurrence of each distinct value in its domain and generate values based on this distribution. We use Laplace smoothing so that nominal at­ tribute values not represented in the training set still have a non-zero probability of occurrence. In constructing artificial data points, we make the simplifying assumption that the at­ tributes are independent. It is possible to more accurately es­ timate the joint probability distribution of the attributes; but this would be time consuming and require a lot of data.

In each iteration, the artificially generated examples are la­ beled based on the current ensemble. Given an example, we first find the class membership probabilities predicted by the ensemble, replacing zero probabilities with a small non-zero value. Labels are then selected, such that the probability of selection is inversely proportional to the current ensemble's predictions.

Algorithm 1 The DECORATE algorithm

Input:

BaseLearn- base learning algorithm

T - set of m training examples < ( x1 , yl), ... , ( Xm, Ym) > with labels Yi E Y .

Csize -desired ensemble size

I max -maximum number of iterations to build an ensemble Rsize -factor that determines number of artificial examples to generate

1. i = 1
2. trials= 1
3. Ci = BaseLearn(T)
4. Initialize ensemble, C* = { C;}
5. 2:. ·ET<C*( · ·);o!y · l 5. Compute ensemble error, E = 2 m 2 2
6. While i < Csize and trials < Imax
7. Generate R size x ITI training examples, R, based on distribution of training data
8. Label examples in R with probability of class labels inversely proportional to C* 's predictions
9. T = TUR
10. C' = BaseLearn(T)
11. C* = C* U{C'}
12. T = T - R, remove the artificial data
13. Compute training error, ~:', of C* as in step 5
14. IfE 1 ~ E
15. i = i + 1
16. E = E 1
17. otherwise,
18. C* = C*- {C'}
19. trials = trials + 1

4 Experimental Evaluation

4.1 Methodology

To evaluate the performance of DECORATE we ran experi­ ments on 15 representative data sets from the UCI repository [Blake and Merz, 1998] used in similar studies [Webb, 2000;

Quinlan, 1996]. We compared the performance of DECO­ RATE to that of Adaboost, Bagging and J48, using J48 as the base Ieamer for the ensemble methods and using the Weka implementations of these methods [Witten and Frank, 1999]. For the ensemble methods, we set the ensemble size to 15. Note that in the case of DECORATE, we only specify a max­ imum ensemble size, the algorithm terminates if the number of iterations exceeds the maximum limit even if the desired ensemble size is not reached. For our experiments, we set the maximum number of iterations in DECORATE to 50. We ran experiments varying the amount of artificially generated data, Rsize; and found that the results do not vary much for the range 0.5 to 1. However, Rsize values lower than 0.5 do adversely affect DECORATE, because there is insufficient ar­ tificial data to give rise to high diversity. The results we report are for Rsize set to 1, i.e. the number of artificially generated examples is equal to the training set size.

The performance of each learning algorithm was evaluated using 10 complete 10-fold cross-validations. In each 10-fold cross-validation each data set is randomly split into 10 equal­ size segments and results are averaged over 10 trials. For each trial, one segment is set aside for testing, while the remaining data is available for training. To test performance on vary­ ing amounts of training data, learning curves were generated by testing the system after training on increasing subsets of the overall training data. Since we would like to summarize results over several data sets of different sizes, we select dif­ ferent percentages of the total training-set size as the points on the learning curve.

To compare two learning algorithms across all domains we employ the statistics used in [Webb, 2000], namely the win/draw/loss record and the geometric mean error ratio. The win/draw/loss record presents three values, the number of data sets for which algorithm A obtained better, equal, or worse performance than algorithm B with respect to classi­ fication accuracy. We also report the statistically significant win/draw/loss record; where a win or loss is only counted if the difference in values is determined to be significant at the 0.05 level by a paired t-test. The geometric mean error ratio

is defined as vrr7=1 ~, where EA and EB are the mean errors of algorithm A and B on the same domain. If the ge­ ometric mean error ratio is less than one it implies that algo­ rithm A performs better than B, and vice versa. We compute error ratios so as to capture the degree to which algorithms out-perform each other in win or loss outcomes.

4.2 Results

Our results are summarized in Tables 1-3. Each cell in the tables presents the accuracy of DECORATE versus another al­ gorithm. If the difference is statistically significant, then the larger of the two is shown in bold. We varied the training set sizes from 1-100% of the total available data, with more points lower on the learning curve since this is where we expect to see the most difference between algorithms. The bottom of the tables provide summary statistics, as discussed above, for each of the points on the learning curve.

DECORATE has more significant wins to losses over Bag­ ging for all points along the learning curve (see Table 2).

DECORATE also outperforms Bagging on the geometric mean ratio. This suggests that even in cases where Bagging beats DECORATE the improvement is less than DECORATE's im­ provement on Bagging on the rest of the cases.

DECORATE outperforms AdaBoost early on the learning curve both on significant wins/draw/loss record and geomet­ ric mean ratio; however, the trend is reversed when given 75% or more of the data. Note that even with large amounts of training data, DECORATE's performance is quite competitive with Ada boost- given 100% of the data DECORATE produces higher accuracies on 6 out of 15 data sets.

It has been observed in previous studies [Webb, 2000; Bauer and Kohavi, 1999] that while AdaBoost usually sig­ nificantly reduces the error of the base learner, it occasionally increases it, often to a large extent. DECORATE does not have this problem as is clear from Table 1.

On many data sets, DECORATE achieves the same or higher accuracy as Bagging and AdaBoost with many fewer training examples. Figure 1 show learning curves that clearly demon­ strate this point. Hence, in domains where little data is avail­ able or acquiring labels is expensive, DECORATE has an ad­ vantage over other ensemble methods.

We performed additional experiments to analyze the role that diversity plays in error reduction. We ran DECORATE at 10 different settings of Rsize ranging from 0.1 to 1.0, thus varying the diversity of ensembles produced. We then com­ pared the diversity of ensembles with the reduction in gener­ alization error. Diversity of an ensemble is computed as the mean diversity of the ensemble members (as given by Eq. 1). We compared ensemble diversity with the ensemble error re­ duction, i.e. the difference between the average error of the ensemble members and the error of the entire ensemble (as in [Cunningham and Carney, 2000]). We found that the correla­ tion coefficient between diversity and ensemble error reduc­ tion is 0.6225 (p 1 « 10- 50 ), which is fairly strong. Further­ more, we compared diversity with the base error reduction, i.e. the difference between the error of the base classifier and the ensemble error. The base error reduction gives a better in­ dication of the improvement in performance of an ensemble over the base classifier. The correlation of diversity versus the base error reduction is 0.1552 (p « 10- 50 ) . We note that even though this correlation is weak, it is still a statistically significant positive correlation. These results reinforce our belief that increasing ensemble diversity is a good approach to reducing generalization error.

To determine how the performance of DECORATE changes with ensemble size, we ran experiments with increasing sizes. We compared results for training on 20% of available data, since the advantage of DECORATE is most noticeable low on the learning curve. Due to lack of space, we do not include the results for all 15 datasets, but present five representative datasets (see Figure 2). The performance on other datasets is similar. We note, in general, that the accuracy of DECORATE increases with ensemble size; though on most datasets, the performance levels out with an ensemble size of 10 to 25.

1 The p-value is the probability of getting a correlation as large as the observed value by random chance, when the true correlation is zero.

5 Related Work

There have been some other attempts at building ensembles that focus on the issue of diversity. Liu et al [ 1999] and Rosen [1996] simultaneously train neural networks in an ensemble using a correlation penalty term in their error functions. Opitz and Shavlik [1996] use a genetic algorithm to search for a good ensemble of networks. To guide the search they use an objective function that incorporates both an accuracy and diversity term. Zenobi et al [2001] build ensembles based on different feature subsets; where feature selection is done using a hill-climbing strategy based on classifier error and diversity. A classifier is rejected if the improvement of one of the metrics lead to a "substantial" deterioration of the other; where "substantial" is defined by a pre-set threshold.

In all these approaches, ensembles are built attempting to simultaneously optimize the accuracy and diversity of indi­ vidual ensemble members. However, in DECORATE, our goal is to minimize ensemble error by increasing diversity. At no point does the training accuracy of the ensemble go below that of the base classifier; however, this is a possibility with previous methods. Furthermore, none of the previous stud­ ies compared their methods with the standard ensemble ap­ proaches such as Boosting and Bagging ([Opitz and Shavlik, 1996] compares with Bagging, but not Boosting).

Compared to boosting, which requires a "weak" base learner that does not completely fit the training data (boosting terminates once it constructs a hypothesis with zero training error), DECORATE requires a strong learner, otherwise the ar­ tificial diversity training data may prevent it from adequately fitting the real data. When applying boosting to strong base learners, they must first be appropriately weakened in order to benefit from boosting. Therefore, DECORATE may be a preferable ensemble meta-learner for strong learners.

To our knowledge, the only other ensemble approach to uti­ lize artificial training data is the active learning method intro­ duced in [Cohn et al., 1994]. The goal of the committee here is to select good new training examples rather than to improve accuracy using the existing training data. Also, the labels of the artificial examples are selected to produce hypotheses that more faithfully represent the entire version space rather than to produce diversity. Cohn's approach labels artificial data ei­ ther all positive or all negative to encourage, respectively, the learning of more general or more specific hypotheses.

6 Future Work and Conclusion

In our current approach, we are encouraging diversity using artificial training examples. However, in many domains, a large amount of unlabeled data is already available. We could exploit these unlabeled examples and label them as diversity data. This would allow DECORATE to act as a form of semi­ supervised learning that exploits both labeled and unlabeled data [Nigam et al., 2000].

Our current study has used J48 as a base learner; how­ ever, we would expect similarly good results with other base learners. Decision-tree induction has been the most com­ monly used base learner in other ensemble studies, but there has been some work using neural networks and naive Bayes [Bauer and Kohavi, 1999; Opitz and Maclin, 1999]. Exper­ iments on "DECORATing" other learners is another area for future work.

By manipulating artificial training examples, DECORATE is able to use a strong base learner to produce an effective, diverse ensemble. Experimental results demonstrate that the approach is particularly effective at producing highly accurate ensembles when training data is limited, outperforming both bagging and boosting low on the learning curve. The empir­ ical success of DECORATE raises the issue of developing a sound theoretical understanding of its effectiveness. In general, the idea of using artificial or unlabeled examples to aid the construction of effective ensembles seems to be a promis­ ing approach worthy of further study.

Acknowledgments

This work was supported by DARPA EELD Grant F3060201-2-0571.