二、xgboost

发布于 2023-07-17 23:38:26 字数 15752 浏览 0 评论 0 收藏 0

xgboost 也是使用与提升树相同的前向分步算法。其区别在于：xgboost 通过结构风险极小化来确定下一个决策树的参数 $ MathJax-Element-104 $ ：
$ \hat\Theta_m=\arg\min_{\Theta_m}\sum_{i=1}^{N}L(\tilde y_i,f_m(\mathbf {\vec x}_i))+\Omega(h_m(\mathbf {\vec x})) $
其中：
- $ MathJax-Element-105 $ 为第 $ MathJax-Element-227 $ 个决策树的正则化项。这是xgboost 和GBT的一个重要区别。
- $ MathJax-Element-107 $ 为目标函数。
定义：
$ \hat y_{i}^{
}=f_{m-1}(\mathbf {\vec x}_i),\quad g_i=\frac{\partial L(\tilde y_i,\hat y_{i}^{
})}{\partial \,\hat y_{i}^{
}},\quad h_i=\frac{\partial^2 L(\tilde y_i,\hat y_{i}^{
})}{\partial ^2\,\hat y_{i}^{}} $
即：
$ MathJax-Element-309 $ 为 $ MathJax-Element-109 $ 在 $ MathJax-Element-110 $ 的一阶导数。
$ MathJax-Element-230 $ 为 $ MathJax-Element-112 $ 在 $ MathJax-Element-142 $ 的二阶导数。
对目标函数 $ MathJax-Element-131 $ 执行二阶泰勒展开：
$ \mathcal L=\sum_{i=1}^{N}L(\tilde y_i,f_m(\mathbf {\vec x}_i))+\Omega(h_m(\mathbf {\vec x}))=\sum_{i=1}^{N}L(\tilde y_i,\hat y_{i}^{}+h_m(\mathbf {\vec x}_i))+\Omega(h_m(\mathbf {\vec x}))\\ \simeq \sum_{i=1}^N\left[ L(\tilde y_i,\hat y_{i}^{})+g_ih_m(\mathbf {\vec x}_i)+\frac 12 h_ih_m^2(\mathbf {\vec x}_i) \right]+\Omega(h_m(\mathbf {\vec x}))+\text{constant} $
提升树模型只采用一阶泰勒展开。这也是xgboost 和GBT的另一个重要区别。
对一个决策树 $ MathJax-Element-277 $ ，假设不考虑复杂的推导过程，仅考虑决策树的效果：
- 给定输入 $ MathJax-Element-122 $ ，该决策树将该输入经过不断的划分，最终划分到某个叶结点上去。
- 给定一个叶结点，该叶结点有一个输出值。
因此将决策树拆分成结构部分 $ MathJax-Element-117 $ ，和叶结点权重部分 $ MathJax-Element-118 $ ，其中 $ MathJax-Element-151 $ 为叶结点的数量。
- 结构部分 $ MathJax-Element-120 $ 的输出是叶结点编号 $ MathJax-Element-328 $ 。它的作用是将输入 $ MathJax-Element-122 $ 映射到编号为 $ MathJax-Element-328 $ 的叶结点。
- 叶结点权重部分就是每个叶结点的值。它的作用是输出编号为 $ MathJax-Element-328 $ 的叶结点的值 $ MathJax-Element-125 $ 。
因此决策树改写为： $ MathJax-Element-126 $ 。

2.1 结构分

