XGBoost核心笔记贪心学院

Bagging和Boosting对比

老师的PPT中对比了 Bagging 和 Boosting 两种常用的集成学习方法。

• Bagging：利用多个过拟合的弱学习器来获得更好的效果。典型的算法有随机森林。
  （请了很多专家回答问题，一起讨论争论）
• Boosting：利用多个欠拟合的弱学习器来获得更好的效果。典型的算法有GBDT/GBRT，Adaboost，XGBoost和LightGBM。（请了一群小学生回答问题）

Bagging

像是随机森林，这种bagging系的算法，它们的思想是训练多个模型每个模型去预测一个结果，然后对这些结果进行加权平均得到最终的预测结果。

Boosting

boosting是基于残差的训练，每个模型在上一个模型预测结果与真实值的残差的基础上再进行训练，达到迭代次数或设定的阈值后停止，最终将各个模型的结果进行求和得到。

提升树-基于残差的训练

在介绍XGBoost之前，还要介绍一下提升树的概念，其实提升树的算法思想是跟XGBoost相同的。


就像上面的三幅图像展示的那样，模型2在模型1的残差基础上进行拟合预测，而模型3则在模型2的基础上进行，最终的结果就像下面的图所示的那样是多个模型预测结果的和。

XGBoost

学习路径

XGBoost的介绍流程将会像图片展示的那样进行，算法的核心也就是这四个步骤。在第一步构建目标函数后，后面的三步则更倾向于是对目标函数的优化。由于构造的目标函数并不能够像逻辑回归那样是连续的，可以直接使用SGD进行优化，因此在算法的第二步使用了泰勒级数的方法去展开目标函数，将一些常量给提取分离出来，能够简化计算；在第三步中，则是考虑如何将树的结构进行参数化，带入到目标方程；第四步则是要查找结构最优的一棵树，而在查找的过程中采用贪心的算法进行，整个查找的过程是一个NP—hard问题。

目标函数构建

我们的预测一定是相加的。

i表示第i个样本，k表示第k棵树
第二颗树来预测第i个样本 第二颗树来预测第i个样本 ······ 第k颗树来预测第i个样本

我们最终的预测结果是k棵树预测结果之和，而目标函数的组成有两部分，第一部分是损失函数（loss function），表示真实值与预测值的差距，具体的损失函数可以选用MSE、交叉熵等，在这篇博客中不做详细介绍；第二部分是penalty /regularization用来控制模型的复杂度，是在控制树的复杂度，是一个惩罚项，经典的示例是正则化。树的复杂度可能会涉及到树的叶节点数、深度、叶节点值等，但具体如何去参数化实现我们还不太清楚，这个会在后面进一步讲解。

叶节点值越大，说明这颗树的复杂度越高。

我们要预测的值是1000，每颗树要预测的值在100-200之间，这个时候我们只需要10棵树，或是说不到10棵树就能凑够1000了。

当我们降低复杂度的时候，比方说100-200变成了20-30，这个时候我们需要50棵树。

化简目标函数

有了目标函数以后，我们还没有好的办法直接对它进行求解，还需要进行化简。

当我训练第k棵树，1到k-1棵树是已知的。


上面的推导，我们做的主要工作是将前k-1个模型的相关表示和第k个模型给分开，这样当我们在训练第k个模型时前k-1个的相关表示便是常量，能够简化运算。

观察上面经过简化的目标函数，我们现在不知道是 f k ( x i ) f_{k}(x_{i}) fk(xi)和 Ω ( f k ) \Omega (f_{k}) Ω(fk)这两个函数如何表达，这将会在下面两节中进行介绍。

使用泰勒级数近似目标函数

泰勒展开在我们大学的高等数学中就已经学过了，它的主要思想是用多项式的形式去近似一些复杂函数，使得在实际工程能够求解得到算数解。

在我们学习优化算法时，梯度下降算法就是利用了一阶的泰勒展开，而牛顿法则是使用的二阶泰勒展开，所以在实际的使用中，牛顿法比梯度下降收敛得更快。

尽管我们对目标函数进行了化简，但直接对目标函数进行求解，运算的复杂度会非常高，所以我们选择对目标函数进行二级泰勒展开，提高模型的训练速度。

当训练第k棵树的时候， g i g_{i} gi和 h i h_{i} hi是前k-1棵树传递给训练第k棵树时的信息

接下来我们要做的事情就是把 f k ( x i ) f_{k}(x_{i}) fk(xi)和 Ω ( f k ) \Omega(f_{k}) Ω(fk)用参数的方式表示，然后把参数找出来。

树结构的参数化

重新定义一棵树

这里详细介绍一下，各个符号的含义

• $w$是一个向量，存储的是叶子节点的值
• $q(x)$表示样本x的位置，即它属于哪一个叶节点，在公式中用作表示ω的下标
• 再需要定义一个 I j I_{j} Ij，是一个集合，表示落在j节点的样本

I j I_{j} Ij用作解决函数中$q(x)$为$w$的下标问题(参数的下标也是一个函数，处理起来非常麻烦)，这种表示方式并不标准化， I j I_{j} Ij就用来将这个公式给标准化。

树的复杂度

树的复杂度 = 叶节点个数 叶节点值

T是叶节点个数数，γ和λ控制权重，是树的叶节点数更重要呢，还是叶节点的值更重要呢？若严格控制叶节点个数γ要调大一些，若严格控制叶节点值（值越小越好）λ要调大一些。

新的目标函数

这样，将上面得到的表达式带入到我们化简得到的目标函数中，得

树的形状已知的条件下，我们可以得到新目标函数的最优解

上面红框部分依旧是常数，我们用 G i G_{i} Gi和 H i H_{i} Hii表示，得

其实，得到的这个函数本质上是一个一元二次函数，因此在 w i w_{i} wi=-b/2a时，能够取到整个函数的最值

这样就得到了第k棵树的最优解。

第k棵树的形状可能有很多个，知道第k棵树的形状（其中一种）我们可以立马求出目标函数的最优解（其中一个）。

现在的问题变成怎么从这么多树的形状中去寻找其中一种树的形状让目标函数最小。

贪心寻找最优结构树

寻找树的形状

利用brute-force search的方法把书的所有结构罗列出来，是指数级别的复杂度，显然是不可取的，还是得回到贪心的法则上。

寻找的思路与决策树的构建是一致的，都是去最大程度降低系统的混乱度，比如说，ID３算法每次寻找某个特征去分割节点时，依据的标准就是让信息增益最大，也就是让整个系统的混乱度降低。

在这里采用的不是熵，而是Obj的值,每次分割节点都是依据Obj值的增量尽可能的大。

寻找最好的Split

以这个方式不断去构造我们的树

这篇好文章是转载于：学新通技术网