机器学习笔记-Gradient Boosted Decision Tree_综合

集成学习系列：

Blending and Bagging
Adaptive Boosting
Decision Tree
Random Forest
Gradient Boosted Decision Tree

Gradient Boosted Decision Tree（梯度提升决策树）

上一篇介绍了 $Random\ Forest$ ，该算法利用 $\text{Bagging}$ 中的 $\text{bootstrap}$ 机制得到不同的 $\text{Decision Tree}$ ，然后将这些 $\text{Decision Tree}$ 融合起来。除了基本的 $\text{Bagging}$ 和 $\text{Decision Tree}$ 之外， $\text{Random Forest}$ 还在 $\text{decision tree}$ 中加入了更多的随机性。有了这些机制之后，我们发现这个算法可以利用 $\text{OOB}$ 数据做 $\text{self validation}$ ，进一步结合 $\text{self validation}$ 的机制和 $\text{permutation test}$ 的做法我们利用 $\text{random forest}$ 来做 $\text{feature selection}$ 。

提升方法 $(boosting)$ 的代表性算法是 $\text{AdaBoost}$ 。提升树是以分类或者回归树为基本学习器的提升方法。由于树的线性组合可以很好的拟合训练数据，即使数据中的输入和输出之间的关系很复杂也没关系，所以提升树是一个高功能的学习算法。本篇讨论针对不同问题的提升树学习算法。其主要的区别在于使用的损失函数不同，首先介绍使用指数损失的分类问题，此时的提升树算法只需要将 $\text{Adaboost}$ 算法的弱分类器设置为加了限制的二分类树即可，可以说提升树算法用于分类是 $\text{Adaboost}$ 的特殊情况。接下来介绍提升树算法损失函数为平方损失时候的回归问题，之后我们会发现对回归问题的提升树算法来说，只需要在每一轮使得弱学习器来简单的拟合当前模型的残差就好了。提升树利用加法模型和前向分步算法实现优化过程，当损失函数为平方损失或者是指数损失时分别为我们上述讨论的回归问题和分类问题。但是对于一般的损失函数而言，每一步的优化并不简单。这样便有了梯度提升算法。其关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值来进行回归树的拟合。

1 - 提升树模型

1.1 - 提升树用于分类-Adaboost的特殊情况

先再回顾下 $\text{random forest}$ 的算法的形式：外层是一个 $\text{bagging}$ ，可以使用 $\text{bootstrap}$ 的方式来得到不同的 $g_t$ ，内层是一个加了更多 $\text{randomness}$ 的 $\text{randomized-decision tree}$ 。
再回忆下 $\text{adaboost}$ 算法的步骤：在这个算法中，每一轮每一个样本被赋予一个权重 $u^{(t)}_n$ ，算法通过最小化被 $u^{(t)}_n$ 加权的 $E_{in}$ 来得到 $g_t$ ，再计算 $g_t$ 的权重 $\alpha_t$ 来融合得到最终的 $G$ 。

我们之前将 $\text{decision tree}$ 搭配 $\text{bagging}$ 得到了 $\text{random forest}$ ，同样地，我们可以将 $\text{decision tree}$ 搭配 $\text{adaboost}$ 得到 $\text{boosting tree}$ 提升树算法。但是现在我们需要面对的一个新的问题是，在算法 $\text{boosting tree}$ 中，决策树作为弱学习器是处理不了加权的数据的，而在 $\text{adaboost}$ 中每一轮的数据都是带有权重的数据，也就是 $\text{adaboost}$ 中的 $\text{base algorithm}$ 要能够解决如下的最小化问题：

m i n i m i z e E u i n = 1 N \sum n = 1 N u n ? e r r (y n, h (x n))

$minimize\ E_{in}^{u} = \frac1N\sum_{n=1}^{N}u_n \centerdot err(y_n, h(x_n))$

因为 $\text{decision tree}$ 有很多种实现，有很多技巧在里面。所以我们决定将 $\text{decision tree}$ 当做是一个黑盒子，我们不再要求这个黑盒子可以处理加权的数据，而是对加权的数据本身做处理，使之变为不加权的数据然后喂给 $\text{decision tree}$ 。

