复杂二叉树的遍历_计算算法的时间复杂度属于

面试准备 集成学习和tree 　　这块儿内容是大头，太多了，单独分出来写。 　　历史可参考： 　　https://zhuanlan.zhihu.com/p/? 　　重复部分以本文为主，做了一些improve。 　　树和集成学习: 　　问：集成学习的方法知道几种？他们有何异同？ 　　集成学习领域的三个主要研究方向： 　　1.强学习器结合，典型的例如简单平均法，加权平均法，投票法，stacking等，来自于模式识别领域，主要研究使用什么样的规则去结合强学习器，使用的学习器往往是异构的（即不同的算法）； 　　2.弱学习器集成，典型的有boosting和bagging，来自于机器学习领域，主要研究怎么通过弱学习器组合得到强学习器，使用的学习器往往是同构的（即相同的算法）； 　　3.混合专家模型，典型的有moe，mmoe，主要集中在神经网络领域，混合专家模型涉及将预测建模任务分解为多个子任务，在每个子任务上训练专家模型，开发一个门控模型，该模型根据要预测的输入学习给予不同的专家模型不同的权重，并进行基础。 　　可以看到，混合专家模型中，多个基学习器是共同训练的；

　　问：可否将随机森林中的基分类器，由决策树替换为线性分类器或K-近邻？请解释为什么？ 　　随机森林属于Bagging类的集成学习方法。Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance。由于
，所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有
，此时可以显著降低variance。若各子模型完全相同，则
因此，对于bagging的基学习器来说，理想的基学习器是低bias的，线性分类器本身的决策边界是超平面，而现实中遇到的分类问题其真实的决策边界往往是非线性的，因此bias往往会比较大，并不适用于bagging的基础框架； 　　对于knn这类特殊的非参+懒惰模型，在k取值相同的情况下，所有的基学习器knn都是完全相同的，并不能降低knn的方差。（这里单纯从bagging层面出发，没有考虑feature的采样，如果考虑了feature的采样则结论为不一定，因为在聚类的问题中也有bagging+knn的组合起到比单个knn更鲁棒更好的吓偶句） 　　问：决策树的损失函数 　　

　　问：xgboost如何调参,给定一个场景如何自定义损失函数？如果样本的权重不一样如何自定义损失函数？ 　　祖传参数+经验微调，max depth，行列采样比例，学习率，树的数量，实际使用中影响最大的，树的数量一般通过早停来确定即可。 　　根据场景，将定性的业务目标抽象为定量的损失函数，计算损失函数的1，2阶梯度，例如： 　　但实际上，其实我们也可以仅计算1阶梯度，2阶梯度直接用常数1来代替也是可以的，同样也可以满足xgb或lgb的工程设计，此时就退化为了原始的gbdt的求解了，仅使用一阶梯度信息。在自定义损失函数中要定义样本权重，通过对grad和hess中对应样本进行加权即可，例如grad=[1,1,1,,1]，我们对第一个样本加权，比例为2，则grad改变为[2,1,1,1]即可； 　　问：能否用LR 做GBDT基模型？ 　　gbdt是boosting的集成学习方法的一种实现，旨在显著降低基模型的偏差而不显著降低基模型的方差（这里仅从gbdt算法层面出发，不考虑xgb这类工程实现在算法上的各种正则或行列采样的优化），对于线性回归模型而言，基模型的“累加”预测最终得到的仍旧是一个线性模型（对于逻辑回归，在gbm的框架下，仍旧是用线性回归来完成分类问题，就好比gbdt用回归树来完成所有的分类或回归问题）， 　　如果我们的基学习器是线性模型，假设我们迭代两次得到两个线性模型，那么
,
,那么整个模型就可以写成： 　　
　　仍旧是一个线性模型。 　　简单点的说法就是，gbm降偏差，当代gbm框架降低偏差和方差，那么就更focus在基模型的多样性上，tree在不同的子数据集上生成的结构截然不同，多样性强，更好的增强集成学习的效果。 　　问：我看你的简历里写在XX项目、XX比赛、XXXX里用过树模型，你知道有哪些常见的树模型吗？ 　　答：id3，c4.5，cart，以及平常比较少接触的c5.0，et(极限随机树)，chaid，多变量决策树等，以及经典的adboost，rf，etf（极限随机森林），iforest和gbdt，神经网络中还有一些仿树模型的神经网络结构例如tabnet，grownet，node等； 　　问：id3，c4.5，cart有什么区别（我觉得应该没什么人会问c5.0这类生僻的东西吧。。） 　　id3是以信息增益为分裂好坏的衡量标准的决策树。……. 　　问：稍等，信息增益怎么计算的？ 　　信息增益=信息熵-条件熵=互信息 　　问：什么是信息熵和条件熵，手写一下公式吧？ 　　这就涉及到随机变量的信息量的衡量了，我们平常听到的许多“熵”其实是可以针对连续或者离散随机变量定义的，不过在决策树中，主要还是针对于离散的随机变量的计算，先说信息量吧： 　　假设我们有一个不同事件的组成的事件集合，则事件集中每一个事件的信息量定义为： 　　
　　其中
表示事件集合 D 中属于第 k 类事件的样本子集。用于衡量事件集合D中事件Ck的不确定性; 　　一般公式中的底数为2，计算的结果的单位为bit。很符合直觉的公式，一个事件发生的概率越大，则这个事件的信息量越小,信息量衡的是不确定性； 　　一个事件集合的信息熵就是事件集合中所有事件的信息量的期望，离散变量中的期望说白了就是加权求和，

　　信息熵衡量了整个事件集合D的不确定性, 　　问：打断一下，公式里为什么要取对数？为什么取负数？ 　　1.取对数很多时候在计算上可以提供很大的便利性，例如计算两个独立事件A，B同时发生从而产生的C事件的信息量，如果取得是对数，我们可以直接进行加法计算而不需要进行乘法计算，例如p(x,y)=p(x)p(y)可以转化为ln(p(x,y))=ln(p(x))*p(y)，相对于加法计算而言，乘法计算更容易导致数据溢出的问题； 　　2.取负数是因为信息熵的计算如果不包含负号则必为负数，log2(x),x<1 则log2(x)，这不符合人类直观上的认知，即不确定性越高，信息熵应该越大； 　　问：好的，继续吧 　　针对某个特征 A，对于数据集 D 的条件熵
为： 　　
　　其中
表示 D 中特征 A 取第 i 个值的样本子集，
表示
中属于第 k 类的样本子集。 　　条件熵用来衡量已知事件集合A的情况下,事件集合D的信息熵,即已知事件集合A的情况下,事件集合D的不确定性。 　　信息增益 = 信息熵 – 条件熵： 　　显然,信息增益衡量的是已知事件集合A的情况下,事件集合D的整体的信息熵(不确定性)的减少程度,本质上就是将原始的D事件集合的信息熵和已知A事件集合之后的D事件集合的信息熵进行对比; 　　问：信息熵公式，说说联合熵的公式，他们的关系是怎样的？ 　　id3中，信息熵衡量的是一维离散随机变量的不确定性，（注意，信息熵，联合熵等各种熵的定义都是适用于连续随机变量和离散随机变量的具体可见：马东什么：机器学习中的信息论 　　）

　　将一维离散随机变量推广到多维离散随机变量时，得到联合熵：

　　条件熵表示在已知随机变量 X 的条件下随机变量 Y 的不确定性：

