由前述内容可知，XGBoost是由多棵决策树（即CART回归树）构成的，那么多棵决策树是如何协作的呢？此时便用到了Boosting技术。Boosting的基本思想是将多个弱学习器通过一定的方法整合为一个强学习器。在分类问题中，虽然每个弱分类器对全局的预测准确率不高，但可能对数据某一方面的预测准确率非常高，将很多局部预测准确率非常高的弱分类器进行组合，即可达到全局预测准确率高的强分类器的效果。

AdaBoost

AdaBoost算法很好地继承了Boosting的思想，即为每个弱学习器赋予不同的权值，将所有弱学习器的权重和作为预测的结果，达到强学习器的效果。对于分类问题，AdaBoost首先为每个训练样本赋予一个初始权值$ω_{i}（i=1,2,…,n）$，每轮对一个弱分类器进行训练，其次将预测结果与样本的类别对比，提高预测错误的样本的权值，降低预测正确的样本的权值；然后计算该分类器的分类误差率，通过分类误差率计算该分类器的权值α，分类误差率越小，权值越大，反之越小；进行下一轮训练得到下一个分类器，如此直至满足停止条件。假设共得到了m个分类器，对应的权值为$α_{i}（i=1,2,…,m）$，则最终分类结果由这m个分类器通过加权投票决定。权值越大的分类器发挥的作用越大，反之越小。AdaBoost算法是一种精确度很高的算法，它可以用各种类型的学习器作为自己的子学习器，将其由弱学习器提升为强学习器。

Gradient Boosting

Gradient Boosting是Boosting思想的另外一种实现，由Friedman于1999年提出。Gradient Boosting与AdaBoost类似，也是将弱学习器通过一定方法的融合，提升为强学习器。与AdaBoost不同的是，它将损失函数梯度下降方向作为优化目标。因为损失函数用于衡量模型对数据的拟合程度，损失函数越小，说明模型对数据拟合得越好，在梯度下降的方向不断优化，使损失函数持续下降，从而提高了模型的拟合程度。
那么我们来看看模型训练的过程。

$$F_{0}(x)=arg \min_{\gamma}(\sum_{n-1}^{N} \frac{1}{2} (y-\gamma)^{2}) \tag{1.1}$$

通过训练一个常数使得所有样本的损失函数最小，每个模型学习之前都计算损失函数的梯度方向。

$$-\frac{\partial L(y,F(x))}{\partial F(x)}=y-F(x) \tag{1.2}$$

偏导数表示损失函数梯度方向。在第一轮的训练中，模型$h_{1}(x)$以$y-F_{0}(x)$为目标值进行学习，就是学习真实值与$F_{0}(x)$的残差，再通过损失函数最小化找到最优的y，由此可以得到$F_{1}(x)=F_{0}(x)+y_{1}h_{1}(x)$.直到模型$F_{M}(x)$.
每次子模型学习的都是前面所有子模型的预测值之和与真实值之间的残差，每轮训练都可以使整体模型的预测值更趋近于真实值，从而使模型最终达到较好的预测效果。

算法第1步初始化一个常数作为初始模型。在第2步中，每一轮均在前面训练的基础上训练一个新的子模型h（x）。第2步①计算损失函数的负梯度，将其作为残差；第2步②训练一个子模型h（x），以拟合第2步①中的残差；第2步③通过线性搜索找到最优γ_{m}，使得损失函数最小。最后，经过M轮训练更新模型，第3步输出最终模型。

Gradient Tree Boosting

Gradient Tree Boosting是Gradient Boosting应用最为广泛的一种实现，它以决策树作为子模型，其中最具代表性的以CART作为子模型。Gradient Tree Boosting主要具有如下优势
·可以有效挖掘特征及特征组合；
·模型具有更好的泛化能力；
·能够达到较高的预测准确率。

Gradient Tree Boosting算法和Gradient Boosting类似，区别只在于Gradient Tree Boosting子模型为树模型。

该算法与Gradient Boosting算法的不同之处在于第2步②，Gradient Tree Boosting算法通过拟合一棵回归树去拟合负梯度，终端区域可以理解为叶子节点。在第2步③生成新的回归树时，对于每个终端区域均计算一个$γ_{jm}$。

XGBoost中的Tree Boosting

首先我们来看xgboost的目标函数

$$obj=\sum_{i=1}^{n} L(y_i, \vec{y_i}) +\sum_{k=1}^{K} \Omega(f_{k}) \tag{1.3}$$

目标函数Obj由两项组成：第一项为损失函数，用于评估模型预测值和真实值之间的损失或误差.第二项为正则化项，用来控制模型的复杂度，正则化项倾向于选择简单的模型，避免过拟合
其中正则化的定义为

$$\Omega(f)=\gamma T + \frac{1}{2} \lambda ||w||^{2} \tag{1.4}$$

第一项$\gamma T$通过叶子节点数以及系数控制树的复杂度。值越大目标函数越大，从而抑制模型的复杂度。第二项为L2正则项，用于控制叶子节点的权重。
Gradient Tree Boosting采用的方法是计算目标函数的负梯度，子模型以负梯度作为目标值进行训练，从而保证模型优化的方向。XGBoost也应用了Gradient Tree Boosing的思想，并在其基础上做了优化。

目标函数近似

我们需要找打一个最优的f(x)使得目标函数最小，但是对于公式中的目标函数，用传统办法很难在欧式空间内进行优化，因此xgboost采用的近似的方式解决。

