集成学习：Boosting（序列化方法）
1.GBDT
GBDT可以用于回归问题（Loss：平方误差损失函数），也可以用于分类问题（Loss：指数损失函数），区别在于使用损失函数的不同。
1.1 GBDT思想
| GBDT：分类、回归 | Adaboost：分类 |
|---|---|
| 用当前模型拟合数据的残差来确定下一个决策树（个体学习器）应该学习什么。 | 通过重赋权法，每次训练，重点学习训练集中的某些数据（上一次训练时学的不够好的数据）。 |
| 从 y 上入手，得出残差（residual），专门学习 | 从 x 上入手，赋予权重（weight），重点学习 |
| 通过梯度提升算法优化损失函数，推导输出模型 | 通过前向分布算法优化损失函数，推导输出模型。 |
1.2 GBDT算法
梯度提升（gradient boosting）算法：提升树算法中，当损失函数是平方误差或指数函数时，优化是相对简单的。对于一般损失函数（优化Loss时，残差无法直接得出，也就无法直接去拟合残差），可以类比最速下降法，使用梯度来进行优化（用负梯度去拟合残差，负梯度就是残差的近似值）。
f(x)或g(x)是由（高维）空间中的无数的点构成，可以看成是一个无穷维的向量，对它们求偏导，就类似于对参数向量求偏导。
梯度提升：回归树推导
利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
梯度提升：分类问题推导
我们的目标是找到α**和f(x)。
通过以下推导找出来的f(x)就是Adaboost中训练出的个体分类器；α**就是Adaboost中的个体分类器权重。Adaboost其实也是在做梯度下降。
2.XGBoost
2.1目标函数分析
目标函数优化为两部分组成：
，其中，
是经验风险（表示模型和训练数据的契合程度），
是结构风险（表示模型自身的性质，例如：正则化，衡量模型的复杂程度）。
【举例】：
对于Ridge regression：
对于Lasso regression：
对于Logistic regression：
提升树的目标函数
对于集成学习中的提升树（boosting tree），假设一共有K棵小树，每棵小树表示为
，则有：
， 其中
为决策树的函数空间。
损失函数通用定义为： 
，
【问题】具体来说，如何定义损失函数和每棵小树的复杂性？
对于决策树，损失的定义可以关联：信息增益、基尼指数等；树的复杂性定义可以关联：剪枝、树的深度约束、叶子节点的权重等。总的来说，CART是用于分类任务，还是回归任务，取决于目标函数如何定义。
提升方法中，在第t轮的学习中，前(t-1）个基学习器已经学到，则有：
，我们需要知道如何训练第t棵小树
！
根据泰勒展开公式：
，
令 
，
令 
，即上一轮学习中对损失函数求的一阶导和二阶导；
则有
由于最优化目标函数和常数项无关，简化目标函数为：
【问题】对需要学习的每棵小树的定义？
每棵小树也是一个函数映射，输入x，先根据树结构找到x应落入的叶子节点，再取出这个节点上的分数。每棵树就是由叶子节点上的分数组成的向量。
，
其中q代表树的结构，q(x)是query出输入x落入哪个叶子节点（输出叶子节点的序号），w则是该叶子节点上的权重（输出叶子节点的分数值）。
【问题】如何定义每棵小树的复杂性？
每棵小树的复杂性
的定义不止一种，因为有多个考虑因素。
如果考虑到叶子节点的数量以及叶子节点的权重，则有：
（注：加入
是为了求导方便，并不影响优化。）
【问题】目标函数的最终形态？
根据以上定义，提升树（第t轮学习）的目标函数变为：
这是T个二次函数的输出之和。
叶子节点将原本的数据集分为多个部分，因此统计所有输入样本对应决策树输出的分数值以及损失函数导数值，就等同于统计所有T个叶子节点上的数据集对应的分数值和损失函数求导；
表示划分到叶子节点 j 中的数据集。
对于一元二次函数 
，连续可微时，通过二阶导数（函数凸凹性）求极值：
，当
时，函数为凹函数，有极小值，在极小值处一阶导数为0，
所以：
理解：
为上一轮（即t-1轮）学习中得到的模型对应的损失函数对第 j 个叶子节点中的数据集对应的输出依次求一阶导数的累加之和，
为上一轮（即t-1轮）学习中得到的模型对应的损失函数对第 j 个叶子节点中的数据集对应的输出依次求二阶导数的累加之和。
其中，
表示决策树结构的好坏（分数越低，结构越好）；
表示模型复杂度。
2.2XGBoost算法
单棵决策树的搜索算法
- 【树结构】枚举这棵决策树所有可能的树结构；
- 【结构分数】计算树结构的结构分数，分数越低，结构越好；例如，有3个叶子节点的单棵决策树：
- 【叶子权重】根据分数找到最好的树结构，并计算叶子权重w。
【问题】一棵树的结构有非常多种，枚举并计算结构分数不可取。如何解决？
贪婪（Greedy）学习：衡量收益
在实际中，不可能枚举所有可能的树结构，可以贪婪的学习决策树：
- 从深度0开始；
对树的每个叶子节点进行分裂（split），期望分裂之后的损失更小，根据损失的变化得到收益（gain）：
对某个属性上的划分，计算划分的收益（Gain），确定最佳的划分点。
- 对每个节点，枚举所有特征/属性；对每个特征，根据特征值排序，按照贪婪学习，计算收益，确定所有特征中，最佳的划分特征和划分点。
时间复杂度：如果样本的特征数量为d，每一层中对每个特征需要n次划分来决定最佳的划分点，则当生成一棵深度为K的树时，总体的时间复杂度为
，每一层的时间复杂度为
。
剪枝
根据目标函数计算的收益（Gain）中，
代表训练的损失（模型能力），γ 代表正则化（模型复杂度）。
当损失值小于正则化值时，收益（Gain）为负！为了避免收益为负数，可以：
- 提前停止分裂（split）节点。当最佳分裂方案出现负收益时，就停止分裂；但假如不停止，后期分裂可能不会为负，仍然有正收益；模型有欠拟合的风险。
后剪枝。先将树生成为最大深度，然后循环的对分裂后产生负收益的节点进行剪枝。
提升树算法
迭代生成每棵小树，每次迭代前，求导计算
；- 使用贪婪（Greedy）学习，生成一棵小树，使得目标函数优化之后的损失最小；
将小树
加入到上一轮学习的模型中，得到当前学习的模型：
，其中
是步长或者缩减（shrinkage），通常赋值为0.1左右。（这意味着不需要在每一步都做全局的优化，有效的防止了过拟合。）
2.3GBDT与XGBoost区别
【个体学习器】GBDT以CART树作为基学习器，XGBoost还支持线性分类器，这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归（分类）或者线性回归（回归）。
- 【目标函数设计】XGBoost在代价函数中加入了正则项，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，防止过拟合。
- 【学习方法】GBDT在优化的时候只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，得到一阶和二阶导数（高阶的泰勒展开更好的拟合的原本的函数！）。
- 【学习方法】XGBoost在进行完一次迭代时，会将叶子节点的权值乘上缩减（shrinkage）系数，相当于学习速率，主要是为了削弱每棵树的影响，让后面有更大的学习空间。（GBDT也有学习速率）。
- 【学习方法】XGBoost借鉴了随机森林的做法，支持列抽样，不仅防止过拟合，还能减少计算。
- 【学习方法】对缺失值的处理。对于特征的值有缺失的样本，XGBoost还可以自动学习出它的分裂方向。
- 【算法实现】XGBoost工具支持并行。XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
若有收获，就点个赞吧
0 人点赞
