深度剖析集成学习Xgboost（续）

对XGBoost来说，真正难度较大的部分并不是梳理以上算法流程，而是证明这一流程可以让模型向着目标函数最小化的方向运行。在这个流程中包括如下很明显的问题：

建树时拟合的 $r_{ik} = -\frac{g_{ik}}{h_{ik}}$ 究竟是什么？拟合它有什么意义？
结构分数和结构分数增益的公式是如何推导出来的？为什么这样建树可以提升模型的效果？
为什么叶子节点的输出值 $w_j$ 是 $-\frac{(\sum_{i \in j} g_{ik})}{\sum_{i \in j} h_{ik} + \lambda}$ ？这样输出有什么意义？
课程的第一部分说XGBoost拟合的也是残差，残差在哪里？

定义目标函数与目标函数的自变量

首先，根据之前对目标函数的定义，XGBoost中目标函数是针对一棵树的目标函数，而不是针对一个样本或一整个算法的目标函数。并且，任意树的目标函数都包括三大部分：损失函数 $l$ 、叶子数量 $T$ 以及正则项。具体地来说：

假设单一树 $f_k$ 的目标函数为 $O_k$ ，总共有 $T$ 片叶子，该树上任意样本 $i$ 的损失函数为 $l((y_i,H(x_i))$ ，其中 $H(x_i)$ 是 $i$ 号样本在集成算法上的预测结果。树上总共有M个样本，目标函数中使用L2正则化（ $\lambda$ 不为0， $\alpha$ 为0），并且 $\gamma$ 不为0，则该树的目标函数为：

$O_k = \sum_{i=1}^Ml(y_i,H_k(x_i)) + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^Tw_j^2$

我们的目标是令目标函数最小，并找出令目标函数最小的某个自变量。对使用普通损失函数的Boosting算法来说，算法的输出值 $H (x)$ 是在迭代过程中不断变化的，损失函数 $l (y, H (x))$ 也是在迭代中不断变小的：

$H_k(x_i) = H_{k-1}(x_i) + f_k(x_i)$

$l_k = l(y_i,H_{k-1}(x_i) + f_k(x_i))$

当迭代到第 $k$ 次时，损失函数中的 $y_i$ 与 $H_{k-1}(x_i)$ 都是常数，只有 $f_k(x_i)$ 是变量，因此我们只需要在损失函数上对 $f_k(x_i)$ 求导，并找到令整体损失函数最小的预测值 $f_k(x_i)$ 即可。在GBDT当中，我们提到过，无论弱评估器 $f_k$ 是什么结构、什么规则、如何建立、如何拟合，只要其最终的输出值 $f_k(x_i)$ 是令整体损失函数 $L$ 最小化的 $f_k(x_i)$ ，那随着算法逐步迭代，损失函数必然会越来越小。因此，一个适合的 $f_k(x_i)$ 不仅能保证损失持续减小，还可以指导单个评估器的建立。

在XGBoost当中，我们也可以对目标函数求导、并找出令目标函数最小的某个自变量，但问题在于，XGBoost的目标函数中存在多个自变量：

\begin{aligned} O_{k} & = \sum_{i = 1}^{M} l (y_{i}, H_{k} (x_{i})) + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} \\ = \sum_{i = 1}^{M} l (y_{i}, H_{k - 1} (x_{i}) + f_{k} (x_{i})) + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} {w_{j}}^{2} \end{aligned}

O_{k} = i = 1 \sum M l (y_{i}, H_{k} (x_{i})) + γ T + \frac{1}{2} λ j = 1 \sum T w_{j}^{2} = i = 1 \sum M l (y_{i}, H_{k - 1} (x_{i}) + f_{k} (x_{i})) + γ T + \frac{1}{2} λ j = 1 \sum T w_{j}^{2}

