原文链接

AdaBoost

简单介绍

AdaBoost是基于boosting的思想，通过多个弱分类器的线性组合来得到强分类器，训练时重点关注被错分的样本，准确率高的弱分类器权重大。

更深一步的介绍

他不改变所给的训练数据，而是不断改变训练数据权值的分布，使得被误分类的数据在后一轮的分类中得到更大的关注。
同时采用加权多数表决的方法，加大分类误差率小的分类器的权值，使其在最后的表决中起更大的作用，减小分类误差率较大的弱分类器的权值，使其在最后的表决中起较小的作用。所有弱分类器的权值 之和并不为1，是通过最后结果的符号来决定实例的类别，该结果的绝对值表示分类的准确度。
Adaboost还有另外一种理解，既可以认为其模型是加法模型、损失函数为指数函数、学习算法为前向分布算法的二类分类学习方法。
加法模型就是多个基函数线性组合得到的模型
前向分布算法：对于加法模型，从前往后，每一步只学习一个基函数及其系数，而不是一次性学习所有的基函数，从而简化优化的复杂度。
函数函数是根据Adaboost算法特点推导而来的。

GBDT

简单介绍

GBDT是基于boosting的思想，串行地构造多棵树来进行数据的预测，它是在损失函数所在的函数空间中做梯度下降，即把待求的决策树模型当作参数，每轮迭代都去拟合损失函数在当前模型下的负梯度，从而使得参数朝着最小化损失函数的方向更新。

更深一步的介绍

GBDT可以看作是AdaBoost的一个推广，AdaBoost是通过错分数据点来识别问题，通过调整错分数据点的权重来改进模型，GBDT是通过负梯度来识别问题，通过负梯度来改进模型，实际上，负梯度绝对值大的样例同样会在之后的训练中受到更大的关注，因为它造成的损失更容易在最后的损失函数中占很大的比重，因此，需要更多地偏向于减小损失。这也是GBDT和AdaBoost相似的一个点，而相比AdaBoost，Gradient Boosting可以使用更多类型的损失函数。
最常见的损失函数是平方损失函数，square loss的优点是便于理解和实现，它的负梯度就是残差，而其他损失函数的负梯度只能看作残差的近似值，它的缺点在于对于异常值它的鲁棒性较差，因此会常用 absolute loss或Huber loss来代替。

Random Forest

简单介绍

随机森林算法背后的思想是群体智慧的体现，它通过随机的行采样（bagging）和列采样(feature bagging)构造不同的训练集，建立一个决策树森林，利用加权平均方式或多数表决的方式得到最后的预测结果，能够并行学习，对噪声和异常数据具有很好的过滤作用，因此有广泛的应用。

更深一步的介绍

随机森林的采样(bagging)和列采样(feature bagging)都是为了减小模型之间的相关性使基学习器变得不通过从而减小集成模型的方差（相比于单棵不随机树），因此随机森林的单棵树都会采用很深的决策树，并不进行剪枝操作，以减小每棵树的偏差，这使得每一棵树就是一个精通于某一个窄领域的专家（因为我们从全部特征中选择部分来让每一棵决策树学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看它，最终通过投票或平均得到结果，这也是群体智慧的体现。

XGboost

简单介绍

xgboost是梯度提升树的一种高效系统实现，是对GBDT进一步的改进，包括对代价函数进行了二阶泰勒展开，在代价函数里加入了正则项，借鉴了随机森林的列采样方法，支持并行计算等。

更深一步的介绍

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

机器学习算法中GBDT和XGBoost的区别有哪些？

LightGBM

简单介绍

LightGBM是一个实现GBDT算法的分布式高效框架。它通过leaf-wise分裂方法进行决策树的生成，通过基于直方图的算法寻找特征分割点，并支持并行学习，能够更高效的处理大数据，也得到越来越广泛的应用。

更深一步的介绍

要减少训练的复杂度，可以通过减少特征量和数据量来实现，即从行和列两个角度来减少数据，同时要尽可能少的影响最后的精度。在LightGBM中，就是这样做的，对应着GOSS和EFB。

GOSS(Gradient-based One-Side Sampling)

GBDT虽然没有数据权重，但每个数据实例有不同的梯度，根据计算信息增益的定义，梯度大的实例对信息增益有更大的影响，因此在下采样时，我们应该尽量保留梯度大的样本（预先设定阈值，或者最高百分位间），随机去掉梯度小的样本。此措施在相同的采样率下比随机才阿姨那个获得更准确的结果，尤其是在信息增益范围较大时。

