Question

1. GBT 的缺点：在构建子决策树时为了获取分裂点，需要在所有特征上扫描所有的样本，从而获得最大的信息增益。

   • 当样本的数量很大，或者样本的特征很多时，效率非常低。
   • 同时GBT 也无法使用类似mini batch 方式进行训练。

2. xgboost 缺点：

   • 每轮迭代都需要遍历整个数据集多次。

     • 如果把整个训练集装载进内存，则限制了训练数据的大小。
     • 如果不把整个训练集装载进内存，则反复读写训练数据会消耗非常大的IO 时间。

   • 空间消耗大。预排序（pre-sorted）需要保存数据的feature 值，还需要保存feature 排序的结果（如排序后的索引，为了后续的快速计算分割点）。因此需要消耗训练数据两倍的内存。

   • 时间消耗大。为了获取分裂点，需要在所有特征上扫描所有的样本，从而获得最大的信息增益，时间消耗大。

   • 对cache 优化不友好，造成cache miss 。

     • 预排序后，feature 对于梯度的访问是一种随机访问，并且不同feature 访问的顺序不同，无法对cache 进行优化。
     • 在每一层的树生长时，需要随机访问一个行索引到叶子索引的数组，并且不同feature 访问的顺序也不同。

3. LightGBM 的优点：

   • 更快的训练效率：在达到同样的准确率的情况下，可以达到比GBT 约20倍的训练速度。
   • 低内存使用。
   • 更高的准确率。
   • 支持并行化学习。
   • 可处理大规模数据。

   

3.1 原理

1. LightGBM 的思想：若减少训练样本的数量，或者减少样本的训练特征数量，则可以大幅度提高训练速度。

2. LightGBM 提出了两个策略：

   • Gradient-based One-Side Sampling(GOSS)： 基于梯度的采样。该方法用于减少训练样本的数量。
   • Exclusive Feature Bundling(EFB)： 基于互斥特征的特征捆绑。该方法用于减少样本的特征。

3.1.1 GOSS

3.1.1.1 算法

1. 减少样本的数量的难点在于：不知道哪些样本应该被保留，哪些样本被丢弃。

   • 传统方法：采用随机丢弃的策略。
   • GOSS 方法：保留梯度较大的样本，梯度较小的样本则随机丢弃。

2. 在AdaBoost 中每个样本都有一个权重，该权重指示了样本在接下来的训练过程中的重要性。

   在GBDT 中并没有这样的权重。如果能知道每个样本的重要性（即：权重），那么可以保留比较重要的样本，丢弃不那么重要的样本。

   由于GBDT 中，负的梯度作为当前的残差，接下来的训练就是拟合这个残差。因此GOSS 采用样本的梯度作为样本的权重：

   • 如果权重较小，则说明样本的梯度较小，说明该样本已经得到了很好的训练。因此对于权重较小的样本，则可以随机丢弃。
   • 如果权重较大，则说明样本的梯度较大，说明该样本未能充分训练。因此对于权重较大的样本，则需要保留。

3. GOSS 丢弃了部分样本，因此它改变了训练样本的分布。这会影响到模型的预测准确性。

   为了解决这个问题，GOSS 对小梯度的样本进行了修正：对每个保留下来的、小梯度的样本，其梯度乘以系数 $ MathJax-Element-341 $ （即放大一个倍数）。

   其中（假设样本总数为 $ MathJax-Element-467 $ ）：

   • $ MathJax-Element-260 $ 是一个0.0~1.0 之间的数，表示大梯度采样比。

     其意义为：保留梯度的绝对值在 top $ MathJax-Element-253 $ 的样本作为重要的样本。

   • $ MathJax-Element-334 $ 是一个0.0~1.0 之间的数，表示小梯度采样比。

     其意义为：从不重要的样本中随机保留 $ MathJax-Element-255 $ 的样本。

   • $ MathJax-Element-256 $ 是一个0.0~1.0 之间的数，表示不重要的样本的比例。

   • $ MathJax-Element-341 $ 刻画了：从不重要的样本中，随机保留的样本的比例的倒数。

