手推 XGBoost 损失函数

前言

在集成学习的博客中，我推导了一次 XGBoost，但是那篇的重点是集成学习，所以写得比较宽泛，以至于在面试的时候忽然间不清楚面试官问的问题，即 XGBoost 损失函数的推导。一直纠结于二阶泰勒展开与正则项，却不明白面试官所问的是进一步的推导，这包括：

1. 叶子节点最优分数推导；
2. 叶子节点代入损失函数后的损失函数推导；
3. 某个节点分裂后的损失

故新开一个博客，用于记录 XGBoost 推导的全过程。

二阶泰勒展开

Note

二阶泰勒展开：

$$f(x+\mathrm{\Delta }x)\simeq f(x)+f^{\prime }(x)\mathrm{\Delta }x+\frac{1}{2}{f}^{″}(x)(\mathrm{\Delta }x{)}^2$$

对于第 $t$ 棵树 $f_t(x)$，其损失函数 ${\mathcal{L}}^{(t)}$ 为：

$$\begin{array}{}\text{(1)}& {\mathcal{L}}^{(t)}=\sum _{i=1}^{n}l(y_i,{\hat{y}}_i^{(t-1)}+f_t({\mathbf{x}}_{\mathbf{i}}))+\mathrm{\Omega }(f_t)\end{array}$$

其中：

• 当前预测：之前 $t-1$ 棵树的预测结果 ${\hat{y}}^{(t-1)}$ 加上当前这棵树的预测结果 $f_t({\mathbf{x}}_i)$ ；
• 标签： $y_i$；
• 正则项：$\mathrm{\Omega }(f_t)=\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2$，其中 $T$ 是当前第 $t$ 棵树的叶子树，可以看到正则项只和当前这棵树有关，且与样本无关；
• 每个样本的损失累加作为最终损失。

因为 ${\hat{y}}^{(t-1)}$ 是已经确定的了，我们可以计算得到 $l(y_i,{\hat{y}}^{(t-1)})$。所以，对 $\text{(1)}$ 中的 $l$ 在 ${\hat{y}}_i^{(t-1)}$ 处做泰勒展开，得到了：

$${\mathcal{L}}^{(t)}\simeq \sum _{i=1}^n[l(y_i,{\hat{y}}^{(t-1)})+g_i{f}_t({\mathbf{x}}_i)+\frac{1}{2}{h}_i{f}_t^2({\mathbf{x}}_i)]+\mathrm{\Omega }(f_t)$$

其中

$$\begin{array}{r}{g}_i=\frac{\partial l(y_i,{\hat{y}}^{(t-1)})}{\partial {\hat{y}}^{(t-1)}}\\ h_i=\frac{{\partial }^{2}l(y_i,{\hat{y}}^{(t-1)})}{\partial {{\hat{y}}^{(t-1)}}^2}\end{array}$$

后面我们将直接忽略上面的近似等于符号，直接将损失函数视为展开后的形式。我们可以看到，现在损失被拆分为了三种项：

1. 前 $t-1$ 棵树的累加的预测结果的损失 $l(y_i,{\hat{y}}^{(t-1)})$；

2. 一阶项 $g_i{f}_t(x_i)$，二阶项 $\frac{1}{2}{h}_i{f}_t^2({\mathbf{x}}_i)$，其中一阶导和二阶导是已经确定的常数

   Caution

   1. 这俩都是损失函数对 ${\hat{y}}^{(t-1)}$的偏导乘以 $f_t({\mathbf{x}}_i)$。在泰勒展开原始形式中，$\mathrm{\Delta }\mathbf{x}$ 就是此时的 $f_t({\mathbf{x}}_i)$；

   2. 偏导是对先前的预测结果做偏导，而不是对样本做偏导；

3. 正则化项；

可以看出，上面的项中，1 是已经确定的了，在训练第 $t$ 棵树的时候，我们不会再去修改前面的 $t-1$ 棵树。我们在优化的时候无需考虑这个常数项。再将正则化项展开，得到了：

$$\begin{array}{}\text{(2)}& {\mathcal{L}}^{(t)}=\sum _{i=1}^n[g_i{f}_t({\mathbf{x}}_i)+\frac{1}{2}{h}_i{f}_t^2({\mathbf{x}}_i)]+\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2\end{array}$$

叶子最优分数推导

从 $\text{(2)}$ 式子中，我们可以看出，式子中存在样本的累加项和叶子节点的累加项。我们可以根据样本被分配到的叶子节点，建立起叶子节点和样本之间的联系：

• 对于第 $j$ 个叶子，其所包含的样本集合是 $I_j$，即 $I_j=\{i\mid q({\mathbf{x}}_i)=j\}$，$q(\mathbf{x})$ 表示样本被划分到的叶子节点，即决策树的结构；
• 对于第 $i$ 个样本，如果它被划分到 $I_j$，则其预测值是该节点的分数 $w_j$，即对于 $i\in I_j$，我们有 $f_t({\mathbf{x}}_i)=w_j$；
• 在之后，我们都用 $i$ 作为样本的编号，用 $j$ 作为叶子的编号；

