XGBoost
和GBDT一样，XGBoost也是一种基于CART树的Boosting算法，让我们来看一下如何通俗的去理解XGBoost。
先简单的回想一下，在我们之前提到过的GBDT中是怎样用很多棵树去做预测的？很简单，我们给了每棵树不同的训练数据，得到多种不同的结果，最终我们把这些结果相加作为最终的预测值就可以了。
XGBoost的定义
举一个简单的例子，我们要预测一家人对电子游戏的喜好程度，考虑到年轻和年老相比，年轻更可能喜欢电子游戏，以及男性和女性相比，男性更喜欢电子游戏，故先根据年龄大小区分小孩和大人，然后再通过性别区分开是男是女，最终给每个人在电子游戏上的喜爱程度进行打分，如下图所示：
我们把上图中得到的树记为tree1，同样我们可以根据日常是否使用电脑来进行新一次的打分，如下图所示：
这样我们就训练好的两棵树tree1和tree2，我们把两棵树的评分结果相加就是最终的结果，如上图中，男孩的得分是2+0.9=2.9，爷爷的得分是-1-0.9=-1.9。
看完了这个例子，你可能会疑惑，这个过程和GBDT不是一样的吗？其实在本质上XGBoost和GBDT的差异就在于目标函数的定义上，别急，继续往下看。
XGBoost的目标函数
看懂了上节中的例子，不难说出XGBoost的核心就是不断的添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。用数学来表示这个模型，如下所示：
这里的K就是树的棵树，F表示所有可能的CART树，f表示一颗具体的CART树，这个模型由K棵CART树组成。有了模型之后，我们的问题也就来了，模型的参数是什么？优化参数的目标函数是什么？
先不考虑参数的问题，我们先来明确一下我们的目标。
显然，我们的目标是要使得树群的预测值
尽量接近真实值 
而且要有尽量大的泛化能力。
所以从数学的角度看，目标就变成了一个泛函数的最优化问题，我们把目标函数简化成如下的形式：
这个目标函数分为两部分：损失函数和正则化项。且损失函数揭示训练误差（即预测分数和真实分数的差距），这里的正则化项由K棵树的正则化项相加而来，也可以说**正则化定义复杂度。**损失函数我们都接触过，树的正则化又是怎样的形式呢，我们后面再做说明。
XGBoost的训练
上节中我们得到了XGBoost的损失函数是加法的形式，我们不妨使用加法训练的方式分步骤对目标函数进行优化，首先优化第一棵树，接下来是第二棵…直至K棵树全被优化完成。优化的过程如下所示：
在第t次迭代的时候，我们添加了一棵最优的CART树f t ,那么这棵树是怎么得到的呢？其实就是在现有的t-1棵树的基础上，使得目标函数最小的那棵CART树，如下所示：
根据化简后的式子，我们知道里面的损失函数，也知道里面的正则项，那么constant又是哪来的呢？（这里是不是有很多问号），先别急，马上就会揭晓答案。
由于目标函数中的y i是真实值，而且通常真实值都是已知的，所以我们不去考虑，对其他的项我们来看一下目标函数和泰勒二阶展开式的对应关系：
得到目标函数的近似式：
如果是MSE则结果如下：
这也就解释了我们在将MSE作为损失函数的时候，为什么会得到一个奇怪的目标函数。同样这个过程也能够让我们对不同损失函数下的目标函数进行一个近似化简。
到这里我们的目标函数就确定了，但是还有最后的一个小东西我们还没有介绍，下面再让我们来说一下正则项。
XGBoost的正则项
这里我们所说的正则项，也可以看作是树的复杂度。
我们先对CART做一个新的定义，式子及结构表示如下：
最终表示成下图所示的形式：
这里出现了两个参数γ 和λ，我们可以设定他们的值去调节树的结构，显然γ 越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大，λ 越大也是希望获得结构越简单的树。
XGBoost的最终形态
我们得到了目标函数，又得到了正则化的表达形式，不妨把他们组合在一起得到最终的结果表达：
这样加了正则项的目标函数里就出现了两种累加：
进一步我们可以接着对式子进行简化，定义：
简化后的式子如下：
然后把最优解带入得到：
拓展：我们再来换个角度理解一下w j ∗
假设我们分到j这个叶子结点上的样本只有一个，则有如下的形式：
此时第一个括号中表示的内容可以看作是学习率，第二个括号中表示的内容可以看作是反向梯度。
XGBoost的最优树结构
有了评判树的结构好坏的标准，我们就可以先求最佳的树结构，这个定出来后，最佳的叶子结点的值实际上在上面已经求出来了。
对于我们最开始的是否喜欢电子游戏的例子，最简单的树结构就是一个结点的树，我们可以计算出这棵单结点树的好坏
，假设我们现在想按照年龄将这棵单节点树进行分叉，我们需要知道：
1、按照年龄分是否有效，也就是是否减少了obj的值；
2、如果可分，那么以哪个年龄值来分。
我们按照年龄进行排序，找出所有的切分点，对于每一个切分点我们去衡量切分的好坏。示例图和计算方式如下表示：
扫描结束后，我们就可以确定是否切分，如果切分，对切分出来的两个节点，递归地调用这个切分过程，我们就能获得一个相对较好的树结构。
注意： xgboost的切分操作和普通的决策树切分过程是不一样的。普通的决策树在切分的时候并不考虑树的复杂度，而依赖后续的剪枝操作来控制。xgboost在切分的时候就已经考虑了树的复杂度，就是那个γ参数。所以，它不需要进行单独的剪枝操作。
问题小结
至此，我们的XGBoost的原理就全都说通了，下面再来看几个通常会遇到的问题：
1.obj中的constant是怎么来的？
文中我们还留了一个问题没有解决，那就是constant具体是怎么来的，让我们来看一下复杂度（正则项）的迭代过程：
这样就很清晰的可以看出所谓的常数，其实就是我们前t-1棵树的复杂度加和。
2.XGBoost为什么用泰勒展开？
XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。简单的说：使用二阶泰勒展开是为了xgboost能够自定义loss function。
3.XGBoost如何寻找最优特征？是有放回还是无放回的呢？
XGBoost在训练的过程中给出各个特征的评分，从而表明每个特征对模型训练的重要性。
XGBoost利用梯度优化模型算法, 样本是不放回的，想象一个样本连续重复抽出,梯度来回踏步，这显然不利于收敛。
XGBoost支持子采样, 也就是每轮计算可以不使用全部样本。
