这一章从AdaBoost开始，讲到boosting-trees，这些方法归结起来，其实都属于additive model，即\(f(x) = \sum_{i=1}^p f_i(x)\)。如果选定了基函数\(b(x;\gamma_m)\)，并且把\(f_i(x)\)的形式限定为系数\(\beta_m\)和基函数的乘积，那么写成递归的形式就是

\[\begin{equation} \label{eq:fsam} f_m(x) = f_{m-1}(x) + \beta_m b(x; \gamma_m) \end{equation}\]

这就是书上Algo-10.2的Forward Stagewise Additive Modeling，其中\((\beta_m, \gamma_m)\)是待优化参数，第\(m\)轮的优化目标是

\[\sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma))\]

这其中，损失函数\(L\)的不同，以及优化方式的不同，产生了不同的算法。Adaboost是取\(L(y,f(x)) = \exp(-yf(x))\)的结果；而GBM则更进一步，从优化方法下手（去fit损失函数\(L\)的梯度），不再依赖exponential loss的特殊结构，从而可以apply各类损失函数，既能用于分类，也能用于回归。

AdaBoost

首先来看看AdaBoost是如何通过exponential loss导出的。AdaBoost.M1是一个二分类模型，标签\(y \in \{-1,+1\}\)，损失函数\(L(y,f(x)) = \exp(-yf(x))\)，根据Alog-10.2，我们要求解这样一个问题：

\[\begin{equation*} \begin{split} (\beta_m, G_m) &= \arg\min_{\beta, G}\sum_{i=1}^N \exp[-y_i(f_{m-1}(x_i) + \beta G(x_i))] \\ &= \arg\min_{\beta, G}\sum_{i=1}^N w_i^{(m)} \exp(-\beta y_i G(x_i)) \\ &= \arg\min_{\beta, G} \left[ e^{-\beta} \cdot \sum_{y_i = G(x_i)} w_i^{(m)} + e^{\beta} \cdot \sum_{y_i \neq G(x_i)} w_i^{(m)} \right] \\ &= \arg\min_{\beta, G} \left[ e^{\beta}\cdot\sum_{i=1}^N w_i^{(m)}I(y_i\neq G(x)) +e^{-\beta}\cdot\sum_{i=1}^N w_i^{(m)}(1-I(y_i\neq G(x))) \right] \\ &= \arg\min_{\beta, G} \left[ (e^{\beta} - e^{-\beta}) \cdot \sum_{i=1}^N w_i^{(m)} I(y_i \neq G(x_i)) + e^{-\beta} \cdot \sum_{i=1}^N w_i^{(m)} \right] \end{split} \end{equation*}\]

其中\(G_m(x) \in \{-1, +1\}\)是一个二分类器，\(w_i^{(m)} = \exp(-y_i f_{m-1}(x_i))\)，\(I(\cdot)\in \{0,1\}\)是indicator函数。注意到第二步用到了exponential的特殊结构，很容易地把前一个基函数\(f_{m-1}\)和当前求解参数分离了，而这对于squared loss之类的损失函数就不适用了。

由于参数\(\beta\)和\(G(x)\)是分离的，可以分别求解。显然

\[G_m = \arg\min_{G} \sum_{i=1}^N w_i^{(m)} I(y_i \neq G(x_i))\]

就是让分类器\(G\)的分类误差最小，只不过这个误差是加了权的，给予上一次错分类的sample更高的权重；求得\(G_m\)后，再对\(\beta\)求导，就能解出\(\beta_m\)了；最后应用(\(\ref{eq:fsam}\))式，就得到了算法的迭代更新规则。

Boosting Trees

回到(\(\ref{eq:fsam}\))式，有没有觉得它像极了steepest descent：令\(b(x; \gamma_m)\)为第\(m\)轮的梯度，\(\beta_m\)便是line-search的结果。借助梯度，我们就不必依赖损失函数的特殊结构，任何存在一阶导数的损失函数都能在这个框架中使用。书上Table-10.2给出了一些损失函数的一阶偏导\(\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\)

以\(L(y_i, f(x_i)) = \frac{1}{2}[y_i-f(x_i)]^2\)为例，它对\(f(x_i)\)的一阶导数为\(y_i - f(x_i)\)。第一步我们初始化\(f_0(x) = ave(y_1, y_2, \dots , y_N) = \bar{y}\)（即\(f_0(x) = \arg\min_\gamma\sum_{i=1}^N L(y_i, \gamma)\)），然后每轮迭代都选取上一轮的\(f_{m-1}\)计算残差，我们会得到：

\[\begin{align*} f_0(x) &= \bar{y} \\ f_1(x) &= f_0(x) - \gamma_1 \sum_{i=1}^N(y_i - f_0(x_i)) \\ &= \bar{y} - \gamma_1 \sum_{i=1}^N(y_i - \bar{y}) \\ f_2(x) &= f_1(x) - \gamma_2 \sum_{i=1}^N(y_i - f_1(x_i)) \\ &= \dots\dots \end{align*}\]

上面的过程有一个明显的问题，就是整个过程都定义在训练集的\((y_i, x_i)\)上，从而无法对新数据做出预测。解决方法是在每一轮引入一棵树，用这棵树去fit由上一轮产生的负梯度\(-\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f=f_{m-1}}\)，这样就得到了书上的Algo-10.3.

这样一个框架，使用不同的损失函数\(L\)，可以变换出多种模型，强烈推荐 Friedman J H. Greedy function approximation: a gradient boosting machine[J]. Annals of Statistics, 2001。事实上，Google Sibyl所描述的用并行boosting解LR就是以negative binomial loglikelihood为loss的GBM，用0/1离散化模拟了树桩。

Regularization

最后描述了GBM两种正则化的方法：shrinkage和subsampling。前者通过在步长上施加一个小的factor得到L1正则的效果。这个原理请参阅Efron的LARS，LARS建立了forward stagewise selection和lasso的联系，而GBM作为forward stagewise的特例，也享有同样的特性；subsampling通过每轮迭代以bootstrap重抽样一部分训练数据，达到正则化的效果。