1 GBDT

1.1 GBDT

GBDT是一种基于boosting集成思想的加法模型，训练时采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差。

GBDT (Gradient Boosting Decison Tree)中的树都是回归树，GBDT用来做回归预测，调整后也可以用于分类（设定阈值，大于阈值为正例，反之为负例)，可以发现多种有区分性的特征以及特征组合。GBDT是把所有树的结论累加起来做最终结论的，GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差(负梯度)，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄;如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。Boosting的最大好处在于，每一步的残差计算其实变相地增大了分错instance的权重，而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。

GBDT使用的是加法模型和前向分布算法，而AdaBoost算法是前向分布加法算法的特例，前向分布算法是加法模型，当基函数为基本分类器时，该加法模型等价于Adaboost的最终分类器。
GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是, 损失函数是, 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器，让本轮的损失函数最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。GBDT本轮迭代只需拟合当前模型的残差。

下面关于GBDT的理解来自论文greedy function approximation: a gradient boosting machine

损失函数的数值优化可以看成是在函数空间，而不是在参数空间。
损失函数L(y,F)包含平方损失 $(y−F)^2$ ，绝对值损失|y−F|用于回归问题，负二项对数似然 $log(1+e−2yF)$ ,y∈{-1,1}用于分类。
关注点是预测函数的加性扩展。

最关键的点在于损失函数的数值优化可以看成是在函数空间而不是参数空间。
GBDT对分类问题基学习器是二叉分类树，对回归问题基学习器是二叉决策树。

1.2 XGBoost

Xgboost是gbdt的改进或者说是梯度提升树的一种，Xgb可以说是工程上的最佳实践模型，XGBoost的基本思想和GBDT相同，但是做了一些优化，如默认的缺失值处理，加入了二阶导数信息、正则项、列抽样，并且可以并行计算等。
简单的说xgb=gbdt+二阶梯度信息+随机特征和样本选择+特征百分位值加速+空值特征自动划分。还有必要的正则项和最优特征选择时的并行计算等。

1.3 LightGBM

LightGBM是一个梯度 boosting 框架，使用基于学习算法的决策树。它可以说是分布式的，高效的。
从 LightGBM 名字我们可以看出其是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。
LightGBM 是为解决GBDT训练速度慢，内存占用大的缺点，此外还提出了：

基于Histogram的决策树算法
单边梯度采样 Gradient-based One-Side Sampling(GOSS)
互斥特征捆绑 Exclusive Feature Bundling(EFB)
带深度限制的Leaf-wise的叶子生长策略
直接支持类别特征(Categorical Feature)
支持高效并行
Cache命中率优化

1.4 CatBoost

CatBoost是一种以对称决策树为基学习器的GBDT框架，主要为例合理地处理类别型特征，CatBoost是由Categorical和Boosting组成。CatBoost还解决了梯度偏差以及预测偏移的问题，从而减少过拟合的发生，进而提高算法的准确性和泛化能力。

2 面试题

介绍一下XGBoost的原理
XGBoost是基于GBDT的一种算法或者说工程实现。
GBDT是一种基于boosting集成思想的加法模型，训练时采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差。
XGBoost的基本思想和GBDT相同，但是做了一些优化，如默认的缺失值处理，加入了二阶导数信息、正则项、列抽样，并且可以并行计算等。
XGBoost和GBDT的不同点：

GBDT是机器学习算法，XGBoost是该算法的工程实现。
基分类器：传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器；
导数信息：GBDT在模型训练时只是用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。（好处：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数。需要注意的是，损失函数需要二阶可导。）
正则项：在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
列采样：传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行列采样，用于防止过拟合。
缺失值处理:传统的GBDT没有涉及对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。对树中的每个非叶子结点， $XGBoost$ 可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支。
特征维度上的并行化。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。
可扩展性：损失函数支持自定义，只需要新的损失函数二阶可导。