定义一个决策树的复杂度为： $ MathJax-Element-127 $ 。
其中： $ MathJax-Element-151 $ 为叶结点的个数； $ MathJax-Element-148 $ 为每个叶结点的输出值； $ MathJax-Element-130 $ 为系数，控制这两个部分的比重。
- 叶结点越多，则决策树越复杂。
- 每个叶结点输出值的绝对值越大，则决策树越复杂。
该复杂度是一个经验公式。事实上还有很多其他的定义复杂度的方式，只是这个公式效果还不错。
将树的拆分、树的复杂度代入 $ MathJax-Element-131 $ 的二阶泰勒展开，有：
$ \mathcal L \simeq \sum_{i=1}^N\left[ g_iw_{q(\mathbf{\vec x}_i)}+\frac 12 h_iw_{q(\mathbf{\vec x}_i)}^2 \right]+\gamma T+\frac 12\lambda \sum_{j=1}^T w_j^2+\text{constant} $
对于每个样本 $ MathJax-Element-308 $ ，它必然被划分到树 $ MathJax-Element-133 $ 的某个叶结点。定义划分到叶结点 $ MathJax-Element-455 $ 的样本的集合为： $ MathJax-Element-135 $ 。则有：
$ \mathcal L \simeq \sum_{j=1}^T\left[ \left( \sum_{i\in \mathbb I_j}g_i\right)w_j+\frac 12 \left(\sum_{i\in\mathbb I_j}h_i +\lambda \right)w_j^2\right]+\gamma T+\text{constant} $
定义： $ MathJax-Element-136 $ 。
- $ MathJax-Element-137 $ 刻画了隶属于叶结点 $ MathJax-Element-455 $ 的那些样本的一阶偏导数之和。
- $ MathJax-Element-139 $ 刻画了隶属于叶结点 $ MathJax-Element-455 $ 的那些样本的二阶偏导数之和。
偏导数是损失函数 $ MathJax-Element-141 $ 关于当前模型的输出 $ MathJax-Element-142 $ 的偏导数。
则上式化简为： $ MathJax-Element-143 $ 。
假设 $ MathJax-Element-148 $ 与与 $ MathJax-Element-149 $ 无关，对 $ MathJax-Element-148 $ 求导等于0，则得到： $ MathJax-Element-147 $ 。
忽略常数项，于是定义目标函数为：
$ \mathcal L^{*}=-\frac12 \sum_{j=1}^T\frac{\mathbf G_j^2}{\mathbf H_j+\lambda}+\gamma T $
在推导过程中假设 $ MathJax-Element-148 $ 与与 $ MathJax-Element-149 $ 无关，这其实假设已知树的结构。
事实上 $ MathJax-Element-150 $ 是与 $ MathJax-Element-151 $ 相关的，甚至与树的结构相关，因此定义 $ MathJax-Element-152 $ 为结构分。
结构分刻画了：当已知树的结构时目标函数的最小值。

2.2 分解结点

现在的问题是：如何得到最佳的树的结构，从而使得目标函数全局最小。

2.2.1 贪心算法

第一种方法是对现有的叶结点加入一个分裂，然后考虑分裂之后目标函数降低多少。
- 如果目标函数下降，则说明可以分裂。
- 如果目标函数不下降，则说明该叶结点不宜分裂。
对于一个叶结点，假如给定其分裂点，定义划分到左子结点的样本的集合为： $ MathJax-Element-153 $ ；定义划分到右子结点的样本的集合为： $ MathJax-Element-154 $ 。则有：
$ \mathbf G_L=\sum_{i\in \mathbb I_L}g_i,\; \mathbf G_R=\sum_{i\in \mathbb I_R}g_i,\\ \mathbf H_L=\sum_{i\in \mathbb I_L}h_i \;\mathbf H_R=\sum_{i\in \mathbb I_R}h_i \\ \mathbf G = \sum_{i\in \mathbb I_L}g_i+\sum_{i\in \mathbb I_R}g_i = \mathbf G_L+\mathbf G_R\\ \mathbf H = \sum_{i\in \mathbb I_L}h_i+ \sum_{i\in \mathbb I_R}h_i = \mathbf H_L+\mathbf H_R $
定义叶结点的分裂增益为：
$ Gain=\frac 12\left[\frac{\mathbf G_L^2}{\mathbf H_L+\lambda}+\frac{\mathbf G_R^2}{\mathbf H_R+\lambda}-\frac{\mathbf G^2}{\mathbf H +\lambda}\right]-\lambda $
其中：
- $ MathJax-Element-155 $ 表示：该叶结点的左子树的结构分。
- $ MathJax-Element-156 $ 表示：该叶结点的右子树的结构分。
- $ MathJax-Element-157 $ 表示：如果不分裂，则该叶结点本身的结构分。
- $ MathJax-Element-158 $ 表示：因为分裂导致叶结点数量增大1，从而导致增益的下降。
每次分裂只一个叶结点，因此其它叶结点不会发生变化。因此：
- 若 $ MathJax-Element-159 $ ，则该叶结点应该分裂。
- 若 $ MathJax-Element-160 $ ，则该叶结点不宜分裂。
现在的问题是：不知道分裂点。对于每个叶结点，存在很多个分裂点，且可能很多分裂点都能带来增益。
解决的办法是：对于叶结点中的所有可能的分裂点进行一次扫描。然后计算每个分裂点的增益，选取增益最大的分裂点作为本叶结点的最优分裂点。
最优分裂点贪心算法：
- 输入：
  - 数据集 $ MathJax-Element-437 $ ，其中样本 $ MathJax-Element-438 $ 。
  - 属于当前叶结点的样本集的下标集合 $ MathJax-Element-234 $ 。
