浅谈集成学习

1. 集成学习

集成学习(ensenble learning)是指通过构建并结合多个学习器来完成学习任务。一般来说，多个“弱学习器”结合起来的效果往往好于单个强学习器的效果，所以集成学习的应用非常广泛，比如著名的集成树模型系列。

集成学习按照个体学习器是否相同，可以分为同质集成和异质集成。同质集成的个体学习器是相同，比如都是决策树，个体学习器也往往被称为基学习器。异质集成中的个体学习器由不同的学习算法生成，比如不同的分类器(如决策树、lr和svm)投票出最终的结果。

集成学习另一种比较普通的分类方法是根据个体学习器之间的组合方式，一种是串行的方式，称为boosting方法，如Adaboost；一种是并行的方法，称为bagging方法，如随机森林。

1.1 从偏差和方差说起

此处所提到的偏差和方差是有一定指代范围的，偏差指的是在训练集上的效果好坏，比如计算的正例的概率都集中在1附近，模型刻画能力较好，那么偏差就较小；方差指的是在不同测试集上的预测效果的浮动程度，比如在不同测试集上正例预测的概率范围都很接近，那么方差就较小。用打靶子来比喻的话，低偏差就是训练的时候每一枪都打到了靶中心周围，而低方差就是不管是训练还是比赛的时候，每次打的位置都比较接近。

偏差相当于刻画了模型在训练集上的效果，方差刻画了模型在不同测试集上的泛化能力，一个欠拟合的模型很明显是偏差大的，一个过拟合的模型很明显是方差大的。

1.2 boosting

boosting方法是集成学习中的第一大类别，这类算法的一般工作机制为：先在训练集上训练出一个个体学习器，然后根据个体学习器的在训练集上的效果，重新分配训练样本的权重，比如对错误分类样本增大权重，在此基础上训练新的个体学习器。直到个体学习器的个数达到了目标的个数，停止训练，将n个个体学习器线性加和作为最终的结果。boosting是一种串行的集成学习算法，主要的目的是降低偏差。

前向分步算法

我们考虑一个加法模型，在我们训练了很多基学习器以后，使用线性相加的形式作为最后的模型。

$$f(x) = \sum_{m=1}^M\beta_mb(x;\gamma_m)$$

$f(x)$是最终的模型，$\beta_m$是每个基学习器的权重，$b(x;\gamma_m)$是基学习器，$\gamma_m$是基学习器的参数。

在给定损失函数$L(yi, \sum{m=1}^Mb(x_i;\gamma_m))$的条件下，即转换为极小化损失函数的问题：

$$\mathop{min}\limits_{\gamma_m, \beta_m} L(y, \sum_{m=1}^M\beta_mb(x;\gamma_m))$$

这种情况非常难以求解，于是，可以转换为从前到后每次求解一个基学习器的权值和参数。

具体算法

输入：训练数据集 $((x_1, y_1),…,(x_n, y_n))$，损失函数 $L(y, f(x))$，基学习器 $b(x, \gamma)$

输出：学习器 $f(x)$

1. 初始化 $f_0(x) = 0$
2. 对0,…,M
   1. 更新 $f_m(x) = f_{m-1} + \beta_mb(x;\gamma_m)$
   2. 极小化损失函数 $(\gamma_m, \beta_m) = \mathop{argmin}\limits_{\gamma_m, \beta_m} L(y, f_{m-1}(x) + \beta_mb(x;\gamma_m))$
3. 得到加法模型

Adaboost

我对于Adaboost算法的理解，就是从前向分步算法推导出来的，所以此处给出前向分步算法推导出Adaboost算法。

算法最终的分类器为

$$f(x) = \sum_{m=1}^M \alpha_mG_m(x)$$

损失函数是指数损失

$$L(y, f(x)) = exp(-yf(x))$$

根据前向分布算法

$$\begin{align*} (G(x), \alpha_m) &= \mathop{argmin}\limits_{G(x), \alpha_m} \sum_iL(y_i, f_{m-1}(x_i) + \alpha_mG(x_i)) \\ &= \mathop{argmin}\limits_{G(x), \alpha_m} \sum_iexp(-y_if_{m-1}(x_i)-y_i\alpha_mG(x_i)) \\ &= \mathop{argmin}\limits_{G(x), \alpha_m} \sum_iw_{mi}exp(-y_i\alpha_mG(x_i)) \end{align*}$$

