目录
Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。
| 论文概况 | 详细 |
|---|---|
| 标题 | 《Mixed Bagging: A Novel Ensemble Learning Framework for Supervised Classification based on Instance Hardness》 |
| 作者 | Ahmedul Kabir, Carolina Ruiz, Sergio A. Alvarez |
| 发表期刊 | IEEE International Conference on Data Mining |
| 发表年份 | 2018 |
| 期刊等级 | CCF-B |
| 论文代码 | https://github.com/KabirRuizAlvarez/Mixed-bagging |
作者单位：
- Department of Computer Science Worcester Polytechnic Institute Worcester, MA, USA
- Department of Computer Science Boston College Chestnut Hill, MA, USA
研究动机
Bagging 是广泛使用的集成学习技术之一，Bagging 中的每个集学习器都是从一个 bootstrap 子集中学习的。本文的思想是使用不均匀的概率分布进行抽样，而是通过样本硬度函数得到，以此来优化 Bagging 的预测性能。
文章贡献
本文提出了一种名为 Mixed Bagging 的 Bagging 框架，其中 bootstrap 得到的数据子集具有不同程度的硬度。这样的混合 bootstrap 将诱导出一组更加多样化的基学习器，且这样的分类器的集合在总体分类任务中更够提高对难分样本的关注。Mixed Bagging 框架中考虑了两种不同的方法，第一种分组混合 Bagging 有三组 bootstrap 的混合部分，分别是 easy、regular、hard。在第二种增量混合 Bagging 的设置中，bootstrap 的硬度是迭代变化的。在 47 个公开的二分类问题上对这两种 Mixed Bagging 方法进行测试，结果验证了本文提出的方法在总体上比对比算法的预测性能好得多。
本文方法
分组混合 Bagging
第一个提出的混合 Bagging 技术有三组 bootstraps：
| bootstrap | 说明 |
|---|---|
| easy | 难分样本的表示不足 |
| regular | 每个样本具有相同的表示概率(与传统 Bagging 相同) |
| hard | 难分样本的表示过多 |
对于 GrpMixBag 引入了两个新的超参数：过采样系数 OC 和混合比率 MR 。OC是一个非负实数，用于控制硬度对实例权重的影响程度，它决定了应该给哪些需要过度表达的样本多大的权重。bootstrap 的权重分配如下公式所示，其中 wi 为样本 i 的权重，IHi 为样本 i 的硬度，OC 为过采样系数。由公式(1)可知由于 IHi 的值的范围是 0~1，wi 的取值范围介于 1~(1+OC) 之间。
第二个超参数混合比率 MR 用于控制不同类别 bootstrap 的比例，在本文中使用 [E, R, H] 的格式表示混合比率，其中 E 代表 easy bootstrap 的分数，R 代表 regular bootstrap 的分数，H 代表 hard bootstrap 的分数，并满足 E+R+H=1。当 MR 为 [0, 1, 0] 时相当于传统的 Bagging，因此 Bagging 可以看作是分组混合 Bagging 的特例。
GrpMixBag 通过构造指定数量的 easy、hard 和 regular bootstrap，根据 OC 进行采样。该过程如下伪代码所示，可以进行网格搜索或其他超参数优化方法来设置最优的 MR 和 OC。
增量混合 Bagging
第二种变体的特点是每个 bootstrap 的硬度在一个连续的间隔上平滑地变化，该方法为增量混合 Bagging(IncMixBag)。首先定义一个实数变量：Bootstrap 硬度 BH，其符号表示 Bootstrap 是 easy(<0) 还是 hard(>0)，其大小表示在较容易或较困难的样本上完成的过采样量。一个 bootstrap 的样本权重用公式(2)表示，其中 wi 为样本 i 的权重，IHi 为样本 i 的硬度，BHb 为 bootstrap b 的硬度。由于 IHi 取值与 0~1，则 wi 的取值范围在 1~(1+abs(BHb)) 之间。
增量混合 Bagging 只使用 Bootstrap 硬度区间 BHI，该参数是一个连续的区间 [L, U]。IncMixBag 的整体流程如下伪代码所示，它通过迭代构造 T 个 bootstrap 来执行，这些 bootstrap 的 BH 值在 [L, U] 范围内增量变化。传统的 Bagging 对应 BHI =[0.0, 0.0]，是 IncMixBag 的特殊情况。
实验结果
本文方法的设置
本文使用的计算硬度 IH 的方法是将每个样本的 IH 估计为预先选择的错误分类器集集成的一部分，使用了 5×10 折的交叉验证方法来进行 IH 近似。为了保证 IH 的简单性和多样性，选择了逻辑回归(LR)、C4.5 决策树(DT)、KNN 和高斯贝叶斯(NB)，可以通过删除或添加分类算法来任意地减小或增大集合。
对于本文提出的两种混合 Bagging 方法，考虑如下三种类型的 bootstraps 组合，对于过采样系数 OC 尝试 1.0、2.0、3.0 几个值。
| bootstraps 组合 | 说明 | 详细设置 |
|---|---|---|
| symmetric | 等量的 easy 和 regular bootstraps | [0.1,0.8,0.1]、[0.2,0.6,0.2]、[0.0,1.0,0.0] |
| easy-oriented | easy bootstraps 比 hard bootstraps 更多 | [0.4,0.4,0.2]、[0.3,0.6,0.1]、[0.2,0.7,0.1]、[0.2,0.8,0.0]、[0.3,0.7,0.0] |
| hard-oriented | hard bootstraps 比 easy bootstraps 更多 | [0.2,0.4,0.4]、[0.1,0.6,0.3]、[0.1,0.7,0.2]、[0.0,0.8,0.2]、[0.0,0.7,0.3] |
数据集和实验设置
实验使用 32 个具有二分类数据集和 5 个三分类数据集，通过 OVO 将每个数据集分成 3 个二分类问题。实验指标使用 Accuracy 和 AUC，通过 10×5 折交叉验证方法，每种 Bagging 方法使用了 10 个 bootstrap。使用 5×5 折交叉验证在训练时使用验证集来选择最佳超参数，对于每个分类任务使用 Wilcoxon 符号秩检验对性能进行验证。
对比实验
将提出的混合 Bagging 方法与基学习器、Bagging、waging、AdaBoost 进行比较，使用 3 种基于决策树的学习器，实验结果如下表所示。对于 decision stump 基学习器，AdaBoost 优于本文的混合 Bagging 方法，但混合 Bagging 方法比 Bagging 要好得多。当基学习器为 depth≤5 的决策树时，混合 Bagging 方法总体上优于其他方法。
下表给出了综合性能的结果，可见 AdaBoost 在最多数量的数据集上实现了最高的准确性，但在很多数据集中的性能却是最差的。GrpMixBag 或 IncMixBag 在大约三分之一的数据集上达到最佳精度，总体性能优于用于对比的算法。
接着对所有方法的误差进行了偏差-方差分解，结果如下表所示。可见 AdaBoost 能够在许多数据集中减少基学习器的偏差，但只能在少数数据集中减少方差。混合 Bagging 能够在许多数据集减少偏差和方差。
优点和创新点
个人认为，本文有如下一些优点和创新点可供参考学习：
- 相比于原始 Bagging 的 bootstrap 是随机抽样得到的，本文提出的 Mixed Bagging 通过样本硬度函数作为抽样的概率分布，可以让 Bagging 具备关注困难样本的能力，有助于提高基学习器的多样性和预测性能；
- GrpMixBag 通过过采样系数和混合比率，能够灵活地改变 bootstrap 中 easy、hard、regular 不同类型的样本比例。IncMixBag 则是可以得到一组迭代变化整体硬度的 bootstrap，这两种思路在其他工作的改进中都值得考虑。