树模型问题汇总

明天更

问：方差和偏差的定义是什么？

偏差是指由有所采样得到的大小为m的训练数据集，训练出的所有模型的输出的平均值和真实模型输出之间的偏差。

方差是指有所有采样得到的大小为m的训练数据集，训练出的所有模型的输出的方差

集成模型，即通过多个高方差模型的平均来降低方差

问：谈谈boosting和bagging是什么？为什么bagging可以减少Variance，boosting可以减少Bias？

boosting：串行的方式训练基分类器，各分类器之间有依赖。每次训练时，对前一层基分类器分错的样本给与更高的权重

bagging：bagging是Bootstrap aggregating的意思，各分类器之间无强依赖，可以并行。

为什么说bagging是减少variance，而boosting是减少bias?

为什么bagging可以减少Variance

Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance（事实上，各模型的分布也近似相同，但不独立）。

由于 E [ ∑ X i n ] = E [ X i ] E\left[\frac{\sum X_{i}}{n}\right]=E\left[X_{i}\right] E[n∑Xi​​]=E[Xi​]，所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有 Var ⁡ ( ∑ X i n ) = Var ⁡ ( X i ) n \operatorname{Var}\left(\frac{\sum X_{i}}{n}\right)=\frac{\operatorname{Var}\left(X_{i}\right)}{n} Var(n∑Xi​​)=nVar(Xi​)​，此时可以显著降低variance。若各子模型完全相同，则 Var ⁡ ( ∑ X i n ) = Var ⁡ ( X i ) \operatorname{Var}\left(\frac{\sum X_{i}}{n}\right)=\operatorname{Var}\left(X_{i}\right) Var(n∑Xi​​)=Var(Xi​)

简单解释一下方差的推导。两随机变量相互独立时，

所以相互独立时， D ( Σ X i / n ) = Σ D ( X i ) / n 2 = n D ( X i ) / n 2 = D ( X i ) / n D(\Sigma X_i/n)=\Sigma D(X_i)/n^2=nD(X_i)/n^2=D(X_i)/n D(ΣXi​/n)=ΣD(Xi​)/n2=nD(Xi​)/n2=D(Xi​)/n

当两个随机变量不相互独立时：

D ( Σ X i / n ) = n D ( X ) + n ( n − 1 ) 2 C o v ( X i , X j ) n 2 ≈ D ( X i ) D(\Sigma X_i/n)=\frac{nD(X)+\frac{n(n-1)}{2}Cov(X_i,X_j)}{n^2} \approx D(X_i) D(ΣXi​/n)=n2nD(X)+2n(n−1)​Cov(Xi​,Xj​)​≈D(Xi​)

bagging方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance。为了进一步降低variance，Random forest通过随机选取变量子集做拟合的方式de-correlated了各子模型（树），使得variance进一步降低。

方差记为 σ 2 \sigma ^2 σ2，两两变量之间的相关性为 ρ \rho ρ，则 Σ X i / n \Sigma X_i/n ΣXi​/n的方差为: ρ ⋅ σ 2 + ( 1 − ρ ) ⋅ σ 2 / n \rho \cdot \sigma ^2 + (1-\rho)\cdot \sigma ^2/n ρ⋅σ2+(1−ρ)⋅σ2/n

bagging降低的是第二项，random forest是同时降低两项。详见ESL p588公式15.1）

为什么boosting可以减少Bias

问：为什么决策树是常用的基分类器？除了决策树还能用哪些

问：bagging中，袋外样本（OOB）出现的概率是多少？

问：说一下AdaBoost的基本思想

问：为什么GBDT处理二分类时，如果损失函数选择指数函数，会退化为AdaBoost？

结论：提升树的损失函数选指数损失函数时，退化为adaboost

证明见《统计学习方法-第一版》 p145-146scikit-learn 梯度提升树(GBDT)调参小结

对于分类模型，有 对数似然损失函数"deviance" 和 指数损失函数"exponential" 两者输入选择。默认是对数似然损失函数"deviance"。在原理篇中对这些分类损失函数有详细的介绍。一般来说，推荐使用默认的"deviance"。它对二元分离分类 和多元分类各自都有比较好的优化。而指数损失函数等于把我们带到了Adaboost算法。

梯度提升树(GBDT)原理小结

问：为什么AdaBoost 是自适应（adaptive）的？

每个新的模型都会基于前一个模型的表现结果调整样本权重。

问：AdaBoost和GBDT的区别是什么？

最主要的区别在于两者如何识别模型的问题。

