Towards a Theoretical Framework for Ensemble Classification

1 Introduction

We apologize that space restrictions are forcing us to be terse. For a more detailed version, see [Seewald, 2003]. We will first explain how Stacking works in order to lay the founda­ tions for our functional definitions of meta classifiers later on. Fig. I shows Stacking on a hypothetical dataset.

During training, all base classifiers are evaluated via cross­ validation on the original dataset. Each classifier's output is a class probability distribution for every example, see Fig. l(b) The concatenated class probability distributions of all base classifiers, followed by the class value, forms the meta-level training set for Stacking's meta classifier, see Fig. l(c) After training the meta classifier, the base classifiers are retrained on the complete training data.

For testing, the base classifiers are queried for their class probability distributions. These form a meta-example for the meta classifier which outputs the final class prediction.

2 Definitions

An arbitrary training dataset with n examples and k classes, and a single test instance, is given. N arbitrary base classifiers have been cross-validated on this dataset, and afterwards re­ trained on the whole dataset. All base classifiers output class probability distributions, i.e. estimated probabilities for each class instead of deciding on a single class.

Then, P;jk refers to the probability given by classifier i for class j on example number k during CV. ?,k is the class prob­ ability distribution of classifier i on instance k. P; refers to Figure 1: Illustration of Stacking on a dataset with three classes (a, b and c), n examples and N base classifiers. P;,jk refers to the probability given by classifier i for class j on example number k.

the class prob.dist. for classifier i on the unknown test in­ stance. A fixed arbitrary order on the class values and N base classifiers is assumed. Classk is the true class for instance k. Attr V eck is the attribute vector of instance k. n is the num­ ber of instances. All indices are zero-based, e.g. the instance id k satisfies the equation 0 :::; k :::; n - 1.

As we mentioned, we assume that all ensemble learning schemes return class probability distributions. If predictions are needed, the position of the maximum class probability in the vector - i.e. the predicted class - is easily obtained via formula (2) Trivially, Stacking with predictions can also be simulated by this variant; simply by transforming the class distributions meta-dataset to predictions via (2) prior to ap­ plying the meta classifier.

We can now characterize every ensemble learning scheme by what features it extracts from the meta-dataset during training and how these features define the mapping from meta-dataset to final class probability distribution.

2.1 Voting

Voting, a straight-forward extension of voting for distribution classifiers, is the simplest case. During training, no features are extracted from the meta-dataset. In fact Voting does not even need the internal crossvalidation. During testing, Voting determines the final class probability distribution as follows .

Thus, it can be easily seen that the meta-classifier defined by just computing the mean probability distribution of the base classifiers - as above- simulates Voting with probability dis­ tributions. Voting with predictions can be mapped similarily. In this case, we use P', instead of P, in formula (3) P', is the vector of P:; for all j, where

2.2 X-Val

For X-Val, which chooses the best base classifier on each fold by an internal ten-fold CV, we first determine the accuracy per classifier, which can be computed directly from the meta­ level dataset, see ( 6) Then, we derive as feature the id of the classifier with the maximum accuracy. Thus, the value of bestC corresponds to our learned model.

During testing, X-Val simply returns bestC's prediction.

2.3 Grading

For Grading [Seewald and Fiirnkranz, 2001], the case is dif­ ficult. While we cannot simulate the original Grading, we will simulate a competitive variant equivalent to accuracy­ weighted voting. More details see [Seewald, 2003].

During training, the accuracies of base classifiers are ex­ tracted using formula (6) The accuracies of all our base clas­ sifiers correspond to our learned model. During testing, we build the combined class probability distribution similar to Voting using predictions but with an additional weight - namely the accuracy we extracted earlier.

where P', is again the vector of P:; for all j.

2.4 Bagging

Bagging [Breiman, 1996] is another common ensemble tech­ nique. Here, the same type of classifier is repeatedly trained on new datasets, which have been generated from the orig­ inal dataset via random sampling with replacement. After­ wards, the component classifiers are combined via simple un­ weighted voting.

Thus, we use same meta-classifier as for Voting with pre­ dictions. The number of base classifiers is equal to the iter­ ation parameter of bagging - each base classifier for Stack­ ing corresponds to one instantiation of the base learner for bagging. In order to simulate the random sampling from the training set, the base learner's training sets have to be modi­ fied before training, via formula (9)

During training, Formula (9) is used to create- for each base classifier separately - a training set of the same size as the original training set via random sampling from the original training set, exactly as in Bagging. These training sets are then used to train the base classifiers. This approach can also be seen as a probabilistic wrapper around each base classifier. No features are extracted from the meta-level dataset during training, as for Voting.

During testing, each base classifier gives a prediction. These predictions are then voted to yield the final prediction, exactly as for Voting with predictions, i.e. (3) modified via ( 4)- for more details refer to subsection 2.1. Concluding, we have shown the equivalence of Bagging and Stacking.

3 Discussion & Conclusion

By definition StackingC [Seewald, 2002], can also be mapped onto Stacking via a special meta classifier. In fact, the avail­ able implementation is a specialized subclass of a common meta classifier, MLR. Another recent variant, sMMS [Dzeroski and Zenko, 2002], is also implemented via a special meta classifier and thus amenable to the same kind of mapping. However, AdaBoost [Freund and Schapire, 1996] cannot be simulated by Stacking because of its sequential nature.

While the given formal definitions of meta classifiers are mainly intended to enable further theoretical work, a direct implementation is also feasible. The cost penalty for the sim­ ulation is small, since training the meta classifiers usually contributes little to the total runtime.

Concluding, we have shown that Stacking is equivalent to common ensemble learning schemes, namely Selection by Crossvalidation (X-Val), Voting of either class probability dis­ tributions or predictions, a competitive variant of Grading , and Bagging. Recent variants such as StackingC [Seewald, 2002] and sMMS [Dzeroski and Zenko, 2002] are also equiv­ alent. Thus we conclude that our approach offers a unique viewpoint on Stacking which is an important step towards a theoretical framework for ensemble learning.

Acknowledgements This research is supported by the Austrian Fonds zur Forderung der Wissenschaftlichen Forschung (FWF) un­ der grant no. Pl2645-INF. The Austrian Research Institute for Arti­ ficial Intelligence is supported by the Austrian Federal Ministry of Education, Science and Culture.