选择性集成，即集成剪枝（Ensemble Pruning），即从一堆基学习器（base learners）中选择一个子集，希望泛化性能（Generalization Performance）越好的同时，子集大小越小。
先前的研究通常使用验证集上的误差（Validation Error）来估计泛化性能，但最近的理论研究显示间隔分布（Margin Distribution）对泛化性能也很重要。
因此本文将使用多目标的演化学习算法，同时优化这三个目标：验证误差（Validation Error）、间隔分布（Margin Distribution）以及集成大小（Ensemble Size）。
领域介绍
集成剪枝方法通常可以划分为两大类：
- 基于排序的剪枝（Ordering-Based Pruning）
- 通常基于贪心策略，迭代式挑选，每次选取一个能使特定指标最大的基学习器；
- 常见的选取指标有：最小化验证误差（Validation Error），最大化学习器多样性（Diversity），最大化互补性（Complementarity），以及多项指标的组合；
- 基于优化的剪枝（Optimization-Based Pruning）
- 通常将集成剪枝形式化为优化问题，并使用演化算法（Evolutionary Algorithms, EAs）来寻找最优子集；
- 一开始的单目标建模（验证误差）[AIJ02] 虽然测试误差较小（Competitive with Ordering-Based Pruning），但集成大小（Ensemble Size）很大；
- 后续的双目标建模（验证误差 + 集成大小）[AAAI15]，提出了 Pareto Ensemble Pruning (PEP) 方法，同时在「测试误差」和「集成大小」两方面超越了之前的方法。
近期关于间隔的研究 [AIJ13] 指出间隔分布对泛化性能有很大影响，因此本文提出了 Margin Distribution guided multi-objective evolutionary Ensemble Pruning (MDEP) 方法，同时最小化验证误差（Validation Error）、间隔比例（Margin Ratio）以及集成大小（Ensemble Size）。
本文测试了三种多目标演化算法（Multi-Objective EAs, MOEAs）来求解上述问题，分别是：NSGA-II [TEC02]、MOEA / D [TEC07] 以及 NSGA-III [TEC13]，在实验中使用 NSGA-III 性能更好。
MDEP 方法
优化目标
如上所述，本文同时优化如下三个目标：
其中 $\boldsymbol{s}$ 表示每个基学习器选（$s_i=1$）或者不选（$s_i=0$），$D=\{(\boldsymbol{x}_i,y_i)\}_{i=1}^m$ 表示验证集，$\operatorname{error}_D(H_{\boldsymbol{s}})$ 表示学习器子集直接 Voting 的误差：
另外 $\rho_D^{\text {ratio}}\left(H_{\boldsymbol{s}}\right)$ 表示选择性集成后的模型，在验证集 $D$ 上的间隔比例（间隔方差 / 间隔均值）：
其中 $\rho_{H_{\boldsymbol{s}}}(\boldsymbol{x}_i,y_i)$ 表示 Pruned Ensemble $H_{\boldsymbol{s}}$ 在 $(\boldsymbol{x}_i,y_i)$ 上的间隔：
优化算法
上述目标可通过 Multi-objective Evolutionary Algorithms 进行解决，本文给出了大致的算法框架：
/image-1.png)
其中 5、6 两步取决于具体的演化学习算法；uniform crossover operator 即 offspring solution 中每个 bit 独立，且 1/2 的概率从 the first parent solution (from line 5) 继承，1/2 的概率从 the second parent solution (from line 5) 继承；bit-wise mutation operator 即每个 bit 独立，且 1/n 的概率翻转。
最终在 solution 集合中选取 validation error 最小的结果，第二关键字是 ensemble size。