Boosting 和 XGBoost 和 LightGBM 和其他

本文记录学习 Boosting 过程中的一些笔记。

集成学习和回归树

集成学习

Boosting 是集成学习中的一支，指的是由多个相关联的决策树联合决策，也就是说，下一棵决策树输入样本会与前面决策树的训练和预测相关，将弱学习器提升为强学习器的集成方法来提高预测精度。

与之对比的是Bagging（如 random foreast 随机森林）算法，即通过自助采样的方法生成众多并行式的分类器，通过“少数服从多数”的原则来确定最终的结果，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有关系。

迭代策略

贪心策略 + 二次最优化（损失函数不是二次函数泰勒展开）求回归树的参数：（1）选取哪个feature分裂节点；（2）节点的预测值。

停止迭代策略

（1）当引入的分裂带来的增益小于一个阀值时，类似预剪枝；

（2）当树达到最大深度时，树太深容易过渡学习局部样本导致 过拟合；

（3）当样本权重和小于设定阈值时（一个叶子节点样本太少了），同样防止过拟合

梯度提升

梯度提升（Gradient Boosting）。

首先需要明确，GB本身是一种理念而非一个具体的算法，其基本思想为：沿着梯度方向，构造一系列的弱分类器函数，并以一定权重组合起来，形成最终决策的强分类器。

那么这一系列的弱分类器是怎么样形成的呢？GBDT的做法是：每一棵树所学习的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。

回归树

回归树（Regression Decistion Tree）的运行流程与分类树基本类似，但有以下两点不同之处：

第一，回归树的每个节点得到的是一个预测值而非分类树式的样本计数，假设在某一棵树的某一节点使用了年龄进行分枝（并假设在该节点上人数>1），那么这个预测值就是属于这个节点的所有人年龄的平均值。
第二，在分枝节点的选取上，回归树并没有选用最大熵值来作为划分标准，而是使用了最小化均方差，即 $\frac{\sum_{i=1}^{n}{} (x_i-\bar{x} )^2}{n}$ 。这很好理解，被预测出错的次数越多，错的越离谱，均方差就越大，通过最小化均方差也就能够找到最靠谱的分枝依据。

GBDT

GB算法中最典型的基学习器是决策树，尤其是CART，正如名字的含义，GBDT是GB和DT的结合。要注意的是这里的决策树是回归树，GBDT中的决策树是个弱模型，深度较小一般不会超过5，叶子节点的数量也不会超过10，对于生成的每棵决策树乘上比较小的缩减系数（学习率<0.1），有些GBDT的实现加入了随机抽样（subsample 0.5<=f <=0.8）提高模型的泛化能力。通过交叉验证的方法选择最优的参数。因此GBDT实际的核心问题变成怎么基于 $\{(x_i, r_{im})\}_{i=1}^n$ 使用CART回归树生成 $\! h_m(x)$ ？

XGBoost

XGBoost是Gradient Boosting Machine的一个c++实现，并在原有的基础上加以改进，从而极大地提升了模型训练速度和预测精度。可以说，XGBoost是Gradient Boosting的高效实现。

XGBoost 的主要优化

在CART基分类器的基础上还支持线性分类器（gblinear），此时XGBoost相当于带 $L_1$ 和 $L_2$ 正则化项的Logistics回归（分类问题）或者线性回归（回归问题）
在目标函数里加入了正则项，用于控制模型的复杂度，防止过拟合。
传统的GBDT在优化时只用到一阶导数，XGBoost则对目标函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。
XGBoost工具支持自定义代价函数，只要函数可一阶和二阶求导。
支持并行化，选择最佳分裂点进行枚举的时候并行，同层级节点内选择最佳分裂点，候选分裂点计算增益用多线程并行。
针对缺失数据的算法，分别假设特征缺失的样本属于右子树和左子树，而且只在不缺失的样本上迭代，分别计算缺失样本属于右子树和左子树的增益，选择增益最大的方向为缺失数据的默认方向。
可实现后剪枝
交叉验证，方便选择最好的参数，early stop，比如你发现30棵树预测已经很好了，不用进一步学习残差了，那么停止建树。
列采样（column subsampling），随机森林的套路，不仅能降低过拟合，还能减少计算。
Shrinkage（缩减），XGBoost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。
xgboost还支持设置样本权重，这个权重体现在梯度g和二阶梯度h上，是不是有点adaboost的意思，重点关注某些样本