Exclusive Feature Bundling(EFB)

通常在真实应用中，虽然特征量比较多，但是由于特征空间十分稀疏，许多特征几乎是互斥的（例如许多特征不会同时为非零值，像one-hot），EFB通过捆绑互斥的特征，并将捆绑问题归约到图着色问题，通过贪心算法求得近似解，以减少特征量。
对于树的分裂方法，它通过leaf-wise分裂产生比level-wise分裂更复杂的树，能够实现更高的准确率。虽然这样有时候会导致过拟合，但可以通过设置max-depth参数来防止过拟合的发生。（每一次的生长都是选取分裂增益最高的节点，而不是对一层中的所有节点都进行分裂）。
其次，它使用基于直方图的算法，将连续的特征值分桶（buckets）装进离散的箱子（bins），并通过直方图做差加速计算兄弟节点的直方图，能够加速训练过程，并实现更少的内存占用。
另外，它支持并行学习，包括特征并行和数据并行。

  • 特征并行的主要思想是不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点（mapreduce思想）
  • 数据并行则是让不同的机器先在不同的记录集合上构造直方图，然后进行全局的合并，组后在合并的直方图上寻找最优分割点。

它还支持直接输入类别特征，在对离散类别特征分裂时，每个取值都当作一个桶，分裂时的增益算的是“是否属于类别”的增益，对于类别特征的操作类似于one-hot编码。

CatBoost

简单介绍

CatBoost是Category和Boosting的缩写，最大的特点就是可以直接处理类别特征，不需要任何预处理来将类别转换为数字。
具体请参考：CatBoost原理及实践

对比分析

xgb是对gbdt的优化改进

  1. 目标函数中加入了正则项来控制模型的复杂度，替代原来的剪枝方法。
  2. 利用了one-hot编码等情况中的特征稀疏性。（仅对特征值为非缺失值的样本的特征进行遍历）
  3. 支持列抽样（同random forest）。
  4. 数据事先排序并按block结构保存，有利于并行计算（树的生成还是串行的，这里说的并行计算指并行计算各个特征的增益或基尼系数）。除此以外，xgb还通过一种可并行的近似直方图算法来高效生成候选的分割点。

  5. 对损失函数进行了优化，gbdt只用到了其一阶导数信息，而xgb同时用到其一阶导与二阶导。

    lgb是在xgb基础上进一步改进

  6. 内存需求小：xgb使用基于pre-sorted的决策树算法，而lgb使用基于histogram的决策树算法。histogram算法占用的内存很小；pre-sorted需要两倍数据大小的内存空间，一半用于数据(float32)，一般用于存放排好序的索引，而histogram不需要存放索引，且特征值只需要存放离散后的值，用uint8即可，故内存需求仅为per-stored的1/8.

  7. 计算速度快：决策树算法的主要操作包括“寻找分割点”与“数据分割”两步，pre-sorted算法和histogram算法在“寻找分割点”上的时间复杂度是一致的；但是在“数据分割”上histogram要快，hisgogram所有特征共享一张索引，而pre-sorted一个特征对应一张索引，若集合level-wise,pre-sorted也可以共用一张索引，但是会带来很多随机访问的问题，速度仍不及histogram。另外，histogram算法还减少了计算分割点增益的次数。
  8. 通信代价小：histogram算法的通信代价远小于pre-sorted，可用于分布式计算。但是，histogram不能找到很精确地分割点，训练误差不如pre-sorted算法，可以说是牺牲一定精度来换取速度。需要指出的是，这种粗狂的分割相当于自带正则效果，所以测试集的误差两种决策树算法差距不大。

参考链接

关键两点差别

1.决策树算法

XGBoost使用的是pre-sorted算法，能够更精确的找到数据分割点；LightGBM使用的是histogram算法，占用的内存更低，数据分割的复杂度更低。

2.决策树生长策略

XGBoost采用的是level(depth)-wise生长策略，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。
LightGMB采用leaf-wise生长策略，每次从当前所有叶子中找到分裂增益最大（一般也是数据量最大）的一个叶子，然后分裂，如此循环；但会生长出较深的决策树，产生过拟合。因此，LightGBM在leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。