旅途的中点

理解#

之前我们已经提到过了GBDT算法的隐患，有着和ID3相似的缺陷。

ID3的缺陷就是如果存在一特殊的特征，其中里面每个值都不一样，比如一个人的身份证号，使得树无限细分，这样的值显然并无意义。

与之类似的，就是GBDT算法中的树的节点个数，如果无限细分下去，那么最终也会得到由单个值组成的叶节点，使得预测和真实值基本没有差别，这显然出现了过拟合的问题。

那么解决这个问题显然是需要正则化，XGboost算法便类似于L2正则化，评估GBTD算法，考虑分裂后是否对模型有帮助。

数学推导#

$Obj = \sum_{i=1}^n L(y_i, \hat{y}_i) + \sum_{k=1}^K \Omega(f_k)$

$\Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2$

其中，L表示损失函数，可以是最小二乘，也可以是其他的，比如熵

$\Omega$便是一个正则化项，$\gamma$和$\lambda$是两个超参

$w_j$是一个很有意思的量，表示权重，这个权重如果不能理解，公式将很难推导，稍后我们详细介绍

那么现在我们开始正式推导:

我们假设$y_i$是真实值，$y_{i-1}$ (前i-1轮的总和)+ $f_t(x_i)$(第i轮预测值)=$y_i$

那么损失函数可以表示为:

$L(y_i,y_{i-1}+f_t(x_i))$

如果用最小二乘作为演示，可以写作:

$L(y_i-(y_{i-1}+f_t(x_i)))$

而泰勒公式可以表示为：

$f(x_0+\Delta x)=f(x_0)+f'(x_0)\Delta x+ \frac{f''(x_0)}{2!}(\Delta x)^2$

显然i-1次预测后，所有的预测值累加起来已经趋近于$y_i$,则新预测值可以被视为$\Delta x$

而$y_i-y_{i-1}$自然被视为$x_0$

为了通用性，我们需要对损失函数求偏导，损失函数的$y_i$（真实值）是一个固定的值,我们对$\hat y$（也就是预测值）求偏导，获得损失函数的变化率

$\frac{\partial L(y, \hat{y})}{\partial \hat{y}}$

接下来我们带入$\hat y=\hat{y}_i^{(t-1)}$

这就是该函数的一阶导，代表着梯度，也就是朝哪里下降：

$g_i = \left[ \frac{\partial L(y_i, \hat{y})}{\partial \hat{y}} \right]_{\text{代入 } \hat{y} = \hat{y}_i^{(t-1)}}$

二阶导同理，只需要再求一次偏导，代表着曲率，也就是下降的速度的变化趋势：

$h_i = \left[ \frac{\partial^2 L(y_i, \hat{y})}{\partial \hat{y^2}} \right]_{\text{代入 } \hat{y} = \hat{y}_i^{(t-1)}}$

这个显然是很好理解的,就是泰勒展开和微积分的运用

下面式子变形为以下形式：

$Obj=\sum_{i=1}^n \left[ L(y_i,\hat y_i^{(t-1)})+g_if_t(x_i)+\frac{1} {2} h_if_t^2(x_i) \right]+\sum_{k=1}^{t-1}\Omega(f_k)+\Omega(f_t)$

这里的定值显然不影响之后的求导，我们假设的是i-1轮已知，则i-1轮前的参数都可以算出来。

$Obj=\sum_{i=1}^n \left[ g_if_t(x_i)+\frac{1} {2} h_if_t^2(x_i) \right]+\Omega(f_t)$

此时我们将$\Omega$带入

$Obj=\sum_{i=1}^n \left[ g_if_t(x_i)+\frac{1} {2} h_if_t^2(x_i) \right]+\gamma T+\frac{1}{2}\lambda \Vert w \Vert^2$

接下来到了一个比较难以理解的点，那就是$g_i$在这里是不一样的。

为什么不一样呢？我们以最小二乘举个例子，最后偏导的结果就是残差：

$\hat{y}-y_i$

在GBDT中，预测值是各个数的平均数（说白了就是减一个同样的值），真实值不一定一样，那么$\hat{y}-y_i$显然也不一样。

这里我们可以开始说 $w$ 了,$w$代表的是叶子权重，而:

$叶子权重=f_t(x_i)$

为什么？

XGBoost是一个加法模型，由多棵决策树组成。模型最终给出的预测值 $\hat{y}_i$，是所有单棵树预测值（也就是样本落在各棵树对应的叶子权重）的总和： $\hat{y}_i = \sum_{k=1}^K f_k(x_i)$ 其中，$f_k(x_i)$ 就是样本 $x_i$ 在第 $k$ 棵树中落入的叶子节点的权重 $w$。

那么知道了这一点，我们继续往下推导，现在令$w$相同的gi的和组成$G_j$,令$w$相同的hi的和组成$H_j$,需要注意的是$\Vert w \Vert^2$代表着L2范数平方再开平方根，最后的结果就是$w_j^2$

$Obj= \sum_{j=1}^{T(叶子数)} \left[ G_jw_j+\frac{1}{2}H_jw_j^2 \right]+\sum_{j=1}^{T(叶子数)}\frac{1}{2}\lambda w_j^2+\gamma T$

显然$\gamma T$也是个常数，可以消去，最终我们对Obj求导：

$0=G_j+(H_j+\lambda)w_j$

$w_j = \frac{-G_j}{h_j+\lambda}$

至此，带入可得：

$Obj=\sum_{j=1}^T[G_j\frac{-G_j}{H_j+\lambda}-\frac{1}{2}H_j(\frac{-G_j}{H_j+\lambda})^2]+\gamma T$

$Obj=-\frac{1}{2}\sum_{j=1}^T(\frac{-G_j}{H_j+\lambda})^2+\gamma T$

这里还有一个点，就是我们选择$y_i-y_{i-1}$展开的时候,$g_i$就已经是一个定值了。

所以当数进行拆分时，我们可以得到这个公式：

$G_{拆分前}=G_{左}+G_{右}$

那么,我们最后评分解是否优秀:

$Gain=Obj_{L+R}-(Obj_L+Obj_R)$ $Gain=[-\frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}+\lambda T] - [-\frac{1}{2}(\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda})+\gamma (T+1)]$

当Gain>0,则可分，Gain<0,则不分。