其中， $T$ 是第 $k$ 棵树上的叶子总量， $f_k(x_i)$ 与 $w_j$ 都是模型输出的预测值（叶子上的输出值），不过表现形式不同，对任意位于叶子 $j$ 上的样本 $i$ 而言，数值上 $f_k(x_i) = w_j$ 。对XGBoost来说，只能选择一个变量作为自变量，考虑到 $f_k(x_i)$ 只与单个样本的精确程度有关，而 $T$ 只与树结构有关，XGBoost论文最终选择了即与精确度有关、又与树结构有关的变量 $w_j$ 。同时，如果知道叶子的最佳输出值 $w_j$ 就可以引导树成长为合理的结构，但只知道叶子的总量 $T$ 是无法指导建树的。

因此，求解XGBoost目标函数的第一步，就是将目标函数尽量整理成以 $w_j$ 表示的形式。

泰勒展开目标函数

在我们的目标函数 $O_k$ 中，可以被泰勒展开的是第一部分损失函数 $L$ ：

$O_k = \sum_{i=1}^Ml \left( y_i,H_{k-1}(x_i) + f_k(x_i) \right) + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^T w_j^2$

由于损失函数 $l$ 中只有唯一变量 $H_{k-1}(x_i) + f_k(x_i)$ ，因此可以将函数简写为 $l(H_{k-1}(x_i) + f_k(x_i))$ 。

根据二阶泰勒展开，已知：

