西瓜书阅读笔记——第8章-集成学习

强烈推荐配合西瓜书阅读使用的南瓜书和南瓜书作者录制的学习视频【吃瓜教程】《机器学习公式详解》（南瓜书）与西瓜书公式推导直播合集。

个体与集成

集成学习ensemble learning的定义

高度概括：“三个臭皮匠，顶个诸葛亮”。

集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统(multi-classifier system)、基于委员会的学习(committee-basedlearning)等。

先由一个现有的学习算法从训练数据中产生一组个体学习器(individual learner)，比如决策树、神经网络算法等，然后通过某种结合策略将这些个体学习器组合起来。如果个体学习器全是一类的，比如全是神经网络的神经网络集成，这样的集成称为“同质”(homogeneous)，其中的个体学习器也叫基学习器(base learner)，相应的学习算法称为"基学习算法"(base learning algorithm)；如果是不同类型的个体学习器进行集成则为"异质"的(heterogenous)，个体学习器此时也称为“组件学习器”(component learner)。

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对泛化性能略优于随机猜测的弱学习器weak learner尤为明显。

如何获得好的集成

高度概括：“君子和而不同”。

要获得好的集成，个体学习器应"好而不同“，个体学习器要有一定”准确性“，不能太坏（至少不差于弱学习器），并且要有"多样性"(diversity)，即学习器间具有差异。

集成个体学习器的收敛性保证

两个基本结论：

随着集成中个体分类器数目的增大，集成的错误率将指数级下降，最终趋向于零；

e=0.5的个体集成器对收敛没有作用，1-2e=0，e不能=0.5，不管<0.5还是>0.5都可以得到比较好的集成结果，如果e>0.5把模型预测错误的取反当作对的就和e<0.5一致？

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类。即个体学习器间存在强依赖关系、必须串行生成的序列化方法（代表方法：Boosting），以及个体学习器间不存在强依赖关系、可同时生成的并行化方法（代表方法：Bagging和"随机森林"(Random Forest））。

Boosting

Boosting先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器;如此重复进行，直至基学习器数目达到事先指定的值$T$，最终将这$T$个基学习器进行加权结合。

基于加性模型的Adaboost

损失函数推导

损失函数：指数函数的形式。

因为$f(x_i)$只会取$\{1,-1\}$，所以如果$f(x_i)=1$，即预测正确损失函数值为$e^{-1}$，如果$f(x_i)=-1$，即错误预测，损失函数值为$e$。这与“预测正确损失函数越小”一致。

$Ex∼D[·] $表示在概率分布 $\mathcal D$ 上的期望，可简单理解为对数据集$D$ 以概率 $\mathcal D$ 进行加权后的期望。

目标是最小化损失函数，可以通过求偏导=0的方式。

求解h

直接求偏导是不好求的，因为有很多个$h_i$连加的形式，所以用前向分布求解：每一轮只学习一个学习器$h_t$。

求解α

Adaboost流程

Boosting特点

Boosting算法要求基学习器能对特定的数据分布进行学习，可通过：

"重赋权法"(re-weighting)实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。
对无法接受带权样本的基学习算法，则可通过"重采样法"(re-sampling)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。

Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件(例如图8.3的第5行，检查当前基分类器是否是比随机猜测好)，一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。

Boosting主要关住降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

Gradient Boosting

Adaboost的损失函数为指数形式，boosting一般化的损失函数定义为以下形式：

Gradient Boosting损失函数推导

利用泰勒级数展开，因为$H_{t-1}(X)$在求解$H_t(X)$的时候是已知的，因此可以在该项处展开。

利用gradient boosting推导Adaboost

GBDT和XGBoost

注意XGBoost是大规模并行boosted tree的工具，并不是单独的算法。

Bagging

想得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立。

虽然"独立"在现实任务中无法做到，但可以设法使基学习器尽可能具有较大的差异。

方法：对训练样本进行采样，使用相互有交叠的采样子集

给定一个训练数据集，采样产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据不同，获得的基学习器可望具有比较大的差异。
为获得好的集成，同时还希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为解决这个问题，可考虑使用相互有交叠的采样子集。

Bagging基本流程

Bagging基于自助采样法(bootstrap sampling)，给定包含个样本的数据集，先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中。初始训练集中约有63.2%的样本出现在采样集中。

可采样出$T$个含$m$个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。

在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法.若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。

Bagging的特点

高效（可并行）：训练一个Bagging集成与直接在使用基学习算法训练一个学习器的复杂度同阶；
可用于很多任务：与标准AdaBoost只适用于二分类任务不间，Bagging能不经修改地用于多分类、回归等任务；
自助采样过程本，剩下约36.8%的样本可用作验证集来对泛化性能进行"包外估计"(out-o f-bag estimate) 。可使用包外样本还可用于辅助剪枝、或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理;当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。
从偏差方差分解的角度看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

随机森林

随机森林(Random Forest，简称RF) 是Bagging的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

传统决策树在选择划分属性时是在当前结点的属性集合(假定有个属性)中选择一个最优属性；

而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含$k$个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里参数$k$控制了随机性的引入程度：若令$k=d$ 基决策树的构建传统决策树相同；若令$k=1 $则是随机选择个属性用划分般情况下，推荐值$k= log_2 d$。

随机森林的特点

随机森林简单、容易实现、计算开销小。
与Bagging基学习器的"多样性"仅通过样本扰动(通过对初始训练集采样)而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终成的泛化性能可通过个体习器之间差异度的增加而进一步提升。
随着个体学习器数目增加，随机森林通常会收敛到更低的误差。
随机森林的训练效率常优于Bagging，因为在个体决策树的构建过程中Bagging 使用的是”确定型"决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的"随机型"决策树则只需考察一个属性子集。

结合策略

学习器结合的好处

统计方面；
计算方面；
表示方面。

结合策略

平均法-数值型输出

简单平均法simple averaging
加权平均法weighted averaging：对给定的基学习器，不同的集成学习方法可视为通过不同的方式来确定加权平均法中的基学习器权重。加权平均法的权重一般是从训练数据中学习而得，比如估计出个体学习器的误差，然后令权重大小与误差大小成反比。

一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。

投票法-分类任务

绝对多数投票法majority voting：若某标记得票过半数，则预测为该标记;否则拒绝预测。"拒绝预测"选项，这在可靠性要求较高的学习任务中是一个很好的机制。
相对多数投票法plurality voting：预测为得票最多的标记，若同时有多个标记获最高票，则从中随机选取一个。
加权投票法weighted voting。

如果个体学习器的输出值类型是类标记，则投票称为“硬投票”hard voting；如果输出值类型是每个类的概率（类概率），称为"软投票"soft voting。基于类概率进行结合却往往比直接基于类标记进行结合性能更好。

注意：不同类型的类概率可能不能直接混用：

对一些能在预测出类别标记的同时产生分类置信度的学习器，其分类置信度可转化为类概率使用，比如SVM的分类间隔值，需要使用一些技术比如Platt缩放、等分回归等进行“校准”后才能作为类概率使用；
若基学习器的类型不同，则其类概率值不能直接进行比较；在此种情形下，通常可将类概率输出转化为类标记输出(例如将类概率输出最大的$h_i^j(x)$设为1，其他设为0，然后再投票。