　　互信息=信息熵-条件熵，用于衡量已知随机变量x的前提下，随机变量y的不确定性的减少程度。 　　上述概念同时适用于离散随机变量和连续随机变量。 　　问：id3有什么缺点？ 　　1.信息增益的划分标准对于事件数量特别多的事件集合，或者说类别特别多的类别特征有明显的优先选择分裂的倾向,一个极端的例子,特征A中的每一个类别的数量均为1,则条件熵
的计算结果为0,这意味着已知A事件的情况下,事件D的不确定性为0,事件D变成了一个必然事件,信息增益达到最大;, 　　2、显而易见，使用信息增益作为分裂好坏的评估方式注定了id3只能处理离散特征和离散的标签值(即只能处理二分类或者多分类问题); 　　3.无法处理缺失值,无剪枝策略容易过拟合, 　　问: id3是多叉树还是二叉树 　　多叉树 　　问:c4.5相对于id3的改进是什么?(基本上按照id3的缺点来记忆即可) 　　c4.5使用了信息增益率克服信息增益偏好高基数类别特征的问题 　　HA(D)是事件A的信息熵,同时由于信息熵偏好于取值较少的类别特征,采用了一种启发式的分裂方式,先找信息增益高于均值的特征,再从这些特征中选择信息增益率高的特征 　　2. c4.5使用了二叉树不再是多叉树, 主要是为了让tree能够使用连续特征和离散特征都作为分裂依据,由于连续特征往往取值很多,进行多叉树分裂不现实并且极其耗费事件,因此使用了二叉树,这因为如此c4.5可以处理连续特征,但仍旧无法处理回归问题; 　　3.c4.5能够处理缺失值以及引入了剪枝的概念来缓解tree容易过拟合的问题,缺失值处理的方式较为简单,非缺失样本正常进行信息增益率计算,缺失样本复制进入左右两个节点,但是进入左右两个节点的过程中,对缺失样本分别进行赋权,进入左节点的缺失样本的权重为 左节点非缺失样本数量/左右节点所有非缺失样本数量,进入右节点的缺失样本权重为 右节点非缺失样本数量/左右节点所有非确实样本数量. 　　c4.5中引入和预剪枝和后剪枝,预剪枝主要从两个层面入手: 　　1 tree的超参,例如min data in leaf; 　　2 分裂必须保证增益大于某一阈值等等; 　　这也是目前主流的剪枝策略,最大的好处在于相对于后剪枝计算复杂度大大下降; 　　后剪枝从下至上,,逐个移除非叶子节点(当然,非叶子节点的子节点也一并移除),然后评估c4.5是否在测试集上的泛化性能变得更好; 　　目前,在gbdt或rf中基本不会使用后剪枝的方式,这样的计算复杂度实在太高了; 　　问:为什么c4.5从信息增益换成信息增益率 举个具体的例子(信息增益比跟信息增益相比，优势是什么？)? 　　假设某个类别特征中的每个类别的数量均为1,则信息增益计算的结果为

　　H(D|A)=0,信息增益最大. 　　而信息增益率的计算结果为:

　　特征A是一个超高基数的类别特征,因此其信息熵很大,这导致特征A的信息增益率由于分母很大而值变得很小,信息增益率实际上是引入了特征的信息熵作为分母来对高基数类别特征进行惩罚; 　　问:CART树和ID3区别？(基本上按照id3的缺点来记忆即可)基尼系数是否就没有信息增益的缺点了？如果把ID3的信息增益换成基尼系数是否就没有偏好高基数类别特征的缺点了? 　　cart时代,tree完全进化为了二叉树,其改进有:引入了gini系数作为分类问题的分裂好坏的评估方式,

　　gini增益为:

因为是二叉树所以只有两项，用Gini(D,A)减去分裂前的Gini 　　gini同样可以用于衡量分裂之后的不同子集的不纯度,gini越大,则不纯度越高即纯度越低,gini越小则纯度越高,当pk=1的时候,即意味着必然事件,gini达到最小值0; 　　使用mse作为回归问题的分裂好坏的评估方式

　　2.使用了二叉树 　　3.cart tree处理缺失值使用了代理分裂(surrogate split),剪枝使用了基于代价复杂度的剪枝(这种生僻的知识点貌似都没看到有面经提到过…所以就不展开研究了,具体可见【机器学习】决策树（上）——ID3、C4.5、CART（非常详细） 　　) 　　对于cart tree来说,由于使用的是二叉树,并不会存在偏好高基数类别特征的问题,对于id3来说,使用了多叉树,因此很容易偏好高基数类别特征,罪魁祸首是多叉树的问题,所以将id3中的多叉树换成二叉树,无论使用信息增益还是gini,都可以避免id3的缺点,单纯将id3中的增益率替换为gini,问题仍旧存在; 　　问:决策树的两种剪枝策略分别是什么？ 　　预剪枝和后剪枝,前者是模型训练前或训练过程中进行剪枝,方法是引入超参进行限制,例如min data in leaf,后剪枝则是自上而下依次删除非叶子节点评估模型在测试集上的误差从而决定是否剪枝的方法; 　　问:什么是前向分布算法,加性模型,梯度提升,集成学习,四者之间有什么关系? 　　前向分步算法的最终形式:

　　
为第m个基学习器的系数,b为第m个基学习器; 　　我们最终要优化的loss function是:

