xgboost理论推导（一）

本文是在学习陈天奇博士的xgboost论文后总结而来，并对相关知识点和公式进行了详细说明，推导和理解。内容安排如下：

顺序	内容	说明
1	树的复杂度衡量	因为xgboost的损失函数包含了正则项，而正则项则是依据树的复杂度进行的，所以先介绍树的复杂度
2	xgboost的损失函数	中间详细介绍了公式的推导过程，并对每个公式进行了详细介绍，方便读者理解。

1，树的复杂度衡量

这里以陈博士论文中的图像为例，说明树的复杂度衡量公式。

陈博士论文中的图像如下：
xgboost理论推导（一）

上图中，是对5个人物（祖孙三代）为例构建决策树实例。首先，根据年龄是否小于15岁进行分类，接着对左支的子集，根据是否为男性进行分类。一共得到三个叶子(leaf)，leaf1,leaf2,leaf3。

使用 $q$ , $T$ 和 $w$ 表示树的复杂度。 $q$ 表示叶子的索引， $q : R^{d} \to {1, 2, \dots, T}$ 。 $T$ 是 $q$ 的最大值，是叶子的总数。示例中， $T$ 为3。 $q (小男孩) = 1 ， q (老奶奶) = 3$ 。 $w$ 是叶子的权重，也称得分。在示例中，小男孩所在的叶子1的权重为 $w 1 = + 2$ 。决策树的最终目的就是得到这个权重。

2，xgboost的损失函数

xgboost的目标函数为：

\begin{matrix} (2) & L (ϕ) = \sum_{i} l ({\hat{y}}_{i}, y_{i}) + \sum_{k} Ω (f_{k}) 这 里 Ω (f) = γ T + \frac{1}{2} λ | | w | |^{2} \end{matrix}

上式中，各项的解释如下：

符号	性质	说明
$l$	损失函数，可微，是一个凸函数。	衡量预测值 ${\hat{y}}_{i}$ 和精确值 $y_{i}$ 之间的差别，可以是差别的L1范数或者差别的L2范数
${\hat{y}}_{i}$	预测值	$l$ 的自变量
$y_{i}$	精确值	$l$ 的自变量
$γ$	$T$ 的权重，即正则化的强度	实际使用中可调
$T$	树的叶子的数量
$λ$	$\| \| w \| \|^{2}$ 的权重，即正则化的强度	实际使用中可调
$\| \| w \| \|^{2}$	叶子得分的L2范数
$Ω$	正则化函数	$Ω (f) = γ T + \frac{1}{2} λ \| \| w \| \|^{2}$

根据xgboost的原理，树的集成方式是加法模型。即：

\begin{matrix} (3) & {\hat{y}}_{i}^{(t)} = {\hat{y}}_{i}^{(t - 1)} + f_{t} (X_{i}) \end{matrix}

公式的中各部分的解释如下：

符号	说明
$t$ , $t - 1$	集成树的迭代次数
$i$	集成树的中，树的编号。
${\hat{y}}_{i}^{(t - 1)}$	第 $i$ 个数的第 $t - 1$ 次迭代的计算结果，即预测值
$f_{t}$	第 $t$ 次迭代后的集成树模型（可以理解为函数）
$X_{i}$	第 $i$ 个树的输入变量（自变量）

公式的整个含义是：

第 $t$ 次迭代后集成树的计算结果 ${\hat{y}}_{i}^{(t)}$ = 前 $t - 1$ 次的累加计算结果 ${\hat{y}}_{i}^{(t - 1)}$ +第 $t$ 次集成树模型计算结果 $f_{t} (X_{i})$

将公式 $(3)$ 带入到公式 $(2)$ 中，可得：

\begin{matrix} (4) & L^{(t)} = \sum_{i = 1}^{n} l (y_{i}, {\hat{y}}_{i}^{(t - 1)} + f_{t} (X_{i})) + Ω (f_{t}) \end{matrix}

含义是：第

t

次迭代的损失函数=

n

个树的损失函数之和+第

t

次迭代的集成树的复杂度惩罚

接着使用泰勒展开式对公式 $(4)$ 进行化简。

已知泰勒展开式为：