其实这一点是很容易做到，权重是从 $\text{bagging}$ 中的 $\text{bootstrap}$ 中得到的，在做 $\text{bootstrap}$ 的时候，得到了几份 $(x_n, y_n)$ ，那么 $(x_n, y_n)$ 的权重就是几： $(x_n, y_n)$ 的权重是3代表抽取到了3份 $(x_n, y_n)$ ，权重是4代表抽取到了4份 $(x_n, y_n)$ ，所以权重就代表了在资料中有几份 $(x_n, y_n)$ 的复制。所以我们就可以根据 $\text{bootstrap}$ 的计算机制得到的权重 $u_n^{(t)}$ 先对资料进行抽样，这样就得到了一笔新的大小为 $N'$ 资料 $\tilde{D}_t$ ，在这笔资料中就隐含了权重的信息。现在看来，在 $\text{bagging}$ 中我们是先 $\text{bootstrap}$ ，通过得到的样本数量获得权重；现在在 $\text{boosting tree}$ 中，我们利用了这个过程的逆过程，根据权重来得到样本的数量，这样做的目的是为了不改变底层的 $\text{decision tree}$ 算法。

所以在 $\text{boosting tree}$ 中，我们没有更改 $\text{decision tree}$ 的部分，没有更改 $\text{adaptive boosting}$ 的部分，而是在中间的环节按照样本的权重做了一个抽样的过程得到新的资料 $\tilde{D}_t$ 然后喂给 $\text{decision tree}$ 。

boosting tree boosting tree $\text{boosting tree}$ ：

AdaBoost+sampling∝u(t)+DecisionTree(D~t) A d a B o o s t + s a m p l i n g ∝ u ( t ) + D e c i s i o n T r e e ( D ~ t ) $AdaBoost + sampling \propto u^{(t)} + Decision Tree(\tilde{D}_t)$

1.2 - 提升树的一些改进

在 $adaboost$ 中，当得到了一个 $g_t$ 的时候，我们下一步需要作出的决定是这个 $g_t$ 该以多大的权重加入到 $G$ 中。这个权重我们记为 $\alpha_t$ ， $\alpha_t$ 的计算公式如下：

α t = l n ? t = l n 1 ? ? t ? t ? ? ? ? ? \sqrt

$\alpha_t = ln{\blacklozenge_t} = ln{\sqrt{\frac{1 - \epsilon_t}{\epsilon_t}}}$
其中

?t ? t $\epsilon_t$ 指的是

gt g t $g_t$ 的错误率。

这样可能会出现一个问题：
如果我们用于训练的资料完全是不同的，那么一棵完全长成的决策树的 $E_{in}$ 就是 $0$ ，那么 $E_{in}^{u} = 0$ ，那么 $\epsilon_t=0$ ，所以 $\alpha_t = \infty$ 。所以在这种情况下，最终只是得到了一棵“最好”的树，这就违背了我们的大主题： $aggregation$ 。
问题出在哪里呢？因为我们把所有的数据都喂给了算法，并且算法能得到的是一个完全长成的树。所以如果要解决这个问题的话，有两个方面可以着手：

不要把所有的数据都喂给算法；
对决策树构造算法做一些限制；

通过这样的技巧我们就可以得到一棵“弱”一点的树。其实我们通过 $\text{bootstrap}$ 抽样已经做到了不将所有的数据都喂给算法。另外通过采用简单的策略，例如限制决策树的高度也可以得到一棵比较“弱”的树。

所以在实际的应用中，提升树通常是如下的形式：原来的 $\text{adaboost}$ 算法的框架下，根据权重进行采样 $\text{sampling}$ ，从而得到隐含有权重意义的数据 $\tilde{D}_t$ ，并且通过这样的采样方式也可以避免得到一棵所谓“最好”的树，然后将 $\tilde{D}_t$ 喂给 $\text{decision tree}$ ，但是 $decision\ tree$ 的构造要加一点限制，通常是限制树的高度，也就是利用数据 $\tilde{D}_t$ 构造一棵 $\text{pruned decision tree}$ 。

boosting tree boosting tree $\text{boosting tree}$ ：

AdaBoost+sampling∝u(t)+pruned Decision Tree(D~t) A d a B o o s t + s a m p l i n g ∝ u ( t ) + p r u n e d D e c i s i o n T r e e ( D ~ t ) $AdaBoost + sampling \propto u^{(t)} + pruned\ Decision\ Tree(\tilde{D}_t)$

1.3 - 提升树实例

