Stacked Generalizations: When Does It Work?

1 Introduction

Stacked generalization is a way of combining multiple models that have been learned for a classification task [Wolpert, 1992]. The first step is to collect the output of each model into a new set of data. For each instance in the original training set, this data set represents every model's prediction of that instance's class, along with its true classification. During this step, care is taken to ensure that the models are formed from a batch of training data that does not include the instance in ques­ tion, in just the same way as ordinary cross-validation. The new data is treated as the data for another learning problem, and in the second step a learning algorithm is employed to solve this problem. In Wolpert's terminol­ ogy, the original data and the models constructed for it in the first step are referred to as level-0 data and level-0 models, respectively, while the set of cross-validated data and the second-stage learning algorithm are referred to as level-1 data and the level-1 generalizer.

In this paper, we show how to make stacked gener­ alization work for classification tasks by addressing two crucial issues which Wolpert [1992] originally described as 'black art' and have not been resolved since. The two issues are (i) the type of attributes that should be used to form level-1 data, and (ii) the type of level-1 general­ izer in order to get improved accuracy using the stacked generalization method.

Breiman [1996a] demonstrated the success of stacked generalization in the setting of ordinary regression. The level-0 models are regression trees of different sizes or lin­ ear regressions using different number of variables. But instead of selecting the single model that works best as judged by (for example) cross-validation, Breiman used the different level-0 regressors' output values for each member of the training set to form level-1 data. Then he used least-squares linear regression, under the con­ straint that all regression coefficients be non-negative, as the level-1 generalizer. The non-negativity constraint turned out to be crucial to guarantee that the predictive accuracy would be better than that achieved by selecting the single best predictor.

Here we show how stacked generalization can be made to work reliably in classification tasks. We do this by using the output class probabilities generated by level-0 models to form level-1 data. Then, for the level-1 gener­ alizer we use a version of least squares linear regression adapted for classification tasks. We find the use of class probabilities to be crucial for the successful application of stacked generalization in classification tasks. How­ ever, the non-negativity constraints found necessary by Breiman in regression are irrelevant to improved predic­ tive accuracy in our classification situation.

In Section 2, we formally introduce the technique of stacked generalization and describe pertinent details of each learning algorithm used in our experiments. Sec­ tion 3 describes the results of stacking three different types of learning algorithms. The following section de­ scribes related work, and is followed by a summary of our conclusions and future work.

2 Stacked Generalization

Given a data set C = {(yn, Xn), n = 1, ... , N}, where Yn is the class value and Xn represents the attribute values of the nth instance, randomly split the data into J almost equal parts £1 , . . . , LJ . Define Lj and£( -j) = £- Lj to be the test and training sets for the jth fold of a J-fold cross-validation. Given K learning algorithms, which we call level-0 generalizers, invoke the kth algorithm on the data in the training set £( -j) to induce a model M~ - j), for k = 1, ... , K. These are called level-0 models.

For each instance x in L j, the test set for the jth cross­ validation fold, let Vk- j) ( x) denote the prediction of the model M~-j) on x. Let

At the end of the entire cross-validation process, the data assembled from the outputs of the K models is

This is the level-1 data. Use some learning algorithm that we call the level-1 generalizer to derive from this data a model M. This is the level-1 model. To com­ plete the training process, models Mk , k = 1, ... , K, are derived using all the data in £ .

Now let us consider the classification process, which uses the models M k. k = 1, ... , K , in conjunction with M. Given a new instance, models Mk produce a vector (z1 , . .. , ZK ) . This vector is input to the level-1 model M, whose output is the final classification result for that instance. This completes the stacked generalization method as proposed by Wolpert [1992], and also used by Breiman [1996a] and LeBlanc and Tibshirani [1993].

As well as the situation described above, which results in the level-1 model M, the present paper also considers a further situation where the output from the level-0 models is a set of class probabilities rather than a single class prediction. If model M~-j) is used to classify an instance x in Lj, let P~-;- j) ( x) denote the probability of the ith output class, and write

As the level-1 data, assemble together the class proba­ bility vector from all K models, along with the original class:

(assuming there are I classes). Denote the level-1 model derived from this as M' to contrast it with M. The rest of the procedure is the same as the original one.