　　前向分布算法是以加性模型的形式存在,二者是不同层面的概念,前向分布算法提出使用加性模型的形式来解决最优化问题,,而boosting系列的集成算法则是前向分布算法的具体的解决方案（包括adaboost和gradient boosting machine）,类似于老师和学生的关系,老师给定问题,学生给出答案,问题 是唯一的,答案不一定是唯一的. 　　梯度提升法是boosting算法中的一种,boosting算法是一大类算法,其地位和梯度下降法是一样的,即boosting算法是一种优化算法,可以用于处理凸优化和非凸优化的问题,adaboost(自适应提升算法),gradient boosting(梯度提升算法)用于处理凸优化问题,brownboost可以用于处理非凸优化问题; 　　由于boosting的求解问题的思路是对大量的弱学习器进行组合从而共同预测,这符合集成学习的定义,因此boosting算法也被归类为集成学习(ensemble learning)的一种; 　　问:你知道gbdt的原理是什么吗?gbdt各基学习器之间是如何产生联系的? 　　gbdt是boosting算法的一种,而boosting算法处理损失函数的优化问题就是对大量的基学习器进行组合,常见的boosting算法有adaboos和gradient boost,gbdt使用的是gradient boost,即梯度提升的思想,并使用了cart tree作为其基学习器, 　　因此,gbdt的原理可以从两个方面解释: 　　1.基学习器的构建方法:第n个基学习器(cart tree)是以第1~n-1个基学习器累积拟合的误差为新标签进行训练的,这里的误差指的是第1~n-1轮的基学习器的累积预测结果和真实标签的损失函数的负梯度, 　　例如损失函数为mse时，一阶梯度是(y_pred-y)，又被叫做残差（残差！=负梯度，当损失函数为mse时，负梯度=残差）; 　　2.基学习器的组合方式:gbdt直接对基学习器进行累加,共同预测,当然,存在学习率的情况下则进行以学习率为权重的加权累加. 　　问:为什么gbdt是以cart tree为基学习器的,为什么不能使用其它的模型作为基学习器? 　　这里涉及到两个问题，一个是gbdt的基学习器必须是一个回归模型，一个是gbdt为什么使用tree作为基学习器。 　　前面提到过，gbdt的训练过程中，第n个基学习器是在1~n-1的基学习器的基础上训练的，具体来说，1~n-1个基学习器共同累加预测得到预测结果，真实标签与预测结果代入损失函数的一阶梯度表达式中计算负梯度，然后第n个基学习器以负梯度为新标签，输入为原始的特征矩阵，进行训练。负梯度一般来说是以连续的形式存在的，因此对于gbdt中的每一个基学习器而言，需要处理的是连续标签的问题，因此只能使用回归模型来处理； 　　第二个问题为什么gbdt使用tree作为基学习器而不能使用其它，这是一个相对复杂的问题，常见的cart tree，本身是低偏差而高方差性质的模型，对于bagging的框架来说很好解释，bagging旨在降低方差对偏差无显著提升，很适合tree的基模型，而对于boosting中的gradient boosting框架而言，本身旨在降低偏差而对方差无显著措施用于提升（这里说的是gbdt不是xgb那些引入了rf思想的工程实现）； 　　这个问题可以从两个角度回答： 　　1.对于boosting或bagging框架而言，由于涉及到大量的基学习器，因此需要尽量使用训练过程较为简单的基模型，像线性回归，nn或svm等这类会涉及到大量迭代的模型而言，使用boosting或bagging的框架会大大增加程序的运行时间，而对于tree而言其训练的过程基于贪心策略，不涉及到复杂的迭代，限制最大深度等模型复杂度的情况下，tree可以很快完成训练； 　　2.我们通过对tree的复杂程度进行限制，例如最大深度或最小叶节点数量，我们实际上是提高了tree的偏差而降低了tree的方差，通过gbm框架的偏差降低作用，达到了同时降低方差和偏差的效果； 　　问：为什么你把多个模型的预测结果做平均/stacking有效? 　　前面提到过，简单平均，stacking等方法都属于集成学习中的“强学习器结合”的研究方向，这个研究方向遵循的基本原则是“好而不同”，即用于集成的基学习器都是强学习器，他们的bias和variance是相似的（毕竟是同一个数据集上训练而来的），假设第i个强基学习器的bias为Xi，有n个基学习器，由于
，所以平均后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有
，此时可以显著降低variance。 　　简单平均等simple的强学习器结合的思路可以从bagging的角度分析，但是stacking这么去理解是非常牵强的，实际上关于stacking并没有太多严谨的理论证明其有效性，在实际应用的过程中stacking也并不总是好于简单平均，因此总的来说stacking也是一个比较偏经验性的方法； 　　问：为什么模型的预测的loss总是无法降低到0？ 　　

　　泛化误差上界理论，《统计学习方法》中仅仅给了二分类问题的泛化误差上界的推导，我也没有闲工夫再去找别的回归或多分类问题上的泛化误差上界的推导了。。。大概知道有这么一个东西就行。 　　总的来说，对于机器学习问题，我们实际上是用经验风险误差去近似估计期望风险误差，因此存在一个泛化误差上界，泛化误差上界与样本数N成正比，与假设空间包含的函数数量d成反比. 因此：当样本数N越大，泛化误差上界越小，当样本数趋于无穷大时，期望风险误差等于经验风险误差，当假设空间F包含的函数越多（可以理解为模型越复杂），泛化误差上界越大. 　　问:gbdt中为什么用负梯度,负梯度的概念是什么,,(导数,偏导数,方向导数,梯度的概念了解吗? 为什么负梯度是函数值下降最快的方向?) 　　首先回答负梯度 的相关概念以及为何负梯度是函数值下降最快的方向。 　　为什么gbdt要用负梯度作为标签，因为负梯度是函数值下降最快的方向,我们的优化目标是最小化目标函数,而gbdt本身是基于梯度提升法去优化目标函数的，

　　梯度提升法可以看作是梯度下降法从参数空间向函数空间的扩展，即我们可以将梯度下降法看作基模型为线性回归这类可以用参数表示的模型下的梯度提升法，因此模型的更新等价于参数的更新。（简单来说，gbdt基于梯度提升法优化目标函数，梯度提升法就是要求用负梯度作为新标签拟合新的函数（模型）然后进行累加的） 　　负梯度是什么?要从斜率说起,一函数中A,B两点之间连接直线的倾斜程度为斜率,其计算公式为

　　当A无限趋近于B时,即delta x 无限趋近于0时,我们有

　　即,在一函数中,导数等于点x0处的切线的斜率. 　　直观来看,某个样本点的导数就是该样本点在该一函数图像上的切线的斜率。导数代表了y相对于x的变化率，说白了就是自变量x变的化导致的y产生的变化的变化程度,导数越大,则x的微小的变化越容易导致y的大幅度变化。 　　当我们分析多函数(函数具有多个自变量)的时候,问题就变得复杂了,此时每一个自变量对应的方向都存在着沿着当前方向的导数,此时我们称每一个方向的导数为偏导数:

　　可以看到,我们在计算某个自变量对应的方向的偏导数的时候,其它方向的自变量都视为常量. 　　对于多函数，偏导数代表了函数值y在某个自变量xi的方向上的变化率。比如一个二函数y(x1,x2)，y对x的x1偏导数就是 固定x2不变，x1的变化导致的y产生的变化的变化程度。 　　偏导数衡量的是函数值在不同的自变量对应的方向上的变化率，如果我们要研究函数值在任意方向上的变化率，例如 y=x+z，我们希望研究函数值y在x和z对应的方向的中间方向上的（即x，z轴的对角线方向）变化率，则使用偏导数无法表达，因此引入了方向导数的概念。 　　方向导数是偏导数在任意方向上的扩展（不仅仅局限于自变量的方向），设l=(x1,x2…xn)

　　可以看到，偏导数是方向导数的特例，当除了delta xj 不变，其它delta xi均为0时，方向导数形式退化为偏导数。当存在任意两个及以上的delta xi不为0，则为方向导数。 　　偏导数和方向导数都是标量， 　　有一些解释是从方向导数和梯度的关系层面去理解的，不过个人感觉从偏导数的角度更好理解和记忆，梯度是函数沿不同自变量方向的模长为偏导数计算结果的向量构成的向量，例如：

　　不同自变量的方向对应的下降最快的方向的 “和向量” 的方向为整个函数下降最快的方向。 　　问：gbdt的推导： 　　

　　感觉从公式上理解挺繁琐的，其实直接用文字描述更简单点： 　　1.初始化基学习器estimator_0, fit(x,y_true),predict得到y_pred,y_accumulate=y_pred； 　　2.将y_accumulate和y_true带入损失函数的负梯度计算公式得到负梯度 y_gradient； 　　3. for i in range(1,M):#M代表了基学习器的数量，人工定义的超参数 　　第i个基学习estimator_i fit(X,y_gradient)，predict得到y_pred_i,y_accumulate+=y_pred_i 　　将y_accumulate和y_true带入损失函数的负梯度计算公式得到梯度 y_gradient； 　　重复循环直到达到停止条件 　　问:gbdt的叶节点权重是怎么计算的?LGB/XGB叶子结点的权重是怎么计算出来的？XGBoost 和 GBDT 分裂叶子节点的不同之处，写一下 　　早期的gbdt的第n个基学习器的都是以前面1~n-1个基学习器的累积预测的预测值(如果从递归的角度来看就是n-1个基学习器预测的结果不过感觉还是以1~n-1这样的口吻会更好记忆)和真实标签之间进行损失函数进行负梯度的计算得到的第n轮的负梯度为标签,原始的输入不变,来进行cart regression tree的训练的,因此,最终gbdt的叶子节点权重的值的计算方式和回归cart tree计算叶子节点的方式是一样的,即第n轮的cart regression tree的叶子节点权重的计算是直接对该叶子节点中所有样本的标签平均(这个标签不是原始的标签，而是1~n-1个cart tree累积预测值 和真实标签代入损失函数负梯度计算公式 计算出来的负梯度）.这一点和xgb具有较大不同. 　　wj=求和（gi）/ 求和（j节点的样本数量）（gbdt中第j个叶子节点的权重的计算公式） 　　xgb的叶节点权重值则是

