XGBoost_原理
XGBoost_ 原理
1. 说明：
难了不会，会了不难，你明白了，觉得这还用说？不明白，跳步之后，似懂非懂。本篇是我对论文《XGBoost: A Scalable Tree Boosting System》的阅读笔记，用大白话解释 xgboost 原理，学霸请跳过，懒得看公式的也请跳过。
2. 第一步：整体误差（重点：整体视角）
整体误差指的是 XGBoost 模型训练完成之后，将训练集中所有实例代入模型，用以下函数（总误差 L()）衡量模型的好坏：
左边是训练集所有实例的误差之和，i 指每个实例，y^是预测值，y 是实际值，而 l() 是衡量 y’与 y 差异的方法，比如 RMSE。左边比较好理解，就是说训练一个模型，最好能对于所有的实例都做出与真实值相似的预测。
右边是正则项，它的用途就是防止模型过拟合，比如说一个模型，一共 400 个实例，模型做了 400 个叶节点，与实例一一对应，它的泛化就很差，所以应该尽量简化模型，正则项在第四步详述。
3. 第二步：计算 t 棵树时的误差（重点：从第 t-1 棵到第 t 棵）
梯度下降决策树是由多棵树组成的模型。假设它由 t 棵树组成，误差是：
还是看左边，计算 n 个实例误差的总合，y 是实际值，而此时的预测值是，之前树的预测值 y’(t-1)，加上第 t 棵树的预测值 ft()，ft() 就是第 t 棵树所做的工作。
4. 第三步：泰勒公式（重点：从始至终计算的都是预测的误差 L()）
泰勒公式：在已知函数在某一点（x0 点）的各阶导数值的情况之下，泰勒公式可以用这些导数值做系数构建一个多项式来近似函数在这一点的邻域中的值。
其中 Rn(x) 是余项。
简单举个例子，我不知道 x 住哪儿 f(x)，但知道 x 附近的 x0 住哪儿 f(x0)，所以我先找到它，然后根据他俩距离的远近 x-x0，以及他俩位置的相对方向（f() 的导数），推出 x 大概住哪儿。
换种写法，求点 x 附近，距离是 delta x 的点的 f()，只考虑两阶导数：
本文中所求的函数 f() 是误差函数 L()，代入进去是：
这里的 delta x 指的是 x 的细微变化，回想第二步的公式中，我们每训练一棵树 ft() 都相当于对上一步结果的微调，于是有：
也就是说，知道第 t-1 棵树预测结果与真实值的误差 L(x)，这个误差函数的一阶导 L’(x)，二阶导 L’’(x)，又知道第 t 棵相对于第 t-1 棵做了什么微调 ft()，于是估计出：加入第 t 棵树之后的预测值与真实值的误差。就有了以下公式：
其中：gi 和 hi 分别是误差函数 l() 对第 t-1 棵预测值的一阶导和二阶导。
简单地说：一共 t 棵树的模型，它的误差是第 t-1 棵树构造模型的误差函数 l()，加上误差函数一阶导 gi 乘第 t 棵树的贡献 ft()，再加误差函数的二阶导 hi 乘第 t 棵树贡献的平方。
5. 第四步：公式右侧正则项（重点：得分 w）
先来看看最普通的单棵决策树，当训练完模型后，预测时把 x 代入树，顺着条件判断的分支，最后落入哪个叶节点，结果就是该叶节点的值。
而 Boost 决策树是多棵决策树，它对 x 的预测结果是，将 x 代入每棵决策树，得到多个叶节点的值 w，将其结果累加得到预测值（最基本的逻辑）。这里各个叶节点的值 w 简称得分。
正则项是为了防止模型太复杂过拟合，公式如下：
其中 T 是树中的叶结点个数，w 是叶节点的得分，γ和λ是可调节的参数，在整体 L() 计算公式中，w 越大误差 L 越大 (w 不均匀)，树的叶子越多 L 也越大，为求得最小的 L，最终在树的复杂度和准确度之间取得平衡。
6. 第五步：以实例为单位变为以节点为单位累加（重点：转换视角）
此时我们的焦点在 ft(x) 上，要分析 L 与 ft 的关系，第 t-1 棵树误差是个常数项，先忽略不看，可写成:
每一个 xi 是一个实例的条件，它经过第 t 棵决策树 ft() 的处理后，会落在某个叶节点上，得到该叶节点的得分 w，即：ft(xi)->wj，因此可将 ft(xi) 转换为 wj，代入，得到以下公式：
其中 T 是树的叶节点个数，需要注意的是其中 Ij，它指的是落入树中节点 j 的所有训练实例。把右侧展开后加入，得到：
7. 第六步：w 如何取值使预测误差最小（重点：求极值）
这是个极值问题，求当误差函数 L() 为最小值时，wj 的取值，求极值即导数为 0 的点，简单推导如下（写得不全，领会精神）：
规范的写法是：
公式的含义是：叶节点的合理取值 w 取决于四个值，第一：落在该点的实例 Ij 都有哪些，第二/三：将这些实例代入之前 t-1 棵决策树预测后，误差的方向一阶导和二阶导，第四是系数λ，人工设置。其原理是，如果之前的树把该点预测大了，则在本树的 w 把它调小点。
把计算好的 w 代入误差公式，简单推导如下（写得不全，领会精神）：
规范的写法是：
用语言描述公式：误差最小的条件是，对所有（T 个）叶节点，代入落入该节点的实例，用之前 t-1 棵树的误差的导出和正则项，即可计算出第 t 棵树的误差。
此处我们看到，计算第 t 棵树的误差时，不需要计算出该树每个叶节点的 w，只需把计算 w 的素材 h,g,Ij,λ代入即可。
8. 第七步：在分裂决策树时计算误差函数（重点：细化到每一次分裂）
此步骤关注的不是整棵树，而是每次分裂，最基本的贪婪算法是：生成树时，从根节点开始，遍历所有属性，遍历所有属性的可能取值作为分裂点，计算该分裂点左子树样本集合 ll 和右子树样本集合 lr 的误差，加起来和不分裂的误差相比，即可判断分裂是否合理。
注意这时的误差 L 计算的不是全树的误差，而权限于与本次分裂相关的实例在分裂前后的误差对比。
再啰嗦一句：误差大小取决于 w；w 值又取决于落入该叶节点的实例，之前的决策树对它们预测值的误差方向；实例有哪些又取决于怎么分裂，所以只要知道了怎么分裂，以前之前树的信息，就能算出分裂后的误差变化。
9. 参考
1)《XGBoost: A Scalable Tree Boosting System》
https://pan.baidu.com/s/1skT2eeh