\begin{aligned} f (x) & \approx \sum_{n = 0}^{2} \frac{f^{(n)} (a)}{n!} (x - a)^{n} \\ \approx f (a) + \frac{f^{'} (a)}{1!} (x - a) + \frac{f^{″} (a)}{2!} (x - a)^{2} \end{aligned}

f (x) \approx n = 0 \sum 2 \frac{f ^{(n)} ( a )}{n !} (x - a)^{n} \approx f (a) + \frac{f ^{'} ( a )}{1 !} (x - a) + \frac{f ^{''} ( a )}{2 !} (x - a)^{2}

令泰勒展开中的 $x = H_{k-1}(x_i) + f_k(x_i)$ ，令泰勒展开中的 $a = H_{k-1}(x_i)$ ，则 $x-a) = f_k(x_i)$ 。据此，损失函数 $l(H_{k-1}(x_i) + f_k(x_i))$ 可以被表示为：

\begin{aligned} l (H_{k - 1} (x_{i}) + f_{k} (x_{i})) & \approx l (H_{k - 1} (x_{i})) + \frac{\partial l (H_{k - 1} (x_{i}))}{\partial H_{k - 1} (x_{i})} * f_{k} (x_{i}) + \frac{\partial^{2} l (H_{k - 1} (x_{i}))}{2 \partial H_{k - 1}^{2} (x_{i})} * f_{k}^{2} (x_{i}) \end{aligned}

l (H_{k - 1} (x_{i}) + f_{k} (x_{i})) \approx l (H_{k - 1} (x_{i})) + \frac{\partial l ( H _{k - 1} ( x _{i} ))}{\partial H _{k - 1} ( x _{i} )} * f_{k} (x_{i}) + \frac{\partial ^{2} l ( H _{k - 1} ( x _{i} ))}{2 \partial H _{k - 1}^{2} ( x _{i} )} * f_{k}^{2} (x_{i})

在XGBoost中我们定义过损失函数的一阶导数与二阶导数：

$g_{ik} = \frac{\partial{l(y_i,H_{k-1}(x_i))}}{\partial{H_{t-1}(x_i)}}$

$h_{ik} = \frac{\partial^2{l(y_i,H_{k-1}(x_i))}}{\partial{H^2_{t-1}(x_i)}}$

在XGBoost原论文中，为了公式简洁， $g_i$ 和 $h_i$ 并没有呈现下标 $k$ ，但我们已经很清楚： $g$ 与 $h$ 是在每一轮迭代时需要被重新计算的。在这里我们也参照原论文中的做法去掉下标 $k$ 。因此，经过泰勒展开后的式子可以化简为：

\begin{aligned} l (H_{k - 1} (x_{i}) + f_{k} (x_{i})) & \approx l (H_{k - 1} (x_{i})) + g_{i} f_{k} (x_{i}) + \frac{1}{2} h_{i} f_{k}^{2} (x_{i}) \\ \approx 常 数 + g_{i} f_{k} (x_{i}) + \frac{1}{2} h_{i} f_{k}^{2} (x_{i}) \end{aligned}

l (H_{k - 1} (x_{i}) + f_{k} (x_{i})) \approx l (H_{k - 1} (x_{i})) + g_{i} f_{k} (x_{i}) + \frac{1}{2} h_{i} f_{k}^{2} (x_{i}) \approx 常数 + g_{i} f_{k} (x_{i}) + \frac{1}{2} h_{i} f_{k}^{2} (x_{i})

不难发现，该式子中 $H_{k-1}(x_i)$ 是常数，因此第一部分 $l(H_{t-1}(x_i))$ 也是一个常数，常数无法被最小化，因此我们可以将常数从该目标函数中剔除。经过泰勒展开，目标函数变为：

\begin{aligned} {\tilde{O}}_{k} & = \sum_{i = 1}^{M} (g_{i} f_{k} (x_{i}) + \frac{1}{2} h_{i} f_{k}^{2} (x_{i})) + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} \\ = \sum_{i = 1}^{M} g_{i} f_{k} (x_{i}) + \frac{1}{2} \sum_{i = 1}^{M} h_{i} f_{k}^{2} (x_{i}) + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} \end{aligned}

\tilde{O}_{k} = i = 1 \sum M (g_{i} f_{k} (x_{i}) + \frac{1}{2} h_{i} f_{k}^{2} (x_{i})) + γ T + \frac{1}{2} λ j = 1 \sum T w_{j}^{2} = i = 1 \sum M g_{i} f_{k} (x_{i}) + \frac{1}{2} i = 1 \sum M h_{i} f_{k}^{2} (x_{i}) + γ T + \frac{1}{2} λ j = 1 \sum T w_{j}^{2}

统一自变量

现在目标函数的前两项分别代表所有样本的 $g_if_k(x_i)$ 之和，以及所有样本的 $h_if^2_k(x_i)$ 之和乘1/2。别忘记，我们选择的唯一的自变量是 $w_j$ ，因此我们希望能够将 $f_k$ 以某种方式转化为 $w_j$ 。之前已经提到过多次，对任意位于叶子 $j$ 上的样本 $i$ 而言，数值上 $f_k(x_i) = w_j$ ，我们可以尝试着从一个样本开始进行转化：

对于单一样本 $i$ ，假设这个样本位于叶子 $j$ 上，应该有：

$g_if_k(x_i) = g_iw_j$

对于一片叶子 $j$ ，我们可以计算这片叶子上所有样本的 $g_iw_j$ 之和：

$\sum_{i \in j} g_iw_j$

而一片叶子上所有样本的 $w_j$ 都是一致的，因此一片叶子上的 $g_iw_j$ 之和可以转变为：

\begin{aligned} \sum_{i \in j} g_{i} w_{j} & = g_{1} w_{j} + g_{2} w_{j} + . . . + g_{n} w_{j} ， 其 中 1, 2... n 是 叶 子 j 上 的 样 本 \\ = w_{j} \sum_{i \in j} g_{i} \end{aligned}

i \in j \sum g_{i} w_{j} = g_{1} w_{j} + g_{2} w_{j} + ... + g_{n} w_{j} ，其中 1, 2... n 是叶子 j 上的样本 = w_{j} i \in j \sum g_{i}

假设现在一共有 $T$ 片叶子，则整棵树上所有样本的 $g_iw_j$ 之和为：

$\sum_{j=1}^T \left( w_j\sum_{i \in j} g_i \right)$

所以：

$\sum_{i=1}^Mg_if_k(x_i) = \sum_{j=1}^T \left( w_j\sum_{i \in j} g_i \right)$

同理，单一样本 $i$ 的 $h_if^2_k(x_i)$ 也可以以相同方式转化。对单一样本：

$h_if^2_k(x_i) = h_iw^2_j$

对一片叶子：

\begin{aligned} \sum_{i \in j} h_{i} w_{j}^{2} & = h_{1} w_{j}^{2} + h_{2} w_{j}^{2} + . . . + h_{n} w_{j}^{2} ， 其 中 1, 2... n 是 叶 子 j 上 的 样 本 \\ = w_{j}^{2} \sum_{i \in j} h_{i} \end{aligned}

i \in j \sum h_{i} w_{j}^{2} = h_{1} w_{j}^{2} + h_{2} w_{j}^{2} + ... + h_{n} w_{j}^{2} ，其中 1, 2... n 是叶子 j 上的样本 = w_{j}^{2} i \in j \sum h_{i}

对整棵树：

$\sum_{i=1}^Mh_if^2_k(x_i) = \sum_{j=1}^T \left( w^2_j\sum_{i \in j} h_i \right)$

因此对整个目标函数有：

\begin{aligned} {\tilde{O}}_{k} & = \sum_{i = 1}^{M} g_{i} f_{k} (x_{i}) + \frac{1}{2} \sum_{i = 1}^{M} h_{i} f_{k}^{2} (x_{i}) + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} \\ = \sum_{j = 1}^{T} (w_{j} \sum_{i \in j} g_{i} + \frac{1}{2} w_{j}^{2} \sum_{i \in j} h_{i}) + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} \end{aligned}

