How are boosted decision stumps different from a decision tree?

Question

For example, taking the image from sebastian raschkas post "Machine Learning FAQ":

I would expect a very similar (if not exactly the same) result for a decision tree: Given only two features, it finds the optimal feature (and value for that feature) to split the classes. Then, the decision tree does the same for each child considering only the data which arrives in the child. Of course, boosting considers all the data again, but at least in the given sample it leads to exactly the same decision boundary. Could you make an example where a decision tree would have a different decision boundary on the same training set than boosted decision stumps?

I have the intuition that boosted decision stumps are less likely to overfit because the base classifier is so simple, but I couldn't exactly pin point why.

Answer 1

The decision boundary in (4) from your example is already different from a decision tree because a decision tree would not have the orange piece in the top right corner.

After step (1), a decision tree would only operate on the bottom orange part since the top blue part is already perfectly separated. The top blue part would be left unchanged.

The boosted stumps, however, operate (as you mentioned) on the full dataset again, which can lead to different results.

Answer 2

Decision stump are decision trees with one step from root to leaves whereas Decision trees can have several steps between root and leaves.

Easy example of these two is that a decision stump could be which side of coin faces up when thrown and a decision tree would be that if the coin could is touching the ground already (states are interconnected):

    stump                         tree
Is the coin thrown       Is it touching ground
        |                            |
  50         50           can turn?       lays still?
                               |              |
                      to right   to left    0    0
                            |         |
                          0  100   100 0

Boosting can't help if decision tree in my example exactly knows before decision for example the side of turning possibility and for stump always one step after.

So, stump can help in finding a statistical pattern in that example but not the underlying external facts affecting the system in certain move, if the conditions vary randomly in time.

Answer 3

The representation power of the models is different. Consider the case of XOR for many features. Assume the all the features are binary, just randomly sampled fro B(0.5).

A decision tree will be able to represent that concept, in exponential size.

Any of the features alone is useless (or misleading). A decision stump is restricted to a single feature.

Even if the decision stumps will choose the right features, one cannot represent XOR using a linear weight of the features. In simpler words, the reason the XOR is not linear is that there is no weight w such that a xor b = w*a + (1-w)*b.