XGBoost原理

1. 整体框架

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

XGBoost原理

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

 $\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$

上一篇:支持向量机优化等价问题


下一篇:一文入门:XGBoost与手推二阶导