XGBoost 算法简析

假设现在需要利用 XGBoost 算法进行建模，以识别智能合约中的庞氏骗局。

简述

假设训练集中有 $\textit{N}$ 个智能合约，训练集表示为 $\{(x_{i}, y_{i}) \mid i = 1, 2, \dots, N \}$，其中 $x_{i} \in R^{d}$ 表示从第 i 个智能合约中提取的特征，$y_{i} \in \{0, 1\}$ 表示第 i 个智能合约的分类标签：当 $y_{i} = 1$ 时，第 i 个智能合约为庞氏骗局；当 $y_{i} = 0$ 时，第 i 个智能合约不是庞氏骗局。现在需要根据这一训练集进行建模。

为了衡量模型的质量，XGBoost 定义了如下的目标函数：

$$obj(\theta) = L(\theta) + \Omega(\theta)$$

其中 $\theta$ 为模型的参数，$L$ 表示损失函数，$\Omega$ 表示正则项。损失函数用于衡量模型预测的准确程度，而正则项会作为惩罚项，以减少过拟合问题。

在建立模型的过程中，如果使用逻辑回归处理分类问题，模型最终的输出为 $(0, 1)$ 范围内的概率值。此时可以设定闸值为 0.5（或更低），即输出结果大于 0.5 的输入将会被判定为庞氏骗局，否则会被判定为非庞氏骗局。这种方法对应的逻辑损失函数为：

$$L(\theta) = \sum_{i}\left[y_{i}\ln(1 + e^{-\widehat{y_{i}}}) + (1 - y_{i})\ln(1 + e^{\widehat{y_{i}}})\right]$$

在 XGBoost 中，模型都是基于决策树建立的，决策树中的每个叶子节点都有对应的权重。决策树的数学定义如下：

$$f_{t}(x) = w_{q(x)}, w \in R^{T}, q : R^{d} \rightarrow \{1, 2, \dots, T\}$$

对于一个数据 $x$，函数 $q(x)$ 会将其映射到某个叶子节点 $t$ 上，而 $w_t$ 表示该叶子节点 $t$ 的权重向量。简而言之，决策树函数会将某个数据映射为对应的权重向量。

为了对树模型进行正则化，XGBoost 中定义树模型的复杂度如下：

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

其中，$\gamma$ 和 $\lambda$ 为模型参数，$T$ 为叶子节点的个数。

与普通的 Bagging 模型不同，XGBoost 集成算法采用迭代的方式逐步提升模型的质量。对于输入的数据 $x_{i}$ 而言，预测值 $\widehat{y}_{i}$ 的计算方法为：

$$\widehat{y}_{i} = \sum_{k=1}^{K} f_{k}(x_{i})$$

其中 $K$ 为决策树的数量，也就是迭代的步数。我们假设第 $t$ 步的预测值为 $\widehat{y}_{i}^{(t)}$，则迭代过程如下：

$$\begin{align*} \widehat{y}_{i}^{(0)} &= 0 \\ \widehat{y}_{i}^{(1)} &= f_{1}(x_{i}) = \widehat{y}_{i}^{(0)} + f_{1}(x_{i}) \\ \widehat{y}_{i}^{(2)} &= f_{1}(x_{i}) + f_{2}(x_{i}) = \widehat{y}_{i}^{(1)} + f_{2}(x_{i})\\ \cdots\\ \widehat{y}_{i}^{(t)} &= f_{1}(x_{i}) + f_{2}(x_{i}) + \dots + f_{t}(x_{i})= \widehat{y}_{i}^{(t - 1)} + f_{t}(x_{i})\\ \end{align*}$$

那么，在每一轮迭代中如何构造决策树呢？XGBoost 中定义第 $t$ 轮迭代的目标函数为：

$$\begin{align*} obj^{(t)} &= \sum_{i=1}^{n} l(y_{i}, \widehat{y}_{i}^{(t)}) + \sum_{i=1}^{t}\Omega(f_{i}) \\ &= \sum_{i=1}^{n} l(y_{i}, \widehat{y}_{i}^{(t - 1)} + f_{t}(x_{i})) + \Omega(f_{t}) + constant \end{align*}$$