GBDT中的梯度是什么对什么的梯度？
当前损失函数L(yi, F(x))对树F(xi)的梯度。
给一个有m个样本，n维特征的数据集，如果用LR算法，那么梯度是几维?
对权重w有n维，对bias有1维，因此是n+1维。
mn的数据集，如果用GBDT，那么梯度是几维？m维？n维？mn维？或者是与树的深度有关？或者与树的叶子节点的个数有关？
梯度是m维，因为GBDT求导是关于所有生成树的和，而所有生成树的和是一维的数值，又总共有m个sample，所以梯度是m维的。
XGBoost的并行是怎么做的？

不是说每棵树可以并行训练， $XGBoost$ 本质上仍然采用 $Boosting$ 思想，每棵树训练前需要等前面的树训练完成才能开始训练。
而是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

XGBoost算法防止过拟合的方法有哪些？

在目标函数中添加了正则化。叶子节点个数+叶子节点权重的L2正则化。
设置目标函数的增益阈值：如果分裂后目标函数的增益小于该阈值，则不分裂。
设置最小样本权重和的阈值：当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂。
设置树的最大深度： $XGBoost$ 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。
列抽样。训练时只使用一部分的特征。
子采样。每轮计算可以不使用全部样本，类似bagging。
early stopping。如果经过固定的迭代次数后，并没有在验证集上改善性能，停止训练过程。
shrinkage。调小学习率增加树的数量，为了给后面的训练留出更多的空间。

使用XGBoost训练模型时，如果过拟合了怎么调参？

控制模型的复杂度。包括max_depth,min_child_weight,gamma 等参数。
增加随机性，从而使得模型在训练时对于噪音不敏感。包括subsample,colsample_bytree。
减小learning rate，但需要同时增加estimator 参数。

XGBoost的正则项是什么？
叶子节点个数和叶子节点权重的L2正则。

img

XGBoost为什么对缺失值不敏感？
一些涉及到对样本距离的度量的模型，如SVM和KNN，如果缺失值处理不当，最终会导致模型预测效果很差。
而树模型对缺失值的敏感度低，大部分时候可以在数据缺失时时使用。原因就是，一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。
另外，XGBoost还有一些处理缺失值的方法。
XGBoost怎么处理缺失值？

这是XGBoost的一个优点。具体处理方法为：

在某列特征上寻找分裂节点时，不会对缺失的样本进行遍历，只会对非缺失样本上的特征值进行遍历，这样减少了为稀疏离散特征寻找分裂节点的时间开销。
另外，为了保证完备性，对于含有缺失值的样本，会分别把它分配到左叶子节点和右叶子节点，然后再选择分裂后增益最大的那个方向，作为预测时特征值缺失样本的默认分支方向。
如果训练集中没有缺失值，但是测试集中有，那么默认将缺失值划分到右叶子节点方向。

XGBoost中的一棵树的停止生长条件

当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。
当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程。
当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细。

XGBoost可以做特征选择，它是如何评价特征重要性的？
XGBoost中有三个参数可以用于评估特征重要性：

weight ：该特征在所有树中被用作分割样本的总次数。
gain ：该特征在其出现过的所有树中产生的平均增益。
cover ：该特征在其出现过的所有树中的平均覆盖范围。覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。

随机森林和GBDT的异同点

相同点：

都是由多棵树组成，最终的结果都是由多棵树一起决定。
不同点：
集成学习：RF属于bagging思想，而GBDT是boosting思想。
偏差-方差权衡：RF不断的降低模型的方差，而GBDT不断的降低模型的偏差。
训练样本：RF每次迭代的样本是从全部训练集中有放回抽样形成的，而GBDT每次使用全部样本。
并行性：RF的树可以并行生成，而GBDT只能顺序生成(需要等上一棵树完全生成)。
最终结果：RF最终是多棵树进行多数表决（回归问题是取平均），而GBDT是加权融合。
数据敏感性：RF对异常值不敏感，而GBDT对异常值比较敏感。
泛化能力：RF不易过拟合，而GBDT容易过拟合。

逻辑回归(LR)和GBDT的区别

