集成学习小结

Feb 27, 2021

集成学习主要有两个思路，Bagging和Boosting。

Bagging

独立训练（可并行）多个基分类器，使用投票法或者平均法集成所有基分类器的结果。

bagging的目标是为了减小方差。

典型算法：RandomForest
Boosting

为每个样本赋一个相同的权重，在一次迭代中，一个基模型对样本的估计有对有错，对于分错的样本，增加其权重，分对的样本，则减少其权重。在进行N次迭代后，得到N个简单的分类器（basic learner），将这些分类器通过权重进行组合，即是boosting模型（方法）。

典型算法：Adaboost、GBDT、XGBoost、LightGBM、CatBoost

下文对上述Boosting和Bagging典型算法的思想、实现方式和优缺点进行总结对比。

一、RandomForest

RF是bagging的扩展，以CART为基学习器，学习过程为：

随机选择样本（有放回抽样）

随机选择样本是bagging的特点
随机选择特征

仅选择$\sqrt{n}$个特征进行决策树的生成（会一定程度上增大偏差），多棵决策树会使得RF的方差降低
构建决策树

构建决策树时，每棵决策树都最大可能的进行生成而不进行剪枝。

多个决策树投票/平均：
- 分类：简单投票法
- 回归：简单平均

优点：

模型方差小，预测准确性高
树构建可并行化，无需剪枝，大数据集、特征数量大时依然适用
无需特征选择，可以给出特征重要性

缺点：

容易过拟合
取值划分较多的属性对RF的影响更大，这种属性权重并不可靠

RF的重要特性是不用对其进行交叉验证或者使用一个独立的测试集获得无偏估计，RF在生成的过程中可以对误差进行无偏估计，由于每个基学习器仅使用了训练集中约63.2%的样本，剩下约36.8%的样本可用做验证集来对模型的泛化能力进行袋外估计。

二、Adaboost

Adaboost的学习过程：

初始化样本权重（$N$个样本：每个样本权重$\frac{1}{N}$），抽样得到一批样本，训练第一个基分类器
计算上一个基分类器的错误率，记为$\epsilon$，通过其计算出基分类器的权重：$\alpha=\frac{1}{2}\ln\frac{1-\epsilon}{\epsilon}$
根据基分类器的分类结果调整样本的权重，正确分类的样本降低权重，错误分类的增加权重。（权重越大，表示分类难度越大）（通过此种方式，使得后续的基分类器更关注分错的样本）
循环执行2～3步，直至误差小于某一个阈值或分类器个数达到上限

优点：

对弱分类器进行级联，提高模型精度
可以使用多样的基分类器

缺点：

基分类器数量不好确定（需要通过交叉验证确定）
对不平衡数据的分类效果不佳
训练比较耗时

三、GBDT（Gradient Boost Decision Tree）

一般的boosting算法关注每一轮迭代中的正/误样本的权重，而GBDT的每一次迭代都是为了减少上一次迭代的残差（通过在残差减小的梯度方向上建立模型），即利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树，GBDT会累加所有（回归）树的结果。

GBDT的执行流程：

使用训练样本训练第一个弱分类器，并将模型结果与真实结果进行比较，得到模型的残差
使用上一步骤中得到的残差训练下一个分类器，再次比较结果，计算残差
循环执行1～2步，直至残差小于某一个阈值或分类器个数达到上限

优点：

可以处理各种类型的数据
调参时间较少的情况下能够获得较高的准确度、泛化能力强

缺点：

高维稀疏数据集上的表现不如支持向量机和神经网络、文本特征的处理能力弱于数值特征
基于boosting思想，需要串行训练，只能在决策树内部进行一些局部的并行化手段

四、XGBoost

XGBoost基于GBDT，可以处理分类任务，也可以处理回归任务。与GBDT的最大区别是，XGBoost对目标函数进行二阶泰勒展开，从而求出下一步需要拟合的树的叶子结点的权重。

XGBoost与GBDT的区别：

