这篇博客介绍一下集成学习的几类：Bagging，Boosting以及Stacking。

传统机器学习算法 (例如：决策树，人工神经网络，支持向量机，朴素贝叶斯等) 的目标都是寻找一个最优分类器尽可能的将训练数据分开。集成学习 (Ensemble Learning) 算法的基本思想就是将多个分类器组合，从而实现一个预测效果更好的集成分类器。集成算法可以说从一方面验证了中国的一句老话：三个臭皮匠，赛过诸葛亮。

Thomas G. Dietterich 指出了集成算法在统计，计算和表示上的有效原因：

统计上的原因
一个学习算法可以理解为在一个假设空间 H 中选找到一个最好的假设。但是，当训练样本的数据量小到不够用来精确的学习到目标假设时，学习算法可以找到很多满足训练样本的分类器。所以，学习算法选择任何一个分类器都会面临一定错误分类的风险，因此将多个假设集成起来可以降低选择错误分类器的风险。
计算上的原因
很多学习算法在进行最优化搜索时很有可能陷入局部最优的错误中，因此对于学习算法而言很难得到一个全局最优的假设。事实上人工神经网络和决策树已经被证实为是一个NP 问题 3 4。集成算法可以从多个起始点进行局部搜索，从而分散陷入局部最优的风险。
表示上的原因
在多数应用场景中，假设空间 H 中的任意一个假设都无法表示 (或近似表示) 真正的分类函数 f。因此，对于不同的假设条件，通过加权的形式可以扩大假设空间，从而学习算法可以在一个无法表示或近似表示真正分类函数 f 的假设空间中找到一个逼近函数 f 的近似值。

集成算法大致可以分为：Bagging，Boosting 和 Stacking 等类型。

Bagging

Bagging是bootstrap aggregating的简写。先说一下bootstrap，bootstrap也称为自助法，它是一种有放回的抽样方法，目的为了得到统计量的分布以及置信区间。基本思想如下：

每次采用有放回的抽样从训练集中取出$n$个训练样本组成新的训练集；
利用新的训练集，训练得到$M$个子模型 $\{h_1,h_2,...,h_M\}$；
对于分类问题，采用投票的方法，得票最多子模型的分类类别为最终的类别；对于回归问题，采用简单的平均方法得到预测值。

Algorithm 1 Bagging 算法
Require:
学习算法 $L$
子模型个数 $M$
训练数据集 $T={(x1,y1),(x2,y2),...,(xN,yN)}$
Ensure:
Bagging 算法 $h_f(x)$
1: function Bagging$(L,M,T)$
2: for $m=1$ to $M$ do
3: $T_m$← boostrap sample from training set $T$
4: $h_m$←$L(T_m)$
5: end for
6: $h_f(x)$←$sign(∑_{m=1}^Mh_m(x))$
7: return hf(x)
8: end function

假设对于一个包含 $M $个样本的数据集 $T$，利用自助采样，则一个样本始终不被采用的概率是 $(1−\frac{1}{M})^M$，取极限有：

\[ \lim_{x \to \infty} \left(1 - \dfrac{1}{M}\right)^M = \dfrac{1}{e} \approx 0.368 \]

即每个学习器仅用到了训练集中 63.2% 的数据集，剩余的 36.8% 的训练集样本可以用作验证集对于学习器的泛化能力进行包外估计 (out-of-bag estimate)。

随机森林

RF和Bagging对比：

随机选择样本和Bagging相同，随机选择特征是指在树的构建中，会从样本集的特征集合中随机选择部分特征，然后再从这个子集中选择最优的属性用于划分，这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的‘平均’特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。

RF的起始性能较差，特别当只有一个基学习器时，但随着学习器数目增多，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging，因为在单个决策树的构建中，Bagging使用的是‘确定性’决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。

优缺点

优点：

训练可以高度并行化，对于大数据时代的大样本训练速度有优势，算是主要优势；
能够处理很高维的数据，并且不用特征选择，而且在训练完后，给出特征的重要性；
相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。
缺点：在噪声较大的分类或者回归问题上容易过拟合。

Boosting

Boosting 是一种提升算法，可以将弱的学习算法提升 (boost) 为强的学习算法。基本思路如下：

利用初始训练样本集训练得到一个基学习器。
提高被基学习器误分的样本的权重，使得那些被错误分类的样本在下一轮训练中可以得到更大的关注，利用调整后的样本训练得到下一个基学习器。
重复上述步骤，直至得到 $M$个学习器。
对于分类问题，采用有权重的投票方式；对于回归问题，采用加权平均得到预测值。

AdaBoost

GBDT

XGB

常用问题解答

1. RF和GBDT的区别

他们都是由多棵树组成，最终的结果都是由多棵树一起决定。而不同点主要有：