在第 $t$ 轮迭代中，只需找到树模型 $f_t$，使得 $obj^{(t)}$ 最小化即可。此时可对损失函数进行泰勒展开（至二阶）：

$$obj^{(t)} = \sum_{i=1}^{n} \left[ l(y_{i}, \widehat{y}_{i}^{(t - 1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_{t}) + constant$$

其中 $g_i = \partial_{\widehat{y}_{i}^{(t - 1)}} l(y_{i}, \widehat{y}_{i}^{(t - 1)})$，$h_i = \partial_{\widehat{y}_{i}^{(t - 1)}}^2 l(y_{i}, \widehat{y}_{i}^{(t - 1)})$。

忽略上式的常数项，得到：

$$\begin{align*} obj^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_{t}) \end{align*}$$

代入决策树模型 $f_{t}(x)$ 的公式以及 $\Omega(f_{t})$ 的值，并将各个数据点映射至决策树的叶子节点上：

$$\begin{align*} obj^{(t)} &\approx \sum_{i=1}^{n} \left[ g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2 \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T}{w_j^{2}}\\ &= \sum_{j=1}^{T} \left[ (\sum_{i \in I_j} g_i) w_{j} + \frac{1}{2} (\sum_{i \in I_j} h_i + \lambda) w_{j}^2 \right] + \gamma T \end{align*}$$

其中 $I_j = \{ i \mid q(x_i) = j \}$，表示映射至叶子节点 $j$ 的数据的序号集合。

记 $G_j = \sum_{i \in I_j} g_i$，$H_j = \sum_{i \in I_j} h_i$，上式简化为：

$$\begin{align*} obj^{(t)} = \sum_{j=1}^{T} \left[ G_j w_{j} + \frac{1}{2} (H_j + \lambda) w_{j}^2 \right] + \gamma T \end{align*}$$

求出 $G_j w_{j} + \frac{1}{2} (H_j + \lambda) w_{j}^2$ 对 $w_j$ 的偏导数，然后令偏导数等于零：

$$\frac{\partial (G_j w_{j} + \frac{1}{2} (H_j + \lambda) w_{j}^2) }{\partial w_j} = G_j + (H_j + \lambda)w_j = 0$$

进而得到极小值点 $w_j^{*} = - \frac{G_j}{H_j + \lambda}$，代入 $obj^{(t)}$ 中，得到：

$$\begin{align*} obj^{*} = - \frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T \end{align*}$$

对于一个给定的 $q(x)$ 函数来说，$obj^{*}$是目标函数的最小值。因此，$obj^{*}$ 可用于衡量某个 $q(x)$ 函数的质量。比如说，在考虑把一个决策树叶节点分裂为两个节点时，可求出分裂的增益值：

$$Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda}\right] - \gamma$$

增益值可以看成原来节点的目标值减去分裂后的两个节点的目标值之和再减去 $\gamma$ 参数的结果。增益值越大，说明分裂效果越好，因此可以通过比较增益值的大小来确定数据的分裂点。

在构建决策树模型的过程中，XGBoost 默认的分裂方式如下：

• 对于每个节点，遍历所有特性。

• 对于每个特征，将所有数据依照当前特征的特征值进行排序。

• 线性遍历所有可能的分裂点，并求出每种分裂方式的增益值。

• 选出增益值最大的分裂方案。

注：除了排序，XGBoost 还提供了基于直方图的分裂方式。虽然后者能提高建模的速度，但是精确度不及前者，因此在追求精确度时采用前一种方式能够达到更好的效果。

为了减少过拟合问题，XGBoost 采用后剪枝策略，即先在规定的深度范围内尽可能地扩展决策树，最后遍历每个节点，根据增益值的大小（见上文）来确定是否进行剪枝（一般是在增益值为负时进行剪枝）。

改进

上文提到预测模型的叠加方法为 $\widehat{y}_{i}^{(t)} = \widehat{y}_{i}^{(t - 1)} + f_{t}(x_{i})$，在实际使用中可增加 $\epsilon$ 参数，也就是将叠加方法改为 $\widehat{y}_{i}^{(t)} = \widehat{y}_{i}^{(t - 1)} + \epsilon f_{t}(x_{i})$。$\epsilon$ 参数用于控制叠加的「步数」，通常设为 0.1，其作用是避免每一步都执行全优化，以防止过度拟合。