LR是线性模型，可解释性强，很容易并行化，但学习能力有限，需要大量的人工特征工程
GBDT是非线性模型，具有天然的特征组合优势，特征表达能力强，但是树与树之间无法并行训练，而且树模型很容易过拟合；
对于高维稀疏数据，GBDT效果不如LR。
先看一个例子：

假设一个二分类问题，label为0和1，特征有100维，如果有1w个样本，但其中只要10个正样本1，而这些样本的特征 f1的值为全为1，而其余9990条样本的f1特征都为0(在高维稀疏的情况下这种情况很常见)。我们都知道在这种情况下，树模型很容易优化出一个使用f1特征作为重要分裂节点的树，因为这个结点直接能够将训练数据划分的很好，但是当测试的时候，却会发现效果很差，因为这个特征f1只是刚好偶然间跟y拟合到了这个规律，这也是我们常说的过拟合。

因为现在的模型普遍都会带着正则项，而 $LR$ 等线性模型的正则项是对权重的惩罚，也就是 $w_1$ 一旦过大，惩罚就会很大，进一步压缩 $w_1$ 的值，使他不至于过大。但是，树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种case，树只需要一个节点就可以完美分割9990和10个样本，一个结点，最终产生的惩罚项极其之小。

这也就是为什么在高维稀疏特征的时候，线性模型会比非线性模型好的原因了：带正则化的线性模型比较不容易对稀疏特征过拟合。

XGBoost中如何对树进行剪枝

在目标函数中增加了正则项：使用叶子结点的数目和叶子结点权重的L2模的平方，控制树的复杂度。
在结点分裂时，定义了一个阈值，如果分裂后目标函数的增益小于该阈值，则不分裂。
当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂。
XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。

XGBoost如何选择最佳分裂点？
XGBoost在训练前预先将特征按照特征值进行了排序，并存储为block结构，以后在结点分裂时可以重复使用该结构。
因此，可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点，根据每次分裂后产生的增益，最终选择增益最大的那个特征的特征值作为最佳分裂点。如果在计算每个特征的最佳分割点时，对每个样本都进行遍历，计算复杂度会很大，这种全局扫描的方法并不适用大数据的场景。XGBoost还提供了一种直方图近似算法，对特征排序后仅选择常数个候选分裂位置作为候选分裂点，极大提升了结点分裂时的计算效率。
XGBoost的延展性很好，怎么理解？
可以有三个方面的延展性：

基分类器：弱分类器可以支持CART决策树，也可以支持LR和Linear。
目标函数：支持自定义loss function，只需要其二阶可导。因为需要用二阶泰勒展开，得到通用的目标函数形式。
学习方法：Block结构支持并行化，支持 Out-of-core计算。

XGBoost如何处理不平衡数据

设置scale_pos_weight来平衡正样本和负样本的权重。例如，当正负样本比例为1:10时，scale_pos_weight可以取10；
你不能重新平衡数据集(会破坏数据的真实分布)的情况下，应该设置max_delta_step为一个有限数字来帮助收敛（基模型为 $LR$ 时有效）。

XGBoost的优缺点

优点
- 精度更高： $GBDT$ 只用到一阶泰勒展开，而 $XGBoost$ 对损失函数进行了二阶泰勒展开。 $XGBoost$ 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；
- 灵活性更强： $GBDT$ 以 $CART$ 作为基分类器， $XGBoost$ 不仅支持 $CART$ 还支持线性分类器，使用线性分类器的 $XGBoost$ 相当于带和正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。此外， $XGBoost$ 工具支持自定义损失函数，只需函数支持一阶和二阶求导；
- 正则化： $XGBoost$ 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合，这也是 $XGBoost$ 优于传统 $GBDT$ 的一个特性。
- Shrinkage（缩减）： 相当于学习速率。 $XGBoost$ 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。传统 $GBDT$ 的实现也有学习速率；
- 列抽样： $XGBoost$ 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。这也是 $XGBoost$ 异于传统 $GBDT$ 的一个特性；
- 缺失值处理： 对于特征的值有缺失的样本， $XGBoost$ 采用的稀疏感知算法可以自动学习出它的分裂方向；
- $XGBoost$ 工具支持并行： $Boosting$ 不是一种串行的结构吗?怎么并行的？注意 $XGBoost$ 的并行不是树粒度的并行， $XGBoost$ 也是一次迭代完才能进行下一次迭代的（第次迭代的代价函数里包含了前面次迭代的预测值）。 $XGBoost$ 的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点）， $XGBoost$ 在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
- 可并行的近似算法： 树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以 $XGBoost$ 还提出了一种可并行的近似算法，用于高效地生成候选的分割点。
缺点
- 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
- 预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

