https://www.zhihu.com/question/269929168?sort=created
先说结论，拟合的是概率值。
XGBoost是GBDT的升级版，下面用GBDT来说明处理分类问题时，每一轮迭代的是什么。
XGBoost和GBDT均是基于CART回归树，对GBDT来说，当预测值为连续值时，计算预测值与真实值之间距离的平方和，均方误差(MSE)是最常用的回归损失函数，此时负梯度刚好是残差，当预测值为离散值，或者说处理分类问题时，拟合的也是‘负梯度’，只是要转一道弯。
这道弯是将预测值和真实值转换为类别的概率，迭代过程就是让预测概率不断接近真实概率。
对数损失logloss 常用于评估分类器的概率输出，对数损失通过惩罚错误的分类，实现对分类器准确度(Accuracy)的量化。 最小化对数损失基本等价于最大化分类器的准确度。为了计算对数损失，分类器必须提供对输入的所属的每个类别的概率值，不只是最可能的类别。
下面以一个简单二分类为例，选取损失函数为logloss：
[图片上传失败...(image-e5c779-1587638268216)]
其中：
[图片上传失败...(image-9362bd-1587638268216)]
代入后可得：
[图片上传失败...(image-822803-1587638268216)]
负梯度在下图可见：
</noscript>
以一个简单的数据集来说明第一步和第二步拟合的是什么。
</noscript>
Yi的取值是0,1，其中0和1亦可以表示样本取正值的真实概率，第一步所有样本未分裂，是一个树桩，让损失函数最小，初始化可得：
[图片上传失败...(image-7c1107-1587638268216)]
= [图片上传失败...(image-15b72e-1587638268216)]
=0.088
第一棵树，当m=1时，计算负梯度 [图片上传失败...(image-c6b696-1587638268216)]
= [图片上传失败...(image-ce4b70-1587638268216)]
可得：
</noscript>
接着，会以 [图片上传失败...(image-cace9f-1587638268216)]
为目标，拟合一颗树。
xgboost是时下热门的机器学习算法，在面试和竞赛中出现的频率非常高，但网上却没有一篇能够完全讲清楚的文章，因此，本文旨在用尽量少的公式，将xgboost讲清楚，明白，透彻。
xgboost是Boost（提升）算法家族中的一员，Boost根本思想在于通过多个简单的弱分类器，构建出准确率很高的强分类器。简单地来说，Boost（提升）就是指每一步我都产生一个弱预测模型，然后加权累加到总模型中，可以用于回归和分类问题。如果每一步的弱预测模型生成都是依据损失函数的梯度方向，则称之为梯度提升(Gradient boosting)，这样若干步以后就可以达到逼近损失函数局部最小值的目标。
boosting集成学习，由多个相关联的决策树联合决策，什么叫相关联，举个例子，有一个样本[数据->标签]是[(2，4，5)->4]，第一棵决策树用这个样本训练得预测为3.3，那么第二棵决策树训练时的输入，这个样本就变成了[(2，4，5)->0.7]，也就是说，下一棵决策树输入样本会与前面决策树的训练和预测相关。其中，0.7是模型预测和样本标记的差，称为残差。我们每次要学习的目标是上次学习的残差，直到残差小到满足我们的要求或其他终止条件。这个残差就是一个加预测值后能得真实值的累加量。
上面的例子，如果第二次直接预测得到0.7，并不一定好，因为每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。换句话说我们思想不完全信任每一个棵残差树，我们认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，只有通过多学几棵树才能弥补不足。
与之对比的是random forest（随机森林）算法，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有啥毛线关系。
xgboost本质上就是k个CART树，k是一个正整数。
CART树也叫分类与回归树，是一种决策树，既能做分类任务也能做回归任务。分类树的输出是样本的类别， 回归树的输出是一个实数（连续型变量）。
回归树的运行流程与分类树基本类似，但有以下两点不同之处：
对于回归问题，我们常用的损失函数是MSE（均方误差），即：
对于分类问题，我们常用的损失函数是对数损失函数：
前面提到，xgboost是具有k个CART树的集成学习算法，那么问题来了，我们应该怎么得到这k个树，k又是多少呢？（注意：不是随机得到k个树，是一个一个来，后一个依赖于前一个）
在我们一颗接着一颗树的构建过程中，我们的目标是：预测误差尽量小，叶子节点尽量少，节点数值尽量不极端。第一个目标很清晰，而第二个目标的原因是因为树的复杂度越低，泛化能力越强，在后面我们会知道叶子节点数量是树的复杂度计算中的一个考量，叶子节点数越多，树越复杂。节点数值尽量不极端指的是某棵树对一个样本的预测值相对于其它树对这个样本的预测值相差比较大，比如某个样本label数值为4，那么第一个回归树预测3，第二个预测为1；另外一组回归树，一个预测2，一个预测2，那么倾向后一种，为什么呢？前一种情况，第一棵树学的太多，太接近4，也就意味着有较大的过拟合的风险。
生成决策树：决策树算法相信大家都比较熟悉了，还不清楚的读者请先了解一下决策树算法。在xgboost中，生成决策树时，划分属性的方式如下：
为了更好的解释xgboost算法，我们必须定义一些公式了。
首先是模型的预测：
模型的目标函数：
综上，我们可以将损失函数用以下函数表示：
但是，损失函数一定是二次函数吗？如果不是，就泰勒展开成二次，简单粗暴。
它背后的思路就是在损失函数上执行梯度下降，然后用基学习器对其进行拟合。当梯度为负时，我们称它为伪残差，因为它们依然能间接帮助我们最小化目标函数。
建树的过程中，在以下情况下完成这棵树的创建：
（1）当引入的分裂带来的增益小于一个阀值的时候，我们可以剪掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思。
（2）当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，树太深很容易出现的情况学习局部样本，过拟合。
（3）当样本权重和小于设定阈值时则停止建树。
1）将树模型的复杂度加入到正则项中，来避免过拟合，因此泛化性能会好于GBDT。XGBoost的正则项会惩罚具有多个叶子节点的树结构。
2）损失函数是用泰勒展开式展开的，同时用到了一阶导和二阶导，可以加快优化速度。
3）和GBDT只支持CART作为基分类器之外，还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化。
4）引进了特征子采样，像RandomForest那样，这种方法既能降低过拟合，还能减少计算。
5）在寻找最佳分割点时，考虑到传统的贪心算法效率较低，实现了一种近似贪心算法，用来加速和减小内存消耗，除此之外还考虑了稀疏数据集和缺失值的处理，对于特征的值有缺失的样本，XGBoost依然能自动找到其要分裂的方向。
6）XGBoost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能，其次在进行节点分裂时，计算每个特征的增益，最终选择增益最大的那个特征去做分割，那么各个特征的增益计算就可以开多线程进行。
3 求解的时候, 对于每一轮迭代 t， 假设前面已经有了 (t-1)*K 颗树，分别对于 t-1 颗树对 K 个类别的预测。现在求的树。 用 L 对求导即可
4 具体的求导过程见 https://github.com/dmlc/xgboost/blob/release_0.72/src/objective/multiclass_obj.cc
这个文件，但是奇怪的是： 二阶导数乘了一个2， 不知道为啥。。。
h = fmax(2.0f * p * (1.0f - p) * wt, eps)
基于如下的考虑：
https://homes.cs.washington.edu/~tqchen/data/pdf/GBCRF-AISTATS15.pdf
related :
https://github.com/dmlc/xgboost/issues/1825
简单而言： 在对 f(x + z) = f(x) + z f'(x) + 0.5 z^2 f''(x) + o(x^2)
展开的时候， min ( f(x) + z f'(x) + 0.5 z^2 f''(x)) 不一定minize 了 f(x+z)
因为 f(x) + z f'(x) + 0.5 z^2 f''(x) 不一定比 f(x +z) 小， 优化它没有用
相反 f(x) + z f'(x) + z^2*f''(x) 则优化了 f(x+z) 的上界限， 间接求到最优解释。
以上只针对 multi-loss 有效， 在 multi-loss 中 f''(x) 必定 >0, 其余的场合不一定适合
