3
$\begingroup$

Descriptions of boosting (and specific techniques like gradient boosting) typically talk about "weak learners" in general, and then immediately switch to discussing boosted trees specifically.

Why is this? I've seen some discussions regarding boosting SVMs, but little to no discussion about boosting neural networks or Gaussian processes, for instance. Is there any literature on the topic of why trees are more suitable for boosting than other "learners"?

$\endgroup$
2
$\begingroup$

Trees are often a good choice for new data mining problems with unknown structure. From The Elements of Statistical Learning section 10.7:

"Industrial and commercial data mining applications tend to be especially challenging in terms of the requirements placed on learning procedures. Data sets are often very large in terms of number of observations and number of variables measured on each of them. Thus, computational considerations play an important role. Also, the data are usually messy: the inputs tend to be mixtures of quantitative, binary, and categorical variables, the latter often with many levels. There are generally many missing values, complete observations being rare. Distributions of numeric predictor and response variables are often long-tailed and highly skewed...In addition they usually contain a substantial fraction of gross mis-measurements (outliers). The predictor variables are generally measured on very different scales.

In data mining applications, usually only a small fraction of the large number of predictor variables that have been included in the analysis are actually relevant to prediction. Also, unlike many applications such as pattern recognition, there is seldom reliable domain knowledge to help create especially relevant features and/or filter out the irrelevant ones, the inclusion of which dramatically degrades the performance of many methods.

In addition, data mining applications generally require interpretable models. It is not enough to simply produce predictions. It is also desirable to have information providing qualitative understanding of the relationship between joint values of the input variables and the resulting predicted response value. Thus, black box methods such as neural networks, which can be quite useful in purely predictive settings such as pattern recognition, are far less useful for data mining.

These requirements of speed, interpretability and the messy nature of the data sharply limit the usefulness of most learning procedures as off- the-shelf methods for data mining. An “off-the-shelf” method is one that can be directly applied to the data without requiring a great deal of time- consuming data preprocessing or careful tuning of the learning procedure.

Of all the well-known learning methods, decision trees come closest to meeting the requirements for serving as an off-the-shelf procedure for data mining. They are relatively fast to construct and they produce interpretable models (if the trees are small). As discussed in Section 9.2, they naturally incorporate mixtures of numeric and categorical predictor variables and missing values. They are invariant under (strictly monotone) transformations of the individual predictors. As a result, scaling and/or more general transformations are not an issue, and they are immune to the effects of predictor outliers. They perform internal feature selection as an integral part of the procedure. They are thereby resistant, if not completely immune, to the inclusion of many irrelevant predictor variables. These properties of decision trees are largely the reason that they have emerged as the most popular learning method for data mining.

Trees have one aspect that prevents them from being the ideal tool for predictive learning, namely inaccuracy. They seldom provide predictive accuracy comparable to the best that can be achieved with the data at hand. As seen in Section 10.1, boosting decision trees improves their accuracy, often dramatically. At the same time it maintains most of their desirable properties for data mining. Some advantages of trees that are sacrificed by boosting are speed, interpretability, and, for AdaBoost, robustness against overlapping class distributions and especially mislabeling of the training data. A gradient boosted model (GBM) is a generalization of tree boosting that attempts to mitigate these problems, so as to produce an accurate and effective off-the-shelf procedure for data mining."

Sorry, long quote, but I think it explains their rationale/excuse for only addressing trees. They go on to derive a Boosting algorithm that uses trees, explain what parameters they have to find to make it work, define steepest descent in the context of what I have seen elsewhere called the "function space" (f = {f(x1), f(x2), ... f(xN)}), explain how constraining their next classifier in the ensemble to a tree that has similar outputs to the steepest descent "direction" generalizes better than just adding the steepest descent function directly (Some kind of regularization going on?), and then define an algorithm.

But they neglect to address the fact that we often do want to use Boosting in the context of pure prediction. And it's great we see such an amazing performance improvement when GradientBoosting with trees, but what about the other weak learners we are used to Boosting being able to handle?

There is no principled reason decision trees could not be replaced with some other low-bias, high-variance learner like small neural nets. It would definitely change steps 2.b. and 2.c. of their algorithm 10.3. It might also change the initialization at step 1. But it could be done! I am not sure there are any common or popular algorithms in the literature, though. When I looked for them I came across your question instead. It may be that trees are easier to train and have a provably low risk as an ensemble such that no one expects anything else to be able to do better?

$\endgroup$
  • $\begingroup$ Thank you! This was the sort of answer I was looking for, so thanks for writing it months after I posted my question. Once I've got time I'll try experimenting a bit with using other types of learners instead of trees. $\endgroup$ – haroba Aug 17 '17 at 21:41
  • $\begingroup$ If you come up with an algorithm that works, post it. Maybe even publish it. $\endgroup$ – Pavel Komarov Aug 17 '17 at 23:01
3
$\begingroup$

That's true. Boosting is meant for weak learners, meaning models that are only a little bit better than random guessing because it allows you to combine all these different weak models that are good at classifying specific examples, but are pretty bad with the rest. In other words, they turn out to be uncorrelated (I bet that's another word you've seen in the articles. Believe me, I've been there).

Neural networks, however, definitely tend not to be weak. Tend to be pretty strong actual, but that does depend on the data you are working with and its structure. I am actually working on a project where I am boosting feedforward networks with data that has significant temporal structure. I include a few time lags in my feature vector, and am hoping that boosting will take care of the rest.

$\endgroup$
  • 1
    $\begingroup$ Ordinary neural networks tend to be strong, but ordinary (fully-developed) decision trees are pretty strong too. Surely it would be possible to construct a "weak" neural network? The reason why I asked this question in the first place is that I was considering building a boosted Gaussian process model where the "weak learners" are ordinary (non-approximated) Gaussian process regression models on small subsets of the training data. $\endgroup$ – haroba May 30 '17 at 8:36
  • $\begingroup$ In fact, I found a paper that did just that, but given that it's been 10 years since the paper was published and I haven't seen anybody else use this kind of model I wonder if it's fundamentally flawed or just plain useless. $\endgroup$ – haroba May 30 '17 at 8:39

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.