\begin{matrix} (5) & f (x + Δ x) = f (x) + f^{'} (x) Δ x + \frac{f^{″} (x)}{2!} (Δ x)^{2} + \dots + \frac{f^{(n)} (x)}{n!} (Δ x)^{n} + R_{n} (x) \end{matrix}

所以，公式

(4)

可以转化为：

\begin{matrix} (6) & L^{(t)} ≃ \sum_{i = 1}^{n} [l (y_{i}, {\hat{y}}^{(t - 1)}) + g_{i} f_{t} (X_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (X_{i})] + Ω (f_{t}) \end{matrix}

公式

(6)

中，

g_{i} = \partial_{\hat{y} (t - 1)} l (y_{i}, {\hat{y}}^{(t - 1)}) h_{i} = \partial_{\hat{y} (t - 1)}^{2} l (y_{i}, {\hat{y}}^{(t - 1)})

并且，公式

(6)

中和公式

(5)

的对应如下：

公式 $(6)$	公式 $(5)$
$l$	$f$
${\hat{y}}_{i}^{(t y - 1)}$	$x$
$f_{t} (X_{i})$	$Δ x$

考虑到 $l (y_{i}, {\hat{y}}^{(t - 1)})$ 是常量（因为前 $t - 1$ 次迭代结果已定，现在处于第 $t$ 次迭代过程中），所以略去常数项，简化公式 $(6)$ 如下：

\begin{matrix} (7) & {\tilde{L}}^{(t)} = \sum_{i = 1}^{n} [g_{i} f_{t} (X_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (X_{i})] + Ω (f_{t}) \end{matrix}

截止到目前，所有的推导的对象都是树，还未深入到树的叶子，不方便实际计算，现在将推导细化到树的叶子。

定义： $I_{j} = {i | q (X_{i}) = j}$ 是第 $j$ 个叶子的实例集。这里扩展 $Ω$ 并将推导细化都树的叶子，重写公式 $(7)$ 如下：

\begin{matrix} (8) & \begin{aligned} {\tilde{L}}^{(t)} & = \sum_{i = 1}^{n} [g_{i} f_{t} (X_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (X_{i})] + Ω (f_{t}) \\ = \sum_{i = 1}^{n} [g_{i} f_{t} (X_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (X_{i})] + γ T + \frac{1}{2} λ | | w | |^{2} \\ = \sum_{j = 1}^{T} [(\sum_{i \in I_{j}} g_{i}) w_{j} + \frac{1}{2} (\sum_{i \in I_{j}} h_{i} + λ) w_{j}^{2}] + γ T \end{aligned} \end{matrix}

需要说明的一点是，上式的前提是树的结构是恒定的。上式的含义是先求每个叶子的损失函数，然后将所有叶子的损失函数求和，并使用叶子的数量进行正则惩罚。

进一步对公式 $(8)$ 进行化简，定义

G_{j} = \sum_{i \in I_{j}} g_{i} H_{j} = \sum_{i \in I_{j}} h_{i}

则公式

(8)

化简为：

\begin{matrix} (9) & {\tilde{L}}^{(t)} = \sum_{j = 1}^{T} [G_{j} w_{j} + \frac{1}{2} (H_{j} + λ) w_{j}^{2}] + γ T \end{matrix}

公式

(8)

对

w_{j}

求一阶偏导，使之为0。得到

{\tilde{L}}^{(t)}

的极小值点

w^{*}

：

\begin{matrix} (10) & w_{j}^{*} = - \frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i} + λ} = - \frac{G_{j}}{H_{j} + λ} \end{matrix}

将

w^{*}

代入公式

(8)

,可得

{\tilde{L}}^{(t)}

的极小值：

\begin{matrix} (11) & \begin{aligned} {\tilde{L}}^{(t)} (q) & = - \frac{1}{2} \sum_{j = 1}^{T} \frac{(\sum_{i \in I_{j}} g_{i})^{2}}{\sum_{i \in I_{j}} h_{i} + λ} + γ T = - \frac{1}{2} \sum_{j = 1}^{T} \frac{G_{j}^{2}}{H_{j} + λ} + γ T \end{aligned} \end{matrix}

陈博士论文中，以一颗数为例，说明了公式

(11)

的计算过程。

通常，不可能枚举所有可能的树结构 $q$ ，一个贪婪算法从单一的叶子开始，迭代的添加到树的分支。假设 $I_{L}$ 和 $I_{R}$ 是拆分后的左和右节点的实例集。假定 $I = I_{L} \cup I_{R}$ ，在分割后的损失函数降低为：

\begin{matrix} (12) & L_{s p l i t} = \frac{1}{2} [\frac{(\sum_{i \in I_{L}} g_{i})^{2}}{\sum_{i \in I_{L}} h_{i} + λ} + \frac{(\sum_{i \in I_{R}} g_{i})^{2}}{\sum_{i \in I_{R}} h_{i} + λ} - \frac{(\sum_{i \in I} g_{i})^{2}}{\sum_{i \in I} h_{i} + λ}] - γ \end{matrix}

这个公式通常用于评估分裂的候选特征。

xgboost理论推导（一）

1，树的复杂度衡量

2，xgboost的损失函数

相关推荐