AdaBoost and gradient boosting

Fix a finite training sample $(x_i,y_i{)}_{i=1}^N$ with $N\ge 1$, $x_i\in \mathcal{X}$, and $y_i\in \{-1,+1\}$, a finite round limit $M\ge 0$, and a weak-learning routine which at each requested round returns a classifier $h_m:\mathcal{X}\to \{-1,+1\}$ for the current observation weights. Initialize $w_i^{(1)}=1\mathrm{/}N$ and $F_0(x)=0$. At round $m$, compute the weighted error $e_m={\sum }_{i=1}^N{w}_i^{(m)}\mathbf{1}\{h_m(x_i)\mathrm{\ne }{y}_i\}$. If $e_m=0$, halt and return $h_m$ itself as a perfect classifier with zero training error; do not form an infinite coefficient. If $e_m\ge 1\mathrm{/}2$, halt and report that the weak-learning condition failed. For $0<e_m<1\mathrm{/}2$, set

$a_m=\frac{1}{2}\log \frac{1-e_m}{e_m},Z_m=2\sqrt{e_m(1-e_m)},$

update $w_i^{(m+1)}=w_i^{(m)}\exp (-a_m{y}_i{h}_m(x_i))\mathrm{/}{Z}_m$, and set $F_m(x)=F_{m-1}(x)+a_m{h}_m(x)$. After $M$ completed weak rounds, return the classifier ${\widehat{y}}_M(x)={\mathrm{sign}}_{+}(F_M(x))$, where ${\mathrm{sign}}_{+}(u)=+1$ for $u\ge 0$ and $-1$ for $u<0$. Thus ties are assigned to $+1$. The coefficient convention is the half-log convention; multiplying every coefficient by the same positive factor does not change the sign classifier. The definition makes no claim about test error or generalization.

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §10.1, Algorithm 10.1, printed pp. 337–338

Robert E. Schapire, “The Boosting Approach to Machine Learning: An Overview,” §2, PDF pp. 2–4

Let $N\ge 1$, let $(x_i,y_i{)}_{i=1}^N$ be a finite sample with $x_i\in \mathcal{X}$ and $y_i\in \mathcal{Y}$, let $f:\mathcal{X}\to \mathbb{R}$ be a score function, and let $\mathrm{\ell }:\mathcal{Y}\times \mathbb{R}\to \mathbb{R}$ be finite-valued. Assume that for each $i$, the one-variable function $t\mapsto \mathrm{\ell }(y_i,t)$ is differentiable at $z_i=f(x_i)$. For a score vector $z=(z_1,\dots ,z_N)$, define the empirical score loss $\mathrm{\Phi }(z)={\sum }_{i=1}^N\mathrm{\ell }(y_i,z_i)$. The pseudo-residual at observation $i$ for $f$ is

$r_i(f)=-{\frac{d}{dt}\mathrm{\ell }(y_i,t)\mid }_{t=f(x_i)}\mathrm{.}$

The sample-score gradient, when its coordinate partial derivatives exist, is the vector $\mathrm{\nabla }\mathrm{\Phi }(z)=({\mathrm{\partial }}_{z_1}\mathrm{\Phi }(z),\dots ,{\mathrm{\partial }}_{z_N}\mathrm{\Phi }(z))$. The sample pseudo-residual vector is $(r_1(f),\dots ,r_N(f))$; the word “pseudo” distinguishes these score derivatives from derivatives with respect to parameters of a restricted model.

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §10.10.3, printed p. 361

Alexey Natekin and Alois Knoll, “Gradient boosting machines, a tutorial,” §2.4

Let $N\ge 1$, let $(x_i,y_i{)}_{i=1}^N$ be a finite sample, let $f:\mathcal{X}\to \mathbb{R}$, and let $U\subseteq \mathbb{R}$ be open with $z_i=f(x_i)\in U$ for every $i$. Suppose each scalar loss $t\mapsto \mathrm{\ell }(y_i,t)$ is defined on $U$ and differentiable at $z_i$. Write ${\mathrm{\partial }}_2\mathrm{\ell }(y_i,z_i)={\frac{d}{dt}\mathrm{\ell }(y_i,t)\mid }_{t=z_i}$ and define $\mathrm{\Phi }:U^N\to \mathbb{R}$ by $\mathrm{\Phi }(w)={\sum }_{i=1}^N\mathrm{\ell }(y_i,w_i)$. Then $\mathrm{\Phi }$ is totally differentiable at $z$, its derivative in a score increment $v=(v_1,\dots ,v_N)$ is

$D\mathrm{\Phi }(z)v={\sum }_{i=1}^N{\mathrm{\partial }}_2\mathrm{\ell }(y_i,z_i)v_i,$