\tilde{O}_{k} = i = 1 \sum M g_{i} f_{k} (x_{i}) + \frac{1}{2} i = 1 \sum M h_{i} f_{k}^{2} (x_{i}) + γ T + \frac{1}{2} λ j = 1 \sum T w_{j}^{2} = j = 1 \sum T (w_{j} i \in j \sum g_{i} + \frac{1}{2} w_{j}^{2} i \in j \sum h_{i}) + γ T + \frac{1}{2} λ j = 1 \sum T w_{j}^{2}

不难发现，现在正则项可以与原来损失函数的部分合并了：

\begin{aligned} = \sum_{j = 1}^{T} (w_{j} \sum_{i \in j} g_{i} + \frac{1}{2} w_{j}^{2} \sum_{i \in j} h_{i} + \frac{1}{2} λ w_{j}^{2}) + γ T \\ = \sum_{j = 1}^{T} (w_{j} \sum_{i \in j} g_{i} + \frac{1}{2} w_{j}^{2} (\sum_{i \in j} h_{i} + λ)) + γ T \end{aligned}

= j = 1 \sum T (w_{j} i \in j \sum g_{i} + \frac{1}{2} w_{j}^{2} i \in j \sum h_{i} + \frac{1}{2} λ w_{j}^{2}) + γ T = j = 1 \sum T (w_{j} i \in j \sum g_{i} + \frac{1}{2} w_{j}^{2} (i \in j \sum h_{i} + λ)) + γ T

合并之后，整个目标函数变为两项，一项是所有叶子上的（损失+正则）之和，另一项是叶子总量。现在，我们可以开始求解最小目标函数以及对应的最优自变量 $w_j$ 了。

求解XGBoost的目标函数

首先，令目标函数中的叶子总量最小是不可能的，过度降低叶子总量会大幅度伤害模型的学习能力，因此我们只能考虑令所有叶子上的（损失+正则）之和最小。

其次，当树建好之后，叶子与叶子之间是相互独立的，因此每片叶子上的（损失+正则）也是相互独立的。我们只要令每片叶子的（损失+正则）都最小，就可以保证全部叶子的（损失+正则）之和最小。故而，我们要令式子中标注为红色的部分最小：

\begin{aligned} {\tilde{O}}_{k} & = \sum_{j = 1}^{T} (w_{j} \sum_{i \in j} g_{i} + \frac{1}{2} w_{j}^{2} (\sum_{i \in j} h_{i} + λ)) + γ T \end{aligned}

\tilde{O}_{k} = j = 1 \sum T ⎝ ⎛ w_{j} i \in j \sum g_{i} + \frac{1}{2} w_{j}^{2} (i \in j \sum h_{i} + λ) ⎠ ⎞ + γ T

叶子权重 $w_j$
将标注为红色的部分命名为 $\mu_j$ ，表示叶子 $j$ 上的损失+正则。则有：

$\mu_j = w_j\sum_{i \in j} g_i + \frac{1}{2}w^2_j(\sum_{i \in j} h_i + \lambda)$

