# Does Wikipedia explain gradient boosting in wrong way?

Why wikipedia's gradient boosting fit h_m through pseudo-residuals while friedman uses line 4 to fit h? My question is not about he uses least squares to fit h_m but he does that fitting B.h(x,a) to pseudo-residuals instead h(x,a) to pseudo-residuals.

• One observation: in the Wikipedia version, if the class of weak learners $\mathcal{H}$ is closed under scaling (i.e. if $h \in \mathcal{H}$ then $\beta h \in \mathcal{H}$ for any scalar $\beta$, which is true for common classes like trees), then the two formulations are equivalent. Not sure if this is the intended resolution to your question; I am also curious about this difference between the two formulations. Commented Apr 12, 2021 at 1:43
• Agreed with @angryavian; (+1) many other authoritative sources from 00's on boosting (e.g. Hastie et al. ESEL (2008), Buhlmann & Hothorn (2007)) as well as newer references (e.g. Murphy's MLPP (2012), Schapire & Freud F&A B (2012), Efron & Hastie's CASI (2016)) don't use $\beta$ as they assume the learner is flexible enough. I think it was just a case of somewhat over-jealous notation that was dropped soon afterwards. Commented Apr 12, 2021 at 3:48
• @angryavian changing βh to h should we change p_m.h to h? another question is what happens with β after line 4? Commented Apr 12, 2021 at 20:13
• @usεr11852 Friedman has started to use h instead βh in decision trees sections but he hasnt commented the why of that. I'm looking for references to use wikipedia's gradient boosting in general way not limited to decision trees. Commented Apr 12, 2021 at 20:17

Responding to your comments, and bringing it back to my original comment:

Line 4 of Friedman's algorithm can be viewed as "finding the best function $$g \in \mathcal{G}$$ that fits the pseudo-residuals via minimizing $$\sum_i [\tilde{y}_i - g(x_i)]^2$$," with $$\mathcal{G}$$ containing all functions of the form $$g(\cdot) := \beta h(\cdot; a)$$.

Once you find the optimal $$g(\cdot) = \beta_m h(\cdot; a_m)$$ (via the optimal $$a_m$$ and $$\beta_m$$ from Line 4), you can do line 5-6 either by throwing away $$\beta_m$$:

(5) $$\rho_m = \arg \min_\rho \sum_{i=1}^N L(y_i, F_{m-1}(x_i) + \rho h(x_i,; a_m))$$

(6)$$F_m(x) = F_{m-1}(x) + \rho_m h(x; a_m)$$

or by keeping $$\beta_m$$:

(5') $$\rho'_m = \arg \min_{\rho'} \sum_{i=1}^N L(y_i, F_{m-1}(x_i) + \rho' \underbrace{\beta_m h(x_i; a_m)}_{g(x_i)})$$

(6')$$F_m(x) = F_{m-1}(x) + \rho'_m \underbrace{\beta_m h(x; a_m)}_{g(x)}$$

These two approaches are actually equivalent since the optimizers of (5) and (5') are related by $$\rho_m = \rho'_m \beta_m$$. The second approach is written in a form more similar to what Wikipedia is doing, since you can write steps 4-6 using only $$g$$ and $$\mathcal{G}$$.

So basically, the formulation in Friedman's "Algorithm 1" is the same as Wikipedia's, except the class of weak learners is not $$\mathcal{H} = \{h(\cdot; a) \mid a \in \mathcal{A}\}$$, but rather $$\mathcal{G} = \{\beta h(\cdot; a) \mid \beta \in \mathbb{R}, a \in \mathcal{A}\}$$.

In the special case where $$\mathcal{H}$$ is closed under scaling (i.e. $$h \in \mathcal{H}$$ implies $$\beta h \in \mathcal{H}$$ for any scalar $$\beta$$; this is true for classes like trees), then $$\mathcal{H} = \mathcal{G}$$ and there is no discrepancy between Wikipedia and "Algorithm 1."

• i got it what you meant but im still in doubt about line 4 notation, Does Friedman take $\mathbf{a}$ and $\beta$ to into $\mathbf{a}_m$ ? can't this adulterate the dimension of $\mathbf{a}$? Commented Apr 12, 2021 at 23:56
• @DaviAmérico Line 4 is an optimization simultaneously w.r.t both $a$ and $\beta$. Friedman throws away $\beta$ and keeps the optimal $a$ (denoted $a_m$). I'm not sure what you mean by "adulterate the dimension." Commented Apr 13, 2021 at 15:55
• i meant: $(\mathbf{a}_m)_{m x 1}=(\mathbf{a}_{optimum},\beta_{optimum})_{(m+1) x 1}$ but he really does: $(\mathbf{a}_m,\beta_m)_{m x 1}=(\mathbf{a}_{optimum},\beta_{optimum})_{(m+1) x 1}$ and $\rho_{m}=arg min_{\rho} \sum_{i=1}^N L(y_i,F_{m-1}(x_i)+\rho h(x_i,\mathbf{a}))$ where $\rho=\rho^{'} \beta_m$ i'm still wondering if his notation at line 4 is right Commented Apr 13, 2021 at 20:01
• @DaviAmérico $(a_m, \beta_m) = (a_{opt}, \beta_{opt})$ is correct. The point of my answer above is to show that getting $a_m$ right is the main point of line 4, because if $a_m$ is correct, then you can replace $\arg\min_{\rho} \sum_i L(y_i, F_{m-1}(x_i) + \rho h(x_i, a))$ with $\arg\min_{\rho} \sum_i L(y_i, F_{m-1}(x_i) + \rho (c h(x_i, a)))$ for any scalar $c$; either way $\rho_m$ will be the same. Commented Apr 13, 2021 at 21:47
• see (Haihao Lu, Sai Praneeth Karimireddy, Natalia Ponomareva,Vahab Mirrokni) they do what you do and see (Buhlmann and Hothorn 2007) page .7 is commented about ignoring the line search at line 5 and the why to do that in page 36. Commented Apr 22, 2021 at 2:14