集成学习

该内容由个人整理和归纳，如有不同见解，还望指教～

集成学习方法有哪些？bagging和boosting的区别？(京东)

• Boosting: AdaBoost, 提升树, GBDT, XGBoost, LightGBM
• Bagging: 随机森林

区别：

• 样本采样方式不同：Bagging 是按照一定标准进行有放回采样，每次的采样是独立的，而 Boosting 每次训练使用的样本相同，但权重会发生变化。
• 样本权重不同：Bagging 是每个样本权重都相同，而 Boosting 中会提升错分样本的权重。
• 学习器的训练顺序不同：Bagging 是可以并行训练的，而 Boosting 只能串行训练 (因为后面的学习器相当于是在前面学习器的基础上做改进)。
• 学习器的结合策略不同：Bagging 在分类分类问题上是通过多数投票法则，回归问题可通过加权平均。Boosting 则是加权相加。

提升树的的随机提升版是怎么做的？

• 每一轮迭代中，新的决策树拟合的是原始训练集的一个子集（而并不是原始训练集）的残差。

  这个子集是通过对原始训练集的无放回随机采样而来。

• 子集的占比 \(f\) 是一个超参数，并且在每轮迭代中保持不变。

  • 如果 \(f=1\) ，则与原始的梯度提升树算法相同。
  • 较小的 \(f\) 会引入随机性，有助于改善过拟合，因此可以视作一定程度上的正则化。
  • 工程经验表明，\(0.5 \leq f \leq 0.8\) 会带来一个较好的结果。

• 这种方法除了改善过拟合之外，另一个好处是：未被采样的另一部分子集可以用来计算包外估计误差。因此可以避免额外给出一个独立的验证集。

在白纸上写下GBDT的原理并介绍下 (京东)

GBDT分类是如何做的？(京东)

GBDT梯度算的干啥的？(京东)

因为在提升树中，当损失函数是平方损失和指数损失函数时，每—步优化是很简单的。但对一般损失函数而言 ， 往往每一步优化并不那么容易。所以提出了梯度提升 (gradient boosting) 算法．这是利用最速下降法的近似方法 ，其关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。对于平方损失函数，其梯度就是残差。而对于其他损失函数，其梯度可以近似为残差。

和其余的boosting方法有什么区别 (京东)

XGBoost 为何采用泰勒二次展开？不是一次或三次？/ XGBOOST相比GBDT多用了二阶导信息，计算更复杂了啊，为啥还要用？ (京东)

• 精确性：相比一阶偏导，二阶偏导有利于梯度下降的更快更准。
• 可拓展性：而对损失函数采用泰勒二次展开即可获得自变量的二阶导数形式，只要损失函数二阶可导，就可根据样本对叶子结点进行进行分裂优化计算，不用管是分类还是回归，所以实现了可以自定义损失函数。

因为二次展开已经能近似大部分的损失函数了，所以不需要再变成更多层次的展开了。且展开越多项，对损失函数的多阶可导要求也就越高。

XGBoost如何寻找最优特征？是有放回还是无放回的呢？

XGBoost在训练的过程中给出各个特征的评分，从而表明每个特征对模型训练的重要性。

XGBoost利用梯度优化模型算法, 样本是不放回的，想象一个样本连续重复抽出,梯度来回踏步，这显然不利于收敛。

XGBoost支持子采样, 也就是每轮计算可以不使用全部样本。

XGBoost 如何提升计算速度？

• 预排序pre-sorted 。

  xgboost 提出column block 数据结构来降低排序时间。

  • 每一个block 代表一个属性，样本在该block 中按照它在该属性的值排好序。
  • 这些block 只需要在程序开始的时候计算一次，后续排序只需要线性扫描这些block 即可。
  • 由于属性之间是独立的，因此在每个维度寻找划分点可以并行计算。

  block 可以仅存放样本的索引，而不是样本本身，这样节省了大量的存储空间。

  如：block_1 代表所有样本在feature_1 上的从小到大排序：sample_no1,sample_no2,.... 。

  其中样本编号出现的位置代表了该样本的排序。

• cache-aware 预取。

  1. 由于在column block 中，样本的顺序会被打乱，这会使得从导数数组中获取 时的缓存命中率较低。

     因此xgboost 提出了cache-aware 预取算法，用于提升缓存命中率。

  2. xgboost 会以minibatch 的方式累加数据，然后在后台开启一个线程来加载需要用到的导数 。

     这里有个折中：minibatch 太大，则会引起cache miss ；太小，则并行程度较低。