XGBoost和LightGBM的区别

树生长策略
- XGB采用level-wise的分裂策略：XGB对每一层所有节点做无差别分裂，但是可能有些节点增益非常小，对结果影响不大，带来不必要的开销。
- LGB采用leaf-wise的分裂策略：Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的，但是很容易出现过拟合问题，所以需要对最大深度做限制。
分割点查找算法
- XGB使用特征预排序算法，LGB使用基于直方图的切分点算法，其优势如下：
  - 减少内存占用，比如离散为256个bin时，只需要用8位整形就可以保存一个样本被映射为哪个bin(这个bin可以说就是转换后的特征)，对比预排序的exact greedy算法来说（用int_32来存储索引+ 用float_32保存特征值），可以节省7/8的空间。
  - 计算效率提高，预排序的Exact greedy对每个特征都需要遍历一遍数据，并计算增益。而直方图算法在建立完直方图后，只需要对每个特征遍历直方图即可。
- LGB还可以使用直方图做差加速，一个节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算
直方图算法
- XGB 在每一层都动态构建直方图，因为XGB的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导)，所以每一层都要重新构建直方图。
- LGB中对每个特征都有一个直方图，所以构建一次直方图就够了
支持离散变量
- XGB无法直接输入类别型变量因此需要事先对类别型变量进行编码（例如独热编码），
- LGB可以直接处理类别型变量。
缓存命中率
- XGB用block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的，这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率。
- LGB是基于直方图分裂特征的，梯度信息都存储在一个个bin中，所以访问梯度是连续的，缓存命中率高。
并行策略-特征并行
- XGB每个worker节点中仅有部分的列数据，也就是垂直切分，每个worker寻找局部最佳切分点，worker之间相互通信，然后在具有最佳切分点的worker上进行节点分裂，再由这个节点广播一下被切分到左右节点的样本索引号，其他worker才能开始分裂。
- LGB特征并行的前提是每个worker留有一份完整的数据集，但是每个worker仅在特征子集上进行最佳切分点的寻找；worker之间需要相互通信，通过比对损失来确定最佳切分点；然后将这个最佳切分点的位置进行全局广播，每个worker进行切分即可。
并行策略-数据并行
- LGB中先对数据水平切分，每个worker上的数据先建立起局部的直方图，然后合并成全局的直方图，采用直方图相减的方式，先计算样本量少的节点的样本索引，然后直接相减得到另一子节点的样本索引，这个直方图算法使得worker间的通信成本降低一倍，因为只用通信以此样本量少的节点
- XGB中的数据并行也是水平切分，然后单个worker建立局部直方图，再合并为全局，不同在于根据全局直方图进行各个worker上的节点分裂时会单独计算子节点的样本索引

GBDT的拟合值残差为什么用负梯度代替，而不是直接拟合残差

image.png

使用残差拟合只是考虑到损失函数为平方损失的特殊情况，负梯度是更加广义上的拟合项，更具普适性。
负梯度永远是函数下降最快的方向，自然也是GBDT目标函数下降最快的方向。注意并不是拟合梯度，只是用梯度去拟合。GBDT本来中的G代表Grandient，本来就是用梯度拟合；
用残差去拟合，只是目标函数是均方误差的一种特殊情况，这个特殊情况跟CART拟合残差一模一样，使得看起来就拟合残差合情合理。
代价函数除了loss还有正则项，正则中有参数和变量，很多情况下只拟合残差，loss变小但是正则变大，代价函数不一定就小，这时候就要用梯度啦，梯度的本质也是一种方向导数，综合了各个方向（参数）的变化，选择了一个总是最优（下降最快）的方向；
最后目标函数可表达为由梯度构成，所以说成是拟合梯度，也好像不是不行