- 输出：当前叶结点最佳分裂点。
- 算法：
  - 初始化： $ MathJax-Element-237 $ 。
  - 遍历各维度： $ MathJax-Element-238 $
    - 初始化： $ MathJax-Element-239 $
    - 遍历各拆分点：沿着第 $ MathJax-Element-474 $ 维：
      - 如果第 $ MathJax-Element-474 $ 维特征为连续值，则将当前叶结点中的样本从小到大排序。然后用 $ MathJax-Element-455 $ 顺序遍历排序后的样本下标：
        $ \mathbf G_L\leftarrow\mathbf G_L+ g_{j},\quad\mathbf H_L\leftarrow \mathbf H_L+ h_{j}\\ \mathbf G_R\leftarrow\mathbf G-\mathbf G_L ,\quad\mathbf H_R\leftarrow \mathbf H-\mathbf H_L \\ score\leftarrow \max(score,\frac{\mathbf G_L^2}{\mathbf H_L+\lambda}+\frac{\mathbf G_R^2}{\mathbf H_R+\lambda}-\frac{\mathbf G^2}{\mathbf H+\lambda}) $
      - 如果第 $ MathJax-Element-474 $ 维特征为离散值 $ MathJax-Element-171 $ ，设当前叶结点中第 $ MathJax-Element-474 $ 维取值 $ MathJax-Element-173 $ 样本的下标集合为 $ MathJax-Element-174 $ ，则遍历 $ MathJax-Element-175 $ ：
        $ \mathbf G_L\leftarrow \sum_{i\in \mathbb I_{j }} g_i,\quad\mathbf H_L\leftarrow \sum_{i\in \mathbb I_{j }} h_i\\ \mathbf G_R\leftarrow\mathbf G-\mathbf G_L ,\quad\mathbf H_R\leftarrow \mathbf H-\mathbf H_L \\ score\leftarrow \max(score,\frac{\mathbf G_L^2}{\mathbf H_L+\lambda}+\frac{\mathbf G_R^2}{\mathbf H_R+\lambda}-\frac{\mathbf G^2}{\mathbf H+\lambda}) $
  - 选取最大的 $ MathJax-Element-245 $ 对应的维度和拆分点作为最优拆分点。
分裂点贪心算法尝试所有特征和所有分裂位置，从而求得最优分裂点。
当样本太大且特征为连续值时，这种暴力做法的计算量太大。

2.2.2 近似算法

近似算法寻找最优分裂点时不会枚举所有的特征值，而是对特征值进行聚合统计，然后形成若干个桶。
然后仅仅将桶边界上的特征的值作为分裂点的候选，从而获取计算性能的提升。
假设数据集 $ MathJax-Element-437 $ ，样本 $ MathJax-Element-438 $ 。
对第 $ MathJax-Element-474 $ 个特征进行分桶：
- 如果第 $ MathJax-Element-474 $ 个特征为连续特征，则执行百分位分桶，得到分桶的区间为： $ MathJax-Element-213 $ ，其中 $ MathJax-Element-195 $ 。
  分桶的数量、分桶的区间都是超参数，需要仔细挑选。
- 如果第 $ MathJax-Element-474 $ 个特征为离散特征，则执行按离散值分桶，得到的分桶为： $ MathJax-Element-213 $ ，其中 $ MathJax-Element-185 $ 为第 $ MathJax-Element-474 $ 个特征的所有可能的离散值。
  分桶的数量 $ MathJax-Element-187 $ 就是所有样本在第 $ MathJax-Element-474 $ 个特征上的取值的数量。