The following two subsections describe the algorithms used as level-0 and level-1 generalizers in the experiments reported in Section 3.

2.1 Level-0 Generalizers

Three learning algorithms are used as the level-0 general­ izers: C4.5, a decision tree learning algorithm [Quinlan, 1993] ; NB, are-implementation of a Naive Bayesian clas­ sifier [Cestnik, 1990] ; and IB1, a variant of a lazy learning algorithm [Aha et al., 1991] which employs the p-nearest­ neighbor method using a modified value-difference met­ ric for nominal and binary attributes [Cost and Salzberg, 1993] . For each of these learning algorithms we now show the formula that we use for the estimated output class probabilities Pi(x ) for an instance x (where, in all cases, I:i Pi(x ) = 1) .

C4.5: Consider the leaf of the decision tree at which the instance x falls. Let mi be the number of (training) instances with class i at this leaf, and suppose the majority class at the leaf is f. Let E = l:i;ii mi . Then, using the Laplace estimator,

NB: Let P(ilx) be the posterior probability of class i, given instance x. Then

IBl: Suppose p nearest neighbors are used; denote them by {(y., x. ),s = 1, ... ,p} for instance x. (We use p = 3 in the experiments.) Then

where f(y. ) = 1 if i = Ys and 0 otherwise, and dis the Euclidean distance function.

In all three learning algorithms, the predicted class of the level-0 model, given an instance x, is that i for which Pj(x) > Pi(x ) for all i =f. f .

2.2 Level-l Generalizers

We compare the effect of four different learning algo­ rithms as the level-1 generalizer: C4.5, IB1(using p = 21 nearest neighbors), 1 NB, and a multi-response linear re­ gression algorithm, MLR. Only the last needs further explanation.

MLR is an adaptation of a least-squares linear regres­ sion algorithm that Breiman [1996a] used in regression settings. Any classification problem with real-valued at­ tributes can be transformed into a multi-response regres­ sion problem. If the original classification problem has I classes, it is converted into I separate regression prob­ lems, where the problem for class e has instances with responses equal to one when they have class e and zero otherwise.

1 A large p value is used following Wolpert's [1992) advice that " . .. it is reasonable that 'relatively global, smooth ... ' level-1 generalizers should perform well."

The input to MLR is level-1 data, and we need to consider the situation for the model M', where the at­ tributes are probabilities, separately from that for the model M, where they are classes. In the former case, where the attributes are already real-valued, the linear regression for class e is simply

In the latter case, the classes are unordered nominal at­ tributes. We map them into binary values in the obvious way, setting pki (X) to 1 if the class of instance X is £ and zero otherwise; and then use the above linear regression.

Choose the linear regression coefficients { akil} to min­ imize

The coefficients { akil} are constrained to be non­ negative, following Breiman's [1996a] discovery that this is necessary for the successful application of stacked gen­ eralization to regression problems. The non-negative­ coefficient least-squares algorithm described by Lawson and Hanson [1995] is employed here to derive the linear regression for each class. We show later that, in fact, the non-negative constraint is unnecessary in classifica­ tion tasks.

With this in place, we can now describe the working of MLR. To classify a new instance x, compute LRt(x) for all I classes and assign the instance to that class e which has the greatest value: LRt (X) > LRt' (X) for all f!' =I= e.

3 Stacking C4.5, NB and IBI

3.1 When does stacking work?

The experiments in this section show that

• for successful stacked generalization it is necessary to use output class probabilities rather than class predictions-that is, M' rather than M;
• only MLR is suitable for the level-1 generalizer.

We use two artificial datasets and eight real-world datasets from the UCI Repository of machine learning df-tabases [Merz and Murphy, 1996] . Details of these are given in Table 1.

For the artificial datasets-Led24 and Waveform­ each training dataset .C is generated using a different

N-nommal; B-bmary; C: Contmuous.

seed. The algorithms used for the experiments are then tested on a separate dataset of 5000 instances. Results are expressed as the average error rate of ten repetitions of this entire procedure.

For the real-world datasets, W-fold cross-validation is performed. In each fold of this cross-validation, the training dataset is used as .C, and the models derived are evaluated on the test dataset. The result is expressed as the average error rate of theW-fold cross-validation. Note that this cross-validation is used for evaluation of the entire procedure, and is quite different from the J­ fold cross-validations employed as part of the stacked generalization operation. However, both W and J are set to 10 in the experiments.

