Woody Tells

Never Settle

0%

集成学习概述

发表于 更新于 分类于 ，
常用的集成算法总结与分析

为什么要用集成学习

  1. More flexible to interpret

  1. Reduce misclassification rate

两个常用的集成学习框架

  1. Bagging
    • random forests
  2. Boosting
    • Adaboost
    • GBDT
    • XGBoost

Bagging

基本思想：通过重置抽样（有放回抽样）在给定的数据集D上抽出m个大小和D一样的数据集，分别用来训练m个分类器，然后将m个分类器的结果通过某种方式形成最终的分类结果。

自助采样法

注意：样本集原本有n个样本，就采样n次。这样样本集中会包括63.2%的原始样本（每个样本都有63.2%的概率会在n次采样中被选中），剩下的36.8%用作对泛化性能的包外估计（out-of-bag estimate）

方差分析

由于多个分类器参与了最终结果的生成，所以方差相对于单个分类器是有所变化的，准确来说，方差要小于单个分类器的方差。

$$
\hat f_{bag}(x) = \frac{1}{M}\sum^M_{m=1}{\hat f_m(x)}
$$

$$
\begin{align}
Var(\hat f_{bag}(x))=& \frac{1}{M^2}[\sum^M_{m=1}Var(\hat f_m(x))+\sum_{t\neq m}Cov(\hat f_t(x),\hat f_m())]\
=& \frac{1}{M^2}[M\sigma^2+M(M-1)\rho(x)\sigma^2]\
=& \frac{1}{M}\sigma^2 + \frac{M-1}{M}\rho(x)\sigma^2\
=& \rho(x)\sigma^2+\frac{1-\rho(x)}{M}\sigma^2
\end{align}
$$

其中，由于$\rho(x)=\frac{Cov(\hat f_t(x),\hat f_m(x))}{\sigma_\theta \cdot \sigma_m}$，而$\sigma_t=\sigma_m=\sigma$
$$
\begin{align}
\rho(x)=\frac{Cov(\hat f_t(x),\hat f_m(x))}{\sigma^2} \
Cov(\hat f_t(x),\hat f_m(x)) = \rho(x)\sigma^2
\end{align}
$$
由于在$Var(\hat f_{bag}(x))$计算式中，将$f_t(x)$与$f_m(x)$前后位置做了区分，故一共有$m(m-1)$对。

在此，暂且将上面的T认为是M。

可见：

  1. M越大，方差越小。
  2. pearson相关系数越小，方差也越小。

所以我们在bagging中引入random sampling，就是为了减小相关系数。

decision tree and bagging tree

决策树分两种：分类树和回归树

其中，分类树以信息论中的启发函数构造决策树，回归树以最小平方误差作为启发函数构造决策树。

以下是最小二乘回归树的构造算法：

其中，c1和c2分别是划分的两个区域对应的y的估计值（也就是输出值），通过最小化估计值与真实值之间的差值来构造决策树，启发信息就是这个差值。


随机森林

  • 随机森林就是带随机采样的决策树/回归树森林。
  • 随机性体现在采样和特征集合选择的随机性

结合策略

针对数值型输出

  1. 简单平均法
  2. 加权平均法

针对类别型输出

  1. 绝对多数投票法（某类别超过一半的票）
  2. 相对多数投票法（某类别票数最多）
  3. 加权投票法

学习法

这是一种比较独特的结合策略，通过串行学习来将不同的模型结果结合起来。

典型代表是stacking，这种结合策略和boosting颇有点神似。

基本思路是先从初始数据集中训练出初级学习器，然后基于初级学习器结果生成一个新的数据集用于训练次级学习器。

  • 将每个点的T个初级学习器结果作为输入特征，该点的原始标签作为新数据集的标签得到新数据集。
  • 在新数据集上使用次级学习算法对次级学习器进行学习。

boosting

模型框架

