An Ensemble Learning Method：Boosting.

1. Boosting的基本思想

Boosting是一种集成学习的方法，主要关注在同一个数据集上按顺序训练一系列相同类型的子模型，这些子模型被称作基学习器(base learner)，不同的基学习器能对不同的数据分布进行学习。Boosting主要关注降低偏差，因此能基于泛化性能相当弱的弱学习器构建出很强的集成学习器。

Boosting的基学习器并不是独立训练的，而是首先从初始数据集中训练一个基学习器，之后在每次训练一个新的基学习器时，会利用已经获得的基学习器的信息；如此反复进行，直至训练得到$T$个基学习器，最终对其进行加权组合。常见的Boosting策略有：

• 重加权(re-weighting)：对每个训练样本赋予权重，如AdaBoost
• 重采样(re-sampling)：根据权重对数据集采样
• 梯度(gradient)方法：利用损失函数的负梯度信息，如Gradient Boosting

以重加权法为例，Boosting的基本流程如下。若需要训练$T$个基学习器\(\{g_t,t=1,2,...,T\}\)，设置训练集中的$N$个样本的初始权重\(\{w_n^{(1)}=\frac{1}{N},n=1,2,...,N\}\)；在第$t$轮训练过程中，根据样本分布为每个训练样本重新赋予权重$w_1^{(t)},w_2^{(t)},…,w_N^{(t)}$。记$ε_t$为基学习器$g_t$在第$t$次赋值的训练集上训练后的错误率，即：

则一种简单的样本权重更新方式表示如下，即增大错误预测样本的权重，减小正确预测样本的权重：

经过上述过程训练，得到$T$个训练好的基学习器\(\{g_t,t=1,2,...,T\}\)，之后可以通过Blending方法集成模型，从而得到最终的结果。

重加权法要求每个基学习器虽然是弱学习器，但仍具有超过统计随机值的表现水平(即比随机猜测好)，即通常$ε_t<0.5$。再训练的每一轮需要检测当前生成的基学习器是否满足该基本条件，一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。这样会导致最终获得的基学习器个数远小于$T$个，使得集成学习性能不佳。

对于无法接受带有权重的样本的基学习器（比如决策树），可以通过重采样(re-sampling)方法实现Boosting。即在每一轮训练中，根据样本分布对训练集进行重新采样，再根据重采样的样本集训练基学习器。这种方法可以通过重启动避免由于不满足弱学习器条件而停止的问题，即抛弃当前不满足条件的基学习器后，可根据当前分布对训练样本重新采样，再根据新的采样结果训练学习器，从而保证学习过程可以持续到$T$轮结束。

2. 自适应梯度提升 AdaBoost

AdaBoost(Adaptive Boosting)是为二分类任务设计的Boosting重加权方法，主要包括：

• 单一模型的训练算法：指数损失函数
• 样本权重的赋值方法：$d_t = \sqrt{\frac{(1-ε_t)}{ε_t}}$
• 不同样本的组合方法：加性模型

若通过$T$轮训练获得$T$个基学习器\(\{g_t,t=1,2,...,T\}\)，则AdaBoost是一种加性模型(additive model)，即基学习器的线性组合：

基学习器的获得是通过迭代地优化指数损失函数(exponential loss function)实现的：

下面以输出标签为$±1$的二分类为例，介绍AdaBoost算法。

(1) AdaBoost算法的流程

假设需要训练$T$个基学习器\(\{g_t,t=1,2,...,T\}\)，训练开始时设置训练集中的$N$个样本的初始样本权重\(\{w_n^{(1)}=\frac{1}{N},n=1,2,...,N\}\)。

引入一个参数$d_t$，则AdaBoost的第$t+1$轮训练中，训练集第$n$个样本权重的更新方法如下：

其中$Z_t$表示第$t$轮训练中所有样本权重的加权和，用于对训练样本集的权重进行归一化，计算为：

注意到所有样本权重的加权和$Z_t$并不等于样本权重之和！事实上通过引入$Z_t$使得每轮训练中的样本权重值和都满足$\sum_{n=1}^{N} w_n^{(t)}=1$。

通常参数$d_t>1$，即增大错误预测样本的权重，减小正确预测样本的权重。 对于第$t+1$次训练，希望新的基学习器能够训练得到与$g_t$互补的模型，即假设$g_t$在重新设置权重的训练集上只能得到随机的效果：

将训练样本权重的更新公式代入得：

将$d_t$提出求和项，并约分$1/Z_t$项：

注意到错误率 $ε_t \propto \sum_{y_n ≠ g_t(x_n)} {w_n^{(t)}}$，得：

解得：

记每一个基学习器$g_t$在最终模型中所占的模型权重为$α_t$，则计算该权重的公式为：

分析：

• 当$g_t$的分类错误率$ε_t=0.5$，则该模型与随机分类无异，对应权重$α_t=0$;
• 当$g_t$的分类错误率$ε_t=0$，则该模型完全分类正确，对应权重$α_t=+∞$；
• 分类错误率$ε_t$越小，投票时模型$g_t$所占比重越大。

