8
$\begingroup$

Boosting algorithms, such as AdaBoost, combine multiple 'weak' classifiers to form a single stronger classifier. Although in theory boosting should be possible with any base classifier, in practice it seems that tree-based classifiers are the most common.

Why is this? What properties of tree classifiers make them best suited for this task? Are there any other base classifiers which also benefit a lot from boosting? I ask with classification problems in mind, but I would also be interested in answers concerning regression applications.

$\endgroup$
10
$\begingroup$

I'm pretty sure you're correct and that there's no reason that necessarily requires using decision trees instead of other classifiers. That said, I think there are a few reasons they're often used. Speed is one factor: Boosting may require training a lot of classifiers. If each one is a giant, multi-layer neural network, the whole procedure is going to be very slow.

More importantly, I think decision trees are "good enough." Since the whole idea behind boosting is pooling weak classifiers, there's not a huge incentive to drop in a heavy-weight solutions that might require more tuning (e.g., fiddling with the hyperparameters and kernel for SVMs).

Finally, boosting and decision trees are, at least in my head, somewhat conceptually similar (e.g., add a node/build a new classifier). A lot of the ensemble learning stuff seems to use trees. I think you could have a "random forest" of Naive Bayes learners if you really wanted to.

$\endgroup$
  • 1
    $\begingroup$ I wasn't totally sure about this, but this thread comes to similar conclusions: stats.stackexchange.com/questions/13597/… $\endgroup$ – Matt Krause Mar 23 '12 at 4:37
  • $\begingroup$ I think speed may be something of a red herring here - most of the time I'd rather have a more accurate classifier than something which is slightly faster to train. After all, CPU time is fairly cheap nowadays. $\endgroup$ – Martin O'Leary Mar 23 '12 at 4:48
  • $\begingroup$ True,true, though the appeal of boosting is that you can get fast, accurate predictions out of methods that can only ordinarily give you fast predictions. That said, I should have emphasized them in this order: Good enough > speed > whatever's going on in my head :-) $\endgroup$ – Matt Krause Mar 23 '12 at 4:53
  • $\begingroup$ I see what you're saying, but I still feel that "good enough" is a bit of an unsatisfying answer. I do take your point about the lack of fiddling with hyper parameters though. $\endgroup$ – Martin O'Leary Mar 23 '12 at 5:47
9
$\begingroup$

There are some characteristics which may add insight to an understanding of ensemble methods.

Bagging

Probably the simplest ensemble method, bagging, which is nothing more than a collection of similar homogeneous classifiers built on resampled training data and held together by a combination method, ameliorates the variance caused by instability in the base classifiers by averaging their outputs. The ensemble leverages this instability to address the variance component of the error of the base classifier and to a lesser degree their bias.

You can think of bagging as providing a significant degree of smoothing to what would otherwise be a very unstable "weak" base classifier.One reason, apart from their tendency towards computational efficiency, why weak classifiers are chosen is that they exhibi higher diversity, which is a beneficial characteristic for ensembles.

If you visualise an bagged ensemble full of very strong stable classifiers, they will have a very high degree of agreement on their classifications of examples presented to the ensemble. In effect they all vote the same way. A committee in which all members vote similarly has little utility over any single member of the committee.

So to work effectively an ensemble must embrace a degree of diversity amongst it's members. Clearly a committee of members who spew forth almost random opinions is not of great utility either. So some intermediate position between these extremes is sought.

In practice, as no complete theory on the subject exists, this compromise is found using empirical methods such as cross-validation or hold out trials. These are used to gauge a suitable strength for the base classifier.

Because this search for an optimum ensemble will normally involve adjusting parameters of the base classifiers and the ensemble itself, it is desirable that the number of such parameters be kept as small as possible. If not, the dimensionality of the parameter search space quickly means that finding the global minimum is computationally intractable. Decision trees are a popular choice because, as has been mentioned, they can be used effectively without necessarily tuning any of their parameters.

Random Forests

Random forests, which are primarily bagged decision trees, leverage the significant instability of trees by the injecting of a strong stochastic component [ the permutations of a small number of features/factors at each decision node within a tree ] to create diversity within the ensemble. Because each node of a tree is presented with a new random selection of features the trees are highly diverse. The ensemble then has the effect of averaging out the variance and bias of the diverse collection of trees.

To be effective a "random forest" of naive Bayes classifiers, or any other stable base classifier such as SVMs, needs the addition of stochastic element. For stable classifiers relatively small variations in training data, such as arise from bagging, lead to very similar classifiers.

To increase diversity other approaches could be applied. For instance permuting the features shown to each base classifier. This has a restriction that the significant available diversity is held to the number of combinations of the feature set. Once the combinations have been exhausted there are no new classifiers available to the ensemble which would vote differently to existing members.

For problems with relatively few features this severely limits the available pool of classifiers. It would be possible to inject further sources of randomness, say by aggressively sub-sampling the training data. The evidence would seem to be, that in the general case, such an approach is inferior to the particular blend of bias and diversity that a random forest offers.

It is possible to successfully utilise other unstable base classifiers, such as multi-layer perceptrons (neural networks) which have few nodes and restricted amounts of training or point based space filling approaches for instance stochastic discrimination, to inject diversity in ensembles methods. Certainly in the case of MLPs a degree of parameter tuning is essential.

Boosting

Boosting takes a different approach to building the ensemble than the simple agglomerative model adopted by Bagging. I suppose conceptually if you think of bagging as being a flat ensemble model, boosting constructs a layered classifier.

Each round of boosting chooses a new classifier from a set of potential classifiers constructed from training data weighted, or resampled, according to the mis-classifications of the previous round. The new classifier is selected so as to minimise the total ensemble error.

This is in sharp contrast to the lack of selection criteria resent in random forest ensemble construction. Each new base classifier is specifically required to focus on the weak points of the existing ensemble, with the result that boosting aggressively drives down training error.

In the early stages of ensemble construction boosting has few weak classifiers and each is focused on different areas of the training space, the effect of this is to primarily reduce bias. As the ensemble size grows the scope for bias reduction diminishes and error from variance is improved.

The benefit from instability in the base classifier for boosting is that as the ensemble grows, the number of remaining mis-classified examples falls. A higher degree of diversity is needed to generate a classifier which adopts a usefully different view of the remaining samples than its predecessors.

The power of this approach can be seen by the fact that acceptable results can be achieved with only decision stumps, though MLPs have proved very effective in general.

Because of this constant focus on the misclassified examples, boosting's weakness is that it can be susceptible to noise, to some extent logitboost attempts to address this failing.

No free lunch

It is worth remembering that no grand unified theory of machine learning exists and that the results of any particular classifier are highly dependent on the type of data it is used with. So, a priori, there isn't any hard and fast reason to assert one classifier type being superior over another, other than the consensus derived from previous experimentation with similar data and the general utility shown by an algorithm across a variety of data sets. To get a good solution, you may want to experiment with a handful of popular approaches.

$\endgroup$
  • $\begingroup$ +1 for mentioning NFL, but I'd argue that NFL is the 'grand unified theory' of machine learning, or as close to such a thing as we're ever likely to see... $\endgroup$ – John Doucette Mar 23 '12 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.