AdaBoost

  • 推导过程见《机器学习》
  • 其中基分类器权重α_m 是通过添加第m个分类器hm之后最小化指数损失函数得来的
  • 理想的新分类器hm可以纠正Gm-1的全部错误，基于这样的推导得到了样本分布更新公式，在接受带权样本的算法中直接就是样本的权重，不接受带权样本就直接re-sample。
  • 理解样本分布更新公式：将所有错分样本的权重增加，使得下一波分类器更加关注这些样本。
  • 上述算法并不很完善，建议看以下《机器学习》的adaboosting算法及推导（实在懒得做搬运工了）。

adaboost的思想就是通过不断添加分类器来纠正之前分类器的错误，这是通过在新的样本分布上使用新分类器最小化损失函数得来的。而提升树是很直观的对残差进行建模，不断添加回归树来补充残差。

损失函数

Adaboost应该使用指数损失函数或者二项式对数似然损失函数（本质上也使用了指数损失），并且后者效果往往还比指数损失要好一些。

关于指数损失函数

GBDT

boosting tree

提升树包括梯度提升树都是通过残差拟合进行boosting的，与标准的boosting相比，权重更新体现在残差越大的样本，其在回归树中的结果就越大，只不过标准的boosting还需要将更新权重的样本重新进行训练，而提升树直接就得到了相应的叶节点区域，直接影响了结果，直接在上一轮学习器结果的基础上，加上残差进行校正，不停的迭代，学习器残差就会越来越小。

算法流程


算法解析

  1. 初始化就是求一个只有一个叶节点区域的树，对于回归树而言，就是所有的样本点都拟合成一个值。
  2. 使用负梯度代替残差，这样更加通用。
  3. 生成新的数据集（xi, rmi）作为生成第m棵回归树的训练数据，得到j个叶节点区域，对每一个叶节点区域计算回归目标值，也就是得到j个回归目标值。
  4. 将j个针对残差的回归目标值乘以示性函数加到之前得到的提升树结果中。
  5. 最终的回归树用法：得到x在M棵回归树中的叶节点区域目标值，进行累加，其实就是一步一步的将残差进行补充。
  6. 提升树类算法就是通过不断向结果中添加残差来对结果进行校正。

正则化技巧

  1. shrinkage ：每次更新，在残差拟合结果上乘以正则化系数
  2. 下采样： 每次更新，都是在训练集的一个子集上进行的

XGBoost

损失函数

$$
L=\sum^{n}{i=1}l(y_i,\hat y_i)+\sum_k\Omega(f_k)
$$
其中，第t棵树生成：
$$
\begin{align}
L^{(t)}=&\sum^{n}{i=1}l(y_i,y_i^{(t)})+\Omega(f_t)\
=&\sum^{n}{i=1}l(y_i,y_i^{(t-1)}+f_t(x_i))+\Omega(f_t)\
二阶泰勒展开\Rightarrow\ \ \simeq&\sum^n{i=1}[l(y_i,y_i^{(t-1)})+g_if_t(x_i)+\frac{h_i}{2}f^2_t(x_i)]+\Omega(f_t)
\end{align}
$$
由于$l(y_i,y_i^{(t-1)})$对$f_t$的优化无影响

另$L^(t)=\sum^n_{i-1}[g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i)]+\Omega(f_t)$

将同一叶节点区域的样本点合并
$$
\begin{align}
L^{(t)}=&\sum^T_{j=1}[(\sum_{i\in I_j}g_i)f_i(x)+\frac{1}{2}(\sum_{i\in I_j}h_i)f_j^2(x)]+\gamma T+\frac{\lambda}{2}\sum^T_{j=1}f_j^2(x)\
=&\sum^T_{j=1}[(\sum_{i\in I_j}g_i)f_i(x)+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)f_j^2(x)]+\gamma T
\end{align}
$$
另$G_j=\sum_{i\in Ij}g_j \ \ \ \ \ H_j=\sum_{i\in I_j}h_i$
$$
L^{(t)}=\sum^T_{j=1}[G_jf_j(x)+\frac{1}{2}(H_jj+\lambda)f_j^2(x)]+\gamma T
$$
构造出关于$f_i(x)$的一元二次方程，解得
$$
\begin{align}
f_j(x)=&-\frac{G_j}{H_j+\lambda}\
\hat L^{(t)}=&-\frac{1}{2}\sum^T_{j=1}\frac{G_j^2}{H_j+\lambda}+\gamma T
\end{align}
$$
其中，$g_i=\frac{\partial l(y_i,y_i^{t-1})}{\partial ly_i^{t-1}}\ \ \ \ \ \ \ \ h_i=\frac{\partial^2 l(y_i,y_i^{t-1})}{(\partial y_i^(t-1))^2}$已知