我们可以将 $\text{(2)}$ 进一步合并同类项，其思路是以叶子节点作为外部累加，对于每个叶子节点，将样本的预测值 $f_t({\mathbf{x}}_i)$ 变成叶子的分数 $w_j$，这样就和正则项有重合的项。于是，变成：

$$\begin{array}{}\text{(3)}& \begin{array}{rl}{\mathcal{L}}^{(t)}& =\sum _{i=1}^n[g_i{f}_t({\mathbf{x}}_i)+\frac{1}{2}{h}_i{f}_t^2({\mathbf{x}}_i)]+\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2\\ & =\sum _{j=1}^T[w_j\sum _{i\in I_j}{g}_i+\frac{1}{2}{w}_j^2\sum _{i\in I_j}{h}_i]+\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2\\ & =\sum _{j=1}^T[w_j\sum _{i\in I_j}{g}_i+\frac{1}{2}{w}_j^2(\sum _{i\in I_j}{h}_i+\lambda )]+\gamma T\end{array}\end{array}$$

对于一个固定的结构 $q(\mathbf{x})$，我们可以计算出 ${\mathcal{L}}^{(t)}$ 对每个叶子节点分数 $w_j$ 的极值点，也就是另 ${\mathcal{L}}^{(t)}$ 对 $w_j$ 的偏导为 0。对 $w_j$ 的偏导形式可以非常简化，因为：

1. 其他叶子节点的项与 $w_j$ 无关，求导后可以直接删去；
2. 叶子结点数量与 $w_j$ 无关，可以直接删除；
3. 一阶项求导只剩下系数；
4. 二阶项求导后平方与 $1/2$ 相乘变成 $1$；

可得：

$$\frac{\partial {\mathcal{L}}^{(t)}}{\partial w_j}=\sum _{i\in I_j}{g}_i+w_j(\sum _{i\in I_j}{h}_i+\lambda )$$

另其为 0，易得：

$$\begin{array}{}\text{(4)}& w_j^{\ast }=-\frac{\sum _{i\in I_j}{g}_i}{\sum _{i\in I_j}{h}_i+\lambda }\end{array}$$

此即为叶子节点的最优分数推导结果，可以看到其与一些因素有关：

1. 正则项中的 $\lambda$；
2. 损失函数对叶子中的所有节点先前预测的一阶导和二阶导。

叶子节点代入损失函数

将每个叶子结点的最优分数代入损失函数，也就是 $\text{(4)}$ 代入 $\text{(3)}$

简化一些累加项方便计算：

• $G_j=\sum _{i\in I_j}{g}_i$
• $H_j=\sum _{i\in I_j}{h}_i$

可以得到：

$$\begin{array}{}\text{(5)}& \begin{array}{rl}{\mathcal{L}}^{(t)}& =\sum _{j=1}^T[w_j{G}_j+\frac{1}{2}{w}_j^2(H_j+\lambda )]+\gamma T\\ & =\sum _{j=1}^T[(-\frac{G_j}{H_j+\lambda })G_j+\frac{1}{2}{(-\frac{G_j}{H_j+\lambda })}^2(H_j+\lambda )]+\gamma T\\ & =\sum _{j=1}^T[(-\frac{G_j}{H_j+\lambda })G_j+\frac{1}{2}{(-\frac{G_j}{H_j+\lambda })}^2(H_j+\lambda )]+\gamma T\\ & =-\frac{1}{2}\sum _{j=1}^T\left[\frac{G_j^2}{H_j+\lambda }\right]+\gamma T\end{array}\end{array}$$

故 XGBoost 第 $t$ 棵树的损失函数是：

$${\mathcal{L}}^{(t)}=-\frac{1}{2}\sum _{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$$

可以看到，其损失函数只受到以下因素的影响：

1. 损失函数对 ${\hat{y}}^{(t-1)}$ 的偏导，一阶偏导越大，损失越大，二阶偏导越小，损失越小；
2. 叶子数量越多，损失越大；

因此，其计算非常快，因为损失函数对 ${\hat{y}}^{(t-1)}$ 的偏导是可以提前计算好的，只需要根据树当前的叶子节点内的样本集合，快速累加即可。

节点分裂后的损失

一个节点 $I$，分裂后变成 $I_L$ 和 $I_R$，即 $I=I_L\cup I_R$，于是乎，对于某个节点，其分裂后，整棵树的损失变化为

$${\mathcal{L}}_{\text{split}}=\frac{1}{2}[\frac{{\left(\sum _{i\in I_L}{g}_i\right)}^2}{\sum _{i\in I_L}{h}_i+\lambda }+\frac{{\left(\sum _{i\in I_R}{g}_i\right)}^2}{\sum _{i\in I_R}{h}_i+\lambda }-\frac{{\left(\sum _{i\in I}{g}_i\right)}^2}{\sum _{i\in I}{h}_i+\lambda }]-\gamma$$

分裂后，叶子节点从 1 个变成了 2 个，所以要多减去一个 $\gamma$。哪个属性带来的分裂损失最小，就选择这个属性分裂。

参考资料

XGBoost: A Scalable Tree Boosting System