2
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ I'm pretty sure he's just using "stumps" for pedagogical purposes here. He's just trying to illustrate how boosting works. $\endgroup$ – David Marx Apr 15 '18 at 19:09
  • $\begingroup$ Stumps are one step decision trees. $\endgroup$ – mico Apr 16 '18 at 17:41
  • 2
    $\begingroup$ 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 $\endgroup$ – oW_ Apr 16 '18 at 22:13
  • $\begingroup$ @oW_ Thanks! That is what I was looking for :-) Do you want to make the comment an answer? $\endgroup$ – Martin Thoma Apr 17 '18 at 4:28
  • $\begingroup$ sure, no problem $\endgroup$ – oW_ Apr 17 '18 at 15:30
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Martin Thoma Apr 17 '18 at 16:23
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you make a minimal example? I'm not convinced right now. $\endgroup$ – Martin Thoma Apr 16 '18 at 7:21
  • $\begingroup$ "The representation power of the models is different." I'm pretty sure this is wrong. While they learn different boundarys with the same data in some cases (as shown by the accepted answer) the set of possible decision boundaries is equal for both model classes. $\endgroup$ – Martin Thoma Apr 17 '18 at 16:27
  • $\begingroup$ That is why I gave the XOR example. It cannot be represented using boosted decision stumps, can it? $\endgroup$ – DaL Apr 20 '18 at 13:19
  • $\begingroup$ Yes, it can. See cs.nju.edu.cn/zhouzh/zhouzh.files/publication/emfa-ch2.pdf Figure 2.3 for example $\endgroup$ – Martin Thoma Apr 20 '18 at 13:32
  • $\begingroup$ I see. We were talking about different problems. I talked about the binary case. $\endgroup$ – DaL Apr 21 '18 at 11:13
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The question was not what a decision stump is. $\endgroup$ – Martin Thoma Apr 16 '18 at 17:10
  • $\begingroup$ 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. $\endgroup$ – mico Apr 16 '18 at 17:20
  • $\begingroup$ "How would a stump find the two classes in second scenario?": No, but boosted decision stumps would. $\endgroup$ – Martin Thoma Apr 16 '18 at 17:50
  • $\begingroup$ 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. $\endgroup$ – mico Apr 16 '18 at 20:36
  • $\begingroup$ 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. $\endgroup$ – mico Apr 16 '18 at 20:40

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.