其中 $w_{mi} = exp(-y_if_{m-1}(_i))$，可以认为是每个样本的权重。

下面求解$\alpha_m$

$$\begin{align*} \sum_{i=1}^N w_{mi}exp(-y_i\alpha G(x_i)) &= \sum_{y_i=G(x_i)}e^{-\alpha} + \sum_{y_i!=G(x_i)}e^{\alpha} \\ &= (e^\alpha - e^{-\alpha})\sum_{i=1}^Nw_{mi}I(y_i\neq G(x_i)) +e^{-\alpha}\sum_{i=1}^Nw_{mi} \end{align*}$$

求导，令导数为0得到

$$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$$

其中

$$e_m = \frac{\sum_{i=1}^Nw_{mi}I(y_i\neq G(x_i)) }{\sum_{i=1}^Nw_{mi}}$$

所以，我们可以算得下一个基分类器训练时每个样本的权重，以及该基分类器在最终的模型中所占的权重，这样就得到了完整的Adaboost的算法形式。

下面具体详细地阐述Adaboost算法

1. 模型为加法模型、损失函数为指数损失函数、学习算法为前向分布算法的学习方法
2. 最终的分类器 $f(x) = \sum_{m=1}^M\alpha_mG_m(x)$
3. 涉及到两个主要问题
   • $\alpha_m$：每个基分类器的权值是多少
   • $w_{mi}$：每个基分类器训练时，各个训练样本的权值是多少
   • 一旦有了这两个参数，可以计算loss，进行训练，同时计算下一个训练样本的权值分布
4. 过程
   • 第m个分类器的分类误差率 $e_m = \sum_{i=1}^Nw_{mi}I(y_i\neq G_m(x_i))$
   • 第m个分类器的loss $\sum_{i=1}^Nw_{mi}exp[-y_i\alpha_m G(x_i)]$
   • 对loss求导可以得到 $\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$ 当 $e_m \leq \frac{1}{2}$ 时，em越小 $\alpha_m$ 的权值越大
     • 训练样本权值更新 $w_{m+1, i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i))$
       • 如果分类正确，则减小样本的权值
       • 如果分类错误，则增大样本的权值
     • 继续如上过程训练

1.3 bagging

bagging是集成学习中的第二大类方法，是并行式集成学习的代表。bagging方法的基础是自助采样法(bootstrap sampling)，我们从样本中抽取一个样本，再把该样本放回原训练集中，再进行第二次采样。根据此方法可以采样得到一个容量为m的子训练样本，原训练样本中有些在子训练样本中从未出现过，有些会重复出现。我们采样出T个这样的容量为m的子训练样本，通过T次的子训练样本可以训练得到T个基分类器。最后T个基分类器结合得到最终的结果(比如投票法)。当我们想得到泛化能力强的集成模型，我们希望每个基分类器尽量独立，也就是具有差异性。通过bagging方法得到的T的基分类器因为训练样本的差异性，模型本身也具有差异性，所以集成以后效果会比较好。

random forest

随机森林是bagging的一个变体，随机森林在以决策树为基础构建bagging集成学习的基础上，在决策树的训练过程中引入了随机属性选择。

具体地，随机森林的基分类器是决策树，每个基分类器的训练样本来自于bagging方法的采样。同时，在每个基分类器的训练过程中，还会随机选择k个属性作为当前基分类器的划分属性集合。这样，对于每个基分类器来说，不仅训练样本不同，用于划分的属性集合也不同，增加了每个基分类器之间的差异性，同时，因为每次不需要考虑所有的属性，计算量减少了，提高了训练效率。

1.4 两种集成方法对比

boosting方法和bagging方法的区别主要体现在两个方面：

一个是体现在每个基分类器的组合形式上，前者是串行，后者是并行。串行的方式，必须得等待前面的基分类器训练完，基于该分类器的结果才可以训练下一个基分类器，和循环神经网络类似，不能进行并行计算提高效率；并行的bagging方法因为每个基分类器之间的训练之间没有相互依赖关系，所以可以进行并行计算提高效率。