4. GOSS 算法：

   • 输入：

     • 训练集 $ MathJax-Element-258 $ ，其样本数量为 $ MathJax-Element-467 $
     • 大梯度采样比 $ MathJax-Element-260 $
       
     • 小梯度采样比 $ MathJax-Element-334 $
     • 当前的模型 $ MathJax-Element-262 $

   • 输出：下一个子树 $ MathJax-Element-277 $

   • 算法：

     • 计算：

       • 修正因子 $ MathJax-Element-264 $
       • 重要的样本数为 $ MathJax-Element-265 $
       • 随机丢弃的样本数为 $ MathJax-Element-266 $
       • 每个样本的损失函数的梯度 $ MathJax-Element-267 $

     • 根据梯度的绝对值大小，将样本按照从大到小排列。

       • 取其中取 $ MathJax-Element-268 $ 的样本作为重要性样本。
       • 在 $ MathJax-Element-271 $ 之外的样本中，随机选取 $ MathJax-Element-272 $ 的样本作为保留样本，剩下的样本被丢弃。

     • 构建新的训练集：重要性样本+随机保留的样本，其中：

       • $ MathJax-Element-271 $ 个重要性样本，每个样本的权重都为 1。
       • $ MathJax-Element-272 $ 个随机保留的样本，每个样本的权重都为 $ MathJax-Element-273 $ 。

     • 根据新的训练集及其权重，训练决策树模型 $ MathJax-Element-277 $ 来拟合残差（即：负梯度 $ MathJax-Element-275 $ ）。返回训练好的 $ MathJax-Element-277 $ 。

5. 由于需要在所有的样本上计算梯度，因此 丢弃样本的比例 ～ 加速比 并不是线性的关系。

3.1.1.2 理论

1. 在GBDT 生成新的子决策树 $ MathJax-Element-277 $ 时，对于当前结点 $ MathJax-Element-330 $ ，考虑是否对它进行分裂。

   假设结点 $ MathJax-Element-330 $ 包含的样本集合为 $ MathJax-Element-280 $ ， 样本维数为 $ MathJax-Element-468 $ 。对于第 $ MathJax-Element-455 $ 维，假设其拆分点为 $ MathJax-Element-283 $ 。

   • 对于分类问题，其拆分增益为信息增益。它刻画的是划分之后混乱程度的降低，也就是纯净程度的提升：

     $ Gain_{j\mid O}(d)=p(O)H(y\mid O)- p(Left) H(y\mid Left)-p(Right)H(y\mid Right) $

     其中：

     • $ MathJax-Element-284 $ 表示样本属于结点 $ MathJax-Element-330 $ 的概率， $ MathJax-Element-286 $ 为结点 $ MathJax-Element-330 $ 上的样本标记的条件熵。
     • $ MathJax-Element-300 $ 表示左子结点的样本集合； $ MathJax-Element-301 $ 表示右子结点的样本集合。
     • $ MathJax-Element-290 $ 表示样本属于结点 $ MathJax-Element-330 $ 的左子结点概率， $ MathJax-Element-292 $ 为左子结点的样本标记的条件熵。
     • $ MathJax-Element-293 $ 表示样本属于结点 $ MathJax-Element-330 $ 的右子结点概率， $ MathJax-Element-295 $ 为右子结点的样本标记的条件熵。

     对于结点 $ MathJax-Element-330 $ 的任意拆分点，由于 $ MathJax-Element-297 $ 都相同，所以：

     $ \max_{j,d}(Gain_{j\mid O}(d)) \rightarrow \min_{j,d}p(Left) H(y\mid Left)+p(Right)H(y\mid Right) $

   • 对于回归问题，其拆分增益为方差增益(variance gain:VG)。它刻画的是划分之后方差的下降；也就是纯净程度的提升：

     $ Gain_{j\mid O}(d)=p(O)Var(y\mid O)-p(Left)Var(y\mid Left)-p(Right)Var(y\mid Right) $

     其中：

     • $ MathJax-Element-298 $ 表示属于结点 $ MathJax-Element-330 $ 的样本的标记的方差。
     • $ MathJax-Element-300 $ 表示左子结点的样本集合； $ MathJax-Element-301 $ 表示右子结点的样本集合。
     • $ MathJax-Element-302 $ 表示属于结点 $ MathJax-Element-330 $ 的左子结点的样本的标记的方差。
     • $ MathJax-Element-304 $ 表示属于结点 $ MathJax-Element-330 $ 的右子结点的样本的标记的方差。

     对于结点 $ MathJax-Element-330 $ 的任意拆分点，由于 $ MathJax-Element-307 $ 都相同，所以：

     $ \max_{j,d}(Gain_{j\mid O}(d)) \rightarrow \min_{j,d}p(Left) Var(y\mid Left)+p(Right)Var(y\mid Right) $