Table 2 shows the average error rates of C4.5, NB and IB 1, and BestCV, which is the best of the three, selected using J-fold cross-validation. As expected, BestCV is almost always the classifier with the lowest error rate. 2

Table 3 shows the result of stacked generalization us­ ing the level-1 model M, for which the level-1 data com­ prises the classifications generated by the level-0 models, and M', for which the level-1 data comprises the prob­ abilities generated by the level-0 models. Results are shown for the best two level-1 generalizers in each case (full results see Ting and Witten [1997a]), along with BestCV. The lowest error rate for each dataset is given in bold.

Table 4 summarizes the results in Table 3 in terms of a comparison of each level-1 model with BestCV totaled over all datasets. Clearly, the best level-1 model is M' derived using MLR. It performs better than BestCV in nine datasets and equally well in the tenth. The best performing M is derived from NB, which performs better than BestCV in seven datasets but significantly worse in two.

The datasets are shown in the order of increasing size. MLR performs significantly better than BestCV in the four largest datasets. 3 This indicates that stacked gener­ alization is more likely to give significant improvements in predictive accuracy if the volume of data is large­ a direct consequence of more accurate estimation using cross-validation.

2 Note that BestCV does not always select the same clas­ sifier in all W folds. That is why its error rate is not always equal to the lowest error rate among the three classifiers.

