1. 整体框架

XGBoost的思想是通过决策树来预测残差，不断的预测直到最终的残差接近0为止。如下图所示，$T_1$、$T_2$表示决策树，$\hat{y}$表示预测值，$y$表示真值，$y-\hat{y}$表示预测值与真值之间的残差。

 由于每一次的预测都会接近上一次的残差，所以最终的预测可以写成如下的数学形式：

 $\hat{y} = \sum{\widetilde{y}_i}$

其中$\widetilde{y}_i$表示第$i$棵树对应的残差

2. 目标函数

在学习的过程中，记第$t$次迭代的$i$棵树的loss为$l_t(y,\hat{y}_i)$，树的复杂度为$\Omega_t$，总的目标函数如下所示：

$L_t=\sum_{i=0}^{n}{l_t(y_i,\hat{y}_i)}+\sum_{j=0}^{t}{\Omega_j}$

接下来需要最小化这个目标函数。

其中，$\sum_{j=0}^{t}{\Omega_j}=\sum_{j=0}^{t-1}{\Omega_j}+\Omega_t$，假设前$t$次迭代的树结构都已经确定了，则$\sum_{j=0}^{t-1}{\Omega_j}$是一个常数，因此在最小化的过程中可以略去：

$minimize L_t=\sum_{i=0}^{n}{l_t(y_i,\hat{y}_i)}+\Omega_t$

到第$k$棵树时，对应的$\hat{y}_i^k=\hat{y}_i^{k-1}+f_k$，利用泰勒级数二阶展开近似$f(x+\Delta{x})=f(x)+f'(x)\Delta{x}+\frac{1}{2}f''(x)\Delta{x}^2$：

$minimize L_t=\sum_{i=0}^{n}{l_t(y_i,\hat{y}_i^{k-1}+f_k)}+\Omega_t$

$ =\sum_{i=0}^{n}  [l_t(y_i, \hat{y}_i^{k-1}) + \partial_{\hat{y}_i^{k-1}} l_t(y_i,\hat{y}_i^{k-1}) f_k + \frac{1}{2} \partial^2_{\hat{y}_i^{k-1}} l_t(y_i,\hat{y}_i^{k-1}) f^2_k] + \Omega_t$

其中$l_t(y_i,\hat{y}_i^{k-1})$为前$k-1$次的loss，已经是一个确定常数，因此也可以略去：

$minimize L_t=\sum_{i=0}^{n}[\partial_{\hat{y}_i^{k-1}} l_t(y_i,\hat{y}_i^{k-1}) f_k + \frac{1}{2} \partial^2_{\hat{y}_i^{k-1}} l_t(y_i,\hat{y}_i^{k-1}) f^2_k]+\Omega_t$

 记$g_i = \partial_{\hat{y}_i^{k-1}} l_t(y_i,\hat{y}_i^{k-1})$，$h_i = \partial^2_{\hat{y}_i^{k-1}} l_t(y_i,\hat{y}_i^{k-1})$，上式简化为

$minimize L_t=\sum_{i=0}^{n}[g_i f_k + \frac{1}{2} h_i f^2_k] + \Omega_t$

 接下来考虑树的参数化，如何使用数学公式来表达树的复杂度

树的复杂度由树的叶子节点可以确定，叶子节点$T$越多，复杂度越高；$\omega$表示叶子节点向量（由每个叶子节点的值组成）。所以有$\Omega_t = \gamma T + \frac{1}{2} \lambda \Vert \omega \Vert^2 $

因为$f_k$代表了第k棵树，其对应的输出（预测）为$w_{q(x)}$，$q(x)$表示x对应的位置下标$i$，所以有

$minimize L_t=\sum_{i=0}^{n}[g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2] + \gamma T + \frac{1}{2} \lambda \sum_{j=0}^T w_j^2$

由于对于第j个叶子节点有$j = q(x_i)$，所以我们调整上式为：

$minimize L_t=\sum_{i=0}^{n}[g_i w_{j} + \frac{1}{2} h_i w_{j}^2] + \gamma T + \frac{1}{2} \lambda \sum_{j=0}^T w_j^2$

$ = \sum_{j=0}^T [w_{j} \sum_{i=0}^{j} {g_i} + \frac{1}{2} w_{j}^2 ( \lambda + \sum_{i=0}^{j} h_i ) ] + \gamma T $

记$G_j = \sum_{i=0}^{j} {g_i}$，$H_j = \sum_{i=0}^{j} h_i$，有

$minimize L_t= \sum_{j=0}^T [ G_j w_{j} + \frac{1}{2} ( \lambda + H_j ) w_{j}^2 ] + \gamma T $

可以看出，当$ w_{j} = - \frac{G_j}{\lambda + H_j}$时，$L_t$取极值。因此目标函数最小值为

$L_t ^{*}= - \frac{1}{2} \sum_{j=0}^T \frac{G_j^2}{\lambda + H_j} + \gamma T $

3. 树的构建

类似于决策树，在选取分割节点的时候，我们使用目标函数来做给特征进行打分，其增益计算如下：

$Gain = \frac{1}{2}[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_R+G_L)^2}{H_R+H_L+\lambda}] - \gamma$