上面提到在 $\text{boosting tree}$ 算法中，决策树在构造的时候需要限制树的高度，得到一些“弱”一点的树，再和 $\text{adaboost}$ 搭配起来。我们考虑一种极端的情况，如果我们限制树的高度小于等于1，此时的决策树变为决策树桩。那么 $\text{adaboost}$ 和这样的 $\text{decision tree}（height<=1）$ 搭配起来会是什么样子的呢？其实这个时候的 $\text{boosting tree}$ 就退化为了 $\text{boosting stump}$ 。

因为针对每一个样本集合，这时 $decision\ tree（CART）$ 需要做的就只是选择一个分支条件 $b(x)$ 将样本集合划分为两个子树。其划分的依据就是要使得划分之后的数据的不纯度最低：

b (x) = a r g m i n d e c i s i o n s t u m p h (x) \sum c = 1 2 | D c w i t h h | ? i m p u r i t y (D c w i t h h)

$b(x) = \mathop{argmin}\limits_{decision\ stump\ h(x)} \sum_{c=1}^{2}|D_c \ with\ h| \centerdot impurity(D_c\ with\ h)$

这个时候就几乎不会出现 $\epsilon = 0$ 的情况， 那么这个时候也不见得会做抽样，而是直接在 $decision\ stump$ 中考虑权重。

所以简单来说，提升树用于分类只是将 $\text{AdaBoost}$ 算法框架中的弱分类器限制为二类分类树即可。

2 - 优化视角下的Adaboost

2.1 - Adaboost的指数损失函数

这一小节通过分析得到 $\text{AdaBoost}$ 算法的损失函数是实际上是指数损失 $L=exp(-ys)$ 。并且可以证明， $\text{AdaBoost}$ 算法是前向分步算法在损失函数为指数函数时的加法模型。

首先我们回忆一下 $\text{AdaBoost}$ 中每一个样本的权重的计算公式， $u_n^{(t+1)}$ 是根据 $u_n^{(t)}$ 计算得到的。如果该样本划分不正确，那么 $u_n^{(t+1)} = u_n^{(t)} \centerdot \blacklozenge_t$ ；如果该样本划分正确，那么 $u_n^{(t+1)} = u_n^{(t)} / \blacklozenge_t$ 。我们再来审视一下这个更新规则：样本划分不正确的意思就是： $y_n \ne g_t(x_n)$ ；样本划分正确的意思就是： $y_n=g_t(x_n)$ 。那么权重 $u$ 的更新规则就变为：

u_{n}^{(t + 1)} = u_{n}^{(t)} ? ?_{t}^{? y_{n} g_{t} (x_{n})}

$u_n^{(t+1)} = u_n^{(t)} \centerdot \blacklozenge_t^{-y_ng_t(x_n)}$

而

αt=ln(?t)=ln(1??t?t????√) α t = l n ( ? t ) = l n ( 1 ? ? t ? t ) $\alpha_t = ln(\blacklozenge_t) =ln(\sqrt{\frac{1 - \epsilon_t}{\epsilon_t}})$ ，所以

?t=eαt ? t = e α t $\blacklozenge_t = e^{\alpha_t}$
更新规则进一步变为：

u (t + 1) n = u (t) n ? e x p (? y n α t g t (x n))

$u_n^{(t+1)} = u_n^{(t)} \centerdot exp({-y_n \alpha_t g_t(x_n))}$

通过这样的表达我们看到样本 $(x_n, y_n)$ 最终的权重 $u_n^{(T+1)}$ 和初始的 $u_n^{(1)}$ 的关系如下：

u (T + 1) n = u (1) n ? \prod t = 1 T e x p (? y n α t g t (x n)) = 1 N ? e x p (? y n \sum t = 1 T α t g t (x n))

$u_n^{(T+1)} = u_n^{(1)} \centerdot \prod_{t=1}^{T}exp\bigg(-y_n\alpha_tg_t(x_n)\bigg) = \frac1N\centerdot exp\bigg(-y_n\sum_{t=1}^{T}\alpha_tg_t(x_n)\bigg)$

我们将 $\sum_{t=1}^{T}\alpha_tg_t(x)$ 称为 $\text{voting score}$ 。因为最后我们需要根据这个分数加一个 $sign$ 的操作来做分类的决定，即我们最终得到的模型是： $G(x) = sign\bigg(\sum_{t=1}^{T}\alpha_tg_t(x)\bigg)$ 。从上面的式子可以看出 $\text{AdaBoost}$ 中的每一个数据点的权重 $u_n^{(T+1)}$ 正比于负 $y_n$ 和 $\text{voting score}$ 的乘积的 $\text{exponential}$ 。

