集成学习

集成学习

集成学习是通过构建并结合多个学习器来完成学习任务. 它一般先产生一组个体学习器, 在使用某种策略将它们结合起来. 集成学习通过将多个学习器进行组合, 通常可以获得比单一学习器显著优越的泛化性能. 如果个体学习器是从相同算法产生的, 那么该集成学习称为同质的, 否则称为异质的通常个体学习器的选取准则是单个学习器要有一定的准确性, 同时学习器之间要保持多样性.

根据个体学习器的生成方式, 目前的集成学习方法可以分为两大类:

  • 个体学习器之间存在强依赖关系, 必须串行生成的序列化方法, 每一轮迭代产生一个个体学习器. 如 Boosting,
  • 个体学习器之间不存在强依赖关系, 可以同时生成的并行化方法, 如 Bagging 和 随机森林(Random Forest, RF)

若基分类器的错误率相互独立, 则随着学习器数量趋近于无穷, 集成学习预测的错误率会趋近于 0. 不过实际中该假设显然不满足, 因为个体学习器是为了解决同一个问题训练出来的, 而且它们的算法也有可能是相似的. 因此个体学习器的准确性和多样性本身就存在冲突. 当单个个体学习器的准确性很高之后, 想要增加多样性就要牺牲准确性. 所以如何产生并结合”好而不同”的个体学习器就是集成学习研究的核心.

Boosting

Boosting(提升方法) 是一种常用的统计学方法. 在分类问题中, 它通过改变训练样本的权重学习多个分类器, 并将这些分类器进行线性组合来提高分类能力.

Boosting 的理论基础是强学习(存在一个多项式的学习算法能把准确率提到很高)和弱学习(算法仅能得到比随机高一点的准确率)是等价的.即若在学习中发现了”弱学习算法”, 则可以通过某些办法将它提升为”强学习算法”.

Boosting 算法的工作原理大体可以表达为:

  • 先从初始训练集训练出一个基学习器.
  • 再根据基学习器的表现 对训练样本分布进行调整, 使得先前基学习器做错的训练样本在后续受到更多关注 .
  • 基于调整后的样本分布来训练下一个基学习器.
  • 重复以上步骤, 直到基学习器的数量达到预设值. 将这些 学习器进行加权组合 .

常见的 Boosting 算法有:

  • AdaBoost 算法是早期的经典 Boosting 算法, 它是前向分布算法的一个特例.
    • AdaBoost算法提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。
    • 加大分类误差率较小的弱分类器的权值,使得它在表决中起较大作用。减小分类误差率较大的弱分类器的权值,使得它在表决中起较小的作用。
    • AdaBoost采用指数损失函数来评估差异度,指数损失函数的缺点是对于异常点非常敏感,因而在噪音比较多的数据集上经常表现不佳。
  • GBDT算法在健壮性方面做了改进:
    • 由于损失函数为非平方误差时, 残差不再等于预测值减去真实值, 而是更为复杂的公式, 因此梯度提升树(GBT)用损失函数的负梯度在当前模型的值作为残差的近似值, 来拟合一颗回归树.
    • GBT 用于分类模型时, 得到梯度提升决策树(GBDT), 用于回归模型时, 得到梯度提升回归树(GBRT)
    • GBDT可以使用任何损失函数 (只要损失函数是一阶连续可导的),这样一些比较健壮的损失函数就能得以应用,使模型抗噪音能力得到增强。
  • XGBoost和LightGBM是现在最流行的Boosting算法:
    • xgboost 也是使用与提升树相同的前向分步算法。其区别在于:xgboost 通过结构风险极小化来确定下一个决策树的参数
    • GBT 只采用一阶泰勒展开, 而 XGBoost 采用到了二阶.

AdaBoost 算法