最优分裂点近似算法：
- 输入：
  - 数据集 $ MathJax-Element-437 $ ，其中样本 $ MathJax-Element-438 $ 。
  - 属于当前叶结点的样本集的下标集合 $ MathJax-Element-234 $ 。
- 输出：当前叶结点最佳分裂点。
- 算法：
  - 对每个特征进行分桶。假设对第 $ MathJax-Element-474 $ 个特征上的值进行分桶为： $ MathJax-Element-213 $ 。
    如果第 $ MathJax-Element-474 $ 个特征为连续特征，则要求满足 $ MathJax-Element-195 $ 。
  - 初始化： $ MathJax-Element-237 $ 。
  - 遍历各维度： $ MathJax-Element-238 $
    - 初始化： $ MathJax-Element-239 $
    - 遍历各拆分点，即遍历 $ MathJax-Element-199 $ ：
      - 如果是连续特征，则设叶结点的样本中，第 $ MathJax-Element-474 $ 个特征取值在区间 $ MathJax-Element-201 $ 的样本的下标集合为 $ MathJax-Element-205 $ ，则：
        $ \mathbf G_L\leftarrow\mathbf G_L+\sum_{ i\in \mathbb I_j}g_i,\quad \mathbf H_L\leftarrow \mathbf H_L+ \sum_{ i\in \mathbb I_j}h_i\\ \mathbf G_R\leftarrow\mathbf G-\mathbf G_L ,\quad\mathbf H_R\leftarrow \mathbf H-\mathbf H_L \\ score\leftarrow \max(score,\frac{\mathbf G_L^2}{\mathbf H_L+\lambda}+\frac{\mathbf G_R^2}{\mathbf H_R+\lambda}-\frac{\mathbf G^2}{\mathbf H+\lambda}) $
      - 如果是离散特征，则设叶结点的样本中，第 $ MathJax-Element-474 $ 个特征取值等于 $ MathJax-Element-221 $ 的样本的下标集合为 $ MathJax-Element-205 $ ，则：
        $ \mathbf G_L\leftarrow \sum_{i\in \mathbb I_{j }} g_i,\quad\mathbf H_L\leftarrow \sum_{i\in \mathbb I_{j }} h_i\\ \mathbf G_R\leftarrow\mathbf G-\mathbf G_L ,\quad\mathbf H_R\leftarrow \mathbf H-\mathbf H_L \\ score\leftarrow \max(score,\frac{\mathbf G_L^2}{\mathbf H_L+\lambda}+\frac{\mathbf G_R^2}{\mathbf H_R+\lambda}-\frac{\mathbf G^2}{\mathbf H+\lambda}) $
    - 选取最大的 $ MathJax-Element-245 $ 对应的维度和拆分点作为最优拆分点。
分桶有两种模式：
- 全局模式：在算法开始时，对每个维度分桶一次，后续的分裂都依赖于该分桶并不再更新。
  - 优点是：只需要计算一次，不需要重复计算。
  - 缺点是：在经过多次分裂之后，叶结点的样本有可能在很多全局桶中是空的。
- 局部模式：除了在算法开始时进行分桶，每次拆分之后再重新分桶。
  - 优点是：每次分桶都能保证各桶中的样本数量都是均匀的。
  - 缺点是：计算量较大。
全局模式会构造更多的候选拆分点。而局部模式会更适合构建更深的树。
分桶时的桶区间间隔大小是个重要的参数。
区间间隔越小，则桶越多，则划分的越精细，候选的拆分点就越多。

2.3 加权分桶

