【读书摘要】集成学习

An overview of ensemble methods in machine learning

为了得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立。尽管“独立”在现实任务中无法做到，但可以设法使得基学习器尽可能有较大的差异。事实上，个体学习器的“准确性”和“多样性”本身就存在冲突。一般的，准确性很高之后，要增加多样性就需要牺牲准确性。所以，如何产生并结合“好而不同”的个体学习器是集成学习研究的核心。

1. 生成个体学习器

根据个体学习器的生成方式，目前的集成学习方法大致可以分为两大类：1. 个体学习器间存在强依赖关系、必须串行生成的序列化方法，其代表是Boosting；2. 个体学习器间不存在强依赖关系、可同时生成的并行化方法，其代表是Bagging和Random Forest。

1.1 串行化方法——Boosting

Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始化训练集出一个基学习器，再根据基学习器的表现对训练样本分布进行调整 ，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合.

从偏差-方差分解的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

1.2 并行化方法——Bagging和随机森林

1.2.1 Bagging

Bootstrap，名字来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，是一种有放回的抽样方法，它是非参数统计中一种重要的估计统计量方差进而进行区间估计的统计方法。其核心思想和基本步骤如下：

1. 采用重抽样技术从原始样本中抽取一定数量（自己给定）的样本，此过程允许重复抽样。
2. 根据抽出的样本计算给定的统计量S
3. 重复上述N次（一般大于1000），得到N个统计量S
4. 计算上述N个统计量S的样本方差，得到统计量的方差

应该说Bootstrap是现代统计学较为流行的一种统计方法。在小样本时效果很好。通过方差的估计可以构造置信区间等，其运用范围得到进一步延伸。

还有一种抽样方法Jackknife，和Bootstrap功能类似，只是有一点细节不一样，即每次从样本中抽样时候只是去除几个样本（而不是抽样），就像小刀一样割去一部分。

Bagging，是由bootstrap aggregating缩写而成，是并行式集成学习方法最著名的代表。给定包含m个样本的数据集，采用有放回抽样的方式，得到含m个样本的采样集，初始训练集中有的样本在采样集中多次出现，有的则从未出现。如此可采样出T个包含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。这就是Bagging的基本流程。

从偏差-方差分解的角度看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

1.2.2 随机森林

随机森林（Random Forest，简称RF）是Bagging的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，传统决策树在选择划分属性时是在当前节点的属性集合（假定有d个属性）中选择一个最优属性；而在RF中，对基决策树的每个节点，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度：若令$k=d$，则基决策树的构建与传统决策树相同；若令$k=1$，则是随机选择一个属性用于划分；一般情况下，推荐值$k=log_2d$。

2. 结合策略

假定集成包含T个基学习器$\left { h_1, h_2, h_3, …, h_T \right }$，其中$h_i$在示例x上的输出为$h_i(x)$。

2.1 平均法

• 简单平均法 $$H(x)=\frac{1} {T} \sum_{i=1}^T h_i(x)$$
• 加权平均法 $$H(x) = \sum_{i=1}^T \omega_i h_i(x)$$ 其中$\omegai$是个体学习器$h_i$的权重，通常要求$\omega_i\geq 0, \sum{i=1}^T \omega_i =1$.

一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。加权平均法的权重一般是从训练数据中学习而得，比如估计出个体学习器的误差，然后令权重大小与误差大小成反比，现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠。

2.2 投票法

对分类任务来说，学习器将从类别标记集合${c_1, c_2, c_3, …, c_N}$中预测出一个标记，最常见的结合策略是使用投票法。将h_i在样本x上的预测输出表示为一个N维向量$(h_i^1(x); h_i^2(x); …; h_i^N(x))$，其中$h_i^j(x)$是$h_i$在类别标记$c_j$上的输出。

• 绝对多数投票法 $$H(x)=\left\{\begin{matrix} c_j, & if \sum_{i=1}^Th_i^j(x)>0.5\sum_{k=1}^N \sum_{i=1}^T h_i^k(x); \\ reject, & otherwise. \end{matrix}\right.$$ 即若某标记得票过半数，则预测为该标记；否则拒绝预测。
• 相对多数投票法 $$H(x)=c_{arg_jmax\sum_{i=1}^Th_i^j(x)}$$
• 加权投票法 $$H(x)=c_{arg_jmax\sum_{i=1}^T \omega_i h_i^j(x)}$$ $\omegai$是$h_i$的权重，通常要求$\omega_i\geq 0, \sum{i=1}^T \omega_i =1$.

在现实任务中，不同类型个体学习器可能产生不同类型的$h_i^j(x)$值，而不同类型的$h_i^j(x)$值不能混用。

2.3 学习法

当训练数据很多时，可以通过另一个学习器来进行结合，从而形成一种更强大的结合策略。Stacking是学习法的典型代表。Stacking本身是一种注明的集成学习方法，且有不少集成学习算法可视为其变体或特例。此处，将其看作一种特殊的结合策略。
Stacking先从初始数据集训练出初级学习器，然后 “生成”一个新数据集用用训练刺激学习器。在这个心数据集中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当做样例标记。