另一个方面是两种方法主要的效果上，前者是主要降低偏差，后者主要降低方差。boosting方法希望在训练集上的误差越小越好，每次的基分类器都是以降低偏差为目标；bagging方法训练样本是有差异的或者因为特征子集也不尽相同，所以每个基分类器是有差异的，这些有差异的基分类器相当于模拟了在不同测试集上的表现，基分类器之间会相互弥补，达到降低方差的效果。

2. 典型的集成树模型

2.1 gradient boost

对于前向分步算法，一个比较关键的问题是，在优化求解m个基学习器时，优化目标是什么。当计算使用指数损失函数作为loss的分类问题时，每个基学习器的优化目标很容易地进行求解，此时就是Adaboost算法；当计算使用平方误差损失作为loss的回归问题时，每个基学习器的优化目标同样很容易求解，就是boosting tree的形式，此时可以直接化解为残差的形式，即每个基学习器优化的是上一个基学习器和目标的残差。

此处可以证明一下平方损失函数作为loss时残差优化目标的推导：

$$L(y, f_{m-1}(x) + \beta_mb(x;\gamma_m)) = (y - f_{m-1}(x) - \beta_mb(x;\gamma_m))^2 = (r - \beta_mb(x;\gamma_m))^2$$

其中 $r = y - f_{m-1}(x)$即为残差形式。

接下来，对于除了以上的两种情况以外的一般损失函数来说，每一步的优化目标并不容易确定，所以，提出了每次的优化目标是损失函数的负梯度在当前模型的值。即优化

$$-[\frac{\partial L(y, f(x_i))}{\partial f(x_i)}]_{f(x) = f_{m-1}(x)}$$

2.2 GBDT

GBDT全称是gradient boosting decision tree。使用的是gradient boosting方法，基学习器是CART树。

对于GBDT回归算法，和上面gradient boosting方法完全类似，基学习器时CART树，使用的loss是平方损失，所以每一个基学习器的优化目标是上一个CART树与优化目标的残差。

比如，我们要用GBDT预测人的年龄，目标是30岁。那么，第一个树的目标是30岁，如果预测的值是20岁，那么第二个树的目标则为30-20=10岁，依次类推下去。

2.3 xgboost

计划看一下陈天奇的论文再做进一步总结。

xgboost和GBDT的主要不同体现在优化的目标上，GBDT优化的是梯度，相当于是一阶导数，而xgboost对loss进行了二阶泰勒展开，同时加上了正则化项作为优化目标，正则化项包括叶子节点个数以及叶子节点输出值的L2值。

3. 典型集成模型对比

rf、GBDT、xgboost、lightGBM

1. random forest

• 优点
  • 训练速度、准确率都较好
  • 能够处理高维数据，不用进行特征筛选，训练后能看到特征的重要性
  • 可以进行并行训练
• 缺点
  • 在噪声大的训练数据上容易过拟合

2. GBDT

• 优点
  • 灵活处理各种数据
  • 较少调参时间内准确度较高
• 缺点
  • boosting方法，串行，难以并行训练

3. xgboost和GBDT

• GBDT是基学习器是回归树，而xgboost支持线性分类器
• GBDT的优化目标只利用了一阶导数，而xgboost利用了一阶导数和二阶导数
• shrinkage。在每个基分类器计算完后，会将叶子节点权值乘以一个参数，为了削弱每颗树的影响，为了让后面有更大的学习空间
• xgboost加入了正则化项，防止了过拟合
• 列抽样，和随机森林一样支持列抽样，防止过拟合，减少计算
• 缺失值的处理
• xgboost进行了并行计算，在特征选择的过程中用了排序方法

4. 为什么rf需要设置树的深度较深，而xgboost并不需要

• rf是bagging方法，主要是降低方差，所以希望单个模型偏差较低，所以倾向于偏差低的单个模型
• xgboost是boosting方法，主要是为了降低偏差，所以希望单个模型方差较低，方差较低就希望单个模型不要太复杂，所以倾向于树的深度浅一些。