XGBoost

模型

XGBoost 算法是 GBDT 算法的高级版本，属于 Boosting 算法的一种，基于加法模型的前向分布算法，利用 CART 树作为弱学习器，并且引入了正则项。

假设 XGBoost 模型中 CART 树有 $K$ 个，有模型

$$f_K(x)=\sum_{k=1}^KT(x;\Theta_k)$$

记正则项为 $\Omega(f_k)$ 为第 $k$ 颗树的正则项，有模型的代价函数 $J(\Theta)$

$$J(\Theta) = \sum_{i=1}^m L\left(y^{(i)},f_{K}(x^{(i)})\right) + \sum_{k=1}^K\Omega(f_k)$$

根据前向分布算法，每次只需优化一颗 CART 树 $k’$：

$$J(\Theta) = \sum_{i=1}^m L\left(y^{(i)},f_{k'-1}(x^{(i)}) + T(x^{(i)};\Theta_{k'})\right) + \sum_{k=1}^{k'-1}\Omega(f_k) + \Omega(f_{k'})$$

有二阶泰勒展开式：

$$f(x + \varDelta x)=f(x) + f'(x)\varDelta x+\frac 1 2 f''(x)\varDelta x^2$$

令 $x=f{k’-1}(x^{(i)})$；$\varDelta x=T(x;\Theta{k’})$，针对函数 $L(f{k’-1}(x^{(i)}) + T(x;\Theta{k’}))$，有

$$\begin{align} J(\Theta) =& \sum_{i=1}^m L\left(y^{(i)},f_{k'-1}(x^{(i)}) + T(x^{(i)};\Theta_{k'})\right) + \sum_{k=1}^{k'-1}\Omega(f_k) + \Omega(f_{k'})\\ =& \sum_{i=1}^m \left[L\left(y^{(i)},f_{k'-1}(x^{(i)})\right) + g^{(i)}_{k'-1}T(x^{(i)};\Theta_{k'}) + \frac 1 2h^{(i)}_{k'-1}T^2(x^{(i)};\Theta_{k'}) \right]\\ &+ \Omega(f_{k'})+C \end{align}$$

其中

$$\begin{align} g^{(i)}_{k'-1} &= \frac{\partial L(y^{(i)},f_{k'-1}(x^{(i)}))}{\partial f_{k'-1}(x^{(i)})}\\ h^{(i)}_{k'-1} &= \frac{\partial^2 L(y^{(i)},f_{k'-1}(x^{(i)}))}{\partial {f_{k'-1}}^2(x^{(i)})}\\ C &= \sum_{k=1}^{k'-1}\Omega(f_k) \end{align}$$

去掉前 $k’-1$ 步早已确定的常数项，可以得到

$$J(\Theta) =\sum_{i=1}^m \left(g^{(i)}_{k'-1}T(x^{(i)};\Theta_{k'}) + \frac 1 2h^{(i)}_{k'-1}T^2(x^{(i)};\Theta_{k'}) \right) + \Omega(f_{k'})$$

令正则项 $\Omega$ 为

$$\Omega(f_{k}) = \gamma T + \frac1 2\lambda\sum_{j=1}^Tw^2_j$$

其中 $T$ 为第 $k$ 颗树的结点个数，$w_j$ 是这颗树第 $j$ 个结点的预测值。

按照回归树)模型，针对第 $k$ 个回归树而言，它把训练集分成了 $T$ 份，用 $R_1,R_2,\cdots,R_T$ 来表示划分好的集合，在每个单元都有一个固定的输出值 $w_j$。

$$T(x^{(i)};\Theta_k) = \sum_{j=1}^T w_jI(x^{(i)}\in R_j)$$

那么可以根据回归树的每个划分好的集合 $R_j$ 来换一种遍历训练集的方式。

$$\begin{align} J(\Theta) =&\sum_{i=1}^m \left(g^{(i)}_{k'-1}T(x^{(i)};\Theta_{k'}) + \frac 1 2h^{(i)}_{k'-1}T^2(x^{(i)};\Theta_{k'}) \right)\\ &+ \gamma T + \frac1 2\lambda\sum_{j=1}^Tw^2_j\\ =& \sum_{j=1}^T\left[ \left ( \sum_{i\in R_j}g^{(i)}_{k'-1}\right ) w_j + \frac1 2\left( \sum_{i\in R_j}h^{(i)}_{k'-1}+\lambda \right)w_j^2 \right]+\gamma T \end{align}$$