现在，对叶子 $j$ 而言，在 $\mu_j$ 上对唯一自变量 $w_j$ 求导，则有：

\begin{aligned} \frac{\partial μ_{j}}{\partial w_{j}} & = \frac{\partial w_{j} \sum_{i \in j} g_{i} + \frac{1}{2} w_{j}^{2} (\sum_{i \in j} h_{i} + λ)}{\partial w_{j}} \\ = \sum_{i \in j} g_{i} + w_{j} (\sum_{i \in j} h_{i} + λ) \end{aligned}

\frac{\partial μ _{j}}{\partial w _{j}} = \frac{\partial w _{j} \sum _{i \in j} g _{i} + \frac{1}{2} w _{j}^{2} ( \sum _{i \in j} h _{i} + λ )}{\partial w _{j}} = i \in j \sum g_{i} + w_{j} (i \in j \sum h_{i} + λ)

令一阶导数为0，则有：

\begin{aligned} \sum_{i \in j} g_{i} + w_{j} (\sum_{i \in j} h_{i} + λ) & = 0 \\ w_{j} (\sum_{i \in j} h_{i} + λ) & = - \sum_{i \in j} g_{i} \\ w_{j} & = - \frac{\sum_{i \in j} g_{i}}{\sum_{i \in j} h_{i} + λ} \end{aligned}

i \in j \sum g_{i} + w_{j} (i \in j \sum h_{i} + λ) w_{j} (i \in j \sum h_{i} + λ) w_{j} = 0 = - i \in j \sum g_{i} = - \frac{\sum _{i \in j} g _{i}}{\sum _{i \in j} h _{i} + λ}

你应该发现了，对一片叶子来说，令目标函数最小的 $w_j$ 就是我们之前提过的叶子权重，也就是XGBoost数学流程当中叶子上的输出值。如果要令叶子的输出非常接近叶子权重公式，那应该如何拟合每个样本呢？

拟合值

对任意位于叶子 $j$ 上的样本 $i$ 来说：

$\mu_i = w_jg_i + \frac{1}{2}w^2_jh_i$

将一片叶子上的 $\mu_j$ 转变成 $\mu_i$ 时，原则上需要将 $\mu_j$ 中的每一项都转换为单个样本所对应的项，然而在转换正则项时则存在问题：与 $\sum_{i \in j} g_i$ 这样可以直接指向单个样本的项不同， $\lambda$ 是针对与一片叶子设置的值，如果要将 $\lambda$ 转变为针对单一样本的正则项，则需要知道当前叶子上一共有多少样本。然而，拟合发生在建树之前，因此在这一时间点不可能知道一片叶子上的样本总量，因此在xgboost的实际实现过程当中，拟合每一片叶子时不涉及正则项，只有在计算结构分数与叶子输出值时才使用正则项。

对 $\mu_i$ 上唯一的自变量 $w_j$ 求导，则有：

\begin{aligned} \frac{\partial μ_{i}}{\partial w_{j}} & = \frac{\partial (w_{j} g_{i} + \frac{1}{2} w_{j}^{2} h_{i})}{\partial w_{j}} \\ = g_{i} + w_{j} h_{i} \end{aligned}

\frac{\partial μ _{i}}{\partial w _{j}} = \frac{\partial ( w _{j} g _{i} + \frac{1}{2} w _{j}^{2} h _{i} )}{\partial w _{j}} = g_{i} + w_{j} h_{i}

令一阶导数为0，则有：

\begin{aligned} g_{i} + w_{j} h_{i} & = 0 \\ w_{j} h_{i} & = - g_{i} \\ w_{j} & = - \frac{g_{i}}{h_{i}} \end{aligned}

g_{i} + w_{j} h_{i} w_{j} h_{i} w_{j} = 0 = - g_{i} = - \frac{g _{i}}{h _{i}}

对任意样本 $i$ 而言，令目标函数最小的最优 $w_j$ 就是我们的伪残差 $r_i$ ，也就是XGBoost数学流程当中用于进行拟合的拟合值。

结构分数

现在，我们把令目标函数最小的最优 $w_j$ 带回到 $\mu_j$ 中，查看 $\mu_j$ 如何变化：