XGBoost使用二阶泰勒展开的目的和优势

XGBoost是以MSE为基础推导出来的，在MSE的情况下，XGBoost的目标函数展开就是一阶项+二阶项的形式，而其他类似Logloss这样的目标函数不能表示成这样形式，为了后续推导的统一，所以将目标函数进行二阶泰勒展开，就可以直接定义损失函数了，只要二阶可导即可，增强了模型的扩展性
二阶信息能够让梯度收敛的更快，拟牛顿法比SGD收敛更快，一阶信息描述梯度变化方向，二阶信息可以描述梯度变化方向是如何变化的。

简单介绍一下LightGBM？
LightGBM是一个梯度 boosting 框架，使用基于学习算法的决策树。它可以说是分布式的，高效的。
从 LightGBM 名字我们可以看出其是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。
LightGBM 是为解决GBDT训练速度慢，内存占用大的缺点，此外还提出了：

基于Histogram的决策树算法
单边梯度采样 Gradient-based One-Side Sampling(GOSS)
互斥特征捆绑 Exclusive Feature Bundling(EFB)
带深度限制的Leaf-wise的叶子生长策略
直接支持类别特征(Categorical Feature)
支持高效并行
Cache命中率优化

介绍一下直方图算法？
直方图算法就是使用直方图统计，将大规模的数据放在了直方图中，分别是每个bin中样本的梯度之和 还有就是每个bin中样本数量

首先确定对于每一个特征需要多少个箱子并为每一个箱子分配一个整数；
将浮点数的范围均分成若干区间，区间个数与箱子个数相等
将属于该箱子的样本数据更新为箱子的值
最后用直方图表示

优点：
内存占用更小：相比xgb不需要额外存储预排序，且只保存特征离散化后的值(整型)
计算代价更小: 相比xgb不需要遍历一个特征值就需要计算一次分裂的增益，只需要计算k次(k为箱子的个数)
直方图做差加速：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到，在速度上可以提升一倍

介绍一下Leaf-wise和 Level-wise？

XGBoost 采用 Level-wise，策略遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，实际上很多叶子的分裂增益较低，没必要进行搜索和分裂
LightGBM采用Leaf-wise的增长策略，该策略每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，Leaf-wise的优点是：在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度；Leaf-wise的缺点是：可能会长出比较深的决策树，产生过拟合。因此LightGBM会在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合

介绍一下单边梯度采样算法(GOSS)？
GOSS算法从减少样本的角度出发，排除大部分小梯度的样本，仅用剩下的样本计算信息增益，它是一种在减少数据量和保证精度上平衡的算法。与此同时，为了不改变数据的总体分布，GOSS对要进行分裂的特征按照绝对值大小进行排序，选取最大的a个数据，在剩下梯度小的数据中选取b个，这b个数据乘以权重 $\frac{1-a}{b}$ ,最后使用这a+b个数据计算信息增益。
介绍互斥特征捆绑算法(EFB)？
互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。
LightGBM的EFB算法将这个问题转化为图着色的问题来求解，将所有的特征视为图的各个顶点，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。另外，算法可以允许一小部分的冲突，我们可以得到更少的绑定特征，进一步提高计算效率。
特征之间如何捆绑？
比如，我们在bundle中绑定了两个特征A和B，A特征的原始取值为区间 $[0,10)$ ，B特征的原始取值为区间 $[0,20)$ ，我们可以在B特征的取值上加一个偏置常量10，将其取值范围变为 $[10,30)$ ，绑定后的特征取值范围为 $[0,30)$
LightGBM是怎么支持类别特征？

