机器学习VIII - 集成学习 (Ensemble Learning)

13 集成学习 (Ensemble Learning)

集成学习是通过构建多个学习器来构建一个大的学习器，有时也会被称之为多分类系统 (Multi-Classifier System) ，基于委员会的学习 (committee-based learning) 等。

如果集成的学习器中，只包含同类的学习器，那这样的集成是同质的 (Homogeneous) ，其中个体学习器称之为“基学习器” （Base Learner），相应的算法称之为“基学习算法” (Base Learning Algorithm) ；如果集成的学习器中包含不同类型的学习器，则这样的集成是异质的 (Heterogenous) ，其中的个体学习器称之为“组件学习器” (Component Learner)。

集成方式主要分为两种，Boosting与Bagging。

13.1 Boosting

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

其中最经典的Boosting算法为AdaBoost (Adaptive Boost) ，是多个基学习器的线性组合。

假设函数如下：

$H(x) = \sum_{t=1}^T\alpha_t h_t(x)$

$T = $ 训练次数

$h_t(x) = $ 每个弱分类器

$\alpha_t = $ 每个弱分类器的权重

完整算法如下：

$\begin{aligned} 输入：&训练集D=\{(x_1, y_1),...,(x_m,y_m)\} \\ &基学习算法L \\ &训练轮数T \\过程： &初始化权重矩阵D_1(i)=1/m \\ &For\ \ t=1,...,T \\ & \quad \quad h_t = L(D,d_t) \quad 注：基于分布D_1(i),训练分类器h_t(x) \\ & \quad \quad \epsilon_t = P_{x\sim D_t}(h_t(x)\neq y) \\ & \quad \quad if \ \ \epsilon_t > 0.5 \ \ then \ \ break \\ & \quad \quad \alpha_t = \frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t}) \\ & \quad \quad D_{t+1}(x) = \frac{D_{t}(x)}{Z_t} \times \left\{ \begin{aligned} exp(-\alpha_t), \quad if \ \ h_t(x)=y \\ exp(\alpha_t), \quad if \ \ h_t(x)\neq y \end{aligned} \right. \\ & \quad \quad \quad \quad \quad \ \ \ = \frac{D_t(x)exp(-\alpha_t y h_t(x))}{Z_t} \\ & end \ \ for \\ 输出：& H(x) = sign(\sum_{t=1}^T\alpha_t h_t(x)) \end{aligned}$

13.2 Bagging

Bagging 是井行式集成学习方法最著名的代表。它直接基于自助来样法 (bootstrap sampling)，给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过随机采样操作，我们得到含m个样本的采样集，再基于每个采样集训练出一个基学习器，再将这些学习器结合。结合时，对分类任务使用简单头皮案发，对回归任务使用简单平均法。

$\begin{aligned} 输入：&训练集D=\{(x_1, y_1),...,(x_m,y_m)\} \\ &基学习算法L \\ &训练轮数T \\过程： &For\ \ t=1,...,T \\ & \quad \quad h_t = L(D,D_{bs}) \quad 注：随机自助抽样 \\ & end \ \ for \\ 输出：& H(x) = \underset{y\in Y}{argmax[card(t:h_t(x) = y)]} 注：选择出现频次最高的预测 \end{aligned}$

由于使用了自助法，每个基学习器只使用了初始训练集中约 63.2% 的样本，剩下的样本可以用来作为测试集。

13.3 随机森林 (RF, Random Forest)

RF是bagging的一个拓展变体，RF在以决策树为基学习器在Bagging的基础上，进一步在决策树的训练过程中引入了随机属性选择。

传统决策树会使用所有特征$m$中最优一个特征，而RF则会现在随机选择k个特征，然后再从其中选择一个最优的属性，一般$k=log_2d$。

13.4 结合策略

13.4.1 平均法

对于数值型的输出，最常见的策略是平均法

简单平均法 (Simple Averaging)
$H(x) = \frac{1}{T} \sum_{i=1}^T h_i(x)$
加权平均法 (Weighted Averaging)
$H(x) =\sum_{i=1}^T w_ih_i(x)$
其中$w_i$为每个学习器的权重，通常要求$w_i \geq 0, \sum_{i=1}^Tw_i=1$

13.4.2 投票法

绝对多数投票法 (Majority Voting)
$H(x) = \left\{ \begin{aligned} &c_j, &&if\ \ \sum_{i=1}^Th_i^j(x)>0.5 \sum^N_{k=1}\sum^T_{i=1}h_i^k(x) \\ &reject, &&otherwise \end{aligned} \right.$
即若某标记得票过半数，则预测为该标记，否则拒绝。
相对多数投票法(Plurality Voting)
$H(x) = c_{\underset{j}{argmax}\sum_{i=1}^Th_i^j(x)}$
即选择得票最多的标记，如果有多个则随机一个。
加权投票法 (Weighted Voting)
$H(x) = c_{\underset{j}{argmax}\sum_{i=1}^T w_i h_i^j(x)}$
其中$w_i$为每个学习器的权重，通常要求$w_i \geq 0, \sum_{i=1}^Tw_i=1$

13.4.3 学习法

当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。Stacking是学习法的代表，我们把个器学习器称之为初级学习器，用于结合的学习器称之为次级学习器，或者是元学习器 (Meta-Learner)。

Stacking先从初始数据集训练出初级学习器，然后“生成”一个新的数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例的输入特征，而初始样本的标记则被当作为样例标记。

一般初级学习器和次级学习器是由不同算法组成的，则是异质的。

$\begin{aligned} 输入：&训练集D=\{(x_1, y_1),...,(x_m,y_m)\} \\ &初级学习算法L_1, L_2, ..., L_T \\ &次级学习算法L \\过程： &for\ \ t=1,...,T \\ & \quad \quad h_t = L_T(D) \\ & end \ \ for \\ &D' = \emptyset \\ &for\ \ i=1,...,m \\ & \quad \quad for\ \ t=1,...,T \\ & \quad \quad \quad \quad z_{it} = h_t(x_i); \\ & \quad \quad end\ \ for \\ & \quad \quad D' = D' \cup ((z_{i1}, z_{i2}, ..., z_{iT}), y_i) \\ & end \ \ for \\ & h' = L(D') \\ 输出：& H(x) = h'(h_1(x), h_2(x), ..., h_T(x)) \ \ 注：选择出现频次最高的预测 \end{aligned}$

在训练阶段，次级训练集是利用初级学习器产生的，若直接用初级学习器的训练集来产生次级训练集，则过拟合风险会比较大。因此，一般是通过使用交叉验证或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。

13.5 多样性 (Diversity)

个体学习器应该“好而不同”，故名思义，多样性度量 (diversity measure) 是用于度量集成中个体分类器的多样性，即估算个体学习器的多样化程度。典型做法是考虑个体分类器的两两相似/不相似性。

给定数据集 $D = \{(x_1,y_1), (x_2,y_2), …, (x_m,y_m)\}$，对于二分类任务，$y_i \in \{-1，+1\}$，分类器$h_i,h_j$的预测结果列联表 (Contingency Table) 为

	$h_i = +1$	$h_i = -1$
$h_j = +1$	$a$	$c$
$h_j = -1$	$b$	$d$

不合适度 (Disagreement Measure)
$dis_{ij} = \frac{b+c}{m} \in [0,1]$
值越大代表多样性越大
相关系数 (Correlation Coeffcient)
$\rho_{ij} = \frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}} \in [-1,+1]$
$Q-$统计量 ($Q-statistic$)
$Q_{ij} = \frac{ad-bc}{ad+bc}$
$\kappa-$统计量 ($\kappa-statistic$)
$\begin{aligned} \kappa &= \frac{p_1-p_2}{1-p_2} \\ p_1 &= \frac{a+d}{m} \\ p_2 &= \frac{(a+b)(a+c)+(c+d)(b+d)}{m^2} \end{aligned}$
若分类器$h_i$与$h_j$完全一致，则$\kappa = 1$；如果仅是偶然一致，则$\kappa = 0$。

13.6 多样性增强

数据样本扰动

利用不同的数据子集训练不同的个体学习器。例如在Bagging中使用自助采样，在AdaBoost中使用序列采样。这种做法对“不稳定基学习器”比较有效，比如决策树，神经网络等。对数据样本扰动不敏感的学习器称之为稳定基学习器 (Stable Base Learner)，例如线性学习器，SVM，k-means，朴素贝叶斯等。
输入属性扰动

从不同子空间训练不同个体学习器。著名的随机子空间 (Random Subspace) 算法，就是从初始属性集中抽取出若干个属性子集，再基于每个属性子集训练一个基学习器。对包含大量冗余属性的数据，在子空间中训练个体学习器不仅能产生多样性大的个体，还会因属性数的减少而大幅节省时间开销，同时，由于冗余属性多，减少一些属性后训练出的个体学习器也不至于太差。若数据只包含少量属性，或者冗余属性很少，则不宜使用输入属性扰动法。
$\begin{aligned} 输入：&训练集D=\{(x_1, y_1),...,(x_m,y_m)\} \\ &基学习算法L \\ &基学习器数T \\ &子空间属性数d' \\过程： &For\ \ t=1,...,T \\ & \quad \quad F_t = RS(D, d') \quad \\ & \quad \quad D_t = Map_{F_t}(D) \\ & \quad \quad h_t = L(D_t) \quad 注：随机自助抽样 \\ & end \ \ for \\ 输出：& H(x) = \underset{y\in Y}{argmax}[card(t:h_t(Map_{F_t}(x)) = y)] 注：选择出现频次最高的预测 \end{aligned}$
输出表示扰动

此类做法的基本思路是对输出表示进行操纵以增强多样性，可对训练样本的类标记稍作变动。例如“翻转法” (Flipping Output) 随机改变一些训练样本的标记；“输出调制法” (Output Smearing) 讲分类输出转化为回归输出后构建个体学习器；如ECOC法利用纠错输出码将多分类任务拆解为一系列二分类任务来训练基学习器。
算法参数扰动

通过随机设置不同的参数，产生差别较大的个体学习器。例如”负相关法” (Negative Correlation) 思式地通过正则化项来强制个体神经网络使用不同的参数。

随机森林中同时使用了数据样本扰动和输入属性扰动。

本文使用 Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 许可协议，转载请注明出处。