我们知道 $\text{AdaBoost}$ 是 $\text{linear blending}$ 的延伸，也就是要将 $g$ 线性的融合在一起。在 $\text{linear blending}$ 中我们可以将整个过程分为两步：1. 将所有的 $g$ 当做是一个特征转换；2. 将特征转换之后的结果使用一个线性的模型融合起来。

$linear\ blending = linear\ model + hypothesis\ as\ transform$

G (x n) = s i g n (\sum t = 1 T α t ? ? ?? w t g t (x n) ? ? ?? ? ? ? ? ? t (x n))

$G(x_n) = sign\bigg(\sum_{t=1}^{T}\underbrace{\alpha_t}_{w_t}\underbrace{g_t(x_n)}_{\phi_t(x_n)}\bigg)$

因为 $g_t(x_n)$ 可以视为特征转换，我们将其记为 $\phi_t(x_n)$ ，将每一个 $g_t(x_n)$ 的权重记为 $w_t$ 。这时， $voting\ score$ 就变成了 $w^T\Phi(x_n)$ 。这样我们就得到了一个我们比较熟悉的形式，因为在硬间隔的 $\text{SVM}$ 中： $margin = \frac{y_n\centerdot(w^T\phi(x_n) + b)}{||w||}$ ，表示这个数据点距离边界有多远。所以在这里 $voting\ score$ （虽然和上面的相比少了一些项）也是某一种距离，也是某一种 $margin$ ，也是在某一个空间中这个点到分割线的距离的一种衡量。

所以 $y_n\centerdot(voting\ score)$ 就相当于在 $SVM$ 中的没有归一化的 $margin$ ，也可以说是函数间隔。结合我们对 $\text{SVM}$ 的认识，我们希望 $y_n\centerdot(voting\ score)$ 越大越好，即首先这个值要是个正的，正值保证了划分的正确性；其次要尽量的大，这样就能有更大的置信区间或者说更大的 $\text{margin}$ 。所以我们就会希望 $exp(-y_n(voting\ score))$ 越小越好。也就是每一个数据点的权重 $u_n^{(T+1)}$ 要越小越好。

通过上面的分析我们知道 $AdaBoost$ 想要达到 $large\ margin$ 的效果，就是要努力的使所有的 $y_n\centerdot(voting\ score)$ 变大，就是要使所有的 $exp(-y_n(voting\ score))$ 变小。就是要最小化 $\sum_{n=1}^{N}u_n^{(T+1)}$ ，现在可以将 $\text{adaboost}$ 的损失函数定义为：

L = \sum n = 1 N u (T + 1) n = 1 N \sum n = 1 N e x p (? y n \sum t = 1 T α t g t (x n)) (1)

$L= \sum_{n=1}^{N}u_n^{(T+1)} = \frac1N\sum_{n=1}^{N} exp\bigg(-y_n\sum_{t=1}^{T}\alpha_tg_t(x_n)\bigg) \tag1$

所以得到了 $AdaBoost$ 的损失函数为指数损失函数。

2.2 - 又一个0/1误差的上界

画出 $\text{0/1 error}$ 和 $\text{AdaBoost error}$ 的曲线发现， $exponential\ error$ （图中的曲线）是 $0/1\ error$ （图中的折线）的一个上限。我们之前就碰到过 $0/1\ error$ 的一些上限， $\text{SVM}$ 的 $\text{hinge error}(max(1 - sy ,0))$ ， $\text{logistic regression}$ 的 $\text{scale cross entropy}(ln(1+exp(-ys)))$ 都是 $0/1\ error$ 的上限，我们之前都是利用这些上限将 $0/1\ error$ 做到最小，从而将分类问题做好。

现在我们从另一个角度看到 $Adaboost$ 通过最小化 $\sum_{n=1}^{N}u_n^{(T+1)}$ 以使得得到的边界有 $large\ margin$ 的效果，所以 $adaboost$ 算法在函数

\sum n = 1 N e x p (? y n \sum t = 1 T α t g t (x n)) (2)

$\sum_{n=1}^{N}exp\bigg(-y_n\sum_{t=1}^{T}\alpha_tg_t(x_n)\bigg)\tag2$