\begin{aligned} μ_{j} & = w_{j} \sum_{i \in j} g_{i} + \frac{1}{2} w_{j}^{2} (\sum_{i \in j} h_{i} + λ) \\ = - \frac{\sum_{i \in j} g_{i}}{\sum_{i \in j} h_{i} + λ} * \sum_{i \in j} g_{i} + \frac{1}{2} (- \frac{\sum_{i \in j} g_{i}}{\sum_{i \in j} h_{i} + λ})^{2} * \sum_{i \in j} h_{i} + λ \\ = - \frac{(\sum_{i \in j} g_{i})^{2}}{\sum_{i \in j} h_{i} + λ} + \frac{1}{2} \frac{(\sum_{i \in j} g_{i})^{2}}{\sum_{i \in j} h_{i} + λ} \\ = - \frac{1}{2} \frac{(\sum_{i \in j} g_{i})^{2}}{\sum_{i \in j} h_{i} + λ} \end{aligned}

μ_{j} = w_{j} i \in j \sum g_{i} + \frac{1}{2} w_{j}^{2} (i \in j \sum h_{i} + λ) = - \frac{\sum _{i \in j} g _{i}}{\sum _{i \in j} h _{i} + λ} * i \in j \sum g_{i} + \frac{1}{2} (- \frac{\sum _{i \in j} g _{i}}{\sum _{i \in j} h _{i} + λ})^{2} * i \in j \sum h_{i} + λ = - \frac{( \sum _{i \in j} g _{i} ) ^{2}}{\sum _{i \in j} h _{i} + λ} + \frac{1}{2} \frac{( \sum _{i \in j} g _{i} ) ^{2}}{\sum _{i \in j} h _{i} + λ} = - \frac{1}{2} \frac{( \sum _{i \in j} g _{i} ) ^{2}}{\sum _{i \in j} h _{i} + λ}

因此，目标函数（所有叶子上的损失）就可以变为：

\begin{aligned} {\tilde{O}}_{k} & = \sum_{j = 1}^{T} (w_{j} \sum_{i \in j} g_{i} + \frac{1}{2} w_{j}^{2} (\sum_{i \in j} h_{i} + λ)) + γ T \\ = \sum_{j = 1}^{T} (- \frac{1}{2} \frac{(\sum_{i \in j} g_{i})^{2}}{\sum_{i \in j} h_{i} + λ}) + γ T \end{aligned}

\tilde{O}_{k} = j = 1 \sum T ⎝ ⎛ w_{j} i \in j \sum g_{i} + \frac{1}{2} w_{j}^{2} (i \in j \sum h_{i} + λ) ⎠ ⎞ + γ T = j = 1 \sum T (- \frac{1}{2} \frac{( \sum _{i \in j} g _{i} ) ^{2}}{\sum _{i \in j} h _{i} + λ}) + γ T

因此，一片叶子上的目标函数就是：

$O_j = -\frac{1}{2}\frac{(\sum_{i \in j} g_i)^2}{\sum_{i \in j} h_i + \lambda} + \gamma$

对任意一片叶子来说，目标函数可以衡量叶子的质量，其中 $\gamma$ 是可以设定的超参数， $\frac{1}{2}$ 为常数，因此对任意叶子，我们希望标注为红色的部分越小越好：

$O_j = \frac{1}{2}\left( \boldsymbol{\color{red}{-\frac{(\sum_{i \in j} g_i)^2}{\sum_{i \in j} h_i + \lambda}}} \right)+ \gamma$

故而，我们希望以下式子越大越好：

$\frac{(\sum_{i \in j} g_i)^2}{\sum_{i \in j} h_i + \lambda}$

这个式子，正是XGBoost用于分枝时的指标“结构分数”（Structure Score）。

结构分数的增益

当分枝的时候，我们希望目标函数越小越好，因此在分枝过程中，父节点的目标函数是大于子节点的目标函数的，因此我们可以使用（父节点目标函数 - 子节点目标函数之和）来衡量分枝的质量，则有：

