# How are boosted decision stumps different from a decision tree?

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.

• I'm pretty sure he's just using "stumps" for pedagogical purposes here. He's just trying to illustrate how boosting works. Commented Apr 15, 2018 at 19:09
• Stumps are one step decision trees.
– mico
Commented Apr 16, 2018 at 17:41
• isn't the decision boundary different already? a decision tree wouldn't have that orange piece in the top right corner in (4).. I think
– oW_
Commented Apr 16, 2018 at 22:13
• @oW_ Thanks! That is what I was looking for :-) Do you want to make the comment an answer? Commented Apr 17, 2018 at 4:28
• sure, no problem
– oW_
Commented Apr 17, 2018 at 15:30

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.

• Interesting. So in principle the decision tree can learn the same decision boundary, but it needs at least one data point in the rectangle to the right. So I'm this case the decision tree would learn a simpler decision boundary than boosted decision stumps. I would say in this example the decision tree overfits less than the boosted decision stumps. Commented Apr 17, 2018 at 16:23

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.

• The question was not what a decision stump is. Commented Apr 16, 2018 at 17:10
• Is that example then not about desicion boundary? How would a stump find the two classes in second scenario? And: about David's comment I put those links.
– mico
Commented Apr 16, 2018 at 17:20
• "How would a stump find the two classes in second scenario?": No, but boosted decision stumps would. Commented Apr 16, 2018 at 17:50
• I was telling how decision stump differs from decision tree (it is kinda subclass of it), but actually reading the article behind that image I found out the method uses stumps only as partial answers that advance towards the ground truth.
– mico
Commented Apr 16, 2018 at 20:36
• Still, my example happens to answer the question even in that case. I don't believe any 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. Sorry about bad example, nobody in real life throws coin like that.
– mico
Commented Apr 16, 2018 at 20:40

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.

• Could you make a minimal example? I'm not convinced right now. Commented Apr 16, 2018 at 7:21
• That is why I gave the XOR example. It cannot be represented using boosted decision stumps, can it?
– DaL
Commented Apr 20, 2018 at 13:19
• Yes, it can. See cs.nju.edu.cn/zhouzh/zhouzh.files/publication/emfa-ch2.pdf Figure 2.3 for example Commented Apr 20, 2018 at 13:32
• I see. We were talking about different problems. I talked about the binary case.
– DaL
Commented Apr 21, 2018 at 11:13
• What do you mean by "binary case"? Commented Apr 21, 2018 at 11:52