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

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..?

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.

• You mention gini index and cross-entropy, and those are typically used for classification trees from my understanding. What about regression trees? I believe we use MSE typically, but in adaboost, is it weighted MSE that we use? Sep 21, 2020 at 12:56
• entropy is not cross-entropy. also, adaboost is not suitable for regression, just for classification. Sep 21, 2020 at 13:27
• Why is not suitable for regression? Sep 21, 2020 at 14:00
• it is what it is, and it's made for classification. if you want to make regression you need to resort to other methods. Gradient boosting, for instance, can be used for both regression and classification, and it's even claimed to have made adaboost obsolete. Xgboost/LGBM are one step further still. Sep 21, 2020 at 14:50

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.

• In your objection function, it seems a classification loss function. What it was a regression tree? What would the loss function look like? weighted MSE? Sep 21, 2020 at 12:53
• In terms of regression for a single-split tree, the loss function would be the sum of squared errors at each region, i.e, the region $R_1 = \{x_n \vert x_n \leq s\}$ and $R_2 = \{x_n \vert x_n > s\}$ Sep 21, 2020 at 13:05
• you point accuracy to be the utility function, that's inexact. ID3-4, C5.0 and CART all use either gini index or entropy. This affects the choices the trees make for the variable to split, while the split point actually is the same for all these loss functions. Sep 21, 2020 at 13:39
• actually, where gini and entropy agree, accuracy can show multiple optima, I can show you an example for this, if you are interested Sep 21, 2020 at 13:54