• Out-of-Core 大数据集。

  xgboost 利用硬盘来处理超过内存容量的大数据集。其中使用了下列技术：

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

XGBoost 的一些内部优化

• 在寻找最佳分割点时，传统的方法会枚举每个特征的所有可能切分点。XGBoost 实现了一种近似的算法，大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
• XGBoost 考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper 提到能提高 50 倍。
• 特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然 Boosting 算法迭代必须串行，但是在处理每个特征列时可以做到并行。
• 按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致 cache miss，降低算法效率。Paper 中提到，可先将数据收集到线程内部的 buffer，然后再计算，提高算法的效率。
• XGBoost 还考虑了数据量比较大的情况，当内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

XGBoost 防止过拟合的方法

• 目标函数添加正则项：叶子节点个数+叶子节点权重的L2正则化
• 列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）
• 子采样：每轮计算可以不使用全部样本，使算法更加保守
• shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间

xgboost适合处理哪些场景的问题？(贝壳)

模型类型来说，回归和分类都可以；按任务类型来说结构化数据，nlp，推荐，排序都可以。

XGBoost 和 GBDT 的区别？(微软，说的要有条理，有哪些算法优化，哪些工程实现优化，可以适当扩展提一下lgb)

XGBoost 是 GBDT 的一种工程实现

1. 基分类器：GBDT 采用的 CART 树，而 XGBoost 还支持线性分类器，相当于在正则化项的LR和线性回归。
2. 梯度信息：GBDT 只使用了一阶梯度去近似残差，而 XGBoost 采用了加入了二阶梯度的信息，使得残差近似得更快更准。
3. 正则化：GBDT 中没有正则化相关的设置，而 XGBoost 在目标函数中设置了叶子结点数和叶子结点的权重的L2范数来防止过拟合(预剪枝)。
4. 损失函数：XGBoost 支持自定义损失函数，要求损失函数二阶可导。
5. 列采样：GBDT 每次划分使用所有的特征，而 XGBoost 划分时会对列进行采样，防止过拟合。
6. 缺失值处理：传统 GBDT 中没有做缺失值的处理，而 XGBoost 在选择计算划分时的得分时，不会将缺失值计算进去，而在向下划分时，有一个默认分裂方向会将缺失值分过去。
7. 并行化：GBDT 没有并行化，而 XGBoost 先将每个特征排序并将其存储为块(block)结构，分裂节点时会在各个块中并行查找最优分裂点，极大提升了训练速度。

Xgboost 和 LightGBM 区别

机器学习-XGBoost和LightGBM

它们都是 GBDT 的一种实现。LightGBM 在 XGBoost 的基础上进行了内存和速度上的优化，在速度和精度上做了一定的权衡。

内存更小：

• XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从 O(2*#data) 降低为 O(#bin) ，极大的减少了内存消耗；
• LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
• LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。

速度更快：

• LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
• LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
• LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
• LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
• LightGBM 对缓存也进行了优化，增加了 Cache hit 的命中率。

Boosting 算法中的学习率的作用和优缺点？

学习率是正则化的一部分，它可以降低模型更新的速度（需要更多的迭代）。

• 经验表明：一个小的学习率 (小于0.1) 可以显著提高模型的泛化能力（相比较于学习率为1的时候) 。
• 如果学习率较大会导致预测性能出现较大波动。

随机森林的优点

• 训练效率较高。因为随机森林使用的决策树只需要考虑所有属性的一个子集，且树的生成可并行化。
• 随机森林简单、容易实现、计算开销小。
• 随机森林在很多现实任务中展现出强大的性能，被称作 “代表集成学习技术水平的方法”。

随机森林的适用场景

数据维度相对低（几十维），同时对准确性有较高要求时。(因为不需要很多参数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。)

各种机器学习算法的应用场景分别是什么（比如朴素贝叶斯、决策树、K 近邻、SVM、逻辑回归最大熵模型）？ - xyzh的回答 - 知乎 https://www.zhihu.com/question/26726794/answer/151282052

集成学习的优点

• 由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能。

  此时如果使用单学习器可能因为造成误选而导致泛化性能不佳，通过学习器组合之后会减小这一风险。

• 学习算法往往会陷入局部极小。有的局部极小点所对应的泛化性能可能很差，而通过学习器组合之后可降低陷入糟糕局部极小的风险。