and its Euclidean gradient is $\mathrm{\nabla }\mathrm{\Phi }(z)=({\mathrm{\partial }}_2\mathrm{\ell }(y_i,z_i){)}_{i=1}^N$. For these possibly local losses, define the pseudo-residual by $r_i(f)=-{\mathrm{\partial }}_2\mathrm{\ell }(y_i,z_i)$; this agrees with the usual definition when the loss is finite-valued on all of $\mathcal{Y}\times \mathbb{R}$. Then the pseudo-residual vector associated with $f$ on this sample is exactly $-\mathrm{\nabla }\mathrm{\Phi }(z)$ in sample-score space.

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §§10.10.1–10.10.3, equations (10.35)–(10.37), printed pp. 358–361

Alexey Natekin and Alois Knoll, “Gradient boosting machines, a tutorial,” §§2.3–2.4

Let $M\ge 0$ be a finite sequence of completed rounds of finite-sample AdaBoost.M1, with weighted errors $0<e_m<1\mathrm{/}2$, scores $F_M(x)={\sum }_{m=1}^M{a}_m{h}_m(x)$, and $Z_m=2\sqrt{e_m(1-e_m)}$. Then

${\sum }_{i=1}^N{e}^{-y_i{F}_M(x_i)}=N{\prod }_{m=1}^M{Z}_m$

and

$\frac{1}{N}{\sum }_{i=1}^N\mathbf{1}\{y_i{F}_M(x_i)\le 0\}\le {\prod }_{m=1}^M{Z}_m\mathrm{.}$

The empty product for $M=0$ is $1$. Under the algorithm's $+1$ tie rule, the empirical classification error is also at most this product. This is a finite training-margin bound only and makes no test-generalization claim.

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §10.4, equations (10.8)–(10.15), printed pp. 343–344

Robert E. Schapire, “The Boosting Approach to Machine Learning: An Overview,” §3, equations (2)–(6), PDF pp. 4–5

Fix a finite regression sample $(x_i,y_i{)}_{i=1}^N$ with $N\ge 1$, $x_i\in {\mathbb{R}}^p$ for a finite $p\ge 1$, and $y_i\in \mathcal{Y}$. Let $\mathrm{\ell }:\mathcal{Y}\times \mathbb{R}\to \mathbb{R}$ be a finite-valued per-observation loss, differentiable in its second argument at every score used. Choose a finite round count $M\ge 0$ and finite integer tree-depth cap $d_{\max }\ge 0$. The algorithm is admissible only when the following required minima are attained: an initial constant minimizer and, at every round, a line minimizer in each terminal leaf. For any admitted run, choose any one such minimizer at each finite stage.

Initialize $f_0(x)=c_0$ with $c_0\in \arg {\min }_{c\in \mathbb{R}}{\sum }_{i=1}^N\mathrm{\ell }(y_i,c)\mathrm{.}$ For each round $m=1,\dots ,M$, perform the following steps.

1. For each observation compute the negative score derivative $r_{im}=-{\mathrm{\partial }}_2\mathrm{\ell }(y_i,f_{m-1}(x_i))\mathrm{.}$

2. Run finite-depth CART regression-tree growth, using squared error and depth cap $d_{\max }$, on the responses $r_{im}$ at features $x_i$. Let its nonempty terminal feature regions be $R_{1m},\dots ,R_{J_{m}m}$; their training-index sets partition $\{1,\dots ,N\}$. This tree fit approximates the unrestricted negative score gradient. Its fitted leaf means are used to determine the regression-tree fit and regions, but are not the boosting update offsets.

3. For each leaf region choose an attained exact line minimizer ${\gamma }_{jm}\in \arg {\min }_{\gamma \in \mathbb{R}}{\sum }_{i:x_i\in R_{jm}}\mathrm{\ell }(y_i,f_{m-1}(x_i)+\gamma )\mathrm{.}$ In particular, zero is an admissible comparison offset.

4. Update $f_m(x)=f_{m-1}(x)+{\sum }_{j=1}^{J_m}{\gamma }_{jm}\mathbf{1}\{x\in R_{jm}\}\mathrm{.}$

The output is $f_M$. Because the run has finitely many rounds and finitely many leaves, choosing one attained minimizer at each stage requires no axiom of choice. The defined variant uses the full training sample and exact leafwise line minimization; shrinkage and subsampling are separate variants. This definition asserts no convergence or generalization result.

Finite-sample pseudo-residual and score-loss conventions

The pseudo-residual vector is the negative score-space gradient

Finite regression-tree regions and nonempty leaf sample sets

The finite-depth CART regression-tree fit

Finite output and nonempty leaves

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §§10.9–10.10.3, printed pp. 353–361

Alexey Natekin and Alois Knoll, “Gradient boosting machines, a tutorial,” §§2.3–2.4

For any finite run of the defined gradient tree boosting algorithm for which the initial constant and every leaf line minimizer are attained, let $L_m={\sum }_{i=1}^N\mathrm{\ell }(y_i,f_m(x_i))$. At every completed round $m$, $L_m\le L_{m-1}$, and hence $L_M\le L_0$. This is a finite-step empirical-loss statement only; it asserts no convergence or generalization result.

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §10.10.3, Algorithm 10.3, printed p. 361