集成学习

1、个体与集成

集成学习(ensemble learning)通过构建并集合多个学习器完成学习任务，有时也被称为多分类器系统(multi-classifier system)、基于委员会的学习(committee based learning)等。先产生一组“个体学习器”(invidual learner)，再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据中产生，例如C4.5决策树、BP神经网络算法等，此时集成中只包含同种类型的个体学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是“同质”的(homogeneous)。同质集成中的个体学习器亦称为“基学习器”(base learner)，相应的算法称为“基学习算法”(base learning algorithm)。集成也包含不同类型的个体学习器。例如同时包含决策树和神经网络，这样的集成是“异质”的(heterogeneous)。异质集成中的个体学习器由不同的学习算法生成，这时就不再有学习算法；相应的，个体学习器一般不称为学习器，常称为“组件学习器”(component learner)或直接称为个体学习器。

集成学习通过将多个学习器进行组合，常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”(weak learner)尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器有时也直接称为弱学习器。但需注意的是，虽然理论上来说使用弱学习器集成足以获得好的性能，但在实践中出于种种考虑，例如希望使用较少的个体学习器，或是重用关于常见学习器的一些经验等，人们往往会使用比较强的学习器。

在一般经验中，如果把好坏不等的东西掺到一起，那么通常结果会是比最坏的要好一些，比最好的要坏一些。集成学习把多个学习器结合起来，如何能获得比最好的单一学习器更好的性能呢？要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，即学习器不能太坏，并且要有“多样性”(diversity)，即学习器具有差异。

我们来做一个简单的分析，考虑二分类问题y \in\{-1,+1\} 和真实函数f ，假定基分类器的错误率为\epsilon ，即对每个基分类器器h_i 有P\left(h_{i}(x) \neq f(x)\right)=\epsilon 假设集成通过简单投票结合T个基分类器，若有超过半数的基分类器正确，则集成分类就正确H(x)=\operatorname{sign}\left(\sum_{i=1}^{T} h_{i}(x)\right)

假设基分类器错误率相互独立，则由Hoeffiding不等式可知，集成的错误率为

上式显示出，随着集成中个体分类器数目T的增大，集成的错误率将指数级下降，最终趋向于零。然而我们必须注意到，上面的分析有一个关键假设：学习器的误差相互独立，在现实任务中，个体学习器是为解决同一问题训练出来的，它们显然不可能相互独立！事实上，个体学习器的“准确性”和“多样性”本身就不存在冲突。一般的，准确性很高之后，要增加多样性就需牺牲准确性。事实上，如何产生并结合“好而不同”的个体学习器，恰是集成学习的核心。根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即个体学习器存在强依赖关系，必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表是Boosting后者的代表是Bagging和“随机森林”(Random Forest)。

2、Boosting

Boosting是一族可将若学习器提升为强学习器的算法，这族算法的工作机制类似：先从初始训练集训练出一个学习器，再根据基学习器的表现对训练样本进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器，如此重复进行，直至学习器数目达到事先指定的值T，最终将这个T个基学习器进行加权结合。Boosting族算法最著名的代表是AdaBoost，如下所示，其中y \in\{-1,+1\} ，f 是真实函数。

输入：训练集D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{m}, y_{m}\right)\right\} ; 基学习算法\Im ; 训练轮数T。 过程：D_{1}(x)=1 / m for t = 1,2,...,T do

h_{t}=\Im\left(D, D_{t}\right); \epsilon_{t}=P_{x \sim D_{t}}\left(h_{t}(x) \neq f(x)\right)

if \epsilon_{t}>0.5

then break \alpha_{t}=\frac{1}{2} \ln \left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)