离散特征建立直方图的过程
统计该特征下每一种离散值出现的次数，并从高到低排序，并过滤掉出现次数较少的特征值, 然后为每一个特征值，建立一个bin容器。
计算分裂阈值的过程
- 先看该特征下划分出的bin容器的个数，如果bin容器的数量小于4，直接使用one vs other方式, 逐个扫描每一个bin容器，找出最佳分裂点;
- 对于bin容器较多的情况, 先进行过滤，只让子集合较大的bin容器参加划分阈值计算, 对每一个符合条件的bin容器进行公式计算
  $\frac{该bin容器下所有样本的一阶梯度之和 }{ 该bin容器下所有样本的二阶梯度之和} + 正则项$
这里为什么不是label的均值呢？其实"label的均值"只是为了便于理解，只针对了学习一棵树且是回归问题的情况，这时候一阶导数是Y, 二阶导数是1)，得到一个值，根据该值对bin容器从小到大进行排序，然后分从左到右、从右到左进行搜索，得到最优分裂阈值。但是有一点，没有搜索所有的bin容器，而是设定了一个搜索bin容器数量的上限值，程序中设定是32，即参数max_num_cat。
LightGBM中对离散特征实行的是many vs many 策略，这32个bin中最优划分的阈值的左边或者右边所有的bin容器就是一个many集合，而其他的bin容器就是另一个many集合。
对于连续特征，划分阈值只有一个，对于离散值可能会有多个划分阈值，每一个划分阈值对应着一个bin容器编号，当使用离散特征进行分裂时，只要数据样本对应的bin容器编号在这些阈值对应的bin集合之中，这条数据就加入分裂后的左子树，否则加入分裂后的右子树。

LightGBM的优缺点
优点：

直方图算法极大的降低了时间复杂度；
单边梯度算法过滤掉梯度小的样本，减少了计算量；
基于 Leaf-wise 算法的增长策略构建树，减少了计算量；
直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗
互斥特征捆绑算法减少了特征数量，降低了内存消耗
缺点：
LightGBM在Leaf-wise可能会长出比较深的决策树，产生过拟合
LightGBM是基于偏差的算法，所以会对噪点较为敏感；

GBDT是如何做回归和分类的

回归
生成每一棵树的时候，第一棵树的一个叶子节点内所有样本的label的均值就是这个棵树的预测值，后面根据残差再预测，最后根据将第一棵树的预测值+权重*(其它树的预测结果)

分类
分类时针对样本有三类的情况，
- 首先同时训练三颗树。
  - 第一棵树针对样本 x 的第一类，输入为（x, 0）。
  - 第二棵树输入针对样本 x 的第二类，假设 x 属于第二类，输入为（x, 1）。
  - 第三棵树针对样本 x 的第三类，输入为（x, 0）。
  - 参照 CART 的生成过程。输出三棵树对 x 类别的预测值 f1(x), f2(x), f3(x)。
- 在后面的训练中，我们仿照多分类的逻辑回归，使用 softmax 来产生概率。
  - 针对类别 1 求出残差 f11(x) = 0 − f1(x)；
  - 类别 2 求出残差 f22(x) = 1 − f2(x)；
  - 类别 3 求出残差 f33(x) = 0 − f3(x)。
- 然后第二轮训练，
  - 第一类输入为(x, f11(x))
  - 第二类输入为(x, f22(x))
  - 第三类输入为(x, f33(x))。
- 继续训练出三棵树，一直迭代 M 轮，每轮构建 3 棵树。当训练完毕以后，新来一个样本 x1，我们需要预测该样本的类别的时候，便可使用 softmax 计算每个类别的概率。

简单介绍Catboost？

相比于XGBoost、LightGBM，CatBoost的创新点有哪些？

自动将类别型特征处理为数值型特征。
Catboost对类别特征进行组合，极大的丰富了特征维度。
采用排序提升的方法对抗训练集中的噪声点，从而避免梯度估计的偏差，进而解决预测偏移的问题。
采用了完全对称树作为基模型。

Catboost是如何处理类别特征的？