AdaBoost 算法流程为

  • 输入为训练数据集 $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})},~~~ x_{i}\in R^{n}, ~~ y_{i}\in {-1, +1}$
  • 初始化训练数据的权值分布 $W_{1} = (w_{1,1}, w_{1,2}, \dots, w_{1,N}), ~~w_{1,i}=\frac{1}{N}$. 该权值对于每个分类器和每个数据点都有一个, 因此在不同轮我们会调整数据的权值分布, 使得容易错的点权重越大.
  • 对 $m = 1,2, \dots, M$
    • 使用权值分布 $W_{m}$ 的训练数据集学习, 得到弱分类器 $h_{m}$
    • 计算 $h_{m}$ 在训练数据集上的分类误差率 $e_{m} = \sum_{i=1}^{N}w_{m,i}I(h_{m}\neq y_{i})$. 它表示所有误分类点的权重之和.
    • 若错误率大于等于 $e_{m}\geq \frac{1}{2}$ 则算法终止, 构建失败.
    • 计算第 m 个学习器$h_{m}$ 的系数 $\alpha_{m} = \frac{1}{2}\log \frac{1-e_{m}}{e_{m}}$, 它是 $e_{m}$ 的单调递减函数, 即误差越小的分类器该系数越大, 在集成时越重要.( 问:该系数为什么是这个形式 )
    • 更新训练数据集的权值分布 $w_{m+1, i} = \frac{w_{m,i}}{Z_{m}}exp(-\alpha_{m}y_{i}h_{m}(x_{i}))$. 其中 $Z_{m}$ 是归一化系数, 它使得 $W_{m+1}$ 称为一个概率分布. $Z_{m} = \sum_{i=1}^{N}w_{m,i}exp(-\alpha_{m}y_{i}h_{m}(x_{i})) $. 对于正确分类的样本, 下一轮的权值为 $w_{m+1,i} = \frac{w_{m,i}}{Z_{m}}exp(-\alpha_{m})$, 由于 $\alpha$ 是正的, 因此该权重在下一轮降低. 而错误的权值则会增加.
  • 根据前面得到的 M 个基本分类器, 构建它们的线性组合得到集成分类器: $H(x) = sign(f(x)) = sign(\sum_{m=1}^{M}\alpha_{m}h_{m}(x)) $.

为了防止过拟合, AdaBoost 还可以加入正则化项. 从上面流程中我们看出, AdaBoost 算法的核心包含两个: 调整数据点的权值分布 和 计算基本分类器的权重系数. 最后对这些分类器进行集成.

当AdaBoost 的基础分类器比较复杂时,AdaBoost 很容易陷入过拟合。但是当AdaBoost 的基础分类器比较简单时,AdaBoost 反而难以陷入过拟合。这也是为什么AdaBoost 的基础分类器经常选择使用树的原因。

AdaBoost 多分类

AdaBoost 实验法推广到多分类有两种算法: SAMME 算法和 SAMME.R 算法. 这里只介绍一些 SAMME 算法.

SAMME 算法大体上和 AdaBoost 算法一致, 不过模型输出的是多分类标签. 因此每个分类器的系数不再是 $\alpha_{m} = \frac{1}{2}\log \frac{1-e_{m}}{e_{m}}$. 现在后面加了一个 $\log(K-1)$ 即

因为系数 $\alpha_{m} \gt 0$, 因此有 $e_{m} \lt \frac{K-1}{K}$, 其余的没什么变化. 因此当 K=2 时 SAMME 算法就会退化为 AdaBoost 算法.具体的流程为

  • 初始化训练数据的权值分布
  • 对于每个分类器 $m = 1, 2, \dots, M$:
    • 根据当前权值分布 $W_{m}$ 学习得到基本分类器 $h_{m}$
    • 计算 $h_{m}$ 上的训练误差率 $e_{m} = \sum_{i=1}^{N}w_{m,i}I(h_{m}(x_{i}) \neq y_{i})$
    • 计算 分类器 $h_{m}$ 的系数 $\alpha_{m} = \frac{1}{2}\log\frac{1-e_{m}}{e_{m}} + \log(K-1)$
    • 更新训练数据的权值分布: $w_{m+1, i} = \frac{w_{m,i}}{Z_{m}}exp(-\alpha_{m}y_{i}h_{m}) $
  • 重复以上步骤, 得到 M 个基本分类器, 而后进行线性组合得到集成分类器:

AdaBoost 回归

AdaBoost 的回归问题可以用 AdaBoost R2 算法解决. 相比于标准 AdaBoost 算法, R2 算法的误差采用平方误差的形式. 分类器系数采用非对数形式(为什么?). 具体流程为

  • 初始化训练数据的权值分布
  • 对于每个分类器 $m = 1, 2, \dots, M$:
    • 根据当前权值分布 $W_{m}$ 学习得到基本分类器 $h_{m}$
    • 计算分类器 $h){m}$ 在训练集上的误差:

    • $ E_{m}$ 为误差绝对值的最大值, 以此对所有的回归误差实现归一化
    • 计算分类器 $h_{m}(x)$ 的系数 $ \alpha_{m} = \frac{e_{m}}{1-e_{m}}$
    • 更新训练数据的权值分布
      重复以上步骤, 得到 M 个基本分类器, 而后进行线性组合得到集成分类器 $H(x) = \sum_{m=1}^{M}(\ln\frac{1}{\alpha})h_{m}(x) $

提升树

提升树(Boosting Tree) 是以决策树为基本学习器的 Boosting 方法. 其中决策树采用二叉树作为基本学习器. 提升树可以表示为以决策树为基本学习器的加法模型(和AdaBoost 类似):

其中 $h_{m}$ 表示第 m 个决策树, $\Theta$ 为该决策树的参数, M 为决策树的数量. 决策树采用 前向分布算法, 每一步通过拟合残差或者残差的近似学习分类器 . 即 $ f_{m}(x) = f_{m-1}(x) + h_{m}(x, \Theta)$. 通过经验风险最小化确定 第 m 个决策树的参数 $\Theta_{m}$. 在回归问题中, 通常采用平方误差损失函数, 在分类问题中, 使用指数损失函数.

算法流程

  • 输入为训练数据集 $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N}) }, ~~~x_{i}\in R^{n}, ~~~y_{i}\in R $
  • 初始化 $f_{0}(x) = 0 $
  • 对于 $m = 1,2, \dots, M$:
    • 计算残差每个样本的 $r_{m,i} = y_{i} - f_{m-1}(x_{i}),~~~i = 1,2,\dots, N$. 构建训练残差 $ r_{m} = {(x_{1}, r_{m,1}), (x_{2}, r_{m,2}), \dots, (x_{N}, r_{m, N})}$. 此时我们学习器学习的目标不是 $y_{i}$ 而是残差.
    • 通过学习一个回归树来拟合残差 $r_{m}$, 得到学习器 $h_{m}$
    • 更新 $f_{m}(x) = f_{m-1}(x) + h_{m}(x, \Theta_{m})$
  • 得到回归问题的提升树 $ f_{M}(x) = \sum_{m=1}^{M}h_{m}(x, \Theta_{m})$

梯度提升树 GBT

在提升树算法中, 我们针对残差进行优化, 但当损失函数是一般函数时, 残差的表达就没那么明显了. 因此 Freidman 提出了梯度提升算法. 它的核心思想是 利用损失函数的负梯度在当前模型的值作为残差的近似值 , 从而拟合一颗回归树.

具体来说, 第 m 步的损失函数为 $L(y, f_{m}) = L(y, f_{m-1} + h_{m})$. 对它进行泰勒展开, 我们已知泰勒展开公式为

现在 $ f_{m-1}$ 对应 x, $h_{m}$ 对应 $\delta x$. 对展开取到一阶, 则有

移项可以看到

在优化 $L(y, f(x))$ 时, 根据梯度更新公式$\theta^{m+1} = \theta^{m} + \eta\delta L$, 有

而 $ f_{m} - f_{m-1} = h_{m} $. 移除常数项$\eta$ 得到