MLR has an advantage over the other three level-1 generalizers in that its model can easily be interpreted. Examples of the combination weights it derives (for the probability-based model M') appear in Table 5 for the Splice dataset. The weights indicate the relative impor­ tance of the level-0 generalizers for each prediction class. In this dataset, NB is the dominant generalizer for pre­ dicting class 2, NB and IB1 are both good at predicting class 3, and all three generalizers make a worthwhile con­ tribution to the prediction of class 1.

3 We regard a 'difference of more than two standard errors as significant (95% confidence).

3.2 Are non-negativity constraints

necessary?

Both Breiman [1996a] and LeBlanc and Tibshirani [1993] use the stacked generalization method in a regression set­ ting and report that it is necessary to constrain the re­ gression coefficients to be non-negative in order to guar­ antee that stacked regression improves predictive accu­ racy. Here we investigate this finding in the domain of classification tasks.

To assess the effect of the non-negativity constraint on performance, three versions of MLR are employed to derive the level-1 model M':

• i each linear regression in MLR is calculated with an intercept constant (that is, I + 1 weights for the I classes) but without any constraints;
• ii each linear regression is derived with neither an in­ tercept constant (I weights for I classes) nor con­ straints;
• iii each linear regression is derived without an inter­ cept constant, but with non-negativity constraints (I non-negative weights for I classes).

The third version is the one used for the results pre­ sented earlier. Table 6 shows the results of all three ver­ sions. They all have almost indistinguishable error rates. We conclude that in classification tasks, non-negativity constraints are not necessary to guarantee that stacked generalization improves predictive accuracy.

However, there is another reason why it is a good idea to employ non-negativity constraints. Table 7 shows an example of the weights derived by these three versions of MLR on the Euthyroid dataset . The third version, shown in row (iii), supports a more perspicuous inter­ pretation of each level-0 generalizer's contribution to the class predictions than do the other two. In this dataset C4.5 is the dominant generalizer, as evidenced by its high weights. However, the negative weights render the interpretation of the other two versions much less clear.

3.3 How does stacked generalization compare to majority vote?

Let us now compare the error rate of M', derived from MLR, to that of majority vote, a simple decision com­ bination method which requires neither cross-validation nor level-1 learning. Table 8 shows the average error rates of BestCV, majority vote and MLR. In order to see whether the relative performances of level-0 generalizers have any effect on these methods, the number of stan­ dard errors (#SE) between the error rates of the worst performing level-0 generalizer and BestCV is given, and the datasets are re-ordered according to this measure. Since BestCV almost always selects the best performing level-0 generalizer, small values of #SE indicate that the level-0 generalizers perform comparably to one another, and vice versa.

MLR compares favorably to majority vote, with seven wins versus three losses. Out of the seven wins, six have significant differences (the only exception is for the Splice dataset); whereas all three losses have insignificant differ­ ences. Thus the extra computation for cross-validation and level-1 learning seems to have paid off.

It is interesting to note that the performance of ma­ jority vote is related to the size of #SE. Majority vote compares favorably to BestCV in the first seven datasets, where the values of #SE are small. In the last three, where #SE is large, majority vote performs worse. This indicates that if the level-0 generalizers perform compa­ rably, it is not worth using cross-validation to determine the best one, because the result of majority vote---which is far cheaper-is not significantly different. The same applies when majority vote is compared with MLR. MLR performs significantly better in the five datasets that have large #SE values, but only one in the other cases.

Summary

• None of the four learning algorithms used to obtain model M perform satisfactorily.
• MLR is the best of the four learning algorithms to use as the level-1 generalizer for obtaining model M'.
• When obtained using MLR, M' has lower predictive error rate than the best model selected by J-fold cross-validation, for almost all datasets used in the experiments.
• Another advantage of MLR over the other three level1 generalizers is its interpretability. The weights O:ki indicates the different contributions that each level-0 model makes to the prediction classes.
• Model M' can be derived by MLR with or without non-negativity constraints. Such constraints make little difference to the model's predictive accuracy.
• The use of non-negativity constraints in MLR has the advantage of interpretability. Non-negative weights O:ki support easier interpretation of the extent to which each model contributes to each class.
• When derived using MLR, model M' compares favor­ ably with majority vote.

4 Related work

Our analysis of stacked generalization was motivated by that of Breiman [1996a], discussed earlier, and LeBlanc and Tibshirani [1993] . LeBlanc and Tibshirani [1993] ex­ amine the stacking of a linear discriminant and a near­ est neighbor classifier and show that, for one artificial dataset, a method such as MLR performs better with non-negativity constraints than without. Our results show that these constraints are irrelevant to MLR's pre­ dictive accuracy in the classification situation.

The limitations of MLR are well-known [Duda and Hart, 1973] . For a /-class problem, it divides the descrip­ tion space into I convex decision regions. Every region is singly connected, and the decision boundaries are linear hyperplanes. This means that MLR is most suitable for problems with unimodal probability densities. Despite these limitations, MLR still performs better as a level-1 generalizer than IBl , its nearest competitor in deriving M' . These limitations may hold the key for a fuller understanding of the behavior of stacked generalization. Jacobs [1995) reviews linear combination methods like that used in MLR.

Previous work on stacked generalization, especially as applied to classification tasks, has been limited in sev­ eral ways. They have a different focus and evaluate the results on just a few datasets [LeBlanc and Tibshirani, 1993; Chan and Stolfo, 1995; Kim and Bartlett, 1995; Fan et al., 1996].

5 Conclusions and future work

We have addressed two crucial issues for the successful implementation of stacked generalization in classification tasks. First, class probabilities should be used instead of the single predicted class as input attributes for higher­ level learning. Second, the multi-response least squares linear regression technique should be employed as the high-level generalizer.

When combining three different types of learning al­ gorithms, this implementation of stacked generalization was found to achieve better predictive accuracy than both model selection based on cross-validation and ma­ jority vote. Unlike stacked regression, non-negativity constraints in the least-squares regression are not neces­ sary to guarantee improved predictive accuracy in clas­ sification tasks. However, these constraints are still pre­ ferred because they increase the interpretability of the level-1 model.

This paper concentrates on finding conditions under which stacked generalization works. A better under­ standing of why it works in this particular configuration may open up other possibilities for further improvement of stacked generalization.

The implication of our successful implementation of stacked generalization is that earlier model combination methods which employs (weighted) majority vote, aver­ aging, or other computations that do not make use of Ievel-l learning, can now apply this learning to improve their predictive accuracy. This includes methods which combine models derived from a single learning algorithm such as bagging and arcing [Breiman, 1996b; 1996c). The full version of this paper [Ting and Witten, 1997a) and a subsequent investigation [Ting and Witten, 1997b) in­ clude studies of this kind of model combination.

Acknowledgments

The authors are grateful to the New Zealand Marsden Fund for financial support for this research.