How to use CART for AdaBoost?

Question

I am trying to use CARTs (Classification and Regression Trees) for AdaBoost as weak learner. My question concerns the update of the weights after fitting the best weak learner.

A single CART node consists of a simple threshold (and of course the selected feature descriptor) which separates the data set for the left successor and/or right successor node.

Let us assume that I want to update the weight of a single data point $x_i$ by using a single CART with depth 3.

                                                 root
                                          /                \
                                        n1(-1)              p1(+1)
                                      /      \           /      \
                                   n2(-1)   p2 (+1)     n3(-1)    p3(+1)

Must I use all traversed nodes for the update of the weight or do I only need the final output of the tree for the update? I saw the first approach in the GML AdaBoost MATLAB Toolbox.

I hope I could describe my problem sufficiently.

Answer 1

AdaBoost makes no assumption about the internals of a classifier, so you should only need the final output.

The weight is used as a coefficient for the classifier (function) trained in the given iteration. Boosting will give you a weighted sum of trees. The leaf regions are typically different from tree to tree, so to approximate the boosted classifier by a single tree, you'd need a tree of a much larger tree depth than for the individual trees.