$$obj=\sum_{i=1}^{n} L(y_i, y^{s-1}+f_{s}(x_i))+ \Omega(f_{s}) \tag{1.5}$$

s表示第s轮训练。

XGBoost引入泰勒公式来近似和简化目标函数。泰勒公式是一个用函数某点的信息描述其附近取值的公式，如果函数曲线足够平滑，则可通过某一点的各阶导数值构建一个多项式来近似表示函数在该点邻域的值。

$$obj=\sum_{i=1}^{n} [L(y_i, y^{s-1}) +g_{i} f_{s}(x_i))+\frac{1}{2} h_{i} f_{x}^{2}(x_i)]+ \Omega(f_{s}) \tag{1.6}$$

$g_i$为损失函数的一阶导数，$h_{i}$是二阶导数。

$$g_{i}=\frac{\partial L(y_{i}, y^{s-1})}{\partial y^{s-1}}$$

$$h_{i}=\frac{\partial^{2} L(y_{i}, y^{s-1})}{\partial y^{s-1}}$$

去掉常数项

$$obj=\sum_{i=1}^{n}[g_{i} f_{s}(x_i) + \frac{1}{2} h_{i} f_{s}^{2}(x_i)] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \tag{1.7}$$

可以看到，XGBoost的目标函数与传统Gradient Tree Boosting方法有所不同，XGBoost在一定程度上作了近似，并通过一阶梯度统计和二阶梯度统计来表示，这就要求XGBoost的损失函数需满足二次可微条件。

经过简单的合并

$$obj=\sum_{j=1}^{T}[(\sum_{i \in I_{j}} g_{i})w_{j} + \frac{1}{2}(\sum_{i \in I_{j}} h_{i} + \lambda)w_{j}^2] + \gamma T \tag{1.8}$$

$I_{j}$为叶子节点的样本集合，就是落到叶子节点j的所有样本。f_{s}（x_{i}）将样本划分到叶子节点，计算得到该叶子节点的分数ω，可以用$ω_{j}$代替$f_{s}(x_{i})$

可以从不同的角度理解式（1.7）和式（1.8）。（1.7）最外层求和公式的维度为样本，可理解为最终的目标函数值是所有样本各自的目标函数值求和所得。（1.8）以叶子节点为维度，每个样本都会对应到每棵树的某一叶子节点上，因此所有的叶子节点也必然能涵盖所有样本在所有树上对应的值。这两个公式是等价的。
从1.8可以看做事一个自变量$w_{j}$和因变量obj的一元二次函数。叶子节点的最优权重为$w^{*}$

$$w^{*}==\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i} + \lambda} \tag{1.9}$$

可以看出叶子权重不仅和一阶导数和二阶导数的信息有关，还和L2的系数有关，此时L2的起到缩小叶子节点的权重的效果。减少对整个预测的影响，从而防止过拟合。得到了叶子节点最优的权重$w^{*}$，对于固定的树结构可以求得最优目标函数值。

$$obj==-\frac{1}{2} \sum_{j=1}^{T} \frac{(\sum_{i \in I_{j}} g_{i})^{2}}{\sum_{i \in I_{j}} h){i} + \lambda} + \gamma T \tag{2.0}$$

经过换元

$$w^{*}==\frac{G_{j}}{H_{j}+\lambda} \tag{2.1}$$

$$obj==\frac{1}{2} \sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda} + \gamma T \tag{2.2}$$

其中2.2可以作为评估树模型的评分函数，评分越小，表明该树模型越好.

利用评分函数即可对一个确定的树模型进行评价。在每一轮训练过程中，只要对所有候选的树模型分别计算评价得分，从中选出最优的即可。但候选树的个数是无穷的，我们不可能得到所有候选树的评价得分。XGBoost采用了贪心算法，即先从树的根节点开始，计算节点分裂后比分裂前目标函数值是否减少，假设当前分裂前节点为j，则其对目标函数的贡献为

$$obj_{j}==\frac{1}{2} \frac{G_{j}^2}{H_{j}+\lambda}+\gamma \tag{2.3}$$

因为其只有一个节点，因此其对树复杂度的贡献是γ。而该节点分裂后，两个子节点的目标函数贡献为

$$obj_{s}==\frac{1}{2} (\frac{G_{jL}^2}{H_{jL}+\lambda} + \frac{G_{jR}^2}{H_{jR}+\lambda})+2 \gamma \tag{2.4}$$

目前目标函数变化为

$$obj_{split}==\frac{1}{2} (\frac{G_{jL}^2}{H_{jL}+\lambda} + \frac{G_{jR}^2}{H_{jR}+\lambda}-\frac{G_{j}^{2}}{H_{j}+\lambda})- \gamma \tag{2.4}$$

我们发现只要找到收益最大的分裂点就可以分裂。

另外，XGBoost还支持行采样和列采样。行采样是对样本进行有放回的采样，即多次采样的集合中可能出现相同的样本。对这样的采样集合进行训练，每棵树训练的样本都不是全部样本，从而避免过拟合。列采样是从M个特征中选取m个特征（m<<M），用于对采样后的数据建立模型进行训练，而非采用所有特征。列采样最初被应用在随机森林算法中，XGBoost借鉴该方法，既能避免模型过拟合，也减少了计算量。根据实践经验，列采样比行法，既能避免模型过拟合，也减少了计算量。根据实践经验，列采样比行采样更能有效避免模型过拟合