基数比较低的类别型特征
利用One-hot编码方法将特征转为数值型
基数比较高的类别型特征
- 首先会计算一些数据的statistics。计算某个category出现的频率，加上超参数，生成新的numerical features。这一策略要求同一标签数据不能排列在一起（即先全是之后全是这种方式），训练之前需要打乱数据集。
- 第二，使用数据的不同排列（实际上是个）。在每一轮建立树之前，先扔一轮骰子，决定使用哪个排列来生成树。
- 第三，考虑使用categorical features的不同组合。例如颜色和种类组合起来，可以构成类似于blue dog这样的特征。当需要组合的categorical features变多时，CatBoost只考虑一部分combinations。在选择第一个节点时，只考虑选择一个特征，例如A。在生成第二个节点时，考虑A和任意一个categorical feature的组合，选择其中最好的。就这样使用贪心算法生成combinations。
- 第四，除非向gender这种维数很小的情况，不建议自己生成One-hot编码向量，最好交给算法来处理。

Catboost如何避免梯度偏差
经典梯度提升算法每个步骤中使用的梯度由当前模型中的相同的数据点(节点)来估计，这导致估计梯度在特征空间的任何域中的分布与该域中梯度的真实分布相比发生了偏移，从而导致过拟合。
对于每一个样本单独训练一个模型，使用模型估计样本的梯度，并用估计的结果对模型进行评分
Catboost如何避免预测偏移？
预测偏移是由梯度偏差造成的。在GDBT的每一步迭代中, 损失函数使用相同的数据集求得当前模型的梯度, 然后训练得到基学习器, 但这会导致梯度估计偏差, 进而导致模型产生过拟合的问题。CatBoost通过采用排序提升 的方式替换传统算法中梯度估计方法，进而减轻梯度估计的偏差。
解释一下排序提升
在传统的GBDT框架当中，构建下一棵树分为两个阶段：选择树结构和在树结构固定后计算叶子节点的值。CatBoost主要在第一阶段进行优化。在建树的阶段，CatBoost有两种提升模式，Ordered和Plain。Plain模式是采用内建的ordered TS对类别型特征进行转化后的标准GBDT算法。Ordered则是对Ordered boosting算法的优化。
Catboost为什么要使用对称树？

对称树是平衡的，不容易过拟合
统一层使用相同的分割准则
每个叶子节点的索引可以被编码为长度等于树深度的二进制向量
首先将所有浮点特征、统计信息和独热编码特征进行二值化，然后使用二进制特征来计算模型预测值

CatBoost的优缺点
优点：

性能卓越： 在性能方面可以匹敌任何先进的机器学习算法；
鲁棒性/强健性： 它减少了对很多超参数调优的需求，并降低了过度拟合的机会，这也使得模型变得更加具有通用性；
实用： 可以处理类别型、数值型特征；
可扩展： 支持自定义损失函数；
缺点：
对于类别型特征的处理需要大量的内存和时间；
不同随机数的设定对于模型预测结果有一定的影响；

gbdt为什么用负梯度代表残差？

上文公式(3)是gbdt的损失函数，对公式(3)进行在 $f_{m-1}(x)处进行$ 泰勒的一阶展开:
$L(y,f_m(x))=L(y,f_{m-1}(x)+\beta_m b(x;\gamma_m))$
$=L(y,f_{m-1}(x))+\frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)}(f_{m}(x)-f_{m-1}(x))$
$=L(y,f_{m-1}(x))+\frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)}(\beta_m b(x;\gamma_m)) \tag{19}$
从我们的目标是损失函数最小化，使公式(19)最小化，由于 $L(y,f_{m-1}(x))$ 是个常数，所以我们的损失函数最小化可以转化为:
$argmin_{(\beta_m,\gamma_m)}=min \frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)}(\beta_m b(x;\gamma_m)) \tag{20}$
将上述式子的两项都看做是向量，为了是相乘之后最小，一定是向量之间的异号,因此得到:
$(\beta_m b(x;\gamma_m)) = - \frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)} \tag{21}$
从公式(20)可以看出第m棵树使用前m-1的负梯度作为残差，所有每次都是拟合的负梯度.

gbdt是训练过程如何选择特征？