新的$T$个叶子节点值可由$f_j(x)=\frac{G_j}{H_j+\lambda}$得到。

  • 简而言之，GBDT使用最速下降法，这里使用牛顿法进行优化。
  • 同样的，都是在已有的学习器基础上添加新的学习器以校正其效果，根据公式可以看到GBDT类似于最速下降法优化学习器，而XGBoost类似于牛顿法优化学习器，二者都是对学习器结果的直接校正，某些情况下可以认为是残差，但是准确来说，就是损失函数关于学习器的负梯度变形。

ps：牛顿法

分裂准则


综合以上，就是利用得到的目标函数进行启发式分支，然后得到的叶子节点的值有公式给出。

缺失值的处理

在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。

在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。

如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。


  • 可以看到，最外层遍历k从1到m是在遍历所有m个特征。
  • 内层是将第k个特征所有无缺失值的样本按照特征k的值进行排序，然后遍历分裂，寻找最优分裂点。
  • 以第一个内层for循环为例，先指定了left的G和H，然后用全集的G和L减去了Left的，所有k特征缺失的点就被划分到了right子树。

近似算法

对于连续型特征值，当样本数量非常大，该特征取值过多时，遍历所有取值会花费很多时间，且容易过拟合。

因此XGBoost思想是对特征进行分桶，即找到l个划分点，将位于相邻分位点之间的样本分在一个桶中。在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。

从算法伪代码中该流程还可以分为两种，全局的近似是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部近似就是在具体的某一次分裂节点的过程中采用近似算法。

正则化

XGBoost还提出了两种防止过拟合的方法：

  1. Shrinkage
  2. Column Subsampling。

Shrinkage方法就是在每次迭代中对树的每个叶子结点的分数乘上一个缩减权重η，这可以使得每一棵树的影响力不会太大，留下更大的空间给后面生成的树去优化模型。

Column Subsampling类似于随机森林中的选取部分特征进行建树。其可分为两种，

  • 一种是按层随机采样，在对同一层内每个结点分裂之前，先随机选择一部分特征，然后只需要遍历这部分的特征，来确定最优的分割点。
  • 另一种是随机选择特征，则建树前随机选择一部分特征然后分裂就只遍历这些特征。

一般情况下前者效果更好。

优点

之所以XGBoost可以成为机器学习的大杀器，广泛用于数据科学竞赛和工业界，是因为它有许多优点：

  1. 使用许多策略去防止过拟合，如：正则化项、Shrinkage and Column Subsampling等。
  2. 目标函数优化利用了损失函数关于待求函数的二阶导数
  3. 支持并行化，这是XGBoost的闪光点，虽然树与树之间是串行关系，但是同层级节点可并行。具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行。训练速度快。
  4. 添加了对稀疏数据的处理。
  5. 交叉验证，early stop，当预测结果已经很好的时候可以提前停止建树，加快训练速度。
  6. 支持设置样本权重，该权重体现在一阶导数g和二阶导数h，通过调整权重可以去更加关注一些样本。

总结

在这里把boosting框架分个类：

  • adaboost是一类，这一类通过更新样本权重来训练新的分类器
  • 还有一类是boosting tree、GBDT和xgboost，通过梯度或者残差来不断修正结果。