问：为什么GBDT要拟合负梯度？

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

我们能通过一阶泰勒展开证明负梯度方向是下降最快的方向。对于函数 f f f： θ k + 1 = θ k − η ∂ f ( θ k ) ∂ θ k \theta_{k+1}=\theta_{k}-\eta \frac{\partial f\left(\theta_{k}\right)}{\partial \theta_{k}} θk+1​=θk​−η∂θk​∂f(θk​)​

在GBDT中，由下列公式再加上 F m ( x ) = F m − 1 ( x ) + T m ( x ) F_{m}(x)=F_{m-1}(x)+T_m(x) Fm​(x)=Fm−1​(x)+Tm​(x)的加法模型定义，

F m ( x ) = F m − 1 ( x ) − η ∂ L ( y , F m − 1 ( x ) ) ∂ F m − 1 ( x ) F_{m}(x)=F_{m-1}(x)-\eta \frac{\partial L\left(y, F_{m-1}(x)\right)}{\partial F_{m-1}(x)} Fm​(x)=Fm−1​(x)−η∂Fm−1​(x)∂L(y,Fm−1​(x))​

得到：

T m ( x ) = − η ∂ L ( y , F m − 1 ( x ) ) ∂ F m − 1 ( x ) T_{m}(x)=-\eta \frac{\partial L\left(y, F_{m-1}(x)\right)}{\partial F_{m-1}(x)} Tm​(x)=−η∂Fm−1​(x)∂L(y,Fm−1​(x))​

问：高维稀疏特征的时候，LR, GBDT 哪个好，为什么？

LR适合处理高维稀疏特征，而GBDT不适合。

问：Xgboost在GBDT上做了哪些改变 / Xgboost在优缺点是什么？

问：Xgboost的损失函数是什么？

GBDT用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。

首先，在GBDT损失函数的基础上，Xgboost加入了正则化项，即对叶子数与叶节点权重的惩罚，即系数为gamma的叶子结点个数和系数为二分之lambda的L2正则项。

如果我们要极小化这个损失函数的话，需要求解J个叶子结点区域的最优解w，Xgboost的GBDT的一阶泰勒展开的基础上做二阶泰勒展开，经整理，最终损失函数为：

L t = ∑ j = 1 J [ G t j w t j + 1 2 ( H t j + λ ) w t j 2 ] + γ J L_{t}=\sum_{j=1}^{J}\left[G_{t j} w_{t j}+\frac{1}{2}\left(H_{t j}+\lambda\right) w_{t j}^{2}\right]+\gamma J Lt​=∑j=1J​[Gtj​wtj​+21​(Htj​+λ)wtj2​]+γJ

问：每个叶子结点区域的最优解 w w w是什么？

w t j = − G t j H t j + λ w_{t j}=-\frac{G_{t j}}{H_{t j}+\lambda} wtj​=−Htj​+λGtj​​

问：如何选择哪个特征和特征值进行分裂，使最终我们的损失函数 L t L_t Lt​最小？

在上一问中， w t j w_{t j} wtj​取最优解的时候，原损失函数对应的表达式为：

L t = − 1 2 ∑ j = 1 J G t j 2 H t j + λ + γ J L_{t}=-\frac{1}{2} \sum_{j=1}^{J} \frac{G_{t j}^{2}}{H_{t j}+\lambda}+\gamma J Lt​=−21​∑j=1J​Htj​+λGtj2​​+γJ

如果我们每次做左右子树分裂时，可以最大程度的减少损失函数的损失就最好了。我们期望最大化：

max ⁡ 1 2 G L 2 H L + λ + 1 2 G R 2 H R + λ − 1 2 ( G L + G R ) 2 H L + H R + λ − γ \max \frac{1}{2} \frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{1}{2} \frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{1}{2} \frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}-\gamma max21​HL​+λGL2​​+21​HR​+λGR2​​−21​HL​+HR​+λ(GL​+GR​)2​−γ

具体做法是对样本排序后求出每个样本的一阶导 g g g和二阶导 h h h，然后线性遍历，求出最大的信息增益。

问：在纸上（白板上）写伪代码，实现Xgboost

输入：训练样本集 D D D，迭代次数 T T T，损失函数 L L L，正则化系数 λ , γ \lambda,\gamma λ,γ 输出： 强学习器 f ( x ) f(x) f(x)

问：xgboost支持用线性分类器做基模型，此时xgboost可以拟合线性不可分的数据集吗？

不能，叠加后仍然是线性的

