# Show that boosted decision stumps lead to an additive model? (ISLR question, proof attempted)

I am working through the Introduction to Statistical Learning questions in my spare time and gradually putting together a solutions set for my own learning.

I've given this a solid attempt and but unfortunately I don't have anyone I can ask to check my work so I was hoping some of the knowledgeable people on here could say if my approach is correct (I have deliberately over-explained to hopefully expose any mistakes in my thinking).

Anyway, thanks in advance as I hope somebody can help! Here is Question 2, Ch. 8, page 332, which asks the following:

Question: It is mentioned in Section 8.2.3 that boosting using depth-one trees (or stumps) leads to an additive model: that is, a model of the form

$$f(X) = \sum_{j = 1}^p f_j(X_j)$$

Explain why this is the case. You can begin with (8.12) in Algorithm 8.2 (see top of page 323)

Algorithm 8.2 and the remaining text on Boosting is focused around boosting regression trees, so I presume this question is also focused on this.

Firstly, recall that a decision tree with $$M$$ terminal nodes ($$M-1$$ splits) can be expressed as:

$$f(X) = \sum_{m = 1}^M c_m \cdot 1_{(X \in R_m)}$$

where, in the regression tree context, $$c_m$$ is the mean response value for the observations in region $$m$$.

A stump is a tree with just $$M = 2$$ terminal nodes (one split), so if we have a decision stump in which a single split occurs on the variable $$X_j$$ (at value $$s$$), we can simplify this representation:

\begin{align} f(X) & = c_1 \cdot 1_{(X \in R_1)} + c_2 \cdot 1_{(X \in R_2)} \\ & = \begin{cases} c_1 && \text{if } X_j < s\\ c_2 & & \text{if } X_j \ge s \end{cases} \\ & = c_1 \cdot I(X_j < s) + c_2 \cdot I(X_j \ge s) \end{align}

With boosted stumps we are not dealing with a single regression stump but $$B$$ stumps, so I will use the following notation:

• Consider $$b = 1, 2, \dots, B$$ stumps in the boosting model, each consisting of a single split
• The splits occur on variables $$X_{j_1}, X_{j_2}, \dots, X_{j_B} \in \{ X_1, X_2, \dots, X_p\}$$
• The splits on these variables occur at the corresponding values $$s_1, s_2, \dots, s_B \in \mathbb{R}$$
• $$\alpha_b, \beta_b \in \mathbb{R}$$ are just constants (the mean response variable in the regions created by stump $$b$$)

For $$b = 1, 2, \dots, B$$, the stumps will therefore take the form:

$$\hat{f}^b(X) = \alpha_b \cdot I(X_{j_b} < s_b) + \beta_b \cdot I(X_{j_b} \ge s_b)$$

Proceeding through Algorithm 8.2, we first set $$\hat{f}(X) = 0$$ and $$r_i = y_i$$ ($$\forall i \in \{1, 2, \dots, n\}$$).

$$b = 1$$:

$$\hat{f}^1(X) = \alpha_1 \cdot I(X_{j_1} < s_1) + \beta_1 \cdot I(X_{j_1} \ge s_1)$$

\begin{align} \hat{f}(X) & \leftarrow \hat{f}(X) + \lambda \hat{f}^1(X) \\ & = \lambda \hat{f}^1(X) \\ \end{align}

\begin{align} r_i & \leftarrow r_i - \lambda \hat{f}^1(X) \\ & = y_i - \lambda \hat{f}^1(X) \\ \end{align}

$$b = 2$$:

$$\hat{f}^2(X) = \alpha_2 \cdot I(X_{j_2} < s_2) + \beta_2 \cdot I(X_{j_2} \ge s_2)$$

\begin{align} \hat{f}(X) & \leftarrow \hat{f}(X) + \lambda \hat{f}^2(X) \\ & = \lambda \hat{f}^1(X) + \lambda \hat{f}^2(X)\\ \end{align}

\begin{align} r_i & \leftarrow r_i - \lambda \hat{f}^2(X) \\ & = y_i - \lambda \hat{f}^1(X) - \lambda \hat{f}^2(X)\\ \end{align}

$$\vdots$$

$$b = B$$:

$$\hat{f}^B(X) = \alpha_B \cdot I(X_{j_B} < s_B) + \beta_B \cdot I(X_{j_B} \ge s_B)$$

\begin{align} \hat{f}(X) & \leftarrow \hat{f}(X) + \lambda \hat{f}^B(X) \\ & = \lambda \hat{f}^1(X) + \lambda \hat{f}^2(X) + \dots + \lambda \hat{f}^B(X) \\ & = \sum_{b = 1}^B \lambda\hat{f}^b(X) \end{align}

\begin{align} r_i & \leftarrow r_i - \lambda \hat{f}^B(X) \\ & = y_i - \lambda \hat{f}^1(X) - \lambda \hat{f}^2(X) - \dots - \lambda \hat{f}^B(X) \\ & = y_i - \sum_{b = 1}^B \lambda\hat{f}^b(X) \end{align}

From the final stump, we have our final updated boosting model $$\hat{f}$$, given by:

\begin{align} \hat{f}(X) & = \sum_{b = 1}^B \lambda\hat{f}^b(X) \\ & = \lambda \sum_{b = 1}^B \alpha_b \cdot I(X_{j_b} < s_b) + \beta_b \cdot I(X_{j_b} \ge s_b) \\ \end{align}

Since $$X_{j_1}, X_{j_2}, \dots, X_{j_B} \in \{ X_1, X_2, \dots, X_p\}$$, we can see that this estimate $$\hat{f}$$ is indeed an additive model of the form $$f(X) = \sum_{j = 1}^p f_j(X_j)$$.

Further Justification:

To show this in more concrete terms, imagine that $$B = 50$$ and $$p = 10$$, so $$X = (X_1, X_2, \dots, X_{10})$$. Suppose that the boosting algorithm split on $$X_5$$ when $$b \in \{ 1, 22, 47\}$$.

In terms of the previous notation, this means that $$X_{j_1} = X_{j_{22}} = X_{j_{47}} = X_5$$.

Hence, in $$f(X) = \sum_{j = 1}^{10} f_j(X_j)$$, we would have:

\begin{align} f_5(X_5) & = \hat{f}^1(X) + \hat{f}^{22}(X) + \hat{f}^{47}(X) \\ & = \lambda \Big[ \alpha_1 \cdot I(X_{j_1} < s_1) + \beta_1 \cdot I(X_{j_1} \ge s_1) \\ & \; \; \; + \alpha_{22} \cdot I(X_{j_{22}} < s_{22}) + \beta_{22} \cdot I(X_{j_{22}} \ge s_{22}) \\ & \; \; \; + \alpha_{47} \cdot I(X_{j_{47}} < s_{47}) + \beta_{47} \cdot I(X_{j_{47}} \ge s_{47}) \Big] \\ & = \lambda \Big[ \alpha_1 \cdot I(X_{5} < s_1) + \beta_1 \cdot I(X_{5} \ge s_1) \\ & \; \; \; + \alpha_{22} \cdot I(X_{5} < s_{22}) + \beta_{22} \cdot I(X_{5} \ge s_{22}) \\ & \; \; \; + \alpha_{47} \cdot I(X_{5} < s_{47}) + \beta_{47} \cdot I(X_{5} \ge s_{47}) \Big] \\ \end{align}

We could do exactly the same $$\forall j \in \{ 1, 2, \dots, 10\}$$, separating out the stumps based on which variable from $$X_1, X_2, \dots, X_{10}$$ they split on, combining them and expressing them as $$f_1(X_1), f_2(X_2), \dots, f_{10}(X_{10})$$.

I believe that if this question were extended past boosted stumps, this property would no longer hold. We would still be able to express the predictions of the boosted model as an a sum of the predictions of many trees trees (this is a clear from the final step of the algorithm, where the final $$\hat{f}$$ takes the form $$\hat{f}(X) = \sum_{b = 1}^B \lambda\hat{f}^b(X)$$). However, the problem arises in expressing these trees as separate functions of the predictors $$X_1, X_2, \dots, X_p$$.

For stumps this was simple; each stump could be represented by $$\hat{f}^b(X) = \alpha_b \cdot I(X_{j_b} < s_b) + \beta_b \cdot I(X_{j_b} \ge s_b)$$, which is clearly a function of one variable ($$X_{j_b}$$).

A stump that split on $$X_3$$ at value $$5.2$$ could be represented by:

$$c_1 \cdot I(X_{3} < 5.2) + c_2 \cdot I(X_{3} \ge 5.2)$$

Consider if that stump was instead a tree, which had a further split (when $$X_{3} \ge 5.2$$) on $$X_{8}$$ at the value $$16.3$$, it would then be represented by:

$$c_1 \cdot I(X_{3} < 5.2) + c_2 \cdot I(X_{3} \ge 5.2) \cdot I(X_{8} < 16.3) + c_3 \cdot I(X_{3} \ge 5.2) \cdot I(X_{8} \ge 16.3)$$

How could we separate this tree into separate functions of variables $$X_3$$ and $$X_8$$? We couldn't, so the additive form $$f(X) = \sum_{j = 1}^{p} f_j(X_j)$$ would not be possible here.

Note that throughout the question I have focused on binary splits of numeric variables, but if $$X$$ contains some (or all) categorical features this is not an issue.

For example, a stump with one split on the categorical variable $$X_j$$ (at values $$v_1, v_2, v_3$$) could be written as:

\begin{align} f(X) & = c_1 \cdot 1_{(X \in R_1)} + c_2 \cdot 1_{(X \in R_2)} \\ & = \begin{cases} c_1 && \text{if } X_j \in \{v_1, v_2, v_3\}\\ c_2 & & \text{if } X_j \notin \{v_1, v_2, v_3\} \end{cases} \\ & = c_1 \cdot I \left( X_j \in \{v_1, v_2, v_3\} \right) + c_2 \cdot I \left( X_j \notin \{v_1, v_2, v_3\} \right) \end{align}

This notation could continue throughout the proof and nothing would change (the final prediction $$\hat{f}$$ would still be a sum of the individual stumps $$\hat{f}^b$$, and these individual stumps and therefore the prediction $$\hat{f}$$ would still be separable and able to be expressed as an additive model of the form $$f(X) = \sum_{j = 1}^{p} f_j(X_j)$$).