个体与集成
集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统，基于委员会的学习。
下图显示出集成学习的一般结构：先产生一组“个体学习器”，再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生，例如C4.5决策树算法、BP神经网络算法等，此时集成中只包含同种类型的个体学习器，例如“决策树集成”中全是决策树。这样的集成是“同质”的。同质集成中的个体学习器亦称“基学习器”，相应的学习算法称为“基学习算法”。集成也可以包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成是“异质”的。 异质集成中的个体学习器由不同的学习算法生成，这时就不再有基学习算法；相应的，个体学习器一般不称为基学习器，常称为“组件学习器”或直接称为个体学习器。
集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”尤为明显，因此集成学习的很多理论研究都是针对学习器进行的，而基学习器有时也被直接称为弱学习器。
在一般经验中，如果把好坏不等的东西掺到一起，那么通常结果会是比最坏的要好一些，比最好的要坏一些。集成学习把多个学习器结合起来，如何能获得比最好的单一学习器的更好的性能呢？要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，即学习器不能太坏，并且要有“多样性”，即学习器间具有差异。
我们来做个简单的分析。考虑二分类问题$\mathbb{y} \in {-1,+1}$和真实函数$f$,假定及分类器的错误率为$\epsilon$,即对每个基分类器$h_i$有
\[P(h_i(\mathbb{x}) \ne f(x))=\epsilon\]假设集成通过简单投票法结合$T$个基分类器，若有超过半数的基分类器正确，则集成分类就正确:
\[H(x)=sign\big( \sum^T_{i=1} h_i(x)\big)\]假设基分类器的错误率相互独立，则由Hoeffding不等式可知，集成的错误率为
\[\begin{align} P(H(x))\ne f((x))&=\sum^{T/2}_{k=0}\dbinom{T}{k}(1-\epsilon)^k\epsilon^{T-k} \\ &\le exp\Big(-\frac{1}{2}T(1-2\epsilon)^2\Big)\end{align}\]上式显示出，随着集成中个体分类器数目T的增大，集成的错误率将指数级下降，最终趋向于零。
然而我们必须注意到，上面的分析有一个关键假设：基学习器的误差相互独立，在现实任务中，个体学习器是为了解决同一个问题训练出来的，它们显然不可能相互独立！事实上，个体学习器的“准确性”和“多样性”本身就存在冲突。一般的，准确性很高之后，要增加多样性就需牺牲准确性。事实上，如何产生并结合“好而不同”的个体学习器，恰是集成学习研究的核心。
根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即个体学习器之间存在依赖关系，必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成并行化方法；前者的代表是Boosting，后者的代表是Bagging和“随机森林”(Random Forest)。
Boosting
Boosting 是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值$T$，最终将这$T$个基学习器进行加权结合。
Boosting族算法最著名的代表是AdaBoost[Freund and Schapire,1997]，算法描述如下所示，其中$y_i \in {-1,+1}$，$f$ 是真实函数。
输入：训练集 $D=(x_1,y_1),(x_2,y_2),…(x_m,y_m)$；基学习算法$\mathcal{L}$;训练轮数$T$.
过程:
1:$\mathcal{D}_1(\boldsymbol{x})=\frac{1}{m}$初始化样本权值分布
2:for $t=1,2,…,T $ do
3: $h_t=\mathcal{L}(D,\mathcal{D_t})$基于分布$\mathcal{D_t}$从数据集D中训练出分类器$h_t$
4: $ \quad \epsilon_t=P_{\boldsymbol{x}\sim\mathcal{D}_t}(h_t(\boldsymbol{x})\ne f(\boldsymbol{x}))$,估计$h_t$的误差
5 $\quad \textbf{if } \epsilon_t\gt0.5 \textbf{ then break}$
6: $\alpha_t=\frac{1}{2}\ln\Big(\frac{1-\epsilon_t}{\epsilon_t}\Big)$确定分类器$h_t$的权重
7: $\quad \quad\quad\quad \mathcal{D}_{t+1}(\boldsymbol{x})=\frac{\mathcal{D}_t(\boldsymbol{x})}{Z_t}\times\begin{cases}\exp(-\alpha_t),& \text{if } h_t(\boldsymbol{x})=f(\boldsymbol{x})\exp(\alpha_t),& \text{if } h_t(\boldsymbol{x})\ne f(\boldsymbol{x})\end{cases}=\frac{\mathcal{D}_t(\boldsymbol{x})\exp(-\alpha_t f(\boldsymbol{x})h_t(\boldsymbol{x}))}{Z_t}$
更新样本分布，其中$Z_t$是规范化因子，以确保$\mathcal{D_{t+1}}$是一个分布
8：end for
输出： $H(x)=sign(\sum^T_{t=1}\alpha h_t(x))$
Boosting 算法要求基学习器能对特定的数据分布进行学习，这可以通过“重赋权法”实施，即在训练过程中的每一轮中，根据样本分布为每个训练样本重新赋予一个权重，对无法接受带权样本的基学算法，则可以通过“重采样法”来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样。再用重采样而得到的样本集对基学习器进行训练。一般而言，这两种做法没有显著的优劣差别。需注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件（如上述算法中第5行，检查当前基分类器是否比随机猜测好），一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。在这种情况下，初始设置的学习轮数$T$也许还远为达到，可能导致最终集成中只包含很少的基学习器而性能不佳。若采用“重采样法”，则可获得“重启动“机会以避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续到预设的$T$轮完成。
从偏差-方差的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建很强的集成。
Bagging与随机森林
设法使基学习器尽可能具有较大的差异，给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样由于训练数据不同，我们获得的基学习器可望具有较大的差异，然而为获得好的集成，我们同时还希望个体学习器不能太差。如果采样出的每个自己都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为了解决这个问题，我们可考虑使用相互有交叠的采样子集。
Bagging
Bagging 是并行式集成学习方法最著名的代表。它直接基于自助采样法（boostrap sampling）。给定包含$m$个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过$m$次随机采用操作，我们得到含$m$个样本的采样集，初始训练集中有的样本在采样集中多次出现，有的则从为出现。
这样，我们可采样出$T$个含$m$个训练样本的采样集，然后基于每个采样集训练出一个基学习器，在将这些基学习器进行结合。这就是Bagging的基本流程。在对预测输出进行结合时，Bagging通常对分类任务使用简答投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可以进一步考察学习器投票的置信度来确定最终胜者。Bagging的算法描述如下所示：
输入：训练集 $D={( x_1,y_1),(x_2,y_2),…(x_m,y_m)}$;基学习算法$\mathcal{L}$，训练轮数$T$
过程：
1：for $t=1,2,…T$ do
2:$\quad \quad h_t=\mathcal{L}(D,\mathcal{D_{bs}})$
3: end for
输出：$H(x)=argmax_{y \in \mathcal{y} } \sum^T_{t=1}\mathbb{I}(h_t(x)=y)$
假定基学习器的计算复杂度$O(m)$。则Bagging的复杂度大致为$T(O(m)+O(s))$，考虑到采样与投票、平均过程的复杂度$O(s)$很小，而$T$通常是一个不太大的常数，因此，训练一个Bagging集成与直接使用基学习器算法训练一个学习器的复杂度同阶，这说明Bagging是一个很高效的集成学习算法。另外，与标准AdaBoost只适用于二分类任务不同，Bagging能不经修改地用于多分类、回归等任务。
自助采样的过程还给Bagging带来了另外一个优点：由于每个基学习器只使用了初始训练集中约63.2%的样本，剩下约36.8%的样本可用作验证集来对泛化性能进行“包外估计”（out-of-bag estimate）。为此需记录每个基学习器所使用的训练样本。不妨令$D_t$表示$h_t$实际使用的训练样本集，令$H^{oob}(\boldsymbol{x})$表示对样本$x$的包外预测，即仅考虑那些未使用$x$训练的基学习器在$x$上的预测，有
\[H^{oob}(\boldsymbol{x})=\mathop{\arg\max}\limits_{y\in\mathcal{Y}}\sum_{t=1}^T\mathbb{I}(h_t(\boldsymbol{x})=y)\cdot\mathbb{I}(\boldsymbol{x}\notin D_t)\]则Bagging泛化误差的包外估计为
\[\epsilon^{oob}=\frac{1}{|D|}\sum_{(\boldsymbol{x},y)\in D}\mathbb{I}(H^{oob}(\boldsymbol{x})\ne y)\]事实上，包外样本还有许多其他用途。例如基学习器时决策树时，可使用包外样本来辅助减枝，或用于估计决策树各结点的后验概率以辅助对零训练的样本结点的处理；当基学习器是神经网络时，使用包外样本来辅助早期停止以减小过拟合风险。
从偏差-方差分解的角度来看，Bagging 主要关注降低方差，因此它不在剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。
随机森林
随机森林（Random Forest，简称RF）是Bagging的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有d个属性）中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含一个$k$个属性的子集，然后在从这个子集中选择一个最优属性用于划分，这里的参数$k$控制了随机性的引入程度：若$k=d$,则基决策树的构建与传统决策树相同，若令$k=1$，则是随机选择一个属性用于划分；一般情况下，推荐值$k=\log_2d$.
随机森林简单、容易实现、计算开销小，令人惊奇的是，它在很多现实任务中展现出强大的性能，被誉为“代表集成学习技术水平的方法”，可以看出随机森林对Bagging只做了小改动，但是与Bagging中基学习器的“多样性”仅通过样本扰动（通过对初始训练集采样）而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。
随机森林的收敛性与Bagging相似，如上图所示，随机森林的起始性能往往相对较差，特别是在集成中只包含一个基学习器时，这很容易理解，因为通过引入属性扰动，随机森林中个体学习器的性能往往有所降低，然而随着学习器数目的增加，随机森林通常会收敛到更低的泛化误差，值得一提的是，随机森林的训练效率优于Bagging，因为在个体决策树的构建中，Bagging使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的“随机型”决策树只需考察一个属性集。
结合策略
学习器结合可能会从三个方面带来好处。
- 从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险。
- 从计算方面来看，学习算法往往陷入局部最小，有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险。
- 从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。
假定集成包含$T$个基学习器${h_1,h_2,…,h_T}$，其中$h_i$在示例$x$上的输出为$h_i(x)$.下面介绍几种对$h_i$进行结合的常见策略。
平均法
对数值型输出$h_i(x)\in \mathbb{R}$，最常见的结合策略是使用平均法
-
简单平均法(simple averaging)
\[H(x)=\frac{1}{T}\sum^T_{i=1}h_i(x)\] -
加权平均法（weighted averaging）
\[H(x)=\sum^T_{i=1}w_ih_i(x)\]其中$w_i$是个体学习器$h_i$的权重，通常要求$w_i\ge0,\sum^T_{i=1}w_i=1$
显然，简单平均法是加权平均法令$w_i=1/T$的特例。加权平均法在集成学习中具有特别的意义，集成学习中的各种结合方法都视为其特例或变体。事实上，加权平均法可认为是集成学习研究的基本出发点，对给定的基学习器，不同的集成学习方法可视为通过不同的方式来确定加权平均法中的基学习器权重。
加权平均法的权重一般是从训练数据中学习而得，现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠。尤其是对规模比较大的集成来说，要学习的权重比较多，较容易导致过拟合。因此，实验和应用均显示出，加权平均法未必一定优于平均法。一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。
投票法
对分类任务来说，学习器$h_i$将从类别标记集合${c_1,c_2,…,c_n}$中预测出一个标记，最常见的结合策略是使用投票法。为了便于讨论，我们将$h_i$在样本$x$上预测输出表示为一个$N$维向量$((h_i^1(\boldsymbol{x});h_i^2(\boldsymbol{x});\cdots;h_i^N(\boldsymbol{x})))$,其中$h^j_i(x)$是$h_i$在类别标记$c_j$上的输出
-
绝对多数投票法
\[H(\boldsymbol{x})=\begin{cases}c_j,&&\text{if }\sum_{i=1}^T h_i^j(\boldsymbol{x}) \gt 0.5 \sum_{k=1}^N\sum_{i=1}^T h_i^k(\boldsymbol{x})\\\text{reject},&&\text{otherwise}\end{cases}\]
即若某标记得票数过半数，则预测为该标记；否则拒绝预测。
-
相对多数投票法
\[H(\boldsymbol{x})=c_{\mathop{\arg\max}\limits_j \sum_{i=1}^T h_i^j(\boldsymbol{x})}\]
即预测为得票数最多的标记，若同时有多个标记获得最高票，则从中随机选取一个。
-
加权投票法
\[H(\boldsymbol{x})=c_{\mathop{\arg\max}\limits_j \sum_{i=1}^T w_ih_i^j(\boldsymbol{x})}\]
与加权平均法类似，$w_i$是$h_i$的权重，通常$w_i\ge0,\sum^T_{i=1}$。
在现实任务中，不同类型个体学习器可能产生不同类型的$h^j_i(x)$值，常见的有：
- 类标记：$h^j_i(x) \in {0,1}$，若$h_i$将样本$x$预测为类别$c_j$的取值为1，否则为0.使用类标记的投票亦称“硬投票”。
- 类概率：$h^j_i(x)\in [0,1]$，相当于对后验概率$P(c_j\mid x )$的一个估计，使用类概率的投票亦称“软投票”。
虽然分类器估计出的类概率值一般都不太准确，但基于类概率进行结合却往往比直接基于类标记进行结合性能更好。需要注意的是，若基学习器的类型不同，则其类概率值不能直接比较进行比较；在此种情形下，通常可将类概率输出转化为类标记输出（例如将类概率输出最大的$h^j_i(x)$设为1，其他设为0）然后再投票。
学习法
当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合，Stacking是学习法的典型代表。我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器。
Stacking先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。Stacking的算法如下，我们假定初级学习器使用不同学习算法产生，即初级集成是异质的。
输入：训练集$D={(x_1,y_1),(x_2,y_2),…(x_m,y_m)}$;初级学习算法$\mathcal{L_1},\mathcal{L_2},…, \mathcal{L_T}$;次级学习算法$\mathcal{L}$
过程： 1： for $t=1,2,…,T $ do
2: $h_t=\mathcal{L_t}(D)$
3: end for
4: $D’=\varnothing$
5: for $i=1,2,…,m$ do
6: for $t=1,2,…, T$ do
7: $z_{it}=h_t(x_i)$
8: end for
9 $\quad D’=D’\bigcup((z_{i1},z_{i2},\cdots,z_{iT}),y_i)$
10: end for
11: $h’=\mathcal{L}(D’)$
输出： $H(x)=h’(h_1(x),h_2(x),…,h_T(x))$
在训练阶段，次级训练集是利用初级学习器产生的，若直接用初级学习器的训练集来产生次级训练集，则过拟合风险会比较大；因此，一般是通过使用交叉验证或留一法这样的方式。用训练初级学习器未使用的样本来产生次级学习器的训练样本。以$k$折交叉验证为例，初始训练集$D$被随机划分为$k$个大小相似的集合$D_1,D_2,…,D_k$。令$D_j$和$D_{oj}=D \mid D_j$分别表示$j$折的测试集和训练集。给定$T$个初级学习算法，初级学习器$h_t^{(j)}$通过在$D_{oj}$上使用第$t$个学习算法而得。对$D_j$中每个样本$x_i$,令$z_{i}=(z_{i1};z_{i2};…z_{iT})$，标记部分为$y_i$。于是在整个交叉验证过程结束后，从这$T$个初级学习器产生的次级训练集$D’={ (z_i,y_i)}^m_{i=1}$,然后$D’$将用于训练次级学习器。
次级学习器的输入属性表示和次级学习器算法对Stacking集成的泛化性能有很大影响。有研究表明，将初级学习器的输出类概率作为次级学习器的输出属性，用多响应线性回归（Multi-response Linear Regression,简称MLR）作为次级学习算法效果较好，在MLR中使用不同的属性集更佳。
参考
来源《机器学习》 周志华