最简单的算法是贪心算法，即对于每个特征通过线性扫描逐个遍历样本，确定该特征的的最佳分裂点。

贪婪算法可以的到最优解，但当数据量太大时则无法读入内存进行计算，近似算法主要针对贪婪算法这一缺点给出了近似最优解。

加权分位数缩略图

XGBoost 不是简单地按照样本个数进行分位，而是以二阶导数值 h i h_i hi​ 作为样本的权重进行划分，如下：

对于样本权值相同的数据集来说，找到候选分位点已经有了解决方案（GK 算法），但是当样本权值不一样时，该如何找到候选分位点呢？（作者给出了一个 Weighted Quantile Sketch 算法，这里将不做介绍。）

问：说说Xgboost的稀疏感知算法

XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。

至于如何学到缺省值的分支，其实很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。

我们知道，决策树的学习最耗时的一个步骤就是在每次寻找最佳分裂点是都需要对特征的值进行排序。而 XGBoost 在训练之前对根据特征对数据进行了排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式（Compressed Sparse Columns Format，CSC）进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。这种块结构存储的特征之间相互独立，方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征作为分裂，这时各个特征的增益计算可以同时进行，这也是 Xgboost 能够实现分布式或者多线程计算的原因。

块结构的设计可以减少节点分裂时的计算量，但特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续，这样会造成缓存命中率低，从而影响到算法的效率。

为了解决缓存命中率低的问题，XGBoost 提出了缓存访问优化算法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就是实现了非连续空间到连续空间的转换，提高了算法效率。

此外适当调整块大小，也可以有助于缓存优化。

当数据量过大时无法将数据全部加载到内存中，只能先将无法加载到内存中的数据暂存到硬盘中，直到需要时再进行加载计算，而这种操作必然涉及到因内存与硬盘速度不同而造成的资源浪费和性能瓶颈。为了解决这个问题，XGBoost 独立一个线程专门用于从硬盘读入数据，以实现处理数据和读入数据同时进行。

xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

相比于Xgboost做了哪些优化？

首先算每个样本的一阶导g和二阶导h，对于某个叶子结点，权重可以直接算出来， w = − G H + λ w=-\frac{G}{H+\lambda} w=−H+λG​。目标函数其实就是 G w + 1 2 ( H + λ ) w 2 + γ T Gw+\frac{1}{2}(H+\lambda)w^2+\gamma T Gw+21​(H+λ)w2+γT（超好理解），把w带入目标函数，化简为

结点分裂的目标转换为使得目标函数最小（和拟合负梯度一个道理，拟合负梯度就表示让梯度变小）

目标函数减小的程度，就是信息增益

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好， 单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS） 利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。

GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。具体算法如下所示：

我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序（无需保存排序后结果），然后拿到前 a % a\% a% 的梯度大的样本，和总体样本的 b % b\% b%，在计算增益时，通过乘上 1 − a b \frac{1-a}{b} b1−a​来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

在构建叶节点的直方图时，我们还可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量。在实际操作过程中，我们还可以先计算直方图小的叶子节点，然后利用直方图作差来获得直方图大的叶子节点。

XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。

【机器学习】决策树（下）——XGBoost、LightGBM（非常详细）

高维特征往往是稀疏的，而且特征间可能是相互排斥的（如两个特征不同时取非零值），如果两个特征并不完全互斥（如只有一部分情况下是不同时取非零值），可以用互斥率表示互斥程度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。

（是不是可以理解为把OHE反过来？）

大部分的机器学习算法都不能直接支持类别特征，一般都会对类别特征进行编码，然后再输入到模型中。常见的处理类别特征的方法为 one-hot 编码，但我们知道对于决策树来说并不推荐使用 one-hot 编码：

LightGBM 原生支持类别特征，采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。假设有某维特征有 k k k 个类别，则有 2 ( k − 1 ) − 1 2^{(k-1)}-1 2(k−1)−1 中可能，时间复杂度为 O ( 2 k ) O(2^k) O(2k) ，LightGBM 基于 Fisher 大佬的 《On Grouping For Maximum Homogeneity》实现了 O ( k log ⁡ k ) O(k\log k) O(klogk) 的时间复杂度。

上图为左边为基于 one-hot 编码进行分裂，后图为 LightGBM 基于 many-vs-many 进行分裂，在给定深度情况下，后者能学出更好的模型。

