0
$\begingroup$

When I learned about CART, we learned that at each split, we try to minimize some measure (usually Gini index) of the split. That is, we determine the predictor and threshold that decreases the Gini index the most.

I am reading about the AdaBoost model and am not seeing the criteria used to determine the splits and how it factors in our weighted observations. I'm assuming we no longer use the Gini index?

To determine a split, do we just minimize the weighted sum of the weighted error rate? Do we pick the split the decreases the weighted error rate the most? Per AdaBoost, the weighted error rate is calculated as: enter image description here

Let's say the two child nodes have a total of 20 observations. Let's say the left node (L) has m observations and thus the right node (R) has (20 - m) observations. Do we determine the split that minimizes:

m/20 * err(L) + (20 - m)/20 * err(R)

where L and R are the left and right child nodes and err(L) is the error rate of the left child node using the formula given by AdaBoost?

$\endgroup$
1
$\begingroup$

I think you're confusing some notions here - no pun intended with your pseudo.

Adaboost is a boosting algorithm that aggregate several "weak learner" to make more robust predictions. Thus it is a meta algorithm so there are two level of optimisation.

  1. Reduce the error over the meta model (aggregation of weak learners) => the weighted error rate intervenes here
  2. Reduce the error over each weak learner. Most of the time weak learners are trees (e.g. CART in sklearn) => Gini or Entropy criteria intervenes here
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So the error rate in the above is not used in building an individual tree at all. So let's say we build a CART. The CART is still built on unweighted data and uses (Gini or entropy) to determine splits. Basically you build the CART per usual. Then the predictions of our CART are fed into the error rate formula above. That allows us to calculate alpha and the weights used in AdaBoost. These weights never affect the CART algo at all? $\endgroup$ – confused Feb 10 at 20:16
  • $\begingroup$ Exactly. Additionally to this: "The CART is still built on unweighted data and uses (Gini or entropy) to determine splits", data are bootstrapped for trees construction. $\endgroup$ – Samos Feb 10 at 21:00
  • 2
    $\begingroup$ Are you sure about this? I thought Adaboost changes the sample weights for each tree built? Original Adaboost doesn't require bagging at all... $\endgroup$ – Ben Reiniger Feb 10 at 22:29
  • $\begingroup$ But if the weights never affect the CART algo, if all you build are tree stumps and you have a dominant predictor, wouldn't each tree be the same and we never focus on areas that were fit poorly? In the regression case it makes more sense since we fit to residuals each time. $\endgroup$ – confused Feb 10 at 22:39
  • $\begingroup$ @BenReiniger That's what I thought too because otherwise I don't see how the algorithm attacks areas that were fit poorly - especially since most trees will have very few splits - often we just use stumps. I just don't know how the weights are incorporated since CARTs split on Gini index. $\endgroup$ – confused Feb 10 at 22:52

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.