Gamer's Show

你知道人生最要紧的事是快乐不停

0%

集成学习

Posted on Edited on In

相关代码与课后习题见我的GitHub

个体与集成

  1. 集成学习(ensemble learning)通过构建数个个体学习器来完成学习任务，每个个体学习器都是经过训练的算法；
  2. 集成的个体算法类型相同的（均为决策树或者均为神经网络等等）被称为“同质”(homogeneous)，反之为“异质”(heterogenous)。
    • 同质中的个体学习器称为“基学习器”(base learner)，相应的算法称为“基学习算法”(base learning algorithm)
    • 异质中的个体称为“组件学习器”(component learner)，或者直接称之为个体学习器
  3. 集成学习对性能提高的研究主要针对“弱学习器”(weak learner)，但是在实际应用中，为了个体学习器尽可能少，还是会使用学习能力更强的学习器。
    • 弱学习器是略优于随机猜测的学习器

研究核心

要获得好的集成，个体学习器应当“好而不同”：准确性+多样性(diversity);

  • 随着继承中个体分类器数目的增大，集成错误率指数级下降，最终趋于0；
  • 但是以上结论基于假设：学习器间的误差相互独立，但由于训练目标是解决同一个问题，所以不可能相互独立，因此可以看出，集成过程中准确性和多样性是类似于查准率和查全率的关系
    因此，如何产生并结合“好而不同”的学习器，是集成学习的核心。

集成学习方法

分为两类：

  1. 序列化：个体学习器间存在强依赖关系，必须串行生成；Boosting
  2. 并行化： 不存在强依赖关系，可以同时生成；Bagging & Random Forest

Boosting

可以将弱学习器提升为强学习器

WorkFlow

前提：base间强依赖 & 串行序列化

  1. 训练一个base
  2. 根据base的表现对训练样本分布进行调整，错误样本关注增加
  3. 基于调整后的样本训练一个base，知道base数为预定超参数n

Example:AdaBoost

加权模型，其实就是通过改变base的线性组合的系数来实现最小化损失函数$$ H(x)=\sum^T_{t=1}\alpha_th_t(x)$$

  1. 初始化样本权值分布，一般初始化每个样本权值相等
  2. 基于分布从数据集中训练出分类器$h_t$
  3. 估计分类器的误差$\epsilon_t$;
    • 这里设定如果误差大于0.5，也就是二分类问题的准确度低于随机猜测正确的概率，break舍去
    • 实际操作中可以自行设定对base精度的要求
  4. 确定分类器的权重$$\alpha_t=\frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t})$$
  5. 更新样本分布，其中$Z_t$是规范化因子，确保最终可以得到一个规范的分布$$ D_{t+1}=\frac{D_t(x)}{Z_t}×\begin{cases}
    exp(-\alpha_t), h_t(x)=f(x) \
    exp(\alpha_t), h_t(x)\ne f(x)
    \end{cases} =\frac{D_t(x)exp(-\alpha_t)f(x)h_t(x)}{Z_t}$$
  6. 最终输出：$$H(x)=sign(\sum^T_{t=1}\alpha_th_t(x))$$

小结

  1. 通过re-weighting对特定的数据分布进行学习，对无法接受带权样本的base，可以re-sampling处理（在训练过程中根据样本分布对训练集进行重新采样，用重采样后的样本对基学习器训练）
  2. 每一轮都会检查base被保留的条件，不符合的舍弃
  3. 从偏差-方差分解的角度来看，Boosting主要关注降低偏差，因此Boosting能基于泛化程度弱的学习器构建强集成

Bagging与随机森林

不存在强依赖关系&同时生成的并行式关系

Bagging

WorkFlow

直接原理：自助采样法bootstrap sampling

  1. 给定m个样本的数据集，有放回的随机抽取，m次随机采样后大概会有63.2%的原始数据出现在新样本集中，以此类推采样出T个类似采样集
    • 可以预留36.8%的数据作为验证集对泛化性能进行“包外估计”
      • 对于决策树base，可以辅助剪枝
      • 对于神经网络base，可以辅助早期停止，降低过拟合
  2. 对分类任务进行简单投票法，票数相同时随机选择一个

小结

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

随机森林Random Forest

RF实质上是Bagging的扩展变体，以决策树为base构建Bagging集成，引入了随机属性选择。

WorkFlow

总体就是对最优属性的选择，所以属性取值不同时的分叉不同，像一棵树。

  1. 对决策树的每个结点，从该节点d个属性中随机选择一个包含k个属性的子集，然后从这个子集中选择一个最优属性用于划分。一般来说选择$k=log_2d$
  2. 离散性质通过取值进行分叉，连续性质通过拟合度分叉

小结

  1. 简单&计算开销小，训练效率高。
  2. base的多样性来自样本+属性的扰动，最终集成泛化性能可以通过base差异度的提升来提升。
  3. 起始性能不好（所以可以增加学习轮次和base）

note

RF是一个“随机型”的决策树，所以说当你的数据集比较少或者说训练轮次不够的时候，验证集精度会有比较大的差距，我用了一个RF+linear来拟合连续性质进行二分类的样例最大会有20%的精度误差，而数据集的属性又比较多，40选15的时候可以有最优达到90%，但是极其不稳定，笨人觉得或许可以直接存起来高精度的RF结果然后给对应的属性加权？不过还没有继续跑ing（痛苦的回忆）

结合策略

学习器结合三大优势：

  1. 统计：学习任务假设空间大时可能多假设同性能，此时结合之后会更稳定
  2. 计算：算法局部极小点降低泛化性能，多次运行结合后可以降低局部极小出现的概率
  3. 表示：可以更好地吻合真实假设，使假设空间扩大

平均法

根据性能加权，但是必须使用非负权重才能优于个体学习器；性能相近的时候简单平均就可以。

投票法

  1. 用于分类任务，可以超过半数也可以选最多；
  2. 类标记投标为硬投票hard voting，类概率标记投票为软投票soft voting。虽然分类概率不准确，但是往往类概率投票准确度会更高。
    • 如果base类型不同，概率不能直接比较，一般就是hard voting了。

学习法

训练数据很多时，用另一个学习器来结合，把base称为初级学习器，用于结合的学习器称为次级学习器或者元学习器meta-learner

Example：Stack算法

  1. 使用初级学习算法产生初级学习器（可以是异质base）
  2. 使用初级学习器的输出产生次级训练集，用于训练次级学习器，此处初级样本的标记仍被当作样例标记
    • 这一步有比较大的过拟合风险，一般使用留一法或者交叉验证，用训练初级学习器未使用的样本产生次级学习器的训练样本
  3. 训练次级学习器并输出T个一一对应T个初级学习器的值
    次级学习器的输入属性表示和该算法对stacking集成的泛化性能影响很大。研究表明初级学习器输出类概率作为次级学习器输入时，用多响应线性回归MLR作为次级学习算法效果更好，使用不同的属性集更佳

多样性

误差-分歧分解