2
$\begingroup$

Wikipedia's geral Gradient Boosting is: enter image description here

Friedman's Gradient Boosting is:

enter image description here

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.

Are wikipedia's gradient boosting and Friedman's Gradient Boosting the same?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – angryavian
    Commented Apr 12, 2021 at 1:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – usεr11852
    Commented Apr 12, 2021 at 3:48
  • $\begingroup$ @angryavian changing βh to h should we change p_m.h to h? another question is what happens with β after line 4? $\endgroup$ Commented Apr 12, 2021 at 20:13
  • $\begingroup$ @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. $\endgroup$ Commented Apr 12, 2021 at 20:17

1 Answer 1

4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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}$? $\endgroup$ Commented Apr 12, 2021 at 23:56
  • $\begingroup$ @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." $\endgroup$
    – angryavian
    Commented Apr 13, 2021 at 15:55
  • $\begingroup$ 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 $\endgroup$ Commented Apr 13, 2021 at 20:01
  • $\begingroup$ @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. $\endgroup$
    – angryavian
    Commented Apr 13, 2021 at 21:47
  • $\begingroup$ 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. $\endgroup$ Commented Apr 22, 2021 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.