Skip to content

继承学习

个体与集成

集成学习(ensemble learning)通过构建并结合多个学习器来提升性能。
要获得好的集成，个体学习器应“好而不同”，即个体学习器有一定“准确性”（学习器不能太坏），并且要有“多样性”（学习器间有差异）

考虑二分类问题，假设基分类器错误率为

\[ P(h_i(x)\neq f(x))=\epsilon \]

假设集成通过简单投票法结合𝑇个分类器，若有超过半数的基分类 器正确则分类就正确

\[ H(x)=\text{sign}(\Sigma^T_{i=1}h_i(x)) \]

假设基分类器的错误率相互独立，则由Hoeffding不等式可得集成的错误率为：

\[ P(H(x)\neq f(x))=\Sigma^{\lfloor T/2\rfloor}_{k=0}\begin{pmatrix}T\\ k\end{pmatrix}(1-\epsilon)^k\epsilon^{T-k} \leq exp(-\frac{1}{2}T(1-2\epsilon)^2) \]

上式显示，在一定条件下，随着集成分类器数目的增加，集成的错误率将指数级下降，最终趋向于0

  • 问题：上面的分析有一个关键假设:基学习器的误差相互独立。在现实任务中，个体学习器是为解决同一个问题训练出来的，它们显然不可能相互独立。事实上，个体学习器的“准确性”和“多样性”本身就存在冲突

根据个体学习器生成方式，集成学习方法分两大类：

  • 个体学习器问存在强依赖关系、必须串行生成的序列化方法：Boosting
  • 个体学习器间不存在强依赖关系、可同时生成的并行化方法：Bagging、随机森林

Boosting

Boosting 是一族可将弱学习器提升为强学习器的算法.这族算法的工作机 制类似:先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整,得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器

alt text

AdaBoost算法：

alt text

基学习器的线性组合：\(H(x)=\Sigma^T_{t=1}\alpha_t h_t(x)\)

最小化指数损失函数：

\[ l_exp(H|D)=E_{x~D}[e^{-f(x)H(x)}] \]

若能令指数损失函数最小化，则上式的偏导值为0，即

\[ \frac{\partial l_{exp}(H|D)}{\partial H(x)}=-e^{-H(x)}P(f(x)=1|x)+e^{H(x)}P(f(x)=-1|x) \]

当基分类器\(h_t\) 基于分布 \(D_t\) 产生后，该基分类器的权重 \(\alpha_t\) 应使得 \(\alpha_t h_T\) 最小化指数损失函数

$$

$$

令指数损失函数的导数为0，即

$$

$$

在获得𝐻𝑡−1之后的样本分布进行调整，使得下一轮的基学习器ℎ𝑡能纠正𝐻𝑡−1的一些错误，理想的ℎ𝑡能纠正全部错误

$$

$$

泰勒展开近似为

$$$$

于是理想的基学习器：

$$$$

注意到 \(E_{x~D}[e^{-f(x)H_{t-1}(x)}]\) 是一个常数，令\(D_t\)表示一个分布，

$$$$

  • Boosting 算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件(例如检查当前基分类器是否是比随机猜测好) ，一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。采用重采样法可避免训练过程过早停止
  • 从偏差——方差分解的角度看， Boosting 主要关住降低偏差，因此 Boosting能基于泛化性能相当弱的学习器构建出很强的集成

Bagging与随机森林

  • Bagging：是一种通用的集成学习框架
  • 随机森林：是Bagging框架的一种具体实现，专用于决策树

Bagging

  • 属于并行式集成学习，直接基于自助采样法
  • 过程：可采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合
  • 时间复杂度低：训练一个 Bagging 集成与直在使用基学习算法训练一个学习器的复杂度同阶
  • 与标准 AdaBoost 只适用于二分类任务不间，Bagging 能不经修改地用于多分类、回归等任务
  • 可使用包外估计：自助采用留下了没被选中的样本，可以作为验证集来对泛化性能进行“包外估计”

随机森林

随机森林(Random Forest/RF)是bagging的一个扩展变种。RF在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择：

  • 采样的随机性
  • 属性选择的随机性
  • 随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能通过个体学习器之间差异度的增加而进一步提升
  • 优点：简单、容易实现、计算开销小，训练效率常高于Bagging

结合策略

平均法

  • 简单平均
  • 加权平均

投票法

  • 绝对多数投票法（majority voting）：若某标记得票过半数，则预测为该标记;否则拒绝预测.
  • 相对多数投票法（plurality voting）：预测为得票最多的标记，若同时有多个标记获最高票，则从中随机选取一个
  • 加权投票法（weighted voting）

学习法

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

多样性

误差-分歧分解

定义学习器 \(h_t\)的分歧（ambuguity）：

\[ A(h_i|x)=(h_i(x)-H(x))^2 \]

集成的分歧：

\[ \bar{A}(h|x)=\Sigma_{i=1}^T w_i A(h_i|x) \]
\[ =\Sigma_{i=1}^T w_i(h_i(x)-H(x))^2 \]
  • 分歧项代表了个体学习器在样本x上的不一致性，即在一定程度上反映了个体学习器的多样性
  • 集成泛化误差为 \(E=\bar E- \bar A\)(\(\bar E\) 表示个体学习器泛化误差的加权均值，\(\bar A\) 表示个体学习器的加权分歧值)：表明个体学习器精确性越高、多样性越大，则集成效果越好。称为误差-分歧分解

多样性度量

  • 用于度量集成中个体学习器的多样性
    • 不合度量：
    • 相关系数：
    • Q-统计量：
    • K-统计量：

多样性扰动

  • 常见的增强个体学习器的多样性的方法：
    • 数据样本扰动
    • 输入属性扰动
    • 输出表示扰动
    • 算法参数扰动

Comments