假设候选样本的第 $ MathJax-Element-474 $ 维特征，及候选样本的损失函数的二阶偏导数为：
$ \mathcal D_k=\{(x_{1,k},h_1),(x_{2,k},h_2),\cdots,(x_{N,k},h_N)\} $
定义排序函数：
$ r_k(z)=\frac{\sum_{\{i\mid (x_{i,k},h_i)\in \mathcal D_k,x_{i,k}\lt z\}} h_i}{\sum_{\{i\mid (x_{i,k},h_i)\in \mathcal D_k\}} h_i} $
它刻画的是：第 $ MathJax-Element-474 $ 维小于 $ MathJax-Element-209 $ 的样本的 $ MathJax-Element-231 $ 之和，占总的 $ MathJax-Element-231 $ 之和的比例。
xgboost 的作者提出了一种带权重的桶划分算法。定义候选样本的下标集合为 $ MathJax-Element-234 $ ，拆分点 $ MathJax-Element-213 $ 定义为：
$ s_{k,1}=\min_{i\in \mathbb I} x_{i,k},\; s_{k,l}=\max_ {i\in \mathbb I}x_{i,k},\quad |r_k(s_{k,j})-r_k(s_{k,j+1})|\lt \epsilon $
其中 $ MathJax-Element-214 $ 表示样本 $ MathJax-Element-308 $ 的第 $ MathJax-Element-474 $ 个特征。即：
- 最小的拆分点是所有样本第 $ MathJax-Element-474 $ 维的最小值。
- 最大的拆分点是所有样本第 $ MathJax-Element-474 $ 维的最大值。
- 中间的拆分点：选取拆分点，使得相邻拆分点的排序函数值小于 $ MathJax-Element-219 $ （分桶的桶宽）。
  - 其意义为：第 $ MathJax-Element-474 $ 维大于等于 $ MathJax-Element-221 $ ，小于 $ MathJax-Element-222 $ 的样本的 $ MathJax-Element-231 $ 之和，占总的 $ MathJax-Element-231 $ 之和的比例小于 $ MathJax-Element-225 $ 。
  - 这种拆分点使得每个桶内的以 $ MathJax-Element-231 $ 为权重的样本数量比较均匀，而不是样本个数比较均匀。
上述拆分的一个理由是：根据损失函数的二阶泰勒展开有：
$ \mathcal L \simeq \sum_{i=1}^N\left[ L(\tilde y_i,\hat y_{i}^{})+g_ih_m(\mathbf {\vec x}_i)+\frac 12 h_ih_m^2(\mathbf {\vec x}_i) \right]+\Omega(h_m(\mathbf {\vec x}))+\text{constant}\\ = \sum_{i=1}^N\frac 12 h_i\left[ \frac{2g_i}{h_i}h_m(\mathbf {\vec x}_i)+h_m^2(\mathbf {\vec x}_i) \right]+\Omega(h_m(\mathbf {\vec x}))+\text{constant}\\ =\sum_{i=1}^N\frac 12h_i\left(h_m(\mathbf {\vec x}_i)-\frac{g_i}{h_i}\right)^2+\Omega^\prime(h_m(\mathbf {\vec x}))+\text{constant} $
对于第 $ MathJax-Element-227 $ 个决策树，它等价于样本 $ MathJax-Element-308 $ 的真实标记为 $ MathJax-Element-229 $ 、权重为 $ MathJax-Element-230 $ 、损失函数为平方损失函数。因此分桶时每个桶的权重为 $ MathJax-Element-231 $ 。

2.4 缺失值

真实场景中，有很多可能导致产生稀疏。如：数据缺失、某个特征上出现很多 0 项、人工进行 one-hot 编码导致的大量的 0。
- 理论上，数据缺失和数值0的含义是不同的，数值 0 是有效的。
- 实际上，数值0的处理方式类似缺失值的处理方式，都视为稀疏特征。
  在xgboost 中，数值0的处理方式和缺失值的处理方式是统一的。这只是一个计算上的优化，用于加速对稀疏特征的处理速度。
- 对于稀疏特征，只需要对有效值进行处理，无效值则采用默认的分裂方向。
  注意：每个结点的默认分裂方向可能不同。
在xgboost 算法的实现中，允许对数值0进行不同的处理。可以将数值0视作缺失值，也可以将其视作有效值。
如果数值0是有真实意义的，则建议将其视作有效值。
缺失值处理算法：
- 输入：
  - 数据集 $ MathJax-Element-437 $ ，其中样本 $ MathJax-Element-438 $ 。
  - 属于当前叶结点的样本的下标集合 $ MathJax-Element-234 $ 。
  - 属于当前叶结点，且第 $ MathJax-Element-474 $ 维特征有效的样本的下标集合 $ MathJax-Element-236 $ 。