2. 对于样本 $ MathJax-Element-308 $ ，设其标记为 $ MathJax-Element-309 $ （它是残差，也是负梯度）。

   对于结点 $ MathJax-Element-330 $ 中的样本，设其样本数量为 $ MathJax-Element-311 $ ，样本的标记均值为 $ MathJax-Element-312 $ ，其方差为：

   $ Var(y\mid O)=\frac{\sum_{i:\mathbf{\vec x}_i\in \mathbb O}(g_i-\bar g)^2}{n_O} =\frac{\sum_{i:\mathbf{\vec x}_i\in \mathbb O}g_i^2-\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb O}g_i\right)^2}{n_O}}{n_O} $

   设总样本数量为 $ MathJax-Element-467 $ ， 则 $ MathJax-Element-314 $ ，则有：

   $ p(O)Var(y\mid O)=\frac{\sum_{i:\mathbf{\vec x}_i\in \mathbb O}g_i^2-\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb O}g_i\right)^2}{n_O}}{N} $

3. 现在考虑回归问题。

   对于拆分维度 $ MathJax-Element-455 $ 和拆分点 $ MathJax-Element-328 $ ， 令左子结点的样本下标为 $ MathJax-Element-317 $ ，样本数量为 $ MathJax-Element-320 $ 右子结点的样本下标为 $ MathJax-Element-319 $ ， 样本数量为 $ MathJax-Element-320 $ 。则方差增益：

   $ p(O)Var(y\mid O)-p(Left)Var(y\mid Left)-p(Right)Var(y\mid Right)=\\ \frac{\sum_{i:\mathbf{\vec x}_i\in \mathbb O}g_i^2-\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb O}g_i\right)^2}{n_O}}{N}-\frac{\sum_{i:\mathbf{\vec x}_i\in \mathbb L}g_i^2-\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb L}g_i\right)^2}{n_{l\mid O}(d)}}{N}-\frac{\sum_{i:\mathbf{\vec x}_i\in \mathbb R}g_i^2-\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb R}g_i\right)^2}{n_{r\mid O}(d)}}{N} $

   考虑到 $ MathJax-Element-321 $ ，因此有： $ MathJax-Element-322 $ 。因此则方差增益：

   $ p(O)Var(y\mid O)-p(Left)Var(y\mid Left)-p(Right)Var(y\mid Right)=\\ \frac 1N\left[\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb L}g_i\right)^2}{n_{l\mid O}(d)}+\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb R}g_i\right)^2}{n_{r\mid O}(d)}-\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb O}g_i\right)^2}{n_O}\right] $

   考虑到总样本大小 $ MathJax-Element-467 $ 是个恒定值，因此可以去掉 $ MathJax-Element-324 $ 。考虑到 $ MathJax-Element-325 $ 并不随着结点 $ MathJax-Element-330 $ 的不同划分而变化因此定义：对于拆分维度 $ MathJax-Element-455 $ 和拆分点 $ MathJax-Element-328 $ ，方差增益为：

   $ V_{j\mid O}(d)=\left[\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb L}g_i\right)^2}{n_{l\mid O}(d)}+\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb R}g_i\right)^2}{n_{r\mid O}(d)}\right] $

4. 考虑在 GOSS 中，在划分结点 $ MathJax-Element-330 $ 的过程中，可能会随机丢弃一部分样本，从而 $ MathJax-Element-330 $ 的样本总数下降。因此重新定义方差增益：

   $ V_{j\mid O}(d)=\frac{1}{n_O}\left[\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb L}g_i\right)^2}{n_{l\mid O}(d)}+\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb R}g_i\right)^2}{n_{r\mid O}(d)}\right] $