　　使用该叶子节点的所有样本在第n轮的 一阶负梯度/(二阶梯度+正则化系数lambda) 　　问:(这里的一系列问题其实根据上面的解答就可以很容易得到答案了,所以这些面经题都放一起写)写出gbdt的推导过程,梯度提升和梯度下降体现在什么地方，在损失函数不是平方损失函数时为什么可以用t-1步分类函数相对于损失函数的负梯度来作为残差的近似值，数学意义是什么? 　　推导过程上面已经用文字表述了，很讨厌记公式。 　　梯度提升这个名字可能有点让人费解，实际上可以将梯度提升和梯度下降对比：

　　GBDT使用梯度提升算法作为训练方法，而在逻辑回归或者神经网络的训练过程中往往采用梯度下降作为训练方法，二者之间有什么联系和区别呢？ 　　下表是梯度提升算法和梯度下降算法的对比情况。可以发现，两者都是在每一轮迭代中，利用损失函数相对于当前模型的负梯度方向的信息来对当前模型进行更新， 　　只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中 　　（线性回归在梯度下降法中一次的参数更新可以看作是梯度提升法中的单个模型的一次的模型更新） 　　从而大大扩展了可以使用的模型种类（这是xgb中gblinear的设计思路）。Microstrong：梯度提升（Gradient Boosting）算法

　　问： gbdt中每个弱分类器是什么，为什么用cart回归树而不是分类树，节点的分裂规则，写出公式。公式中的每个值在实际训练过程中是怎么计算出来的，举列子说明（gbdt的基tree的节点的分裂规则参照cart regression tree即可，如果是xgb的话，参考本篇文章关于xgb分裂的gain的公式部分） 　　原始gbdt的每个弱分类器是cart regression tree，xgb则是xgb tree（分裂规则遵循gain公式，不能算是cart tree了）计算方法和过程基本上别的问题里都回答了这里不黏贴了好麻烦。

　　问：bagging和boosting介绍一下，为什么bagging能降低方差,boosting能够降低偏差?（从偏差和方差角度解释boosting和bagging等） 　　Bagging对样本进行重复的采样，使用每一次采样得到的子样本集训练一个模型，最后多所有模型进行平均，boosting则是是对大量的弱学习器进行组合，并且每一个弱学习器的训练都和已经训练完毕的弱学习器强相关，最终对所有弱学习器的预测进行累加从而完成预测。 　　由于bagging在同一个数据集上重复采样并且使用完全相同的基学习器，因此不同的基学习器之间的偏差和方差具有较高的相似性。假设第i个子模型的bias为Xi，则bagging的平均偏差为 　　
，（这里的期望的公式推导可见：

Michael Tan：理解期望、方差常见公式 　　随机变量的期望的线性关系与是否独立无关 　　） 　　这里有一个很有意思的地方，假设基学习器的bias 有正有负，则最终求期望的结果是有可能出现平均的bias小于任意一个bias的。我们在做强学习器集成的时候，使用的简单平均法，就可以达到这样的效果，但是bagging诞生之初主要是用于同质的弱学习器（即同一种算法）集成的，并且这些学习器的初始超参数又基本相同，因此基学习器之间往往bias非常接近并且同号（尤其是bagging一般都和tree结合使用），因此bias比较不容易产生上述的这种理想情况而更多的是同正或同负（可以观察一下rf的每一个tree的bias情况）。 　　因此，bagging后的集成模型的bias和单个子模型的bias接近，一般来说不能显著降低bias。 　　另一方面，若各子模型完全独立，则有
，此时可以显著降低variance。 　　详细公式推导可见下：Michael Tan：理解期望、方差常见公式 　　若各子模型完全相同，则
，此时不会降低variance。bagging方法得到的各子模型因为都是在同一个数据集的不同的子数据集上训练的，是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance，rf在bagging的基础上对特征也采用了抽样，进一步增强了子模型之间的独立性，更好的降低了variance。 　　而boosting是串行的逐步的最小化损失函数，第n个基学习器是在前1~n-1个基学习器的预测结果和真实标签计算的损失函数的负梯度下拟合的，其bias自然是逐步下降的； 　　boosting对于variance的效果，要具体情况具体分析，对于gradient boosting而言，从过拟合的角度来说，由于gradient boosting是在训练集数据上训练的，loss过低会出现过拟合训练集的问题，因此gradient boosting 容易导致variance的降低。但是adaboost不同，虽然adaboost通过让第n个学习器更加第n-1个学习器预测错误的样本从而降低整体的loss，但是adaboost训练的过程中，对于样本的reweight本身也是一种广义上的bagging，因此adaboost对于variance实际上也能够起到一定的降低（这一点参考adaboost的最小间隔和优化间隔理论，adaboost在训练集的loss几乎降低为0的情况下继续训练仍旧能够继续降低在测试集上的误差的现象） 　　gbdt的集成框架用于降低偏差，不能显著降低方差，并且训练集loss过低会有过拟合训练集的问题，但目前gbdt的工业实现，xgb，lgb，catboost等都引入了rf的行列采样的bagging思想用终于降低方差，所以从这个层面来看，xgb等工程实现里的gbdt算法实际上能够在降低偏差的同时也降低方差，理论上和实际应用过程中，xgb等算法也确实比rf来的好； 　　问：rf里的行采样、列采样的作用？rf为什么要使得每棵树不一样？ 　　rf在bagging的框架上对bagging进行了特征层面的扩展（不再局限于样本层面），bagging是在样本层面进行有放回重复采样的，而rf在同时在样本和特征的层面上进行了bagging。之所以这么做主要原因在于，bagging旨在降低方差，各子模型完全独立，则有
，此时可以显著降低variance。若各子模型完全相同，则
，此时不会降低variance。因此rf中自然希望每棵tree越不同越独立则整体降低方差的效果越好，通过对原始的特征空间进行子空间采样，来尽量最大程度保证每一棵tree能够在不同的子空间上进行训练。 　　问：GBDT和随机森林的树的深度哪一个比较深？为什么？ 　　这个问题的问法其实挺有问题的。。。不做任何限制或前提假设其实没什么比较的意义。。估计面试官还是想考察gbdt和rf的知识点吧。 　　gbdt本身能够大幅度降低bias，因此单个树的bias并不会显著影响整个gbdt的bias，所以树不需要构建的太深。而对于rf而言，并不能显著降低bias，所以需要每棵树的bias越低越好，即树需要分裂的更深。 　　问：随机森林一个数据被重复采样的概率是多少？会有多少的样本不被采样到?什么是oob？ 　　对于一个样本，它在某一次含m个样本的训练集的随机采样中，每次被采集到的概率是1/m。不被采集到的概率为1−1/m。如果m次采样都没有被采集中的概率是(1−1/m)^m,m次都采样到的概率为 1/m^m。当m→∞时，(1−1/m)^m→1/e≃0.368（大约1/3的样本不会被采样到，这部分样本称为oob样本，out of bag）,1/m^m趋近于0；oob是out of bag，即随机采样的过程中没有被采样到的样本。 　　问：GBDT的G梯度的向量长度为多少 　　