对于平方损失函数, 它等价于通常意义上的残差, $-\frac{\partial L(y, f_{m-1})}{\partial f_{m-1}} = 2(y-f_{m-1})$. 对于一般损失函数, 它是残差的近似. 不直接同残差而用负梯度代替的原因就是这个, 残差并不总是 $y-f_{m}$ 这种简单的形式, 当代有正则或者其他复杂的损失函数时, 残差的表达就没那么明显了. 而负梯度只要损失函数可导就可以用.

GBDT 与 GBRT 的算法流程一样, 只不过损失函数的形式不一样, 因此这里以 GBRT 为例说一下算法流程

  • 对于 $m = 1, 2, \dots, M$ :
    • 对于 每个数据点 $i = 1, 2, \dots, N$ 计算残差 $ r_{m,i} = -\frac{\partial L(y, f_{m-1})}{\partial f_{m-1}} $
    • 根据残差生成第 m 个学习器用到的数据集 ${(x_{1}, r_{1}), (x_{2}, r_{2}), \dots, (x_{N}, r_{N})} $
    • 利用该数据集拟合一颗树, 将空间划分为多个叶节点区域$R_{m,j}$
    • 对每个区域 $R_{m,j}$, 计算该区域的输出值
      , 即该值为使得损失函数最小的值作为该节点的输出值
    • 更新模型 $f_{m}(x) = f_{m-1}(x)\sum_{j=1}^{J}c_{m,j}I(x\in R_{m,j})$
  • 得到最终回归树 $ f_{M}(x) = \sum_{m=1}^{M}\sum_{j=1}^{J}c_{m,j}I(x\in R_{m,j}) $

模型可以通过增加正则化提升泛化能力, 增加方法是在模型更新时添加一个系数(学习率):

)实践表明, 一个小的学习率(小于0.1)可以显著提高模型的泛化能力, 如果学习率较大会导致预测性能出现较大波动.

还有一种正则化策略是控制叶节点样本个数, 若叶节点样本少于预设值, 则停止划分,.节点样本数是一个超参, 需要调试获得.

Freidman 还提出了一种叫随机梯度提升的方法来提高模型泛化能力. 它的核心思想是在每一轮迭代中, 使用的不是全部的数据集, 而是全部数据集的不放回随机采样, 采样占比是一个超参数, 一般来说在 0.5-0.8 之间会带来比较好的结果.

xgboost

xgboost 也是使用与提升树相同的前向分步算法. 区别是 xgboost 通过结构风险最小化来确定下一个决策树的参数, 即 拟合的目标不再是残差, 还多了正则项 , 公式表达为

其中 $\Omega(h_{m})$ 为第 m 个决策树的正则化项. 括号中是我们的目标函数 $mathcal{L}$. 在 GBT 中, 我们考虑了损失函数 的一阶展开, 并把一阶导数的负值即负梯度作为残差的近似, 并拟合它. 而 XGBoost 考虑了损失函数的二阶导数 . 为了表达方便, 我们先定义损失函数的各阶导数

则损失函数 L 的泰勒展开式保留到二阶有

注意区分 $h_{i}$ (二阶导数) 和 $h_{m}$ (模型输出).

先假设给定决策树的结构, 我们的优化目标是最小化目标函数, 因为我们前面说 xgboost 考虑了正则化项, 它用来限制决策树的复杂度. 一个可选的复杂度定义为

$w_{j}$ 为节点j 的输出值. $\gamma$, $\lambda$ 为非负系数, 分别控制叶节点个数和叶节点输出的绝对值的比重. 叶节点个数越多, 决策树越复杂. 叶节点输出的绝对值越大, 决策树越复杂. 复杂度的定义公式是一个经验公式, 可以根据具体问题取选择. 将该公式带入损失函数有