- 输出：当前叶结点最佳分裂点。
- 算法：
  - 初始化： $ MathJax-Element-237 $ 。
  - 遍历各维度： $ MathJax-Element-238 $
    - 先从左边开始遍历：
      - 初始化： $ MathJax-Element-239 $
      - 遍历各拆分点：沿着第 $ MathJax-Element-474 $ 维，将当前有效的叶结点的样本从小到大排序。
        这相当于所有无效特征值的样本放在最右侧，因此可以保证无效的特征值都在右子树。
        然后用 $ MathJax-Element-455 $ 顺序遍历排序后的样本下标：
      $ \mathbf G_L\leftarrow\mathbf G_L+ g_j,\quad\mathbf H_L\leftarrow \mathbf H_L+ h_j\\ \mathbf G_R\leftarrow\mathbf G-\mathbf G_L ,\quad\mathbf H_R\leftarrow \mathbf H-\mathbf H_L \\ score\leftarrow \max(score,\frac{\mathbf G_L^2}{\mathbf H_L+\lambda}+\frac{\mathbf G_R^2}{\mathbf H_R+\lambda}-\frac{\mathbf G^2}{\mathbf H+\lambda}) $
    - 再从右边开始遍历：
      - 初始化： $ MathJax-Element-242 $
      - 遍历各拆分点：沿着 $ MathJax-Element-474 $ 维，将当前叶结点的样本从大到小排序。
        这相当于所有无效特征值的样本放在最左侧，因此可以保证无效的特征值都在左子树。
        然后用 $ MathJax-Element-455 $ 逆序遍历排序后的样本下标：
      $ \mathbf G_R\leftarrow\mathbf G_R+ g_j,\quad\mathbf H_R\leftarrow \mathbf H_R+ h_j\\ \mathbf G_L\leftarrow\mathbf G-\mathbf G_R ,\quad\mathbf H_L\leftarrow \mathbf H-\mathbf H_R \\ score\leftarrow \max(score,\frac{\mathbf G_L^2}{\mathbf H_L+\lambda}+\frac{\mathbf G_R^2}{\mathbf H_R+\lambda}-\frac{\mathbf G^2}{\mathbf H+\lambda}) $
  - 选取最大的 $ MathJax-Element-245 $ 对应的维度和拆分点作为最优拆分点。
缺失值处理算法中，通过两轮遍历可以确保稀疏值位于左子树和右子树的情形。

2.5 其他优化

2.5.1 正则化

xgboost 在学习过程中使用了如下的正则化策略来缓解过拟合：
- 通过学习率 $ MathJax-Element-246 $ 来更新模型： $ MathJax-Element-247 $ 。
- 类似于随机森林，采取随机属性选择。

2.5.2 计算速度提升

xgboost 在以下方面提出改进来提升计算速度：
- 预排序pre-sorted 。
- cache-aware 预取。
- Out-of-Core 大数据集。

2.5.2.1 预排序

xgboost 提出column block 数据结构来降低排序时间。
- 每一个block 代表一个属性，样本在该block 中按照它在该属性的值排好序。
- 这些block 只需要在程序开始的时候计算一次，后续排序只需要线性扫描这些block 即可。
- 由于属性之间是独立的，因此在每个维度寻找划分点可以并行计算。
block 可以仅存放样本的索引，而不是样本本身，这样节省了大量的存储空间。
如：block_1 代表所有样本在feature_1 上的从小到大排序：sample_no1,sample_no2,.... 。
其中样本编号出现的位置代表了该样本的排序。

2.5.2.2 预取

由于在column block 中，样本的顺序会被打乱，这会使得从导数数组中获取 $ MathJax-Element-309 $ 时的缓存命中率较低。
因此xgboost 提出了cache-aware 预取算法，用于提升缓存命中率。
xgboost 会以minibatch 的方式累加数据，然后在后台开启一个线程来加载需要用到的导数 $ MathJax-Element-309 $ 。
这里有个折中：minibatch 太大，则会引起cache miss ；太小，则并行程度较低。

2.5.2.3 Out-of-Core

xgboost 利用硬盘来处理超过内存容量的大数据集。其中使用了下列技术：
- 使用block 压缩技术来缓解内存和硬盘的数据交换IO ：数据按列压缩，并且在硬盘到内存的传输过程中被自动解压缩。
- 数据随机分片到多个硬盘，每个硬盘对应一个预取线程，从而加大"内存-硬盘"交换数据的吞吐量。

分享到QQ

分享到微博