Ensemble Learning

Algorithm
machine learning
集成学习的概念

机器学习中有着多种多样的算法，不同的算法有着不同优劣。对于现有单一算法的优化往往比较困难而且不一定会取得更好的效果。集成学习的思想就是将多个个体学习器组合起来以取得更好的性能。这对于弱学习器更加实用，集成学习的很多理论都是针对弱学习器的。集成学习有如下几个优点：

  1. 减小“泛化性能不佳”的风险
  2. 降低陷入局部极小值的风险
  3. 更加全面的假设空间近似(多个学习器可以扩大假设空间)

目前集成学习方法按照个体学习器的生成方法可以分为两类：Boosting和随机森林。Boosting方法不在这里介绍，本文会介绍到随机森林。

学习器的结合方法
平均法

平均法的思想很简单，即将各个学习器加权平均

其中，$h_i(x)$为第$i$个学习器的结果。

投票法

投票法的思想也很简单，就是按照一定的规则进行投票选出最佳结果。一般作用于分类任务，定义学习器$h_i(x)$从预测标记集合中$\lbrace c_1,c_2,…,c_N \rbrace$。加权投票法可以表示为

其中，$h_i^j(x)$表示$h_i(x)$在类别标记$c_j$上的输出。

Stacking

Stacking先从数据集中训练出初级学习器，然后再生成“新的数据集”用于生成次级学习器。具体来说，初级学习器的输出被当作次级学习器的样例输入。Stacking算法描述如下（假定初级学习器使用不同的学习算法）

输入：训练集$D=\lbrace (x_1,y_1),…,(x_m,y_m) \rbrace$；初级学习器算法$\gamma_1,…,\gamma_T$；次级学习算法$\gamma$

1 $h_t = \gamma_t(D), \; t=1,…,T$
2 $D^{‘}=\varnothing$
3 $for\; i=1,…,m$
4 $\quad for\; t=1,…,T$
5 $\quad \quad z_{it}=h_t(x_i)$
6 $\quad D^{‘}=D^{‘} \cup ((z_{i1},…,z_{iT}),y_i)$
7 $h^{‘}=\gamma(D^{‘})$

输出：$H(x)=h^{‘}(h_1(x),…,h_T(x))$

训练阶段，次级训练集的是初级学习器产生的。如果直接使用初级学习器的训练集来产生次级训练集，过拟合风险比较大。一般使用cross validation或者留一法等方法，用初级学习器未使用的样本来产生次级学习器的训练样本。

Bagging与随机森林 （Random Forest）
Bagging

Bagging是并行式集成学习算法的代表，基于自助采样法（bootstrap sampling）。给定包含$m$个样本的训练集，每次随机选择一个样本，采样方式为放回式采样。采样$m$次，得到一个训练集，初始训练集中大约有63.2%的样本出现在新样本集中。

按照上面的方法，采集$T$个新的训练集，然后基于每个新的样本集训练出基学习器，然后将基学习器组合起来。这便是Bagging的基本思想。Bagging算法描述如下

输入：训练集$D=\lbrace (x_1,y_1),…,(x_m,y_m) \rbrace$；基学习器算法$\gamma$；训练轮数$T$

1 $for\;t=1,…,T$
2 $\quad D_{bs} \xleftarrow{bootstrap\; sampling} D$
3 $\quad h_t=\gamma(D_{bs})$

输出：$H(x)=\arg\max_{y\in Y} \sum_{t=1}^T I(h_t(x)=y)$

因为自助采样平均只使用初始训练集的63.2%，剩下的样本可用做验证集来对泛化性能进行“包外估计”（out-of-bag estimate）。令$D_t$表示$h_t$使用的样本集，令$H^{oe}(x)$表示对样本$x$的包外估计，且仅考虑那些未使用样本$x$的基学习器再$x$上的预测

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

Bagging主要侧重于降低方差，所以在不剪枝决策树、神经网络等易受样本扰动的学习器上效果明显。

随机森林

随机森林是Bagging的扩展，规定基学习器为决策树，在以基学习器为决策树构建Bagging集成学习器的基础上，进一步在决策树的训练过程中引入了随机属性选择。传统决策树在训练时，需要选取当前结点属性集中最佳属性，而在随机森林中则是先从属性集随机选出一个包含$k$个属性的子集，然后再从这个自己中选择最佳属性。很明显，随机森林的效率要比Bagging高，二者收敛性相似。一般地，随机森林的起始性能较差，随着个体学习器的数目增大，随机森林的泛化误差会收敛到更低。

分享到