5. 在GOSS 中：

   • 首先根据样本的梯度的绝对值大小降序排列。
   • 然后选取其中的 top a 的样本作为重要样本，设其集合为 $ MathJax-Element-331 $ 。则剩下的样本集合 $ MathJax-Element-350 $ 保留了 1-a 比例的样本。
   • 在剩下的样本集合 $ MathJax-Element-350 $ 中，随机选取总样本的 $ MathJax-Element-334 $ 比例的样本保留，设其集合为 $ MathJax-Element-436 $ 。
   • 最后将样本 $ MathJax-Element-336 $ 划分到子结点中。

   重新定义方差增益为：

   $ \tilde V_{j\mid O}(d)=\frac{1}{\tilde n_O}\left[\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb A_l}g_i+\frac{1-a}{b}\sum_{i:\mathbf{\vec x}_i\in \mathbb B_l}g_i\right)^2}{\tilde n_{l\mid O}(d)}+\frac{\left(\sum_{i:\mathbf{\vec x}_i\in \mathbb A_r}g_i+\frac{1-a}{b}\sum_{i:\mathbf{\vec x}_i\in \mathbb B_r}g_i\right)^2}{\tilde n_{r\mid O}(d)}\right] $

   其中：

   • $ MathJax-Element-337 $ 表示所有保留的样本的数量。 $ MathJax-Element-338 $ 分别表示左子结点、右子结点保留的样本的数量。

   • $ MathJax-Element-339 $ 分别表示左子结点、右子结点的被保留的重要样本的集合。

     $ MathJax-Element-340 $ 分别表示左子结点、右子结点的被保留的不重要样本的集合。

   • $ MathJax-Element-341 $ 用于补偿由于对 $ MathJax-Element-350 $ 的采样带来的梯度之和的偏离。

   由于 $ MathJax-Element-436 $ 的大小可能远远小于 $ MathJax-Element-350 $ ，因此估计 $ MathJax-Element-345 $ 需要的计算量可能远远小于估计 $ MathJax-Element-346 $ 。

6. 定义近似误差为： $ MathJax-Element-347 $ ， 定义标准的梯度均值：

   $ \bar g_l(d)=\frac{ \sum_{i:\mathbf{\vec x}_i\in \mathbb L}g_i }{n_{l\mid O}(d)} ,\quad \bar g_r(d)= \frac{ \sum_{i:\mathbf{\vec x}_i\in \mathbb R}g_i }{n_{r\mid O}(d)} $

   则可以证明：至少以概率 $ MathJax-Element-348 $ 满足：

   $ \varepsilon(d) \le C_{a,b}^2 \ln \frac 1\delta \times\max \left\{\frac{1}{n_{l\mid O}^j(d)},\frac{1}{n_{r\mid O}^j(d)}\right\}+2D\times C_{a,b}\sqrt{\frac{\ln 1/\delta}{n}} $

   其中：

   • $ MathJax-Element-349 $ ，刻画的是剩余样本集合 $ MathJax-Element-350 $ 中最大梯度的加权值。
   • $ MathJax-Element-351 $ ， 刻画的是未采取GOSS 时，划分的左子结点的梯度均值、右子结点的梯度均值中，较大的那个。

   结论：

   • 当划分比较均衡（即： $ MathJax-Element-352 $ ） 时，近似误差由不等式的第二项决定。

     此时，随着样本数量的增长，使用GOSS 和原始的算法的误差逼近于 0 。

   • 当 $ MathJax-Element-353 $ 时，GOSS 退化为随机采样。

7. GOSS 的采样增加了基学习器的多样性，有助于提升集成模型的泛化能力。

3.1.2 EFB

1. 减少样本特征的传统方法是：使用特征筛选。

   该方式通常是通过 PCA 来实现的，其中使用了一个关键的假设：不同的特征可能包含了重复的信息。这个假设很有可能在实践中无法满足。

2. LightBGM 的思路是：很多特征都是互斥的，即：这些特征不会同时取得非零的值。如果能将这些互斥的特征捆绑打包成一个特征，那么可以将特征数量大幅度降低。

   现在有两个问题：

   • 如何找到互斥的特征。
   • 如何将互斥的特征捆绑成一个特征。