上做最小化，我们就将 $(2)$ 定义为 $adaboost\ error\ measure$ 。最终通过最小化 $err_{\widehat{ada}}$ 将 $err_{0/1}$ 做到最好。

$err_{0/1}(s, y) = |[ys \le 0]|$
$err_{\widehat{ada}}(s, y) = exp(-ys)$

在 $AdaBoost$ 中既然我们想要所有的样本点的权重越小越好，也就是想要最后的权重的总和越小越好，也就是要在上式 $(1)$ 中做最小化。 $AdaBoost$ 就是要做如下的一个最优化的问题：

m i n h E A D A = 1 N \sum n = 1 N e x p (? y n \sum t = 1 T α t g t (x n))

$\mathop{min}\limits_{h}\quad E_{ADA} = \frac1N\sum_{n=1}^{N} exp\bigg(-y_n\sum_{t=1}^{T}\alpha_tg_t(x_n)\bigg)$

解决上述最优化问题利用的工具是梯度下降法，梯度下降法的思路基本上是：当想要最小化一个函数的时候，可以看看从当前的点出发往哪个方向 $v$ 走一小步会使得结果变好。通常的方法是在该点附近使用泰勒公式进行展开，之后通过分析可以得到能使得函数变小的最好的方向就是负梯度的方向。沿着这个方向走一个小小的步长 $\eta$ ，这样就离我们的目标更近了一步。

泰勒展开

m i n | | v | | = 1 E i n (w t + η v) \approx E i n (w t) + η v T ▽ E i n (w t) (3)

$\mathop{min}\limits_{||v|| =1}\ E_{in}(w_t+ \eta v) \approx E_{in}(w_t) + \eta v^T\triangledown E_{in}(w_t)\tag3$

现在如果我们想要找一个函数 $g_t$ 当做方向，（向量和函数在本质上是一样的。当操作的对象是向量的时候，我们根据下标 $index$ 可以得到向量中的值；当操作的对象是函数的时候，我们根据输入 $x$ 可以得到函数的输出值，所以向量的 $index$ 是整数，函数的 $index$ 是实数。这样看来，函数就是无限维度的向量）。在 $gradient\ descent$ 中，我们想要找一个好的向量方向，沿着这个向量方向走一个步长 $\eta$ 来做最优化；在这里我们想要找一个好的函数 $h(x)$ ，沿着这个函数走一个步长 $\eta$ 来做最优化。
当前的 $adaboost$ 已经得到函数是 $\sum_{\tau = 1}^{t-1}\alpha_{\tau}g_{\tau}(x_n)$ , 所以就是要在 $\sum_{\tau = 1}^{t-1}\alpha_{\tau}g_{\tau}(x_n)$ 上加一个好的函数 $h(x_n)$ （向量方向）和步长 $\eta$ 的乘积 $\eta h(x_n)$ 来使得最终的结果变好一点。

m i n h E a d a ? = 1 N \sum n = 1 N e x p (? y n (\sum τ = 1 t ? 1 α τ g τ (x n) + η h (x n))) (4)

$\mathop{min}\limits_{h}\ \widehat{E_{ada}} = \frac1N\sum_{n=1}^{N}exp\bigg(-y_n\big(\sum_{\tau = 1}^{t-1}\alpha_{\tau}g_{\tau}(x_n) + \eta h(x_n)\big)\bigg)\tag4$
现在我们要想办法将

(4) ( 4 ) $(4)$ 变成

(3) ( 3 ) $(3)$ 的形式，

m i n h E a d a ? = 1 N \sum n = 1 N e x p (? y n (\sum τ = 1 t ? 1 α τ g τ (x n) + η h (x n))) = 1 N \sum n = 1 N e x p ((? y n) \sum τ = 1 t ? 1 α τ g τ (x n)) ? e x p (? y n η h (x n)) = \sum n = 1 N u (t) n e x p (? y n η h (x n)) \approx t a y l o r \sum n = 1 N u (t) n (1 ? y n η h (x n)) = \sum n = 1 N u (t) n ? η \sum n = 1 N u (t) n y n h (x n)