训练得到一系列基学习器\(\{g_t,t=1,2,...,T\}\)后，最终的集成模型为：

(2) AdaBoost的VC维

定义某假设函数对于观测样本的误差为$E_{in}$，该误差可以计算得到；定义该假设函数对于总样本的误差为$E_{out}$，该误差不可计算。 则AdaBoost的VC维表示为：

AdaBoost具有良好的性质：

• 若基本模型仅比随机结果好一些($ε_t<\frac{1}{2}$)，则经过$T=O(\log N)$次迭代后$E_{in}≈0$；
• 若样本数$N$很大，则最终得到的模型满足$E_{out}≈E_{in}$。

(3) 指数损失 Exponential Loss

根据定义的模型权重\(\{α_t,t=1,2,...,T\},α_t = \ln(d_t)\) 对于标签是$±1$的二分类任务，样本集的权重更新可以表示为：

其中所有样本权重的加权和$Z_t$也可由模型权重\(α_t\)表示为：

若初始样本权重$w_n^{(1)}=\frac{1}{N}$，则样本权重更新为：

对于单个样本$(x_n,y_n)$的样本权重$w_n$，当算法对该样本分类正确时，$y_n$应与$g(x_n)$同号，且$g(x_n)$越大越好（类似于间隔的概念），即$w_n$是逐渐减小的。

对于所有样本，可以列出一个最优化问题，即最小化所有样本权重：

上式称为指数损失(exponential loss)。故AdaBoost的优化问题也可以看作通过加性模型(即每次训练一个新的基学习器$g_t$)迭代地优化指数损失函数。值得一提的是，上式省略了所有样本权重的加权和$Z_t$，后面会看到这也导致了AdaBoost算法的训练误差界。

⚪ 指数损失函数与0/1损失

指数损失函数是$0/1$损失的一个上界：

下面证明在分类任务中指数损失是$0/1$损失的一个一致(consistent)替代损失函数。不妨记AdaBoost获得的集成模型为$G(x) = \sum_{t=1}^{T} {α_tg_t(x)}$，则指数损失表示为：

令其对$G(x)$的偏导为$0$：

解得：

则AdaBoost的输出可以表示为：

上式表示若指数损失最小化，则模型达到贝叶斯最优错误率，这与$0/1$损失是一致的。而指数损失是连续可微函数，因此AdaBoost选用指数损失函数作为$0/1$损失函数的替代。

⚪ AdaBoost算法的训练误差界

下面求指数损失函数的误差界：

因此指数损失函数的误差界与所有样本权重的加权和$Z_t$相关；该结论从指数损失函数的推导过程中也能看出(推导过程省略了$\prod_{t=1}^{T} Z_t$)。因此在每轮训练时，通过选择合适的$g_t$使得$Z_t$尽可能小，从而使训练误差下降最快。

⚪ 二分类问题的AdaBoost算法的训练误差界

上面求得了指数损失函数的误差界$\prod_{t=1}^{T} Z_t$，对于二分类问题,注意到错误率的定义$ε_t \propto \sum_{y_n ≠ g_t(x_n)} {w_n^{(t)}}$，则有：

根据上式可得对于二分类问题，AdaBoost算法的训练误差以指数速率下降。

(4) 从优化角度理解AdaBoost：如何选择$α_t$

AdaBoost可以被写作一个优化问题，即求第$t$个基学习器$g_t$及其权重$α_t$时，最小化指数损失函数：

根据样本集的权重更新规律：

指数损失目标函数化简为：

把上式拆分成$y_n=g_t(x_n)$和$y_n≠g_t(x_n)$两种情况：

上式对$α_t$求导，令其为$0$，可以得到：

解得：

这与之前的定义是吻合的。

3. 梯度提升 Gradient Boosting

Boosting方法按顺序训练一系列基学习器$g_t$，通过加权这些基学习器得到最终的结果：

对于二分类任务，AdaBoost把损失函数设置为指数损失函数，从而给出了每次寻找一个新的模型函数$g_t$的解析方法，即每一次迭代都是通过确定的公式计算得到的。然而对于一般损失函数而言，每一步优化过程并不容易。

Freidman提出了梯度提升 (Gradient Boosting)方法，在每一轮迭代中，首先计算出当前模型在所有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合并计算出该弱分类器的权重，最终实现对模型的更新。

在梯度提升过程中，假设经过了$T-1$次训练得到的模型为：

在第$T$次训练中，需要确定模型$g_T$及其权重$α_T$，使得：

对于任意损失函数$L(y,f(x))$，对其在$f(x)=f_{T-1}(x)$处进行一阶泰勒展开：

令$f(x)=f_{T}(x)$：

因此若希望损失函数减小，则$f_{T}(x)-f_{T-1}(x)$应与\([\frac{\partial L(y,f(x))}{\partial f(x)}]_{f(x)=f_{T-1}(x)}\)异号，记为：

上式可以看作在函数空间中的梯度下降算法，$α_T$可以看作学习率：

因此第$T$次训练中的模型$g_T$可以拟合当前损失函数的负梯度：