对于每个样本 $x_{i}$, 它必然会被分到树 $h_{m}$ 的某个节点. 定义划分到叶节点 j 的集合 为 $I_{i} = {i | q(x_{i}) = j} $, 节点 j 的输出值为 $w_{j}$, 因此上式可以整理成

上式我们发现最前面的求和符号变了, 这是因为我们现在不再是对每个数据点的求和, 而是针对每个节点. 节点内的导数(包含一阶和二阶导数)可以表示为节点内各样本点导数的和, 即 $\sum_{i\in I_{j}} g_{i}$. 因此我们可以定义节点内导数的和

因此损失函数可以进一步简化为

假设 $w_{j}$ 与 T, $G_{j}$, $H_{j}$ 无关, 则上式对 $w_{j}$ 求导并令导数为 0. 则得到模型输出值的最优解

. 忽略常数项, 将上式带入损失函数, 可以得到

假设 $w_{j}$ 与 T, $G_{j}$, $H_{j}$ 无关 其实意味着树的结构已知, 因此上式刻画了在已知树的结构的目标函数. 可是实际上我们并不知道树的结构, 那如何得到最佳的树结构使得目标函数全局最小呢?

一种方法是 对现有的叶节点加入一个分裂, 然后考虑分裂之后目标函数降低多少 , 若目标函数下降则可以分裂. 假设分裂后左节点的一阶导数和二阶导数为

, 右节点的为

. 则定义叶节点分裂的增益为

即分裂后左右子树的损失函数的负值相比于分裂前损失函数的负值下降了多少(很绕口, 其实就是损失函数前面有一个负号, 这里去掉了). 后面那个 $\lambda$ 表示分裂导致叶节点数增大1, 从而导致增益的下降. 若增益大于0 则可以分裂.

知道分裂方法后, 我们要做的就是对叶节点中所有可能分裂的节点做一次扫描, 然后计算每个分裂点的增益, 选取增益最大的分裂点作为本叶节点的最优分裂点(这个流程其实和其他分裂的一样, 只不过分裂标准不是信息增益那种).

对于连续值的情况, 可以对特征值进行聚合统计, 形成若干个桶. 而后仅仅将桶边界上的特征作为分裂点的候选. 具体分成多少个桶, 分桶的区间都是超参数, 需要仔细挑选.桶的划分一般有两种模式:

  • 全局模式: 在算法开始时, 对每个维度分桶一次, 后续的分裂都依赖于该分桶并不再更新. 优点是计算量小, 缺点是经过多次分裂后, 叶节点的样本可能在很多桶中都是空的(稀疏了)
  • 局部模式: 除了在算法开始时分桶, 每次拆分后都重新分桶. 优点是每次分桶后保证各同中的样本数量是均匀的, 缺点是计算量较大.

LightGBM

Bagging

Bagging 直接基于自助采样法(bootstrap sampling). 其基本步骤为: 给定包含 N 个样本的数据集, 先随机取出一个样本放入采样集中, 再把该样本放回原始数据集. 这样经过 N 次随机操作, 得到包含 N 个样本的采样集. Bagging 的基本流程为:

  • 经过 M 轮自助采样, 可以得到 M 个包含N 个训练样本的采样集
  • 基于每个数据集训练一个基学习器
  • 将这 M 个学习器进行线性组合, 得到集成模型

得到学习器后, 在使用时分类任务可以采取简单的投票法, 回归任务使用简单平均法得到模型输出.

从效果上来说, Bagging 和 Boosting 的区别为:

  • Bagging 主要关注降低方差(增强泛化能力), 它能平滑强学习器的方差, 因此它在非剪枝决策树, 神经网络等容易受到样本扰动的学习器上效果更明显.
  • Boosting 主要关注降低偏差(提升模型拟合能力), 它能将一些弱学习器提升为强学习器. 因此它在 SVM, KNN 等不容易受到样本扰动的学习器上效果更明显.

随机森林(Random Forest, RF)