$\begin{align*} \mathop{min}\limits_{h} \widehat{E_{ada}} &= \frac1N\sum_{n=1}^{N}exp\bigg(-y_n\big(\sum_{\tau = 1}^{t-1}\alpha_{\tau}g_{\tau}(x_n) + \eta h(x_n)\big)\bigg) \\ &= \frac1N\sum_{n=1}^{N}exp\big((-y_n)\sum_{\tau = 1}^{t-1}\alpha_{\tau}g_{\tau}(x_n)\big)\centerdot exp\big(-y_n \eta h(x_n)\big) \\ & = \sum_{n=1}^{N} u_n^{(t)}exp\big(-y_n\eta h(x_n)\big) \\ & \overset{taylor}{\approx} \sum_{n=1}^{N} u_n^{(t)}\big(1-y_n\eta h(x_n)\big) \\ &= \sum_{n=1}^{N} u_n^{(t)} - \eta \sum_{n=1}^{N}u_n^{(t)}y_n h(x_n) \end{align*}$

泰勒展开式： $exp(x) = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdot + \frac{x^N}{N!} + \cdots$

通过上面的操作得到了和在 $gradient\ descient$ 中类似的形式，现在我们的目标是要找到一个好的 $h$ 来最小化 $\sum_{n=1}^{N}u_n^{(t)}(-y_n h(x_n))$ 。对于二分类问题来说：