• 某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时使用单学习器肯定无效。

  通过学习器组合之后，由于相应的假设空间有所扩大，有可能学得更好的近似。

加权平均和简单平均那个更好？

现实任务中训练样本通常不充分或者存在噪声，这就使得加权平均学得的权重不完全可靠。尤其是对于规模比较大的集成学习，要学习的权重比较多，很容易出现过拟合。通常如果个体学习器性能相差较大时，适合使用加权平均法；个体学习器性能相差较近时，适合使用简单平均法。

集成学习方法中，如何进行多样性增强？

一般的思路是在学习过程中引入随机性。常见的做法是：对数据样本、输入属性、输出表示、算法参数进行扰动。

1. 数据样本扰动：给定初始数据集，可以从中产生出不同的数据子集。再利用不同的数据子集训练出不同的个体学习器。

   • 数据样本扰动通常是基于采样法，此类做法简单高效、使用最广。

   • 对于常见的基学习器，如决策树、神经网络等，训练样本稍加变化就会导致学习器有显著的变动，数据样本扰动法对这样的“不稳定基学习器”很有效。

   • 对于一些基学习器对数据样本的扰动不敏感，如线性学习器、支持向量机、朴素贝叶斯、 近邻学习器等，这样的基学习器称作稳定基学习器。

     对于此类的基学习器进行集成往往需要使用输入属性扰动等其他机制。

2. 输入属性扰动：训练样本通常由一组属性描述，不同的“子空间”提供了观察数据的不同视角。显然从不同子空间训练出来的个体学习器必然有所不同。

   • 对于包含了大量冗余属性的数据，在子空间中训练个体学习器不仅能够产生多样性大的个体，还会因为属性数量的减少而大幅节省时间开销。

     同时由于冗余属性多，减少一些属性之后训练的个体学习器也不至于太差。

   • 对于只包含少量属性的数据，或者冗余属性较少，则不宜采用输入属性扰动法。

3. 输出表示扰动：此类做法的思路是对输出表示进行操纵以增强多样性。

   如：可以对训练样本的类标记稍作变动，如翻转法Flipping Output随机改变一些训练样本的标记。

4. 算法参数扰动：基学习算法一般都有超参数需要设置。可以通过随机设置不同的超参数，从而产生差别较大的个体学习器。

   使用单一学习器时通常需要使用交叉验证等方法来确定最佳的超参数值。这种做法实际上是用了不同的超参数训练出来了多个学习器，只不过最终挑选出来效果最好的那个学习器来使用。

   集成学习则是相当于把所有这些学习器都利用起来。

5. 不同的多样性增强机制可以同时使用。如随机森林同时是用了数据样本扰动和输入属性扰动。

RF vs GBT

1. 从模型框架的角度来看：

   • 梯度提升树GBT 为boosting 模型，多个学习器串行生成。
   • 随机森林RF 为bagging 模型，多个学习器并行生成。

2. 从偏差分解的角度来看：

   • 梯度提升树GBT 采用弱分类器（高偏差，低方差）。梯度提升树综合了这些弱分类器，在每一步的过程中降低了偏差，但是保持低方差。可能会过拟合。
   • 随机森林 RF 采用完全成长的子决策树（低偏差，高方差）。随机森林要求这些子树之间尽可能无关，从而综合之后能降低方差，但是保持低偏差。树的数目多时，不会过拟合。

3. 从采样方式看：

   • 提升树 GBT 采用了所有数据和所有特征对学习器进行训练 (XGBoost 没有)。
   • 随机森林在样本上采用的bootstrap采样，同时在特征上也会进行采样，会得到多个数据集，每个数据集会训练得到一个学习器。

4. 如果在梯度提升树和随机森林之间二选一，几乎总是建议选择梯度提升树。

   • 随机森林的优点：天然的支持并行计算，因为每个子树都是独立的计算。

   • 梯度提升树的优点：

     • 梯度提升树采用更少的子树来获得更好的精度。

       因为在每轮迭代中，梯度提升树会完全接受现有树（投票权为1）。而随机森林中每棵树都是同等重要的（无论它们表现的好坏），它们的投票权都是 \(\frac{1}{N}\)，因此不是完全接受的。

     • 梯度提升树也可以修改从而实现并行化。

     • 梯度提升树有一个明确的数学模型。因此任何能写出梯度的任务，都可以应用梯度提升树（比如 ranking 任务）。而随机森林并没有一个明确的数学模型。