《机器学习》笔记 —— 集成学习

发表于 | 分类于 | 阅读次数:

通过构建并结合多个学习器来完成学习任务。

个体学习器通常由一个现有学习算法从训练数据产生，再由某种策略将他们结合起来。

同质集成中的个体学习器亦称为“基学习器”，相应的学习算法称为“基学习算法”。

异质集成中的个体学习器由不同学习算法组成，个体学习器称为“组件学习器”

考虑二分类问题\(y\in \{-1,+1\}\)和真实函数\(f\),假定基学习器的错误率为\(\epsilon\)，即对每个即分类器\(h_i\)有： \[ p(h_i(x)\neq f(x)) = \epsilon \]

用简单投票法结合T个基分类器，若超过半数的基分类器正确，则分类正确： \[ H(x)=sign(\sum_{i=1}^Th_i(x)) \]

假设基分类器错误率相互独立，则有Hoeffding不等式可得集成错误率为： \[ \begin{align} p(H(x)\neq f(x)) &=\sum_{k=0}^{\lfloor T/2 \rfloor}C_T^k(1-\epsilon)^k\epsilon^{T-k} \\ & \leq exp(-\frac{1}{2}T(1-2\epsilon)^2) \end{align} \]

随着T增大，错误率将以指数级下降。

根据个体学习器的生成方式，目前集成学习方法大致可以分成两类，一类是个体学习器之间存在强依赖关系、必须串行生成的序列化方法，代表是Boosting方法，第二类是个体学习器之间不存在强依赖关系、可同时生成的并行方法，代表是Bagging和随机森林。

Boosting

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

AdaBoosting算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：训练集D={(x1,y1),(x2,y2),...,(xm,ym)}
	 基学习器算法L
	 训练轮数T
过程：
	D1(x) = 1/m
	for t = 1,2,...,T do
		ht = L(D,Dt)
		et = P(ht(x)!=f(x))
		if et > 0.5 then break
		alpha_a = 1/2ln((1-et)/et)
		Dt+1(x) = Dt(x)/Zt x exp(-alpha_t*f(x)ht(x))
	end for
输出：H(x) = sign(\sum_t^T alpha_tht(x))

Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法”实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重，对无法接受带权样本的基学习算法，则可通过“重采样法”来处理，即在每一轮中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件（检查当前基分类器是否比随机猜想好），一旦条件不满足，则当前基学习器被抛弃且学习过程停止。在此情况下，初始设置的轮数T还远远没达到，科恩个导致最终因基学习器数量较少而性能不佳，若采用“重采样法”则可重启动的训练，避免训练过早停止，即抛弃不满足条件的基学习器后，根据当前分布对训练样本进行重新采样，再基于新的采样结果重新训练。

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

Bagging

并行式集成学习方法的代表，基于自助采样，采样出T个含m个训练样本的采样，然后基于每个采样集训练出一个基学习器，再将基学习器进行结合。Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。

训练一个Bagging集成与直接使用基学习算法训练一个学习器复杂度同阶，由于每个基学习器只使用了初始训练集中约63.2%的样本，剩下约36.8%的样本可用作验证集对泛化性能进行包外估计。

当基学习器是决策的时，可使用包外样本来辅助剪枝或用于估计决策树中各结点的后验概率以辅助队零训练样本结点的处理。当基学习器是神经网络时，可用来辅助提取终止减小过拟合。

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

随机森林

随机森林是Bagging的一个扩展变体，RF在以决策树为基学习器构建Bagging集成的基础上，在决策树训练过程中引入随机属性。

对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分，k控制随机性引入程度，一般情况下推荐值\(k=\log_2d\)，随机森林的训练效率常优于Bagging，因为在个体决策树构建过程中，Bagging使用确定型决策树，而RF使用“随机型”决策树（只需考虑一个属性子集）。

结合策略

平均法

1）简单平均法： \[ H(x)=\frac{1}{T}\sum_{i=1}^Th_i(x) \]

  1. 加权平均法： \[ H(x)=\sum_{i=1}^Tw_ih_i(x) \]

其中\(w_i\)是个体学习器\(h_i\)的权重，通常要求\(w_i \geq 0 \text{, } \sum_{i=1}^Tw_i=1\)

加权平均法的权重一般是从训练数据中学习而得，现实中训练样本通常不充分或存在噪声，这使得学得的权重并不可靠，尤其是对规模比较大的集成来说，要学习的权重比较多，较容易出现过拟合，因此加权平均有时候未必优于简单平均法。

投票法

假设学习器\(h_i\)在样本x的预测输出表示为一个N维向量\((h_i^1(x);h_i^2(x);\dots ; h_i^N(x))\)，其中\(h_i^j(x)\)是\(h_i\)在类别标记\(c_j\)上的输出。

1）绝对多数投票法： \[H(x) = \left\{ \begin{array}{rl} & c_j & \qquad \quad \text{if }\sum_{i=1}^Th_i^j(x)>0.5 \sum_{k=1}^N\sum_{i=1}^Th_i^k(x) \\ & \text{reject}& \qquad \quad \text{otherwise}\\ \end{array} \right. \]

若某标记得投票超过半数，则预测为该标记，否则拒绝预测。

2）相对多数投票法 \[ H(x)=c_{\arg\max_j \sum_{i=1}^Th_i^j(x)} \] 即预测为得票最多的标记，若同时有多个标记获得最高票，则从中随机选取一个

3）加权投票法 \[ H(x)=c_{\arg\max_j\sum_{i=1}^Tw_ih_i^j(x)} \] 与加权平均法类似，\(w_i\)是\(h_i\)的权重，通常\(w_i \geq 0\)，\(\sum_{i=1}^Tw_i=1\)