令 $Gj,H_j$ 为在 $R_j$ 结点上的样本的 $g{k’-1},h_{k’-1}$ 之和，即

$$G_j = \sum_{i\in R_j}g^{(i)}_{k'-1};\quad H_j = \sum_{i\in R_j}h^{(i)}_{k'-1}$$

代入则有

$$J(\Theta) = \sum_{j=1}^T\left( G_jw_j + \frac1 2\left( H_j+\lambda \right)w_j^2 \right)+\gamma T$$

$J(\Theta)$ 对 $w_j$ 求偏导，得

$$\hat{w}_j = -\frac{G_j}{H_j+\lambda}$$

进而有

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

但是上式需要遍历所有可能的树结构 $\Theta$，我们可以用一种贪婪算法来遍历结构：从一个树根开始迭代增加分支。假定一个节点 $I$ 被分为左右节点 $I_L,I_R$，$I=I_L\cup I_R$，我们可以计算出分裂该节点之后代价函数的减少情况：

$$J_\text{split} = \frac1 2 \left[ \frac{(\sum_{i\in I_L}g_i)^2}{(\sum_{i\in I_L}h_i)+\lambda}+\frac{(\sum_{i\in I_R}g_i)^2}{(\sum_{i\in I_R}h_i)+\lambda} - \frac{(\sum_{i\in I}g_i)^2}{(\sum_{i\in I}h_i)+\lambda} \right]-\gamma$$

可以用上式来评估该点是否值得分支。

防止过拟合

由于树形模型容易过拟合，除了正则项，我们还可以引入学习率 $\eta$（可能是这样👇）:

$$J(\Theta) = \sum_{i=1}^m L\left(y^{(i)},f_{k'-1}(x^{(i)}) + \eta T(x^{(i)};\Theta_{k'})\right) + \Omega(f_K)$$

或者采用类似于随机森林的列采样，每棵树只对随机抽取的特征进行训练。

切分点选择

第一种方法就是遍历所有的属性的所有可能切分点，找出最佳切分点 $\hat J_\text{split}$。当然，如果数据量过大导致内存不能全部加载，则不能使用这种贪婪算法。

第二种方法就是：对属性 $j$ 利用一组分位点 $S_j$ 进行切分

$$S_j=\{ s_{j1},s_{j2},\dots \}$$

将连续的数据依据这些分位点进行分桶。当想寻找切分点时，遍历这些分位点，找到最优位置即可。根据切分策略的不同，分为整个树只使用一组切分点与每个切分点都用一组切分点两种策略。

在 XGBoost 中，运用了一种加权的方式。我们可以将代价函数重写成

$$\begin{align} J(\Theta) &= \sum_{i=1}^m \left(g^{(i)}_{k'-1}T(x^{(i)};\Theta_{k'}) + \frac 1 2h^{(i)}_{k'-1}T^2(x^{(i)};\Theta_{k'}) \right) + \Omega(f_{k'})\\ &=\sum_{i=1}^m \frac 1 2 h^{(i)}_{k'-1}\left(2\frac {g^{(i)}_{k'-1}}{h^{(i)}_{k'-1}}T(x^{(i)};\Theta_{k'}) + T^2(x^{(i)};\Theta_{k'}) + (\frac {g^{(i)}_{k'-1}}{h^{(i)}_{k'-1}})^2\right) + \Omega(f_{k'})+C\\ &=\sum_{i=1}^m \frac 1 2 h^{(i)}_{k'-1}\left(T(x^{(i)};\Theta_{k'}) - (-\frac {g^{(i)}_{k'-1}}{h^{(i)}_{k'-1}})\right)^2 + \Omega(f_{k'})+C \end{align}$$

这样就可以把代价函数看成加权最小二乘法，权重为 $h^{(i)}{k’-1}$，$-\frac {g^{(i)}{k’-1}}{h^{(i)}_{k’-1}}$ 是二阶泰勒展开的最优点。

稀疏处理

XGBoost 还可以自动处理空缺值。模型将属性 $j$ 的空缺的样本先不参与分支，将其归为一类 $I{j,\text{null}}$，之后将其中的样本分别归入分支后的左右节点 $I_L,I_R$，比较一下那种情况的代价函数最优，选择最优的一边将 $I{j,\text{null}}$ 中的样本归入其中。