\begin{aligned} G a i n & = O_{p} - (O_{l} + O_{r}) \\ = - \frac{1}{2} \frac{(\sum_{i \in P} g_{i})^{2}}{\sum_{i \in P} h_{i} + λ} + γ - (- \frac{1}{2} \frac{(\sum_{i \in L} g_{i})^{2}}{\sum_{i \in L} h_{i} + λ} + γ - \frac{1}{2} \frac{(\sum_{i \in R} g_{i})^{2}}{\sum_{i \in R} h_{i} + λ} + γ) \\ = - \frac{1}{2} \frac{(\sum_{i \in P} g_{i})^{2}}{\sum_{i \in P} h_{i} + λ} + γ + \frac{1}{2} \frac{(\sum_{i \in L} g_{i})^{2}}{\sum_{i \in L} h_{i} + λ} - γ + \frac{1}{2} \frac{(\sum_{i \in R} g_{i})^{2}}{\sum_{i \in R} h_{i} + λ} - γ \\ = \frac{1}{2} (\frac{(\sum_{i \in L} g_{i})^{2}}{\sum_{i \in L} h_{i} + λ} + \frac{(\sum_{i \in R} g_{i})^{2}}{\sum_{i \in R} h_{i} + λ} - \frac{(\sum_{i \in P} g_{i})^{2}}{\sum_{i \in P} h_{i} + λ}) - γ \\ = \frac{1}{2} (S c o r e_{L} + S c o r e_{R} - S c o r e_{P}) - γ \end{aligned}

G ain = O_{p} - (O_{l} + O_{r}) = - \frac{1}{2} \frac{( \sum _{i \in P} g _{i} ) ^{2}}{\sum _{i \in P} h _{i} + λ} + γ - (- \frac{1}{2} \frac{( \sum _{i \in L} g _{i} ) ^{2}}{\sum _{i \in L} h _{i} + λ} + γ - \frac{1}{2} \frac{( \sum _{i \in R} g _{i} ) ^{2}}{\sum _{i \in R} h _{i} + λ} + γ) = - \frac{1}{2} \frac{( \sum _{i \in P} g _{i} ) ^{2}}{\sum _{i \in P} h _{i} + λ} + γ + \frac{1}{2} \frac{( \sum _{i \in L} g _{i} ) ^{2}}{\sum _{i \in L} h _{i} + λ} - γ + \frac{1}{2} \frac{( \sum _{i \in R} g _{i} ) ^{2}}{\sum _{i \in R} h _{i} + λ} - γ = \frac{1}{2} (\frac{( \sum _{i \in L} g _{i} ) ^{2}}{\sum _{i \in L} h _{i} + λ} + \frac{( \sum _{i \in R} g _{i} ) ^{2}}{\sum _{i \in R} h _{i} + λ} - \frac{( \sum _{i \in P} g _{i} ) ^{2}}{\sum _{i \in P} h _{i} + λ}) - γ = \frac{1}{2} (S cor e_{L} + S cor e_{R} - S cor e_{P}) - γ

其中， $\gamma$ 是可以设定的超参数， $\frac{1}{2}$ 为常数，因此：

$Gain = Score_L + Score_R - Score_P$

这就是我们在分枝时所使用的结构分数增益了。

现在你发现了，XGBoost流程中所使用的全部新公式（包括独特的拟合值、独特的分枝指标、独特的输出值）都是通过令目标函数最小而求解出来的。因此，XGBoost整个流程就保证了目标函数一定是向着最小化方向进行迭代的，新生成的每片叶子上的输出值 $w_j$ 都是会令目标函数最小化的输出值。现在，你可以回答最开始的问题了

相关阅读:
RedisTemplate缓存List的操作
【C/PTA】函数专项练习（一）
GAMES202 Real-Time Global Illumination
自由曲线与曲面 -计算机图形学
基于NoCode构建简历编辑器
自定义注解和@Target、@Retention注解的使用
软件打不开，文件找不到了，如何找到隐藏文件？（windows和mac解决方案）
玩转 GPT4All
比较不同项目管理工具的团队协作功能，找出最全面的一款
2024中国商业医疗险发展研究蓝皮书

原文地址：https://blog.csdn.net/weixin_54884881/article/details/126008293