Adaboost -- how does reweighting affect the learning process for the subsequent learner?

Question

In Adaboost, when you reweight the samples, how does the training process for the next classifier in the boosting algorithm take in to account the weights? Is it reflected in the loss function of the learner? The ESL book doesn't really talk about this.

In addition, if say we are using trees as the weak learners, how is each subsequent tree determined? In other words and on top of the reweighted training samples, how do we choose what variables to study at each node for the next tree, how many terminal nodes, etc..?

Answer 1

Tree learning algorithms in general support weighted samples. Weights are included in the computation of the loss function (which may be Gini impurity index or entropy) so that each point contribution to the loss is weighted, and consequently each point contribution to the model training can be considered to have that weight.

The other parts of the algorithm are the same as usual: nodes of the trees are created in a greedy fashion using the variable and the threshold that maximize the reduction in the loss function (this reduction is called information gain). Further constrains on the number and dimension of leaf nodes, depth of the tree, or pruning steps may be adopted independently of the weights. It is usual to fix a low tree maximum depth, to the limit that simple decision stumps may be used (depth = 1) to force the weak learners to be simple and weak indeed.

A famous example that helped me a lot to understand Adaboost uses decision stumps as weak learners, and, while they are very rough, the ensemble can come out to be quite neat. You can appreciate that example in this very brief video, or, treated with much better rigour, in this longer one. You can see that data points with higher weight have a greater influence on the trees (well, stumps really): as they are counted more in the loss function, the model focuses more on them.

Answer 2

To answer your first question, suppose that we are at the $m$-th iteration of AdaBoost, so that we already have a set of weights $\{w^{(m)}_n\}_{n=1}^N$ for each of the datapoints. If our base learners are single-split trees, AdaBoost will learn the next base classifier such that minimizes:

$$ J_m = \sum_{n=1}^N w^{(m)} \mathbb{1}(t_n \neq G_m({\bf x}_n, d, s)) $$

Here $G$ is our single-split tree which we define as

$$ G_m({\bf x}_n, d, s) = \begin{cases} 1 & x_{nd} \leq s \\ -1 & x_{nd} > s \end{cases} $$

Where $s$ is the cutoff point and $d$ is the target dimension (or feature). Note that the cost function $J_m$ weights each of the observations.

Regarding to your second question, again, considering $J_m$, we would choose the feature $d$ and cutoff point $s$ that minimizes the cost function. $d$ can either be chosen randomly or try different values of $d$ and see which one results in the lowest score. To choose $s$, however, one must try a set of cutoff points. e.g., [0.1, 0.2, ..., 1, 1.2] and see which one results in the lowest score for a given $d$.

If you would like to see an implementation of this idea in python, you can check out this notebook.