RF 是 Bagging 的一个扩展变体, 它对 Bagging 做了点小改动:

  • Bagging 中基学习器的”多样性”来自于样本的扰动, 样本的扰动来自于对初始训练集的随机采样
  • RF 中的基学习器的多样性不仅来自样本扰动, 还有属性扰动. 即在决策树进行分裂时, 我们不再是使用全部的属性, 而是选取其中的一部分(k 个)作为候选属性, 而后选取符合条件的分裂点. 当 $k$ 等于全部属性时, 此时决策树的构建和传统的相同, 当 k 等于1时, 则随机选取一个属性进行划分. 一般建议 $k=\log_{2}n$ , n 为属性的数量.

随机森林的优点有:

  • 训练效率较高: 因为RF 使用的决策树只需要考虑所有属性的一个子集
  • 随机森林简单, 容易实现, 计算开销小
  • RF 的性能表现很好

集成策略

通过对多个学习器进行组合, 可以:

  • 单一学习器不一定能够得到最优解, 往往是众多有效模型中的一个, 而把多个有效模型进行组合后, 可以减小泛化能力不佳的风险
  • 学习算法可能陷入局部极小值, 多个学习器可以降低该风险
  • 多种算法结合, 扩大假设空间.

一般来说集成策略有三大类:

  • 平均法
  • 投票法
  • 学习法

平均法

平均法通常用于各种回归任务中, 可以分为:

  • 简单平均法: 即取各个模型输出的平均值, 每个学习器的权值都相同
  • 加权平均法: 各个学习器的权重是学出来的.

现实任务中, 数据集往往有限 或存在噪声, 因此对于规模较大的集成学习来学, 要学习的参数较多, 很容易出现过拟合. 因此有些时候简单平均法效果不一定弱于加权平均法. 一般来说, 当个体学习器间差距较大时, 适合用加权平均法. 个体学习器间性能相差不大时, 用简单平均法.

投票法

投票法常用语分类任务中:

  • 多数投票法: 若某个标记得到的票数过半, 则预测为该标记. 不过实际中可能所有标记都没过半, 因此该方法用的比较少.
  • 相对多数投票法: 选取得票最多的标记作为预测值(用的比较多)
  • 加权投票法: 类似于加权平均法, 权重也是学习得到的

学习法

在学习法中, 个体学习器的分类结果通过与另一个学习器进行下一轮训练. 此时个体学习器称为初级学习器. 用于组合的学习器称为次级学习器或者元学习器. 学习法典型的代表就是 stacking 集成算法.

stacking 算法首先从初始数据集训练出初级学习器. 然后将初级学习器的预测结果作为一个新的数据集用于训练次级学习器. 在这个新的数据集中, 初级学习器的输出被当做样本输入特征, 初始样本的标记仍被视为标记. 更简单来说, 就是次级学习器使用的数据集不是初始数据集$(x_{i}, y_{i})$, 而是初级学习器的输出 $h(x_{i})$ 和 对应标签组成的数据集 ${h(x_{i}, y_{i})}$.这样就像一个大的学习器, 被分成很多小的学习器, 其中每个小学习器分别训练, 但数据(特征)的流动是连续的, 即前一个的输出特征是后一个学习器的输入.

但直接使用初级学习器产生的训练集进行训练容易过拟合. 因此一般使用交叉验证, 使用训练初级学习器时未使用的样本来产生次级学习器的训练样本.

上图是一个 stacking 示例, 初级学习器采用 RF 或者 XGB. 次级用的 LR. 我们以 RF 那个为例, 首先我们对训练数据分为 5 分, 采用交叉验证, 即用其中的4 个作为训练集, 另一个作为验证集. 做 5 次, 将每次验证集的预测结果保留下来. 把它们组合起来(放在一起), 再结合对应的标签就是次级学习器的训练集了. 对于测试集, 在交叉验证的过程中的每一步, 都会对它进行一次预测, 将每次预测的结果保存下来取平均作为次级学习器的测试集. 有了训练集和测试集, 接下来正常学习 次级学习器 LR 就好了.

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章