GBDT是机器学习算法，而XGBoost是GBDT的一种实现
在使用CART作为基分类器时，XGB加入了正则项（树的叶子结点个数、每个叶子结点上输出的分数的L2范数的平方和）来控制模型的复杂度，防止过拟合
GBDT训练时仅使用了代价函数的一阶导数，XGB使用了一阶和二阶导数（xgboost支持自定义代价函数（二阶可导即可））
在XGB中有一个Shrinkage操作，对应到XGB实现中的eta参数，在进行一轮迭代后，将叶子结点上的权重乘以该系数，来削弱当前基分类器的影响，增大后续的学习空间（实际操作中，eta设置的小一点，迭代次数可以稍微设置大一些）
XGB使用列抽样技术（column sampling），能够在减少计算的同时，减弱过拟合倾向
GBDT对缺失值没有处理，XGB能够自动学习缺失值的处理方法
XGB支持决策树构建级别的并行化，在决策树学习过程中，确定最优分割点时，需要对特征的取值进行排序，XGB在训练之前对数据作了预排序并保存为block结构，在后续的训练过程中复用此结构，另外，在进行结点分裂时，计算各个特征的增益也可以使用多线程并行进行
GBDT使用CART作为基分类器，XGB支持多种类型的基分类器
GBDT每次迭代使用全部数据，XGB使用自助法抽样数据

优点：

计算效率高，使用二阶导数
缺点：每次迭代需要遍历整个数据集，内存占用大

五、LightGBM

LGB是一个实现了GBDT算法的高效的分布式框架。

降低训练复杂度可以从两个角度入手（在尽可能保证精度的前提下）：减少特征、减少数据量，在LightGBM中，对应的手段是GOSS和EFB。

GOSS（Gradient-based One-side Sampling）

训练过程中，每个数据实例拥有不同的梯度，梯度大的实例对信息增益的影响更大，因此，在下采样时应尽可能保留梯度大的样本（通过阈值或百分比来限制），随机去掉梯度小的样本。这个技术能够获得比随机采样更精确的的结果。
EFB（Exclusive Feature Bundling）

在实际应用中，特征之间可能存在着互斥的情况，EFB对互斥特征进行绑定，将绑定问题约束到图着色问题，通过贪心算法求近似解，通过此种方式减少了特征的数量。

LightGBM与XGBoost的区别：

内存方面：在计算分类特征的增益时，XGB使用预排序法（pre-sorted）处理节点分类（比较精确，但时间开销比较大）；LGB使用基于histogram的决策树算法，节省了内存占用（～$\frac{1}{8} \cdot$pre-sorted算法）
效率方面：决策树算法的主要操作有两个：分割点寻找和数据分割，在第一个操作上，pre-sorted和histogram算法的时间复杂度是一样的，在数据分割操作上，histogram比pre-sorted要快（histogram中，所有特征共享一个索引，而pre-sorted中，每个特征对应一个索引），此外，histogram还减少了计算分割点增益的次数
通信方面：histogram的通信代价远小于pre-sorted，适用于分布式计算
XGB的生成策略是level-wise（不容易过拟合，但效率低，在分裂时，部分增益小的树也进行了增长），LGB使用leaf-wise（高效，但容易生成深度过大的树，从而导致过拟合，因此需要限制最大深度）
训练精度方面：histogram由于无法找到精确的分割点，与pre-sorted相比，相当于通过牺牲精度来换取效率

六、CatBoost（Category Boosting）

CatBoost是以对称决策树为基学习器的GBDT框架，能够高效地处理类别型特征，此外，CatBoost还解决了梯度偏差（Graident Bias）和预测偏移（Prediction Shift）的问题，能够减弱过拟合现象，提高预测准确性。

CatBoost的学习算法基于GPU实现，打分算法基于CPU实现。

CatBoost相对于XGB和LGB的改进：

能够自动采用特殊方式处理类别型特征
对类别特征进行组合，丰富了特征种类
基模型采用对称树
使用排序提升的方法对抗训练集中的噪声点，从而避免梯度估计的偏差，解决了预测偏移的问题

CatBoost如何处理类别特征（categorical features）

对数据做一些统计，计算某个category出现的频率，再加上一些超参数，生成新的数值型特征
对数据进行若干种排列，在每一轮建树之前，随机选择一种数据排列来生成树
对category特征进行组合，在组合数量过大时，CatBoost通过贪心算法选择来选择最好的一部分组合

优点：

性能强，可以匹敌任何先进的机器学习算法
鲁棒性高，减少了超参数调整的需求，降低了过拟合的风险，模型的泛用性更强
实用性强：体现在可以自动处理数值特征和类别特征
可扩展：支持自定义loss函数

缺点：

对类别特征的处理对时间和空间的需求比较大
模型随机种子的设定会影响模型的预测结果

Shihanmax's blog