Gradient Boosting

Definition

Build $f_t=f_{t-1}+w_t{h}_{{\theta }_t}$ step by step. Compute $r_i=\partial \ell (y_i,f_{t-1}(x_i))/\partial f_{t-1}(x_i)$, fit $h_{\theta }$ to $-r_i$ by least squares, choose $w_t$ by a line search.

Formula

$$\begin{array}{rl}& {\theta }_t=\underset{\theta }{\mathrm{argmin}}\sum _i(-r_i-h_{\theta }(x_i){)}^2\\ & w_t=\underset{w}{\mathrm{argmin}}\sum _i\ell (y_i,f_{t-1}(x_i)+w{h}_{{\theta }_t}(x_i))\end{array}$$

• Squared loss: $-r_i$ is the residual $y_i-f_{t-1}(x_i)$.
• Exponential loss: the stagewise problem is solved exactly by AdaBoost.
• XGBoost = gradient boosting with decision trees; boosted trees reduce bias sequentially, random forests reduce variance in parallel.

Appears in

• Lecture 6, stagewise additive modeling
• Lecture 6, the algorithm and residual fitting
• Lecture 6, XGBoost and forests

Related concepts

• AdaBoost
• Random Forest
• Stochastic Gradient Descent