XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器，其更关注与降低基模型的偏差。XGBoost是一种提升树模型（Gradient boost machine），其将许多树模型集成在一起，形成一个很强的分类器。而所用到的树模型则是CART回归树模型。讲解其原理前，先讲解一下CART回归树。

一、CART回归树

　　CART回归树中定义树为二叉树，通过GINI增益函数选定最优划分属性。由于CART为二叉树，与其他决策树相比其在选择了最优分类特征之后，还需要选择一个最优的特征值划分点。比如当前树结点是基于第j个特征值进行分裂的，设该特征值小于s的样本划分为左子树，大于s的样本划分为右子树。

CART回归树实质上就是在该特征维度对样本空间进行划分，而这种空间划分的优化是一种NP难问题，因此，在决策树模型中是使用启发式方法解决。典型CART回归树产生的目标函数为：

因此，当我们为了求解最优的切分特征j和最优的切分点s，就转化为求解这么一个目标函数：

所以我们只要遍历所有特征的的所有切分点，就能找到最优的切分特征和切分点。最终得到一棵回归树。

二、XGBoost基本思想

　　XGBoost的核心思想与GBM一致，其在实现的过程中通过不断地添加新的树（基模型），不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，用来拟合上次预测的伪残差。当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值。

 

其中q(x)对应的是CART的结构，表示x对于某一个CART树的叶子节点位置$W_{q(x)}$表示输入x对于某棵CART树的分数。T是树中叶子节点的个数，每个$\mathrm{f}_k(x_i)$对于的是一个CART树，由树的结构q以及叶子节点值w确定。如下图例子，训练出了2棵决策树，小孩的预测分数就是两棵树中小孩所落到的结点的分数相加。爷爷的预测分数同理。

三、XGBoost原理 

　　了解一个学习器，主要是要去理解其损失函数，XGBoost损失函数定义为：

 

其中第一项为常规损失函数，第二项目为正则项目，用来限制模型的复杂度，降低过拟合的风险。正则化项同样包含两部分，T表示叶子结点的个数，w表示叶子节点的分数。γ、λ为参数分别控制CART树的个数、叶子节点的分数值。

XGBoost采用的也是加性模型的方式，形式化之后的损失函数如下图所示：

对于表达形式比较复杂，不易理解的函数我们可以尝试使用泰勒展开的技巧，注意到$f_t(xi)$对于的是泰勒展开的$\Delta{x}$项目（泰勒展开不清楚的话em....），展开之后的损失函数如下所示：

其中$g_i$为$l(y_i,\wildtilde{y}^{t-1})$的一阶导，$h_i$为其二阶导数