1 引言

本文主要结合了李宏毅的机器学习课程之Ensemble和周志华的《机器学习》西瓜书两者的说法，对ensemble这一竞赛利器做了总结。
Ensemble主要可以分为bagging和boosting两种方法。其中，bagging适用于基模型复杂度比较高的情况（如树模型），其目的是为了减小variance，即阻止过拟合的情况。而boosting则是适用于基模型是弱学习器的情况，其目的是减小biases，基本上多弱模型都可以用（如果分类正确率低于50%，取个反就可以了）~

2 Bagging

个人觉得bagging其实和神经网络中的drop-out非常相似。我们只给每个模型看数据的一部分，不给它们看全貌，然后希望它们在这一部分上有比较好的学习结果，最后综合各个模型的结果，做一个blending，得到最终的结果。
Bagging在选取数据时，采用的是bootstrap的方法，即有放回的抽样。假设我们有 m$m$ 个样本的数据集 D$D$ 。我们希望利用有放回的抽样方法构造一个新的数据集 D′$D^{\prime }$，其样本个数仍旧是m。显然 D$D$ 中的一些数据会在 D′$D^{\prime }$ 中重复出现，这也就意味着有一部分数据在 D′$D^{\prime }$ 中是不会出现的。

图1 bagging示意图（此图出自李宏毅的视频）
我们可以做一个简单的估计。样本在m次采样中，始终没有被采到的概率为 (1−1m)m$(1-\frac{1}{m}{)}^m$ ，取极限的话为

limm→∞(1−1m)m→1e≈0.368$$\underset{m\to \mathrm{\infty }}{lim}(1-\frac{1}{m}{)}^m\to \frac{1}{e}\approx 0.368$$

这一部分没有被采样到的数据可以作为验证集来使用，这个方法被称“包外估计”(out-of-bag estimate)。
根据该方法训练得到多个模型之后，可以取平均或者投票得到最终结果。
其中，随机森林便是一个典型的利用bagging方法的模型，只不过在随机森林当中，数据的特征也是随机选取的。

3 Boosting

Boosting的主要想法是在已有模型的基础上，重视被错分的样本，再训练一个模型来融合到原模型中，以此来提高模型的准确率，如此不断反复。那么如何重视被错分的样本呢？这就是boosting的一个有意思的地方了。它给每个样本赋予了一个权重，每次boosting之后，样本的权重就会被更新，而这里的权重直接影响了训练时的Loss function。

L(f)=∑nl(f(xn),yn)→L(f)=∑nunl(f(xn),yn)$$L(f)=\sum _{n}l(f(x^n),y^n)\to L(f)=\sum _n{u}_{n}l(f(x^n),y^n)$$

式中，un$u_n$ 即为每个样本的权重。也就是说，现在我们的样本变成了这个样子
{(x1,y1,u1),(x2,y2,u2),⋯,(xn,yn,un)}$\{(x^1,y^1,u^1),(x^2,y^2,u^2),\cdots ,(x^n,y^n,u^n)\}$
Boosting的方法有很多，我们这里主要讲一下其中比较流行的AdaBoost算法。
假设我们在第一个基模型 f1(x)$f_1(x)$ 上训练得到的错误率为（此时所有样本权重均相同）

ϵ1=∑nun1δ(f1(xn)≠yn)Z1$${ϵ}_1=\frac{\sum _n{u}_1^n\delta (f_1(x^n)\ne y^n)}{Z_1}$$

其中

Z1=∑nun1$$Z_1=\sum _n{u}_1^n$$

我们希望学习器的错误率 ϵ1${ϵ}_1$ 是大于0.5的，否则我们取个反，或者不要这个学习器，换一个。
知道了哪些训练错了，哪些训练对了之后，我们就要进行最重要的重新分配权重了。所谓的重新分配权重就是给正确的权重除以一个 d1$d_1$ ，错误的权重乘以一个 d1$d_1$，d1>1$d_1>1$。
那么这个 d1$d_1$ 怎么来？我们希望再更新权重之后，新的权重满足下式

∑f1(xn)≠ynun2=∑f1(xn)=ynun2$$\sum _{f_1(x^n)\ne y^n}{u}_2^n=\sum _{f_1(x^n)=y^n}{u}_2^n$$

也就是说，从权重上来看要错的对的各占一半，即