3.1.2.1 互斥特征发现

1. 定义打包特征集为这样的特征的集合：集合中的特征两两互斥。

   给定数据集 $ MathJax-Element-437 $ ，其中样本 $ MathJax-Element-438 $ 。

   如果对每个 $ MathJax-Element-356 $ ，都不会出现 $ MathJax-Element-357 $ ，则特征 $ MathJax-Element-455 $ 和特征 $ MathJax-Element-474 $ 互斥。

2. 可以证明：将每个特征划分到每个打包特征集中使得打包特征集 的数量最小，这个问题是NP 难的。

   为了解决这个问题，LightGBM 采用了一个贪心算法来求解一个近似的最优解。

3. 将每个特征视为图中的一个顶点。

   遍历每个样本 $ MathJax-Element-451 $ ， 如果特征 $ MathJax-Element-382 $ 之间不互斥（即 $ MathJax-Element-378 $ ），则：

   • 如果顶点 $ MathJax-Element-382 $ 之间不存在边，则在顶点 $ MathJax-Element-382 $ 之间连接一条边，权重为 1 。
   • 如果顶点 $ MathJax-Element-382 $ 之间存在边，则顶点 $ MathJax-Element-382 $ 之间的边的权重加 1 。

   最终，如果一组顶点之间都不存在边，则它们是相互互斥的，则可以放入到同一个打包特征集 中。

4. 事实上有些特征之间并不是完全互斥的，而是存在非常少量的冲突。即：存在少量的样本，在这些样本上，这些特征之间同时取得非零的值。

   如果允许这种少量的冲突，则可以将更多的特征放入打包特征集中，这样就可以减少更多的特征。

5. 理论上可以证明：如果随机污染小部分的样本的特征的值，则对于训练accuracy 的影响是：最多影响 $ MathJax-Element-367 $ 。其中 $ MathJax-Element-368 $ 为污染样本的比例， $ MathJax-Element-467 $ 为样本数量 。

6. 互斥特征发现算法：

   • 输入：

     • 数据集 $ MathJax-Element-437 $ ，其中样本 $ MathJax-Element-438 $ 。
     • 冲突阈值 $ MathJax-Element-409 $ 。

   • 输出：打包特征集 的集合 $ MathJax-Element-436 $

   • 算法：

     • 构建图 $ MathJax-Element-406 $ ：

       • 每个特征作为一个顶点。

       • 遍历每个样本 $ MathJax-Element-451 $ ：

         • 遍历所有的特征对 $ MathJax-Element-376 $ ，如果特征 $ MathJax-Element-382 $ 之间不互斥 （即 $ MathJax-Element-378 $ ）则：

           • 如果顶点 $ MathJax-Element-382 $ 之间不存在边，则在顶点 $ MathJax-Element-382 $ 之间连接一条边，权重为 1 。
           • 如果顶点 $ MathJax-Element-382 $ 之间存在边，则顶点 $ MathJax-Element-382 $ 之间的边的权重加 1 。

     • 对每个顶点，根据 degree （与顶点相连的边的数量）来降序排列。

     • 初始化： $ MathJax-Element-418 $

     • 根据顶点的排序遍历顶点：

       设当前顶点为 $ MathJax-Element-455 $ 。

       • 遍历 打包特征集 $ MathJax-Element-420 $ ，计算顶点 $ MathJax-Element-455 $ 与 打包特征集 $ MathJax-Element-439 $ 的冲突值 $ MathJax-Element-423 $ 。如果 $ MathJax-Element-424 $ ， 则说明顶点 $ MathJax-Element-455 $ 与 打包特征集 $ MathJax-Element-426 $ 不冲突。此时将顶点 $ MathJax-Element-455 $ 添加到 打包特征集 $ MathJax-Element-439 $ 中，退出循环并考虑下一个顶点。

         顶点 $ MathJax-Element-455 $ 与 bundle 特征集 $ MathJax-Element-439 $ 的冲突值有两种计算方法：

         • 计算最大冲突值：即最大的边的权重： $ MathJax-Element-396 $
         • 计算所有的冲突值：即所有的边的权重： $ MathJax-Element-397 $

       • 如果顶点 $ MathJax-Element-455 $ 未加入到任何一个 打包特征集 中 ，则：创建一个新的 打包特征集 加入到 $ MathJax-Element-436 $ 中，并将顶点 $ MathJax-Element-455 $ 添加到这个新的 打包特征集 中。

     • 返回 $ MathJax-Element-436 $