集成学习：RF属于bagging思想，而GBDT是boosting思想；
偏差-方差权衡：RF不断的降低模型的方差，而GBDT不断的降低模型的偏差；
训练样本：RF每次迭代的样本是从全部训练集中有放回抽样形成的，而GBDT每次使用全部样本；
并行性：RF的树可以并行生成，而GBDT只能顺序生成(需要等上一棵树完全生成)；
最终结果：RF最终是多棵树进行多数表决（回归问题是取平均），而GBDT是加权融合；
数据敏感性：RF对异常值不敏感，而GBDT对异常值比较敏感；
泛化能力：RF不易过拟合，而GBDT容易过拟合。

2. XGBoost与GBDT有什么不同

基分类器：XGBoost的基分类器不仅支持CART决策树，还支持线性分类器，此时XGBoost相当于带L1和L2正则化项的Logistic回归（分类问题）或者线性回归（回归问题）；
导数信息：XGBoost对损失函数做了二阶泰勒展开，GBDT只用了一阶导数信息，并且XGBoost还支持自定义损失函数，只要损失函数一阶、二阶可导；
正则项：XGBoost的目标函数加了正则项，相当于预剪枝，使得学习出来的模型更加不容易过拟合；
列抽样和缩减：XGBoost支持列采样，与随机森林类似，同时对每棵树输出使用shrinkage，都是用于防止过拟合；
缺失值处理：对树中的每个非叶子结点，XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支；
并行化：注意不是tree维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度；
可并行的近似直方图算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

3. XGBoost为什么使用泰勒二阶展开

精准性：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，阶信息本身就能让梯度收敛更快更准确。这一点在优化算法里的牛顿法里已经证实了。可以简单认为一阶导指引梯度方向，二阶导指引梯度方向如何变化。
可扩展性：Xgboost官网上有说，当目标函数是MSE时，展开是一阶项（残差）+二阶项的形式（官网说这是一个nice form），而其他目标函数，如logloss的展开式就没有这样的形式。为了能有个统一的形式，所以采用泰勒展开来得到二阶项，这样就能把MSE推导的那套直接复用到其他自定义损失函数上。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。

4.XGBoost为什么快

分块并行：训练前每个特征按特征值进行排序并存储为Block结构，后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点；
候选分位点：每个特征采用常数个分位点作为候选分割点；
CPU cache 命中优化：使用缓存预取的方法，对每个线程分配一个连续的buffer，读取每个block中样本的梯度信息并存入连续的Buffer中;
Block 处理优化：Block预先放入内存；Block按列进行解压缩；将Block划分到不同硬盘来提高吞吐

5. XGBoost防止过拟合的方法

目标函数添加正则项：叶子节点个数+叶子节点权重的L2正则化；
列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）；
子采样：每轮计算可以不使用全部样本，使算法更加保守；
shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间；
剪枝：多种方式限制树的复杂度

Stacking

Stacking 本身是一种集成学习方法，同时也是一种模型组合策略，我们首先介绍一些相对简单的模型组合策略：平均法 和 投票法。

对于 数值型的输出 $h_i(x)∈R$，

简单平均法 (Simple Averaging)
加权平均法 (Weighted Averaging)
绝对多数投票法 (Majority Voting)
相对多数投票法 (Plurality Voting)
加权投票法（Weighted Voting)

Stacking 算法过程如下：

次级学习器的训练集是有初级学习器产生的，如果直接利用初级学习器的训练集生成次级学习器的训练集，过拟合风险会比较大。因此，一般利用在训练初级学习器中未使用过的样本来生成次级学习器的训练样本。以 k 折交叉检验为例：初始的训练集 T 被随机划分为 k 个大小相近的集合 $T_1,T_2,...,T_k$。令 $T_j $和$ T¯_j=T∖T_j $表示第 j 折的测试集和训练集。则对于 M 个初级学习算法，学习器$ h_m(j) $是根据训练集 $T¯_j $生成的，对于测试集 $T_j $中的每个样本 $x_i$，得到 $z_{im}=h_m(j)(x_i)$。则根据 $x_i $所产生的次级学习器的训练样本为 $z_i=((z_{i1},z_{i2},...,z_{iM}),y_i)$。最终利用 M 个初级学习器产生的训练集 $T^′={(z_i,y_i)}_{i=1}^N$ 训练次级学习器。

下图展示了一些基础分类器以及 Soft Voting 和 Stacking 两种融合策略的模型在 Iris 数据集分类任务上的决策区域。数据选取 Iris 数据集中的 Sepal Length 和 Petal Length 两个特征，Stacking 中的次级学习器选择 Logistic Regression，详细实现请参见这里。

Reference

集成学习算法 (Ensemble Learning)