　　这题 其实问的挺奇怪的。。。 　　这个从xgb中叶节点权重的计算上和tree的打分函数中很容易看出来，每个样本的gi是一个标量，如果一定要说G梯度的向量长度，只能说某个叶子节点的G梯度的向量长度为这个叶节点的样本数量。 　　问：xgboost中的打分函数？ 　　

　　xgb的打分函数可以类别为cart tree中的gini或id3中的信息熵，是一种用于衡量划分效果好坏的评估方法，xgb的分裂增益gain的公式就是根据这里的打分函数得到的。

　　分裂前和分裂后的打分函数的差值即为xgb的分裂公式。 　　问：Xgb里防止过拟合可以设置的参数，平常怎么调参的？什么参数效果最明显？ 　　树的数量，学习率，行列采样比例，树的最大深度，l1，l2正则化，叶节点数量，叶节点最小样本数量等等，树的数量一般通过早停来自动确定，其它参数则根据一些经验参数设定做微调。 个人用过的，比较立竿见影的超参数主要是，树的数量，学习率，行列采样比例以及树的最大深度 效果最明显。 　　问：xgboost/lgb 是如何训练的？ 　　1.初始化基学习器estimator_0（xgb初始输出y_pred为全0，lgb初始全为0.5，当然也可以使用标签均值等的简单的初始化策略）； 　　2.将y_pred和y_true带入损失函数的1，2 阶 梯度计算公式得到一，二阶梯度 y_first_order_gradient和y_second_order_gradient； 　　3. for i in range(1,M):#M代表了基学习器的数量，人工定义的超参数 　　第i个基学习estimator_i 基于gain的分裂公式

　　进行分裂，直到到达终止条件（最大深度，gain小于0或人工设定的阈值以及其它的超参数的限制等等） 　　重复循环直到达到停止条件 　　问： 为什么xgb，lgb对稀疏数据的处理不好？ 　　参考大佬的回答：关于sklearn中的决策树是否应该用one-hot编码？ 　　one-hot coding是类别特征的一种通用解决方法（这里的稀疏数据的典型代表就是高基数类别特征的onehot，低基数类别特征的onehot相对来说影响更小一些），然而在树模型里面，这并不是一个比较好的方案，尤其当类别特征维度很高的时候。主要的问题是：可能无法在这个类别特征上进行切分。使用one-hot coding的话，意味着在每一个决策节点上只能用 one-vs-rest (例如是不是狗，是不是猫，等等) 的切分方式。当特征纬度高时，每个类别上的数据都会比较少，这时候产生的切分不平衡，切分增益（split gain）也会很小（比较直观的理解是，增益很小的切分和不切分几乎没有区别），所以最终会导致决策树不在这些特征上做分裂或者即使分裂了对于loss的降低影响也很小；统计显著性差，会影响决策树的学习。因为就算可以在这个类别特征进行切分，也会把数据切分到很多零散的小空间上，如图1左所示。而决策树学习时利用的是统计信息，在这些数据量小的空间上，统计信息不准确，学习会变差。但如果使用图1右边的切分方法，数据会被切分到两个比较大的空间，进一步的学习也会更好。

　　参照一下xgb或lgb的叶节点权重计算公式：

　　如果这里叶节点的样本数量很少，则计算出来的叶节点权重w的统计显著性差，（gbdt是对样本所落在的所有的叶节点权重进行累加得到最终样本的预测结果的）。就好比我们计算5个样本的均值和计算个样本的均值，计算结果的可信度是不同的。 　　问：xgb中的特征选择能否并行？xgboost是如何实现并行的,xgboost为何能并行化？ 　　可以。先预排序，然后是特征粒度的并行，gradient boosting本身无法并行，xgb是在单个tree的层面上进行特征层面的并行，（这种并行的机制也适用于普通的决策树），因为tree在选择最优分裂特征时，需要计算候选特征集中所有特征的最优分裂点，而每个特征的最优分裂点的计算是相互完全独立的，因此非常适合进行并行； 　　问：xgb的feature importance有几种，怎么输出的，物理含义是什么？如何比较feature importance 　　比较常用的，split和gain，split统计某个特征在xgb的训练过程中被用于分裂的次数的累积，gain统计某个特征在xgb的训练过程中被用于分裂从而带来的增益的累积

　　除此之外，xgb实现了其它的一些feature importance方法：

　　weights=split（split是lgb里的超参数名） 　　gain（average gain其实是）：xgb在分裂过程中使用了n次feature1，则feature1的gain=n次分裂的gain的总和/n 　　total_gainxgb在分裂过程中使用了n次feature1，则feature1的total_gain=n次分裂的total_gain的总和 　　cover(average cover):xgb在分裂过程中使用了n次feature1，每次使用feature1分割的样本的数量之和/n； 　　total_cover(average cover):xgb在分裂过程中使用了n次feature1，每次使用feature1分割的样本的数量之和； 　　一般来说，feature importance得到的重要性高的特征会进行有限分析，以及会对重要性高的特征做一些特征组合的操作。 　　问：xgboost和gbdt有什么区别？ 　　xgboost是gbdt的一种优化后的工程实现，相对于早期的gbdt而言进行了大量的improve。 　　（1）损失函数的二阶泰勒展开； 　　（2）引入了树的正则化（l2 约束叶节点权重不能太大，类似于lr中的l2正则化的作用，gamma的约束则是约束叶子节点的数量）：



　　（3）引入rf中的列采样的思想； 　　（4）引入学习率（这一点其实感觉不算。。）； 　　（5）基学习器的改进,包括了： 　　a、使用了一种新的xgb tree，xgb tree使用了一种新的分裂好坏的评估方式以用于决定如何分裂（这一点是由loss function 反向推导出来的，早期的gbdt，单个tree就是cart regression tree，使用mse指导分裂，间接优化loss function，xgb中直接从待优化的loss function出发，推导出直接优化loss function的分裂公式）； 　　b、自动缺失值处理（稀疏感知）； 　　c、更多的分裂策略包括了原始的基于贪心策略的分裂和一些近似分裂算法以及仿lightgbm的直方图优化算法（目前常用的基本上是hist ，即仿lgb的直方图优化，说白了就是特征做分箱）； 　　d、实现了level-wise和leaf-wise的两种分裂方式（最新版的已经把lgb的leaf wise的生长模式包含进来了），没有实现catboost中的symmetric的分裂方式（完全对称二叉树） 　　问:手推xgboost? 　　xgb的目标函数有一些特殊,是针对第t轮迭代定义的:

　　yi hat(t) 表示的是到第t轮为止,1~t 轮的所有的tree对样本i的累积预测结果,yi表示真实的标签值,constant指的是前面1~t-1棵树的正则项,因为第t轮的时候,前面1~t-1棵树的结构已经固定了,因此1~t-1棵树的正则项的计算结果是固定的常数,因此作为constant存在; 　　二阶泰勒展开公式:

　　带入可得:

　　其中:

　　去掉常数项constant和l(yi,yi(t-1))部分之后,将从样本层面的求和转化为叶子节点层面的求和,定义集合
为树的第j个叶节点上的所有样本点的集合，即给定一颗树，所有按照决策规则被划分到第j个叶节点的样本集合。则根据式2中对模型复杂度惩罚项的定义，

　　对于样本xi 而言ft(xi)=样本xi所落在的叶子节点权重，T表示当前的tree的叶节点数量。 　　求导:

　　wj 带入式（9）,

　　我们称上述的L(t)为树的打分函数,用于衡量树结构好坏的标准，xgb之于打分函数可以类比于于id3之于信息熵的概念或者cart tree之于gini； 　　我们用打分函数选择最佳切分点 　　其中:

　　xgb分裂的判断依据如下：

　　xgb之于gain函数可以类别于id3的信息增益或者cart tree的gini增益 　　问:为什么做二阶泰勒展开?为什么不三阶？XGBoost 如果损失函数没有二阶导，该怎么办？ 　　其实根据xgboost的推导我们可以看出,其实xgboost做一阶泰勒展开也是完全ok的,如果仅做一阶泰勒展开,则推导过程变为:

　　最终可得:

　　损失函数没有二阶导可以直接使用常数1来替代，此时xgb就退化为了仅使用一阶梯度的形式了，其实xgb中mse也只能做成一阶的，因为mse的二阶导就是常数1； 　　xgb做二阶泰勒展开的原因有： 　　1.引入和牛顿法类似的思路， 　　将二阶梯度作为一阶梯度的除项，用于修正 loss function的更新方向，思想和nn中引入二阶矩估计加速收敛的思想是类似的，可以起到加快收敛速度的效果，可以看下分裂的增益公式：

　　分裂增益公式是由loss function推导而来的，实际上每一次分类都类似于 nn中的一个batch，都在减少loss function的值；

　　一阶梯度反应当前loss function下降曲线的最快下降速度，二阶梯度反应当前的loss function下降曲线的最快下降速度的加速度

红色曲线是牛顿迭代法，绿色曲线是梯度下降 　　2.工程设计上： 　　所有的loss function做二阶泰勒展开之后可以使用同一个求解器来求解，因为展开之后的loss function的形式均为：

　　上面是一个变量的简单二次函数的总和，可以通过使用已知技术来最小化，而我们需要将原始目标函数（考虑到有的目标函数不一定是实数域的，通过泰勒展开可以将非实数域的loss function转化为实数域的loss function）转换为欧几里得域中的函数，以便能够使用传统的优化技术（梯度上升法）。 　　（这块儿可以参考一下牛顿法解决的问题，牛顿法中使用的 二阶泰勒展开 不仅仅包括常见的实数域的function，也可以解决复数域的funciton 牛顿迭代法_百度百科 　　） 　　不考虑三阶则是一种精度和速度的折衷的设计。 　　问:xgb是怎么分裂的?XGBoost 计算节点分裂收益的公式手写一下 　　根据前面对目标函数推导得到的打分函数,我们可以评估分裂之后的打分和分裂之前的打分的差值:

　　因为一个父节点分裂为两个左右子节点之后,此时的叶子节点由原来的1个增加为了2个,因此gamma*(T+2-1-T)=gamma 　　根据上述的gain函数,选择gain最大的分裂方式进行分裂; 　　问：gbdt的概率是怎么计算的？gbdt能否计算多分类问题（xgb怎么多分类），是互斥多分类问题，还是非互斥多分类？如果要做非互斥多分类，在gbdt哪一步做改进？ 　　样本所在叶子节点权重值基于learning rate加权求和，然后加入sigmoid或者softmax函数得到概率； 　　gbdt算法可以完成多分类。 　　首先，xgboost中的object of 多分类，一个是multi softprob 一个是multi softmax ，二者其实是一个东西，只不过前者输出概率结果，后者直接输出预测概率最大值对应的class； 　　而lightgbm中对于多分类的问题则多了一种选择， 　　multiclass 和 multiova 　　首先是multiova，这个其实很好理解，对于A，B，C三类而言，实际上我们是产生了三个gbdt模型，第一个gbdt模型用于fit(A,others)，第二个模型用于fit(B,others)，第三个模型用于fit(c,others)，三个模型完全独立，因此最终的决策是A，B，C模型分别输出一个binary的概率，所以使用multiova会出现单个样本的概率之和超过1的情况；

　　对于multi class而言，则是不采用这种策略，看官方文档： ︎, default = , type = int, aliases: , , , , , , , , , , constraints: number of boosting iterationsNote: internally, LightGBM constructs trees for multi-class classification problems 　　可以看到，对于multi class而言，产生了num_class*num_iterations 棵trees。和xgb中的实现是保持一致的。 　　这块儿可以参考一下softmax 回归 　　softmax回归（以三分类为例）：softmax([w11*x1,w12*x2,w13*x3……w1n*xn],[w21*x1,w22*x2,w23*x3……w2n*xn],[w31*x1,w32*x2,w33*x3……w3n*xn])=[y_pred1,y_pred2,y_pred3]其中 y_true=[0,0,1],[0,1,0]或[1,0,0]参数表示为矩阵形式[w11,w12….w1n]，[w21,w22….w2n]，[w31,w32….w3n]这里需要注意，softmax回归的参数是矩阵，不像逻辑回归一样只是一个向量。 　　from 马东什么：关于softmax的导数 　　然后参考一下原作者的回答：https://github.com/microsoft/LightGBM/issues/1518 　　实际上思路不复杂，仍旧是ovr的形式来做的，因此每个iterations会有三棵树，只不过每个iteration，三棵树的输出 rawscore 假设分别为 x1，x2，x3，则使用softmax（x1，x2，x3）来完成当前分裂的预测，并计算一阶和二阶梯度进入下一次分裂。和multiova 不同的地方在于，三棵树之间并不是独立的，因为三者的输出经过softmax进行归一化然后共同参与到当前iteration的计算过程之中。 　　问：Shrinkage作用，为什么设置学习率可以防止过拟合？为什么一般情况下设置学习率模型效果会变好，原理是什么？在gbdt训练过程中，学习率是如何使用的。 　　Shrinkage说的是learning rate学习率，一般学习率设置越小越容易防止过拟合，学习率越小，则需要拟合越多的树，每个树对预测结果的贡献越小，这样即使部分的tree拟合的不好对模型整体的影响也被大量的tree稀释了；学习率在gbdt中的作用就是 累积求和的时，每个tree的预测是乘以learning rate之后再进行累积求和的，其实就是基于learning rate的加权求和、 　　问：LightGBM的直方图 排序后会比xgboost的效果差吗，为什么 　　lgb的单个tree的bias会差于xgb，毕竟分箱之后做的不精确分裂，单个tree的bias会偏大，但是在gradient boosting的框架下，单个tree的bias并不是特别重要，毕竟可以通过拟合更多的tree来弥补，而lgb基于分箱之后的不精确分裂可以一定程度上降低单个tree的variance，整体上lgb的bias会和xgb接近但是variance更优； 　　问:树的正则化是怎么定义的? 　　使用树的叶子节点个数(树的l1正则)

　　、每个叶子节点权重（叶结点的socre值）的l2范数(平方和)(树的l2正)

　　，进行了惩罚项的定义，并加入损失函数之中,gamma和lambda都是人工定义的超参数； 　　问:Xgb是怎么处理缺失值的,这么处理的好处是什么? 　　xgb使用了一种简单的策略处理缺失值，训练阶段，仅仅在特征非缺失的样本上遍历，按照gain的公式:

　　分别将该特征缺失的样本的gi和hi累加到GL和HL中,计算一次Gain_left,然后再计算一次将gi和hi累加到GR和HR中,再计算一次得到Gain_right,比较Gain_left和Gain_right的大小,将缺失数据放到gain更大的那一次分裂中去. 　　这么做的好处是简单,计算迅速,但是明显可以看出这种处理方案比较粗糙,会使得单个tree的预测误差变大,但是在gbm的框架上,单个基学习器的误差可以通过叠加更多的基学习器来弥补. 　　当预测的时候出现缺失值,默认是分到右枝; 　　问：Xgboost怎么处理离散特征？ 　　xgb暂时无法直接处理离散特征，需要将离散特征转化为连续值才能正常处理，例如各种编码方式等； 　　问：Xgboost的正则项使用L1还是L2？L1和L2有什么区别？正则项里如何限制算法的复杂度？ 　　xgb的正则和线性模型中的l1和l2的定义不同，xgb中的l1正则是将叶节点数量作为正则项加入损失函数中，而l2正则则是将叶节点权重的l2范数作为正则项加入损失函数中。这样在模型训练的过程中，如果叶节点数量太多或叶节点权重太大则会对损失函数进行惩罚，从而限制了xgb的叶节点数量和叶节点权重。（实际上xgb的最终输出就是一个lr，叶节点数量代表了lr 的权重系数的数量，叶节点权重就是lr的权重系数的大小，可以认为xgb的决策形式实际上就是一种复杂的polynomial lr，polynomial是无脑做特征组合，而xgb则是根据目标函数做有选择地特征组合） 　　问：Xgb的工程层面的优化有了解过吗？ 　　1 预排序和block结构: 决策树的分裂是需要对原始特征做排序的,排序之后才能正常分裂,早期的gbdt是每一棵树,每一次分裂都进行一次排序,好处是不需要消耗额外的内存空间,坏处就是太慢了; xgb中,对每一维的特征先进行一次排序,然后排序后的结果存成block,假设排序之后的结果为presort,则presort还会有presort.index的额外存储,用来存放当前排序后的特征值对应的原始样本所在的index; 　　2 并行,gbdt因为本身是串行的算法无法在模型层面上并行,所以xgb是在单树的层面上做并行的,每个特征的预排序结果存成block之后,block之间是完全独立的,那么就可以进行并行化处理了; 　　3 缓存访问,presort之后的特征值是以数组形式存储的,内存空间连续,但是通过索引访问原始的样本时,这个访问对应的内存空间则是不连续的,(对操作系统这块儿的知识不太熟悉所以后面还是讲一些比较大白话的东西),做法就是把要访问的样本的信息转化为连续的内存空间; 　　4 其它:”核外”块计算（Blocks for Out-of-core Computation）。当数据量非常大的是时候我们不能把所有数据都加载内存中，因为装不下。那么就必须的将一部分需要加载进内存的数据先存放在硬盘中，当需要时在加载进内存。这样操作具有很明显的瓶颈，即硬盘的IO操作速度远远低于内存的处理速度，那么肯定会存在大量等待硬盘IO操作的情况。针对这个问题作者提出了“核外”计算的优化方法。具体操作为，将数据集分成多个块存放在硬盘中，使用一个独立的线程专门从硬盘读取数据，加载到内存中，这样算法在内存中处理数据就可以和从硬盘读取数据同时进行。为了加载这个操作过程，作者提出了两种方法。 块压缩（Block Compression）。论文使用的是按列进行压缩，读取的时候用另外的线程解压。对于行索引，只保存第一个索引值，然后用16位的整数保存与该block第一个索引的差值。作者通过测试在block设置为
个样本大小时，压缩比率几乎达到26%
29%（貌似没说使用的是什么压缩方法…….）。 块分区（Block Sharding ）。块分区是将特征block分区存放在不同的硬盘上，以此来增加硬盘IO的吞吐量。 　　问：lgb相比xgb做了什么改进？ 　　按照目前应用的情况来看，重要的区别排名如下： 　　1、直方图优化和直方图做差加速； 　　2、直接支持对类别特征的分裂,内置了类别特征的正则化处理(相对于xgb来说多了一个正则化的方法)； 　　关于lgb对类别特征是如何支持地可见： 　　马东什么：不手写lightgbm（1）—怎么分桶的 　　对于类别特征的处理可以说是比较复杂了。。。 　　3、efb和goss(论文中重点提到的)； 　　4、使用了leaf-wise的生长方式，当然这个区别现在已经不存在了，xgb，lgb和catboost都已经实现了leaf-wise的生长方式了； 　　问：lightgbm的叶子节点是怎么分裂的？ 　　leaf-wise，即比较左右子节点的分裂增益，仅在分裂增益最大的子节点上进行进一步的分裂； 　　问：直方图优化是怎么做的具体？看过源码吗？直方图做差加速是怎么做的? 　　是的，直方图优化简单来说就是对连续特征和离散特征进行分箱，lgb默认是255的最大分箱数量，因为可能有的连续特征取值还不到255，那么就不必分箱了，这么做的好处是， 　　时间复杂度上看： 　　xgb的贪婪策略遍历分裂的时间复杂度为O(data)，而lightgbm基于直方图的划分方式只需要O(max_bin)的时间复杂度， 　　空间复杂度上看： 　　xgb的贪婪策略要进行预排序，同时保留预排序后的样本的索引值，其形式是feature下的feature.index的形式,feature.index和feature的长度是一样的； 　　lightgbm本身构建直方图的过程中是有做排序的,不知道为啥那么多人说lgb不用做排序 　　Features – LightGBM 3.2.1.99 documentation 　　官网上写了已经

　　这里面涉及到两个东西,Histogram和bins: 　　首先,在训练之前,对特征进行排序,排序之后,lgb根据预排序的结果定义Histogram,可以把Histogram看作字典,这个字典保存了每个特征的bins的区间定义,实际上就是定义了一个[-inf,1],[1,3]….[n,inf]这样的结构,比如默认max bin是255,则区间的数量最大是255.这个区间定义的过程是需要先对原始的特征做排序的,然后才能定义的出来. 　　然后,区间定义的过程中,每个feature中的每一个样本对应的这个feature的value都会被转化为其对应的区间下的有序的index,,比如值在[-inf,1]则为0,在[1,3]则为1,这样的话,n个样本在这个feature下的n个value就会被转化为n个整型数,这n个整型数存储为上图中的f.bins,为了方便理解,这里称之为histogram_key, 　　因为这个整型数的最大值不会超过max bins,所以max bins比较小的时候可以用int8这样的数据类型存储; 　　接着,每次分裂的时候,会生成一个新的Histogram,将bins下每个样本对应的histogram_key对应的一阶梯度和二阶梯度累积到Histogram的histogram_key里. 　　Histogram做差加速发生在分裂的时候,我们只需要计算左节点的1,2阶梯度总和以及样本数量,然后用父节点的1,2阶梯度总和和样本数量减去就可以得到右节点的1,2阶梯度总和和样本数量了,这里是在Histograrm中进行遍历的,Histograrm的histogram_key最多只有max bins个,所以最多也只需要遍历max bins次. 　　问：那么LGB是使用什么方法处理类别特征的,类别特征又是怎么转化为bins的? 　　lgb有一个max_cat_to_onehot,如果类别特征的类别数量cat小于这个值,则分裂的过程等效于对类别做onehot,然后在cat个onehot特征上分别做分裂; 　　如果类别数量cat超过这个参数,则lightgbm做的是梯度编码,sum_gradient/sum_hessian,将类别特征中的每一个类别按照这个公式进行离散数据连续化,思路类似于woe和target encoding编码,就是通过使用标签的信息来对离散特征进行统计编码,编码之后的类别特征就成为了连续特征,但是和连续特征的划分方式不太一样; 　　不过有一些细节的地方,这部分是后来开发者加上去的:https://github.com/microsoft/LightGBM/issues/1934 　　1 lgb中,类别特征的分裂是从左到右和从右到左两个方向,并且并不是枚举所有的分裂节点,而是受max-cat-threshold这个超参数的限制,默认值是32,也就是只会去枚举左右各16一共32个可分裂的间隔; 　　2.cat_smooth是一个平滑系数,也是人工可以设定的超参数,主要是用于:sum_gradient/(sum_hessian+cat_smooth) 避免编码的时候出现除0的问题并且起到一定的平滑小类别的噪声的作用; 　　3.min_data_per_group,也是超参数,用于设定类别特征划分的过程中,左右节点最少的样本数量,避免了某个左节点或右节点划分出来的样本太少(高基数的类别特征比较容易出现这个问题) 　　4.cat_l2 对于类别特征划分的正则项系数,这里的处理思路也很简单,源代码里有写: 　　https://github.com/Microsoft/LightGBM/blob/fb28070e1daa500b087dae/src/treelearner/feature_histogram.hpp#L112-L234 　　xgb和lgb分裂的时候的分裂好坏的评估方法都是:

　　cat_l2的作用,就是在分裂类别特征的时候,额外再将gain-cat_l2,施加了相对于连续特征分裂更加严格的正则化; 　　问：说说LGB的efb具体是怎么做的? 　　efb,eclusive feature bundling, 　　默认参数是enable_bundle=True, 　　其实做的事情很简单,假设下图是分桶之后的结果:

　　efb主要是针对于原始数据存在大量的稀疏特征而提出的优化方法,思路就是将稀疏的特征合并,例如上图, 　　efb中引入了偏移常量offset,也就是feature1中的最大值.详细可见: 　　hcccccccc：详解LightGBM两大利器：基于梯度的单边采样（GOSS）和互斥特征捆绑（EFB） 　　lgb的efb的超参数设定中允许一定的误差存在，即少量feature1和feature2都非0的部分也给feature1 引入offset，例如上图中，feature1=1且feautre2=0的部分也可以做一个+4的处理，这会导致feature_bundle中出现错误的4和正确的4共存的情况，一般来说超参数默认是不允许efb存在误差的； 　　问：那你顺便说一下goss吧? 　　goss,goss实现了一种灵活的行采样方法,当然列采样方法还是按照gbdt那一套来的,goss的思路也不复杂,按照样本的一阶梯度进行排序,然后对前a%大的样本A进行保留,对剩余的样本B进行b%的采样,然后,为了保证整体的一阶梯度的期望不变,对剩余样本B的权重进行放大,放大的倍数为

　　这里a和b都是人工可以设定的超参数,注意样本数量的变化是指数下降的,因为每一次都是在上一棵树拟合的样本上继续进行采样的; 　　实际使用的时候,泛化性能往往要稍微弱于gbdt,但是训练速度相当快. 　　问：leaf-wise和level-wise的区别,哪种更好? 　　大家熟悉的id3,c4.5,cart,gbdt,rf的概念里,都是level-wise的生长方式,父节点分裂为左右子节点之后,每个左右子节点成为新的父节点之后递归继续分裂; 　　leaf-wise则是,父节点分裂之后,比较左右两个子节点的gain,仅仅在gain最大的那个节点上继续分裂,这么做的好处是如果某次分裂之后,左右节点中某个节点的增益很小,就没有必要继续分裂了,节约时间,坏处就是如果左右节点增益差不多,根据leaf-wise的思路,最终会选择其中增益最大的一个节点,放弃其实也存在较大增益的另一个节点,这样分裂其实整体的误差都会偏大,需要更多的tree才能收敛.没有好坏之分. 　　问： 说一下lightgbm为什么泛化性能要比xgb好？ 　　最主要的原因还是在于直方图算法，对特征进行分箱，使用“不精确”的分裂方法，这种不精确的分裂方法起到了一定的正则化的作用，使得模型的训练过程相对于贪婪的分裂规则更不容易过拟合到训练数据集上。 　　问：树集成模型，层数少+树多，与层数多+树少，哪个更能防止过拟合？ 　　层数少，基tree的variance相对小，bias相对大，叠加树多做平均，variance会进一步下降，但bias则下降的幅度往往不显著； 　　层数少+树多更能防止过拟合，层数少，base tree的variance更低，rf的集成框架下variance更低，防止过拟合效果好；（相应的bias会降低，具体的就是训练和测试集的metrics的gap变小，但是训练和测试集的metrics整体都变差） 　　对于gbdt而言，也是一样，base tree的variance更低， 　　层数少+树多 更能够避免过拟合。 　　问：集成树模型/树模型存在一个特征选择的过程，为什么还要人工做选择特征呢，按道理不是一样的吗？ 　　1.效率层面：gbdt的训练是需要消耗较多时间的，如果能够人工先筛选掉一部分显然无效的特征，可以降低训练gbdt的计算压力； 　　2.gbdt做特征选择的局限性，即feature importance并不是万能的，例如对于toxic feature，feature importance是无法识别的，这个时候就需要用permutation importance，null importance等方法来帮助识别； 　　问：stacking模型融合怎么做的？为什么有效？ 　　n个模型stacking，n个模型分别k折交叉验证，取k折交叉验证过程中的预测结果作为meta data，n个模型最终会得到n列的meta features，然后使用meta features和原始标签训练一个meta estimator，从而完成一个两层的stacking模型。当然，stacking和深度学习一样可以做的很深，meta estimator也可以使用很复杂的模型。 　　stacking并不是总是work的，一般来说，多个不同的基学习器具有相似的bias和variance才能达到好的效果，但是他们的局部的精度必然要存在较大不同（否则如果多个模型都在同样的样本上犯错，在同样的样本上不犯错，集成没什么意义）； 　　即“强学习器结合”这一ensemble learning的研究方向遵循好而不同，背后的原因是，一些模型的局部高精度的预测往往会抵消一些其它模型的局部高误差。 　　问:单决策树如何后剪枝，xgb中实现的是哪一种？ 　　后剪枝的方法有很多，参考阿泽写的就好了：阿泽：【机器学习】决策树（上）——ID3、C4.5、CART（非常详细） 　　xgb做的是预剪枝，计算gain的时候，如果gain小于0则不分裂。 　　问：GBDT每棵树分裂特征会重复利用吗？ 　　可以重复使用 　　问：如果单棵决策树在数据集上的表现很差,还要尝试随机森林吗？ 　　不用，bias很差，rf不能降低bias，最终的结果应该是rf的效果也不好； 　　问：理解GBDT使用的梯度上升法与梯度下降法的区别 　　下表是梯度提升算法和梯度下降算法的对比情况。可以发现，两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新，只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。

　　from Microstrong：梯度提升（Gradient Boosting）算法 　　问:谈谈Adaboost的原理及其实现思路，adaboost和gbdt有什么联系吗？说说adaboost损失函数？ 　　马东什么：从离散型adaboost 到概率型 adaboost 　　下面这篇讲的是离散的adaboost，也是我们比较熟悉的西瓜书上写的那一版，流程写的很清楚，就不赘述了。梦里寻梦：（十三）通俗易懂理解——Adaboost算法原理 　　问:xgboost和lightgbm在工程层面的优化有了解过吗? 　　xgb的工程层面的优化：金贵涛：对xgboost的理解 　　lightgbm工程层面的优化Microstrong：深入理解LightGBM