人工智能机器学习之 Boosting 算法

广义的偏差（bias）描述的是预测值和真实值之间的差异，方差（variance）描述距的是预测值作为随机变量的离散程度。Boosting 是个非常强大的学习方法, 它也是一个监督的分类学习方法。它组合许多“弱”分类器来产生一个强大的分类器组。一个弱分类器的性能只是比随机选择好一点，因此它可以被设计的非常简单并且不会有太大的计算花费。将很多弱分类器结合起来组成一个集成的类似于 SVM 或者神经网络的强分类器。boosting 如何确定弱的规则？可以应用不同分配下的基础的（机器）学习算法，每个算法都会生成一个弱规则，这是一个迭代的过程，多次迭代后，Boosting 算法可以将它们组合成一个强大的决策规则。为了选择正确的分配方式，可以遵循下面几个步骤：步骤 1：所有分布下的基础学习器对于每个观测值都应该有相同的权重步骤 2：如果第一个基础的学习算法预测错误，则该点在下一次的基础学习算法中有更高的权重步骤 3：迭代第 2 步，直到到达预定的学习器数量或预定的预测精度。最后，将输出的多个弱学习器组合成一个强的学习器，提高模型的整体预测精度。Boosting 总是更加关注被错误分类的弱规则。

Boosting 算法的底层可以是任何算法，关于 boosting 算法，我们需要知道其中最有名的 3 个算法：AdaBoost(Adaptive Boosting)GBDTXGBoost

AdaBoost 在每一轮如何改变训练数据的权值或概率分布？提高那些被前一轮弱分类器错误分类样本的权值，并降低那些被正确分类的样本的权值。经过一轮的权值加大后，后一轮的弱分类器就会更关注那些没有被正确分类的样本。持续下去，分类问题便会被一系列弱分类器“分而治之”。

如何将弱分类器组合成一个强分类器？    即弱分类器的组合，AdaBoost采取加权多数表决法，具体的所，就是加大误差率小的弱分类器的权值，使其在表决中起更大的作用，另一方面，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

Gradient Boosting 它主要的思想是，每一次建立模型是在之前建立模型损失函数的梯度下降方向。这句话有一点拗口，损失函数(loss function)描述的是模型的不靠谱程度，损失函数越大，则说明模型越容易出错（其实这里有一个方差、偏差均衡的问题，但是这里就假设损失函数越大，模型越容易出错）。如果我们的模型能够让损失函数持续的下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度（Gradient)的方向上下降。Gradient Boosting 是非常经典而又重要的提升方法，他与 AdaBoost 一样都是讲弱分类器合成强分类，但是其大致区别有:Gradient Boosting 通过残差来变量的改变错误分类的权重,而 AdaBoost 就真的直接去修改分类错误的训练权重了 Gradient Boosting 接入的分类器一般完整的决策树居多，但是 AdaBoost 一般使用二层决策树

XGBoostXGBoost 是 “Extreme Gradient Boosting”的简称，是 GBDT 的一种高效实现，XGBoost 中的基学习器除了可以是 CART（gbtree）也可以是线性分类器（gblinear）。在 GBDT 思想下，XGBoost 对其中的步骤进行了具体实现。变化 1：提高了精度 – 对 Loss 的近似从一阶到二阶。。传统 GBDT 只使用了一阶导数对 loss 进行近似，而 XGBoost 对 Loss 进行泰勒展开，取一阶导数和二阶导数。同时，XGBoost 的 Loss 考虑了正则化项，包含了对复杂模型的惩罚，比如叶节点的个数、树的深度等等。通过对 Loss 的推导，得到了构建树时不同树的 score。具体 score 计算方法见论文 Sec 2.2。变化 2：提高了效率 – 近似算法加快树的构建。XGBoost 支持几种构建树的方法。第一：使用贪心算法，分层添加 decision tree 的叶节点。对每个叶节点，对每个 feature 的所有 instance 值进行排序，得到所有可能的 split。选择 score 最大的 split，作为当前节点。第二：使用 quantile 对每个 feature 的所有 instance 值进行分 bin，将数据离散化。第三：使用 histogram 对每个 feature 的所有 instance 值进行分 bin，将数据离散化。

    变化3：提高了效率 – 并行化与cache access。XGBoost在系统上设计了一些方便并行计算的数据存储方法，同时也对cache access进行了优化。这些设计使XGBoost的运算表现在传统GBDT系统上得到了很大提升。

Xgboost 和 GBDT 的区别传统 GBDT 以 CART 作为基分类器，xgboost 还支持线性分类器，这个时候 xgboost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。传统 GBDT 在优化时只用到一阶导数信息，xgboost 则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost 工具支持自定义代价函数，只要函数可一阶和二阶求导。Xgboost 在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的 score 的 L2 模的平方和。从 Bias-variance tradeoff 角度来讲，正则项降低了模型的 variance，使学习出来的模型更加简单，防止过拟合，这也是 xgboost 优于传统 GBDT 的一个特性。Shrinkage（缩减），相当于学习速率（xgboost 中的 eta）。xgboost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把 eta 设置得小一点，然后迭代次数设置得大一点。（补充：传统 GBDT 的实现也有学习速率）列抽样（column subsampling）。xgboost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是 xgboost 异于传统 gbdt 的一个特性。缺失值的处理。对于特征的值有缺失的样本，xgboost 可以自动学习出它的分裂方向。xgboost 工具支持并行。boosting 不是一种串行的结构吗?怎么并行的？注意 xgboost 的并行不是 tree 粒度的并行，xgboost 也是一次迭代完才能进行下一次迭代的（第 t 次迭代的代价函数里包含了前面 t-1 次迭代的预测值）。xgboost 的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost 在训练之前，预先对数据进行了排序，然后保存为 block 结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个 block 结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以 xgboost 还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

XGBoost 优势：显式地将树模型的复杂度作为正则项加在优化目标公式推导里用到了二阶导数信息，而普通的 GBDT 只用到一阶允许使用列抽样(column(feature)sampling)来防止过拟合，借鉴了 Random Forest 的思想，sklearn 里的 gbm 好像也有类似实现。实现了一种分裂节点寻找的近似算法，用于加速和减小内存消耗。节点分裂算法能自动利用特征的稀疏性。样本数据事先排好序并以 block 的形式存储，利于并行计算 penalty function Omega 主要是对树的叶子数和叶子分数做惩罚，这点确保了树的简单性。支持分布式计算可以运行在 MPI，YARN 上，得益于底层支持容错的分布式通信框架 rabit。

总结一般来说，Gradient Boosting(GB)方法适用于异质化数据。即，若你的数据集全由图片数据构成或者全由视频数据构成之类的，我们称其为同质化数据，这时使用神经网络往往会有更好的表现。但对于异质化数据，比如说数据集中有 user gender，user age，也有 content data 等等的情况，GB 方法的表现往往更好。GB 方法比神经网络的入门门槛更低，使用起来也更简单。