= = = \sum n = 1 N u (t) n (? y n h (x n)) \sum n = 1 N u (t) n {? 1 i f y n = h (x n) 1 i f y n \neq h (x n) ? \sum n = 1 N u (t) n + \sum n = 1 N u (t) n {0 i f y n = h (x n) 2 i f y n \neq h (x n) ? \sum n = 1 N u (t) n + 2 E u (t) i n ? N (1) (2) (3) (4)

$\begin{align} &\sum_{n=1}^{N}u_n^{(t)}(-y_n h(x_n)) \\ =& \sum_{n=1}^{N}u_n^{(t)} \left\{ \begin{aligned} -1 \quad if\ y_n = h(x_n) \\ 1 \quad if\ y_n\ne h(x_n) \end{aligned} \right. \\ =& -\sum_{n=1}^{N}u_n^{(t)} + \sum_{n=1}^{N}u_n^{(t)} \left\{ \begin{aligned} 0 \quad if\ y_n = h(x_n) \\ 2 \quad if\ y_n\ne h(x_n) \end{aligned} \right. \\ =& -\sum_{n=1}^{N}u_n^{(t)} + 2E_{in}^{u^{(t)}} \centerdot N \end{align}$

我们的出发点是要找到一个好的 $h(x)$ 让 $\sum_{n=1}^{N}u_n^{(t)}(-y_n h(x_n))$ 变小，经过上面的推导发现想要让 $\sum_{n=1}^{N}u_n^{(t)}(-y_n h(x_n))$ 变小的就要让 $E_{in}^{u^{(t)}}$ 变小。能够使得 $E_{in}^{u^{(t)}}$ 变小的正是 $adaboost$ 中的 $base\ algorithm$ 算法 $\mathcal{A}$ 。所以 $base\ algorithm$ 找到了一个好的函数方向。我们原来认为 $\mathcal{A}$ 找到的 $g_{t}$ 只是为了让 $E_{in}^{u^{(t)}}$ 变小，现在经过这样的推导发现，这个 $g_t$ 是一个能够让 $E_\widehat{ada}$ 变小的函数方向。

$adaboost$ 通过大概的最小化 $\widehat{E_{ada}} = \sum_{n=1}^{N} u_n^{(t)}exp\big(-y_n\eta h(x_n)\big)$ 得到了一个好的函数（方向），按照 $gradient\ descent$ 的做法，现在要做的就是沿着这个方向走一小步。但是在这里我们不仅仅满足于只走一小步，而是想要走一大步。也就是说在 $g_t$ 被固定了之后，想要选择一个最大的 $\eta$ 来使得 $\widehat{E_{ada}}$ 最小：

m i n η E a d a ? = \sum n = 1 N u (t) n e x p (? y n η g t (x n)) ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

$\mathop{min}\limits_{\eta}\widehat{E_{ada}} = \sum_{n=1}^{N} \underbrace{u_{n}^{(t)}exp(-y_n\eta g_t(x_n))}_{\bigcirc}$
那么怎么来得到这个最好的步长

η η $\eta$ 呢？

当 $y_n = g_t(x_n)$ 的时候， $\bigcirc = u_{n}^{(t)}exp(-\eta)$
当 $y_n \ne g_t(x_n)$ 的时候， $\bigcirc = u_{n}^{(t)}exp(+\eta)$

E a d a ? = (\sum n = 1 N u (t) n) ? ((1 ? ?) e x p (? η) + ? t e x p (+ η))

$\widehat{E_{ada}} = (\sum_{n=1}^{N}u_n^{(t)}) \centerdot \big((1 - \epsilon)exp(-\eta) + \epsilon_t \ exp(+\eta)\big)$
对

η η $\eta$ 求导来得到最优解:

? E a d a ? ? η = 0 ? η t = l n 1 ? ? t ? ? ? ? ? ? \sqrt = α t

$\frac{\partial\widehat{E_{ada}}}{\partial \eta} = 0 \longrightarrow \eta_t = ln\sqrt{\frac{1-\epsilon_t}{\epsilon}} = \alpha_t$

所以这样看来， $adaboost$ 使用 $base\ algorithm\ \mathcal{A}$ 来得到一个最好的函数方向，当最好的函数方向 $g_t$ 得到之后， $adaboost$ 给这个 $g_t$ 一个权重或者说是票数 $\alpha_t$ ，现在我们知道了这个由 $adaboost$ 给出的权重 $\alpha_t$ 是一个最佳问题的解。所以 $adaboost$ 通过也可以称为 $steepest\ descent\ with\ approximate\ functional\ gradient$ 。

3 - Gradient Boosting

上一小节对 $\text{adaboost}$ 做了另一种解释， $\text{adaboost}$ 的每一轮可以看做是在最小化 $\text{exponential error}$ ：在每一轮中首先找出一个 $h$ ，将这个 $h$ 作为 $g_t$ ；然后再决定要沿着这个 $g_t$ 走多远的距离，这个距离会变成 $g_t$ 的权重 $\alpha_t$ 。所以一共有两个最佳化的过程：一个是对 $h$ 的最佳化过程，一个是对 $\eta$ 的最佳化过程。

m i n η m i n h 1 N \sum n = 1 N e x p (? y n (\sum τ = 1 t ? 1 α t g τ (x n) + η h (x n))) (1)

$\mathop{min}\limits_{\eta}\mathop{min}\limits_{h}\frac1N\sum_{n=1}^{N}exp\bigg(-y_n\big(\sum_{\tau=1}^{t-1} \alpha_t g_{\tau}(x_n) + \eta h(x_n)\big)\bigg)\tag1$

这样的概念可以不可以用在不同的 $\text{error function}$ 上呢？也就是说不再仅仅只是 $(1)$ 中的 $\text{exponential error}$ 。例如如果我们想做的是 $logistic\ regression$ 的话，我们关注的 $error$ 是 $cross\ entropy\ error$ ，如果我们想做的是 $regression$ 的话，我们关注的 $error$ 是 $squared\ error$ 。

3.1 - 前向分步算法优化加法模型

基于上述的讨论，将 $（1）$ 式进行扩展，将 $err$ 换掉，不再局限于使用 $exponential\ error$ ，而是可以使用任何我们感兴趣的 $error\ function$ 。

m i n η m i n h 1 N \sum n = 1 N e r r (\sum τ = 1 t ? 1 α t g τ (x n) + η h (x n), y n) (1)

$\mathop{min}\limits_{\eta}\mathop{min}\limits_{h}\frac1N\sum_{n=1}^{N}err\bigg(\sum_{\tau=1}^{t-1} \alpha_t g_{\tau}(x_n) + \eta h(x_n), y_n\bigg)\tag1$

这是一个新的 $aggregation$ 的模型：从当前已经得到的模型 $\sum_{\tau=1}^{t-1} \alpha_t g_{\tau}(x_n)$ 出发，沿着 $h(x_n)$ 走步长 $\eta$ ，目的是为了让 $err$ 变小，所以同样的在每一轮都是做两件事：先决定一个好的方向 $h$ 作为 $g_t$ ，然后决定要沿着这个 $g_t$ 更新多远得到步长 $\eta$ 并作为权重 $\alpha_t$ 将 $g_t$ 融入到最中的 $G$ 中。所以这样的模型很像是 $adaboost$ 只不过是对 $adaboost$ 做了延伸，我们称之为 $gradientBoost$ ，由不同的 $error\ funciton$ 就可以解决不同的问题例如 $regression$ 或者是 $soft\ classification$ 。

3.2 - 提升树用于回归

当我们想要使用 $\text{boosting tree}$ 做 $regression$ 的时候应该怎么做呢？我们关心的是 $squared\ error$ ： $err (s, y) = (s - y)^2$

m i n η m i n h 1 N \sum n = 1 N e r r (\sum τ = 1 t ? 1 α τ g τ (x n) ? ? ?? ? ? ? ? ? ? ? ? ? ? s n + η h (x n), y n)

$\mathop{min}\limits_{\eta}\mathop{min}\limits_{h}\frac1N\sum_{n=1}^{N}err\bigg(\underbrace{\sum_{\tau=1}^{t-1} \alpha_{\tau} g_{\tau}(x_n)}_{s_n} + \eta h(x_n), y_n\bigg)$

我们将使用当前已经得到的模型 $\sum_{\tau=1}^{t-1} \alpha_{\tau} g_{\tau}(x_n)$ 对样本 $x_n$ 做出的预测结果记为 $s_n$ ，我们的目的就是要从 $s_n$ 出发沿着某个 $h(x_n)$ 更新某个步长 $\eta$ 来使得 $err$ 变小。所以第一步我们首先找一个最好的 $h(x)$ 作为 $g_t$ ：

m i n h 1 N \sum n = 1 N e r r (s n + η h (x n), y n) \approx t a r l o r m i n h 1 N \sum n = 1 N e r r (s n, y n) + 1 N \sum n = 1 N η h (x n) ? e r r ( s , y n ) ? s | s = s n = m i n h c o n s t a n t s + η N \sum n = 1 N h (x n) 2 (s n ? y n) ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

$\begin{align*} & \mathop{min}\limits_{h}\frac1N\sum_{n=1}^{N}err(s_n+\eta h(x_n), y_n) \\ & \overset{tarlor}{\approx} \mathop{min}\limits_{h}\frac1N\sum_{n=1}^{N}err(s_n, y_n) + \frac1N\sum_{n=1}^{N}\eta h(x_n) \frac{\partial err(s, y_n)}{\partial s}|_{s=s_n} \\ &= \mathop{min}\limits_{h} \underbrace{constants + \frac{\eta}{N}\sum_{n=1}^{N}h(x_n)2(s_n-y_n)}_{\bigcirc} \end{align*}$

我们现在是要找一个 $h(x_n)$ 来使得 $\bigcirc$ 最小，那么易知当 $h(x_n) = -\infty\centerdot(s_n - y_n)$ 的时候，上式可以取得最小。因为首先 $-(s_n - y_n)$ 保证了结果是负数，再乘以一个 $\infty$ ，就是负的无穷大，这是最直观的该最小化问题的解。但是因为在这里 $h(x_n)$ 相当于一个方向，所以应该对其长度进行一下限制，这样就可以避免出现 $-\infty$ 。并且长度的问题最后交给步长 $\eta$ 来解决。
基于以上的讨论我们应该解决的问题是：

m i n | | h | | = 1 c o n s t a n t s + η N \sum n = 1 N h (x n) 2 (s n ? y n)

$\mathop{min}\limits_{||h|| = 1}\quad constants + \frac{\eta}{N}\sum_{n=1}^{N}h(x_n)2(s_n-y_n)$

但是这样的话变成了需要求解一个有条件 $||h||=1$ 的最佳化问题，因为我们并不在乎 $h$ 的大小，所以我们将其作为一个惩罚项放入目标函数中的，只是限制使得 $h(x)$ 不要太大即可，新的问题变为：

m i n h c o n s t a n t s + η N \sum n = 1 N (2 h (x n) (s n ? y n) + h (x n) 2) = c o n s t a n t s + η N \sum n = 1 N (c o n s t a n t + (h (x n) ? (y n ? s n) ? ? ?? ? ? ? ? ? ? r e s i d u a l) 2)

$\begin{align*} & \mathop{min}\limits_{h}\quad constants + \frac{\eta}{N}\sum_{n=1}^{N}\bigg(2h(x_n)(s_n-y_n) + h(x_n)^2\bigg) \\ & = constants + \frac{\eta}{N}\sum_{n=1}^{N}\bigg(constant + \big(h(x_n) - \underbrace{(y_n - s_n)}_{residual}\big)^2\bigg) \\ \end{align*}$

$y_n$ 是目标值， $s_n$ 是目前给出的预测值，我们将 $y_n - s_n$ 定义为残差 $residual$ 。为了达到最小化的目的，就是要找一个 h