∑f1(xn)≠ynun1d1=∑f1(xn)=ynun1/d1$$\sum _{f_1(x^n)\ne y^n}{u}_1^n{d}_1=\sum _{f_1(x^n)=y^n}{u}_1^n/d_1$$

其中，Z1ϵ1=∑f1(xn)≠ynun1d1$Z_1{ϵ}_1=\sum _{f_1(x^n)\ne y^n}{u}_1^n{d}_1$， Z1(1−ϵ1)=∑f1(xn)=ynun1d1$Z_1(1-{ϵ}_1)=\sum _{f_1(x^n)=y^n}{u}_1^n{d}_1$，代入上式可得

d1=(1−ϵ1)/ϵ1−−−−−−−−−√$$d_1=\sqrt{(1-{ϵ}_1)/{ϵ}_1}$$

再用此时的权重去训练出第二个模型 f2(xn)$f_2(x^n)$ 。之后，继续如此操作，直到达到弱分类器个数限制。
为了方便表示，我们通常把d$d$ 表示成 eα$e^{\alpha }$ 的形式，那么，权重的更新可以直接写成

unt+1=unt⋅e−ynft(xn)αt=∏i=1te−ynαifi(xn)$$u_{t+1}^n=u_t^n\cdot e^{-y_n{f}_t(x^n){\alpha }_t}=\prod _{i=1}^t{e}^{-y_n{\alpha }_i{f}_i(x^n)}$$

其中，αt=ln(dt)${\alpha }_t=ln(d_t)$。
得到所有的模型之后，我们希望把训练的 T$T$ 个模型融合起来，这个融合的过程就叫做blending。
一种简单的做法就是直接取结果的平均

H(x)=sign(∑t=1Tft(x))$$H(x)=sign(\sum _{t=1}^T{f}_t(x))$$

但这样的做法不够机智。我们每个模型的可信度是不同的，我们需要给每个模型一个权重，得到一个加权平均的结果

H(x)=sign(∑t=1Tαtft(x))$$H(x)=sign(\sum _{t=1}^T{\alpha }_t{f}_t(x))$$

这里的αt${\alpha }_t$ 就是我们前面的 αt=ln((1−ϵ1)/ϵ1−−−−−−−−−√)${\alpha }_t=ln(\sqrt{(1-{ϵ}_1)/{ϵ}_1})$。可以证明随着模型数量的增加，模型在训练集上的表现会越来越好，详细证明可参见李宏毅的视频。

4 Gradient Boosting

顾名思义，这是用Gradient的方法来进行boosting。上文中的Adaboost其实就是一种特殊的Gradient Boosting。Gradient Boosting的总体流程为

图2 Gradient Boosting流程图
既然是要做Gradient，当然要有目标函数啊。这里的目标函数就是

L(g)=∑nl(yn,g(xn))$$L(g)=\sum _{n}l(y^n,g(x^n))$$

于是，就有

gt(x)=gt−1−η∂L(g)∂g(x)|g(x)=gt−1(x)$$g_t(x)=g_{t-1}-\eta \frac{\mathrm{\partial }L(g)}{\mathrm{\partial }g(x)}{|}_{g(x)=g_{t-1}(x)}$$

又由于

gt(x)=gt−1(x)+αtft(x)$$g_t(x)=g_{t-1}(x)+{\alpha }_t{f}_t(x)$$

所以我们希望 −η∂L(g)∂g(x)|g(x)=gt−1(x)$-\eta \frac{\mathrm{\partial }L(g)}{\mathrm{\partial }g(x)}{|}_{g(x)=g_{t-1}(x)}$ 和 αtft(x)${\alpha }_t{f}_t(x)$ 是方向相同的。即找到一个 ft(x)$f_t(x)$ 使得

maxft(x)−ηft(x)∂L(g)∂g(x)|g(x)=gt−1(x)$$\underset{f_t(x)}{max}-\eta f_t(x)\frac{\mathrm{\partial }L(g)}{\mathrm{\partial }g(x)}{|}_{g(x)=g_{t-1}(x)}$$

然后找一个 αt${\alpha }_t$ 使得 L(g)$L(g)$ 最小。
当 L(g)=∑ne−yng(xn)$L(g)=\sum _n{e}^{-y^{n}g(x^n)}$ 的时候，可以推出这就是我们的Adaboosting。
详细推导过程偷下懒，参见李宏毅的视频即可。