7. 互斥特征发现算法的算法复杂度为： $ MathJax-Element-402 $ ，其中 $ MathJax-Element-467 $ 为样本总数， $ MathJax-Element-468 $ 为样本维数。

   • 复杂度主要集中在构建图 $ MathJax-Element-406 $ 。
   • 该算法只需要在训练之前执行一次。
   • 当特征数量较小时，该算法的复杂度还可以接受。当特征数量非常庞大时，该算法的复杂度太高。
   • 优化的互斥特征发现算法不再构建图 $ MathJax-Element-406 $ ，而是仅仅计算每个特征的非零值。

8. 优化的互斥特征发现算法：

   • 输入：

     • 数据集 $ MathJax-Element-437 $ ，其中样本 $ MathJax-Element-438 $ 。
     • 冲突阈值 $ MathJax-Element-409 $ 。

   • 输出：打包特征集 的集合 $ MathJax-Element-436 $

   • 算法：

     • 初始化：所有特征的非零值数量组成的数组 $ MathJax-Element-411 $

     • 计算每个特征的非零值 (复杂度 $ MathJax-Element-472 $ ) ：遍历所有的特征 $ MathJax-Element-455 $ 、遍历所有所有的样本 $ MathJax-Element-414 $ ，获取特征 $ MathJax-Element-455 $ 的非零值 $ MathJax-Element-416 $ 。

     • 根据 $ MathJax-Element-417 $ 对顶点降序排列。

     • 初始化： $ MathJax-Element-418 $

     • 根据顶点的排序遍历顶点：

       设当前顶点为 $ MathJax-Element-455 $ 。

       • 遍历 打包特征集 $ MathJax-Element-420 $ ，计算顶点 $ MathJax-Element-455 $ 与 打包特征集 $ MathJax-Element-439 $ 的冲突值 $ MathJax-Element-423 $ 。如果 $ MathJax-Element-424 $ ， 则说明顶点 $ MathJax-Element-455 $ 与 打包特征集 $ MathJax-Element-426 $ 不冲突。此时将顶点 $ MathJax-Element-455 $ 添加到 打包特征集 $ MathJax-Element-439 $ 中，退出循环并考虑下一个顶点。

         顶点 $ MathJax-Element-455 $ 与 bundle 特征集 $ MathJax-Element-439 $ 的冲突值有两种计算方法：

         • 计算最大冲突值：即最大的非零值： $ MathJax-Element-431 $
         • 计算所有的冲突值：即所有的非零值： $ MathJax-Element-432 $

         这里简单的将两个特征的非零值之和认为是它们的冲突值。它是实际的冲突值的上界。

       • 如果顶点 $ MathJax-Element-455 $ 未加入到任何一个 打包特征集 中 ，则：创建一个新的 打包特征集 加入到 $ MathJax-Element-436 $ 中，并将顶点 $ MathJax-Element-455 $ 添加到这个新的 打包特征集 中。

     • 返回 $ MathJax-Element-436 $

3.1.2.2 互斥特征打包

1. 互斥特征打包的思想：可以从打包的特征中分离出原始的特征。

   假设特征 a 的取值范围为 [0,10)， 特征 b 的取值范围为 [0,20) 。如果a,b 是互斥特征，那么打包的时候：对于特征 b的值，给它一个偏移量，比如 20。

   最终打包特征的取值范围为：[0,40)。

   • 如果打包特征的取值在 [0,10)， 说明该值来自于特征 a 。
   • 如果打包特征的取值在[20,40)，说明该值来自于特征 b 。

2. 基于histogram 的算法需要考虑分桶，但是原理也是类似：将 [0,x] 之间的桶分给特征 a， 将 [x+offset,y] 之间的桶分给特征 b。 其中 offset > 0 。