gbdt使用基学习器是CART树，CART树是二叉树，每次使用yes or no进行特征选择，数值连续特征使用的最小均方误差，离散值使用的gini指数。在每次划分特征的时候会遍历所有可能的划分点找到最有的特征分裂点，这是用为什么gbdt会比rf慢的主要原因之一。

gbdt应用在多分类问题？

gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值。这个要求每轮迭代的时候，弱分类器的输出的结果相减是有意义的。残差相减是有意义的。

对于多分类任务，GDBT的做法是采用一对多的策略也就是说，对每个类别训练M个分类器。假设有K个类别，那么训练完之后总共有M*K颗树。

两层循环的顺序不能改变。也就是说，K个类别都拟合完第一颗树之后才开始拟合第二颗树，不允许先把某一个类别的M颗树学习完，再学习另外一个类别。

xgb为什么使用二阶梯度信息，为什么不使用三阶或者更高梯度信息？

xgb之所以使用二阶梯度信息，是因为从泰勒展开式来看，gbdt使用的一阶梯度的泰勒展开式，丢失了很多的信息，使用二阶可以使损失函数更加准确。从泰勒展开的角度来看展开的次数越多越能更精准的表示损失函数的值，但是如果我们使用二阶梯度就要要求损失函数二阶可导，如果使用n阶展开就要求损失函数n阶可导，但是有很多损失函数不是n阶可导的，比如均方误差，因此使用二阶梯度信息是一个泰勒展开和损失函数选择的折中。

lgb相对xgb做了哪些改进？

直方图算法，LightGBM提供一种数据类型的封装相对Numpy,Pandas,Array等数据对象而言节省了内存的使用，原因在于他只需要保存离散的直方图，LightGBM里默认的训练决策树时使用直方图算法，XGBoost里现在也提供了这一选项，不过默认的方法是对特征预排序，直方图算法是一种牺牲了一定的切分准确性而换取训练速度以及节省内存空间消耗的算法.

在训练决策树计算切分点的增益时，预排序需要对每个样本的切分位置计算，所以时间复杂度是O(#data)而LightGBM则是计算将样本离散化为直方图后的直方图切割位置的增益即可，时间复杂度为O(#bins),时间效率上大大提高了(初始构造直方图是需要一次O(#data)的时间复杂度，不过这里只涉及到加和操作).

直方图做差进一步提高效率，计算某一节点的叶节点的直方图可以通过将该节点的直方图与另一子节点的直方图做差得到，所以每次分裂只需计算分裂后样本数较少的子节点的直方图然后通过做差的方式获得另一个子节点的直方图，进一步提高效率

节省内存,将连续数据离散化为直方图的形式，对于数据量较小的情形可以使用小型的数据类型来保存训练数据
不必像预排序一样保留额外的对特征值进行预排序的信息
减少了并行训练的通信代价.

稀疏特征优化、直接支持类别特征、网络通信优化

比较一下catboost、lgb和xgb？
XGBoost、LightGBM和CatBoost都是目前经典的SOTA（state of the art）Boosting算法，都可以归类到梯度提升决策树算法系列。三个模型都是以决策树为支撑的集成学习框架，其中XGBoost是对原始版本的GBDT算法的改进，而LightGBM和CatBoost则是在XGBoost基础上做了进一步的优化，在精度和速度上都有各自的优点。

三个模型树的构造方式有所不同，XGBoost使用按层生长（level-wise）的决策树构建策略，LightGBM则是使用按叶子生长（leaf-wise）的构建策略，而CatBoost使用了对称树结构，其决策树都是完全二叉树。

对于类别特征的处理。XGBoost本身不具备自动处理类别特征的能力，对于数据中的类别特征，需要我们手动处理变换成数值后才能输入到模型中；LightGBM中则需要指定类别特征名称，算法即可对其自动进行处理；CatBoost以处理类别特征而闻名，通过目标变量统计等特征编码方式也能实现类别特征的高效处理。

机器学习GBDT、XGBoost、LightGBM以及CatBoost