D_{t+1}(x)=\frac{D_{t}(x)}{Z_{t}} \times\left\{\begin{array}{cl} \exp \left(-\alpha_{t}\right), & \text { ifht }(x)=f(x) \\ \exp \left(\alpha_{t}\right), & \text { ifht }(x) \neq f(x) \end{array}=\frac{D_{t}(x) \exp \left(-\alpha_{t} f(x) h_{t}(x)\right)}{Z_{t}}\right.

end for 输出：

H(x)=\operatorname{sign}\left(\sum_{t=1}^{T} \alpha_{t} h_{t}(x)\right)

若H(x)能令指数损失函数最小化，则考虑对H(x)的偏导

\frac{\partial l_{e x p}(H \mid D)}{\partial H(x)}=-e^{H(x)} P(f(x)=1 \mid x)+e^{H(x)} P(f(x)=-1 \mid x)

令上式为零可解得

H(x)=\frac{1}{2} \ln \frac{P(f(x)=1 \mid x)}{P(f(x)=-1 \mid x)}

因此，有

\operatorname{sign}(H(x))=\operatorname{sign}\left(\frac{1}{2} \ln \frac{P(f(x)=1 \mid x)}{P(f(x)=-1 \mid x)}\right)=\left\{\begin{array}{c} 1, P(f(x)=1 \mid x)>P(f(x)=-1 \mid x) \\ -1, P(f(x)=1 \mid x)<P(f(x)=-1 \mid x) \end{array}\right.

这意味着sign(H(x))达到了贝叶斯最优错误率。换言之，有指数损失函数最小化，则分类错误率也将最小化；这说明指数损失是分类任务原本0/1损失函数的一致性(consistent)替代损失函数。由于这个替代函数有更好的数学性质，例如它是连续可微函数，因此我们用它代替0/1损失函数作为优化目标。在AdaBoost算法中，第一个分类器h_1 是通过直接将学习算法用于初始数据分布而得；此后迭代地生成h_t 和\alpha_t ，当基分类器h_t 基于分布D_t 产生后，该基分类器的权重\alpha_t 应使得\alpha_t h_t

最小化指数损失函数：

其中\epsilon_{t}=P_{x \sim D_{t}}\left(h_{t}(x) \neq f(x)\right) ，考虑指数损失函数的导数:

令上式为零可解得

这恰是上面算法中第6行的分类器权重更新公式。

AdaBoost算法在获得H_{t-1} 之后样本分布将进行调整，使下一轮学习器h_t 能纠正H_{t-1} 的一些错误。理想的h_t 能纠正H_{t-1}

的全部错误，即最小化：

注意到f^{2}(x)=h_{t}^{2}=1 ，上式可使用e^{-f(x) h_{t}(x)} 的泰勒展开式近似为：

于是理想的学习器：

注意到E_{x \sim D}\left[e^{-f(x) H_{t-1}(x)}\right] 是一个常数，令D_t 表示一个分布：

根据指数期望的定义这等价于令：

由f(x), h(x) \in\{-1,+1\} ，有

则理想的基学习器

h_t将在分布D_t 下最小化分类误差，因此，弱分类器将基于分布D_t 来训练，且针对D_t 的分类误差应小于0.5。这在一定程度上类似“残差逼近”的思想，考虑到D_t 和D_{t+1} 的关系，有

Boosting算法要求基学习器能对特定的数据分布进行分布，这可通过“重赋权法”(re-weighting)实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋值一个权重。对无法接受带权样本的基学习算法，则可以通过“重采样法”(re-samping)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再通过重采样而得到的样本集对基学习器进行训练。一般而言，这两种做法没有显著的优劣差别。需注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件，一旦条件不满足，则当前学习器即被抛弃，且学习过程停止。在此种情形下，初始设置的学习轮数T也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。若采用“重采样法”，则可获得“重启动”机会以避免训练过程早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出学习器，从而使得学习过程可以持续到预设的T轮完成。

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

3、Bagging

欲得到泛化性能很强的集成，集成中的个体学习器应该尽可能相互独立；虽然“独立”在现实任务中无法做到，但可以设法使基学习器尽可能具有较大的差异，给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干不同的子集，再从每个数据子集中训练出一个基学习器。这样由于训练数据的不同，我们获得的基学习器可望具有比较大的差异。然而，未获得好的集成，我们同时还希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为解决这个问题，我们可考虑使用相互有交叠的采样子集。

Bagging是并行式集成学习方法最显著的代表。从名字即可看出，它直接基于自助采样法(bootstrap sampling)给定包含m个样本的数据集。我们先随机取出一个样本放入采样集中，再把该样本放回初始初始数据集，使得下次采样时该样本仍可能被选中，这样，经过m次随机采样操作，我们得到含m个样本的采样集，初始训练集中有的样本在采样集中出现多次，有的则从未出现。

照这样，我们可采样出T个含m个训练样本的采样集训练出一个基学习器，再将这些基学习器进行结合。这就是Bagging的基本流程。在对预测输出进行进行结合时，Bagging通常对象分类任务是用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可以进一步考察学习器投票的置信度来确定最终胜者，Bagging的算法描述下图所示。

输入：训练集

D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{m}, y_{m}\right)\right\}

基学习算法\Im ; 训练轮数T. 过程： for t = 1,2,..,T do

h_{t}=\Im\left(D, D_{b s}\right) end for 输出：

\underset{y \in Y}{\arg \min } \sum_{i=1}^{T} I\left(h_{t}(x)=y\right)

假定基学习器的计算复杂度为O(m)，则Bagging的复杂度大致为T(O(m)+O(s))。考虑到采样与投票/平均过程的复杂度O(s)很小，而T通常是一个不太大的常数，因此训练一个Bagging集成与直接使用基学习算法训练一个学习器的复杂度同阶，这说明Bagging是一个很高效的集成学习算法。另外，与标准AdaBoost只适用于二分类不同，Bagging能不经修改地用于多分类、回归任务。

值得一提的是，自助采样过程还给Bagging带来了另一个优点：由于每个基学习器只使用了初始训练集中的63.2%的样本，剩下的月36.8%的样本可用作验证集来对泛化性能进行“包外估计”。为此需记录每个基学习器所使用的训练样本，不妨令D_t 表示h_t 实际使用的训练样本集。令H^{o o b}(x) 表示样本x的包外预测，即仅考虑那些未使用x训练的基学习器在x上的预测，有

则Bagging泛化误差的外包估计为

事实上，外包样本还有许多其他用途，例如当基学习器是决策时，可使用外包样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；当基学习器是神经网络时，可使用外包样本来辅助早期停止以减小过拟合的风险。从偏差-方差分解的角度看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效果更为明显，我们以基于信息增益划分