3. 互斥特征打包算法：

   • 输入：

     • 数据集 $ MathJax-Element-437 $ ，其中样本 $ MathJax-Element-438 $ 。
     • 待打包的特征集合 $ MathJax-Element-439 $ 。

   • 输出：打包之后的分桶

   • 算法：

     • 令 $ MathJax-Element-450 $ 记录总的分桶数量， $ MathJax-Element-441 $ 记录不同的特征的边界。初始化： $ MathJax-Element-442 $ 。

     • 计算特征边界：遍历所有的特征 $ MathJax-Element-443 $ ：

       • 获取特征 $ MathJax-Element-455 $ 的分桶数量 $ MathJax-Element-445 $ ，增加到 $ MathJax-Element-450 $ ： $ MathJax-Element-447 $
       • 获取特征 $ MathJax-Element-455 $ 的分桶边界： $ MathJax-Element-449 $

     • 创建新特征，它有 $ MathJax-Element-450 $ 个桶。

     • 计算分桶点：遍历每个样本 $ MathJax-Element-451 $ ：

       • 计算每个特征 $ MathJax-Element-452 $ ：

         • 如果 $ MathJax-Element-453 $ ，则：如果 $ MathJax-Element-454 $ 在特征 $ MathJax-Element-455 $ 的第 $ MathJax-Element-474 $ 个分桶中， 那么在打包后的特征中，它位于桶 $ MathJax-Element-457 $ 中。
         • 如果 $ MathJax-Element-458 $ ，则不考虑。

4. 互斥特征打包算法的算法复杂度为 $ MathJax-Element-472 $ ，其中 $ MathJax-Element-467 $ 为样本总数， $ MathJax-Element-468 $ 为样本维数。

5. 也可以首先扫描所有的样本，然后建立一张扫描表，该表中存放所有样本所有特征的非零值。

   这样互斥特征打包算法在每个特征上仅仅需要扫描非零的样本即可。这样每个特征的扫描时间从 $ MathJax-Element-462 $ 降低为 $ MathJax-Element-463 $ ， 其中 $ MathJax-Element-464 $ 为该特征上非零的样本数。

   该方法的缺陷是：消耗更多的内存，因为需要在整个训练期间保留这样的一张表。

3.2 优化

1. LightGBM 优化思路：

   • 单个机器在不牺牲速度的情况下，尽可能多地用上更多的数据。
   • 多机并行时通信的代价尽可能地低，并且在计算上可以做到线性加速。

2. LightGBM 的优化：

   • 基于histogram 的决策树算法。
   • 带深度限制的leaf-wise 的叶子生长策略。
   • 直方图做差加速。
   • 直接支持类别（categorical） 特征。
   • 并行优化。

3.2.1 histogram 算法

1. 基本思想：先把连续的浮点特征值离散化成 $ MathJax-Element-474 $ 个整数，同时构造一个宽度为 $ MathJax-Element-474 $ 的直方图。

   在遍历数据时：

   • 根据离散化后的值作为索引在直方图中累积统计量。
   • 当遍历一次数据后，直方图累积了需要的统计量。
   • 然后根据直方图的离散值，遍历寻找最优的分割点。

2. 优点：节省空间。假设有 $ MathJax-Element-467 $ 个样本，每个样本有 $ MathJax-Element-468 $ 个特征，每个特征的值都是 32 位浮点数。

   • 对于每一列特征，都需要一个额外的排好序的索引（32位的存储空间）。则pre-sorted 算法需要消耗 $ MathJax-Element-469 $ 字节内存。
   • 如果基于 histogram 算法，仅需要存储feature bin value（离散化后的数值），不需要原始的feature value，也不用排序。而bin value 用unit8_t 即可，因此histogram 算法消耗 $ MathJax-Element-470 $ 字节内存，是预排序算法的 $ MathJax-Element-471 $ 。

3. 缺点：不能找到很精确的分割点，训练误差没有pre-sorted 好。但从实验结果来看， histogram 算法在测试集的误差和 pre-sorted 算法差异并不是很大，甚至有时候效果更好。

   实际上可能决策树对于分割点的精确程度并不太敏感，而且较“粗”的分割点也自带正则化的效果。