其基本思想在于每次分组时都会根据训练目标对类别特征进行分类，根据其累积值 ∑  gradient  ∑  hessian  \frac{\sum \text { gradient }}{\sum \text { hessian }} ∑ hessian ∑ gradient ​ 对直方图进行排序，然后在排序的直方图上找到最佳分割。此外，LightGBM 还加了约束条件正则化，防止过拟合。

传统的特征并行算法在于对数据进行垂直划分，然后使用不同机器找到不同特征的最优分裂点，基于通信整合得到最佳划分点，然后基于通信告知其他机器划分结果。

传统的特征并行方法有个很大的缺点：需要告知每台机器最终划分结果，增加了额外的复杂度（因为对数据进行垂直划分，每台机器所含数据不同，划分结果需要通过通信告知）。

LightGBM 则不进行数据垂直划分，每台机器都有训练集完整数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

传统的数据并行策略主要为水平划分数据，然后本地构建直方图并整合成全局直方图，最后在全局直方图中找出最佳划分点。

这种数据划分有一个很大的缺点：通讯开销过大。如果使用点对点通信，一台机器的通讯开销大约为 O ( m a c h i n e × f e a t u r e × b i n ) O(machine\times feature\times bin) O(machine×feature×bin)；如果使用集成的通信，则通讯开销为 O ( 2 × f e a t u r e × b i n ) O(2\times feature\times bin) O(2×feature×bin)，

LightGBM 采用分散规约（Reduce scatter）的方式将直方图整合的任务分摊到不同机器上，从而降低通信代价，并通过直方图做差进一步降低不同机器间的通信。

针对数据量特别大特征也特别多的情况下，可以采用投票并行。投票并行主要针对 数据并行 时 数据合并的通信代价比较大的瓶颈进行优化，其通过投票的方式只合并部分特征的直方图从而达到降低通信量的目的。

大致步骤为两步：

上边说到 XGBoost 的预排序后的特征是通过索引给出的样本梯度的统计值，因其索引访问的结果并不连续，XGBoost 提出缓存访问优化算法进行改进。

而 LightGBM 所使用直方图算法对 Cache 天生友好：

首先，所有的特征都采用相同的方法获得梯度（区别于不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中； 其次，因为不需要存储特征到样本的索引，降低了存储消耗，而且也不存在 Cache Miss的问题。

GBDT类模型总结

代码文档

【务实基础】梯度提升树GBDT

简要介绍：GBDT是先产生一个弱学习器 (也叫基学习器)，训练后得到样本的 “残差” (严格来说是负梯度)，然后再产生一个弱学习器并基于上一轮学习器得到的 “残差” 进行训练，不断迭代，最后加权结合所有弱学习器得到强学习器。

【务实基础】XGBoost

代码文档: https://xgboost.readthedocs.io/en/latest/get_started.html

简要介绍：为了避免GBDT过拟合，XGBoost提出加入三种正则化手段：在损失函数内加入正则化、缩减树权重和列采样。此外，XGBoost在树分裂点划分上，采用近似算法 (即以特征值分位数作为候选分裂点)。同时，针对近似算法还额外补充三种策略去优化模型训练速度：局部分裂策略 (即在新分裂结点下的样本集中重新提出分位数点)、加权分位数策略 (即以二阶导数加权赋值) 和稀疏值策略 (即对缺失值和稀疏值数据自动划分方向)。最后，XGBoost还进行了工程上的优化：列块并行学习、缓存访问和块式核外计算。

代码文档: https://lightgbm.readthedocs.io/en/latest/

简要介绍: LGBM比XGBoost更快，且很好保持住了准确性。它主要从三方面着手：

(1) 在树方面，提出了直方图算法寻找最佳分裂点，而且还采用Leaf-wise树生长策略。

(2) 在样本数上，使用GOSS保留所有大梯度样本但随机采样小梯度样本，减少训练样本量。

(3) 在特征数上，使用EFB捆绑互斥特征，将特征变稠密。此外，作者还采用GS编码，在GBDT一类模型中，这是第一次能直接支持类别型特征，不需要提前独热编码后再输入至模型中。最后，同样地，LightGBM也跟XGBoost一样进行了工程优化，使得训练能高效并行且增加Cache命中率。

【务实基础】CatBoost

代码文档: https://catboost.ai/docs

简要介绍: CatBoost解决了由训练集和测试集分布不一致带来的预测偏移问题，主要是从两方面入手：(1) 使用Ordered TS对类别型特征编码，成功避免目标泄露。(2) 使用Ordered Boosting提升方法，使模型获取无偏残差，保证模型不偏于训练集。此外，模型还对类别型特征进行特征组合，给训练输入增加了特征交互的信息。