4. 采用histogram 算法之后，寻找拆分点的算法复杂度为：

   • 构建histogram： $ MathJax-Element-472 $ 。
   • 寻找拆分点： $ MathJax-Element-473 $ ，其中 $ MathJax-Element-474 $ 为分桶的数量。

5. 与其他算法相比：

   • scikit-learn GBDT、gbm in R 使用的是基于pre-sorted 的算法。
   • pGBRT 使用的是基于histogram 的算法。
   • xgboost 既提供了基于pre-sorted 的算法，又提供了基于histogram 的算法。
   • lightgbm 使用的是基于histogram 的算法。

3.2.2 leaf-wise 生长策略

1. 大部分梯度提升树算法采用level-wise 的叶子生长策略：

   

   而lightgbm 采用leaf-wise 的叶子生长策略：

   

2. level-wise ：

   • 优点：过一遍数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。
   • 缺点：实际上level-wise是一种低效算法 。它不加区分的对待同一层的叶子，带来了很多没必要的开销：实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

3. leaf-wise：是一种更为高效的策略。每次从当前所有叶子中，找到分裂增益最大的一个叶子来分裂。

   • 优点：同level-wise 相比，在分裂次数相同的情况下，leaf-wise 可以降低更多的误差，得到更好的精度。

   • 缺点：可能会长出比较深的决策树，产生过拟合。

     因此 lightgbm 在 leaf-wise 之上增加了一个最大深度限制，在保证高效率的同时防止过拟合。

3.2.3 直方图做差加速

1. 通常构造直方图，需要遍历该叶子上的所有数据。但是事实上一个叶子的直方图可以由它的父亲结点的直方图与它兄弟的直方图做差得到。

   LightGBM 在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。

3.2.4 直接支持 categorical 特征

1. 通常对categorical 特征进行one-hot 编码，但是这个做法在决策树学习中并不好：对于取值集合较多的categorical feature，学习到的树模型会非常不平衡；树的深度需要很深才能达到较高的准确率。

   LightGBM 直接支持categorical 特征。

3.2.5 并行优化

3.2.5.1 特征并行

1. 传统的特征并行算法主要体现在决策树中的最优拆分过程中的并行化处理：

   • 沿特征维度垂直划分数据集，使得不同机器具有不同的特征集合。
   • 在本地数据集中寻找最佳划分点：(划分特征，划分阈值) 。
   • 将所有机器上的最佳划分点整合，得到全局的最佳划分点。
   • 利用全局最佳划分点对数据集进行划分，完成本次最优拆分过程。

2. LightGBM 在特征并行上进行了优化，流程如下：

   • 每个机器都有全部样本的全部特征集合。

   • 每个机器在本地数据集中寻找最佳划分点：(划分特征，划分阈值) 。

     但是不同的机器在不同的特征集上运行。

   • 将所有机器上的最佳划分点整合，得到全局的最佳划分点。

   • 利用全局最佳划分点对数据集进行划分，完成本次最优拆分过程。

3. LightGBM 不再沿特征维度垂直划分数据集，而是每个机器都有全部样本的全部特征集合。这样就节省了数据划分的通信开销。

   • 传统的特征并行算法需要在每次最优拆分中，对数据划分并分配到每台机器上。
   • LightGBM 特征并行算法只需要在程序开始时，将全量样本拷贝到每个机器上。

   二者交换的数据相差不大，但是后者花费的时间更少。

4. LightGBM 的特征并行算法在数据量很大时，仍然存在计算上的局限。因此建议在数据量很大时采用数据并行。

3.2.5.2 数据并行

1. 传统的数据并行算法主要体现在决策树的学习过程中的并行化处理：

   • 水平划分数据集，使得不同机器具有不同的样本集合。
   • 以本地数据集构建本地直方图
   • 将本地直方图整合为全局直方图
   • 在全局直方图中寻找最佳划分点。

2. LightGBM 在数据并行上进行了优化，流程如下：

   • LightGBM 使用Reduce scatter 的方式对不同机器上的不同特征进行整合。每个机器从本地整合直方图中寻找最佳划分点，并同步到全局最佳划分点中。
   • LightGBM 通过直方图做差分加速。