集成学习--百面机器学习

集成学习--百面机器学习

 

集成学习

boosting & bagging

读书笔记--《百面机器学习》

作者：诸葛越，葫芦娃

集成学习分哪几种？他们有何异同？

Boosting

Boosting方法训练基分类器时采用串行的方式，各个基分类器之间有依赖。

它的基本思想是将基分类器层层叠加，每一层在训练的时候，对前一层基分类器分错的样本，给予更高的权重。测试时，根据各层分类器的结果的加权得到最终结果。

Boosting思想的核心是迭代式学习，从错误中学习。独孤九剑。

Bagging

Bagging与Boosting的串行训练方式不同，Bagging方法在训练过程中，各基分类器之间无强依赖，可以进行并行训练。其中很著名的算法之一是基于决策树基分类器的随机森林（Random Forest）。为了让基分类器之间互相独立，将训练集分为若干子集（当训练样本数量较少时，子集之间可能有交叠）。Bagging方法更像是一个集体决策的过程，每个个体都进行单独学习，学习的内容可以相同，也可以不同，也可以部分重叠。但是由于个体之间存在差异性，最终做出的判断不会完全一致。在最终做决策时，每个个体单独做出判断，再通过投票或者平均的方式做出最后的集体决策。

Bagging的主要思想是集体投票，类似于，三臭皮匠，顶一个诸葛亮。

我们在从消除基分类器的偏差和方差的角度来理解Boosting和Bagging方法的差异。基分类器有时候又被称作为弱分类器，因为基分类器的错误率要大于集成分类器。基分类器的错误是偏差和方差两种误差之和。偏差主要是由于分类器的表达能力有限导致的系统性错误，表现在训练误差不收敛。方差是由于分类器对于样本的分布过于敏感，导致在训练样本较少时，产生过拟合。

Boosting方法是通过逐步聚焦于基分类器分错的样本，减小集成分类器的偏差。Bagging方法则是采用分而治之的策略，通过对训练样本多次采样，并分别训练多个不同的模型，然后做综合，来减少集成分类器的方差。假设所有基分类器出错的概率是独立的，在某个测试样本上，用简单多数投票法来集成结果，超过半数基分类器出错的概率会随着基分类器的数量增加而下降。

集成学习有哪些基本步骤？请举几个集成学习的例子?

虽然集成学习的具体算法和策略各有不同，但都共享同样的基本步骤。

集成学习一般可以分为三个步骤：

一，找到误差相互独立的基分类器

二，训练基分类器

三，合并基分类器的结果

合并基分类器的方法有voting和stacking两种。前者是利用投票的方式，将获得最多选票的结果作为最终的结果。后者是用串行的方式，把前一个基分类器的结果输出到下一个基分类器，将所有基分类器的输出结果相加（或者用更复杂的算法融合，比如把各基分类器的输出作为特征，使用逻辑回归作为融合模型进行最后的结果预测）作为最终的输出。以Adaboost为例，其基分类器的训练和合并的基本步骤如下：

确定基分类器：事实上，任何分类模型都可以作为基分类器，但树形结构由于结构简单且较容易产生随机性所以比较常用。

...............

从Adaboost的例子中我们可以明显地看到boosting的思想，对分类正确的样本降低了权重，对分类错误的样本升高或者保持权重不变。在最后进行模型融合的过程中，也根据错误率对基分类器进行加权融合。错误率低的基分类器拥有更大的话语权。

另一个非常流行的模型是梯度提升决策树，其核心思想是，每一棵树学的是之前树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。

我们以一个视频网站的用户画像为例，为了将广告定向投放给指定年龄的用户，视频网站需要对每个用户的年龄进行预测。在这个问题中，每个样本是一个已知年龄和性别的用户，而特征则是包括这个人访问的时长，时段，观看的视屏的类型等。

例如用户A的真实年龄是25岁，但第一棵决策树预测的年龄是22岁，差了3岁，即残差为3。那么在第二颗树里我们把A的年龄设为3去学习，如果第二棵树能把A分到3岁的叶子节点，那么两棵树的结果相加起来就可以得到A的真实年龄。如果第二颗树的结论是5岁，则A仍然存在-2岁的残差，第三棵树里把A的年龄设置为-2岁，继续学习。这里使用残差继续学习，就是GBDT中Gradient Boosted所表达的思想。

常用的基分类器是什么？

常见的基分类器是决策树，主要有以下三个方面的原因。

第一，决策树可以较为方便地将样本的权重整合到训练过程中，而不需要使用过采样的方法来调整样本权重。

第二，决策树的表达能力和泛化能力，可以通过调节树的层数，来做折中。

第三，数据样本的扰动对决策树的影响较大，因此不同子样本集合生成的决策树基分类器随机性较大，这样的‘不稳定学习器’更适合作为基分类器。

此外，在决策树节点分裂的时候，随机地选择一个特征子集，从中找出最优分裂属性，很好地引入了列采样随机性。典型的随机森林，就有两个随机性，行采样和列采样。

除了决策树，神经网络也适合作为基分类器，主要由于神经网络模型也比较不稳定，而且还可以通过调整神经元数量，连接方式，网络层数，初始权值等方式来引入随机性。

可否将随机森林中的基分类器，由决策树替换为线性分类器或KNN？请问为什么？

随机森林属于bagging类的集成学习。Bagging的主要好处是集成后的分类器的方差，比基分类器的方差小。Bagging所采用的基分类器，最好是本身对样本分布较为敏感的（即所谓的不稳定的分类器），这样Bagging才能有用武之地。线性分类器或者KNN都是较为稳定的分类器，本身方差就不大，所以以他们为基分类器使用Bagging并不能在原有基分类器的基础上获得更好的表现，甚至可能因为Bagging的采样，而导致他们在训练中更难收敛，从而增大了集成分类器的偏差。

什么是偏差和方差？

在有监督学习中，模型的泛化误差来自于两个方面--偏差和方差，具体来讲方差和偏差的定义如下：

........................

参考：

在模型预测中，模型可能出现的误差来自两个主要来源，即：因模型无法表示基本数据的复杂度而造成的偏差（bias），或者因模型对训练它所用的有限数据过度敏感而造成的方差（variance）。

1) 如果模型具有足够的数据，但因不够复杂而无法捕捉基本关系，则会出现偏差。这样一来，模型一直会系统地错误表示数据，从而导致预测准确率降低。这种现象叫做欠拟合（underfitting）。简单来说，如果模型不适当，就会出现偏差。或者，我们可能有本质上是多项式的连续数据，但模型只能表示线性关系。在此情况下，我们向模型提供多少数据并不重要，因为模型根本无法表示其中的基本关系，我们需要更复杂的模型。那是不是拟合程度越高越好呢？也不是，因为还会有方差。

2)方差就是指模型过于贴近训练数据，以至于没办法把它的结果泛化（generalize）。而泛化是正事机器学习要解决的问题，如果一个模型只能对一组特定的数据有效，换了数据就无效了，我们就说这个模型过拟合。

如何从减小方差和偏差的角度解释boosting和bagging的原理？

Bagging提高弱分类器的性能的原因是降低了方差。

Boosting提高若分类的性能的原因是降低了偏差。

首先，Bagging是Bootstrap Aggregating的简称，意思就是再抽样，然后在每个样本上训练出来的模型取平均。

..............也就是说方差减小到原来的n分之一，即1/n.

再看boosting,大家应该记得Boosting的训练过程。在训练好一个弱分类器后，我们需要计算弱分类器的错误或者残差，最为下一个弱分类器的输入。这个过程本身就是在不断地减小损失函数，来使得模型不断地逼近“靶心”，使得模型偏差不断降低。但是Boosting的过程并不会显著地降低方差。这是因为Boosting的训练过程使得各个弱分类器之间是强相关的，缺乏独立性，所以并不会对降低方差有作用。

关于泛化误差，方差，偏差和模型复杂度的关系图如下所示。不难看出方差和偏差是相辅相成，矛盾又统一的，二者并不是完全独立存在的。

对于给定的学习任务和训练数据集，我们需要对模型的复杂度做合理的假设。

如果模型复杂度过低，虽然方差很小，但是偏差会很高；

如果模型复杂度过高，虽然偏差降低了，但是方差会很高；

所以，需要综合考虑方差和偏差选择合适复杂度的模型来进行训练。

GBDT的基本原理是什么？

梯度提升决策树（Gradient Boosting Decision Tree, GBDT）是Boosting算法中非常流行的模型，也是近来在机器学习竞赛，商业应用中表现非常优秀的模型。GBDT非常好地体现了“从错误中学习的理念”，基于决策树预测的残差进行迭代的学习。GBDT几乎是算法工程师的必备技能，也是机器学习面试中的必考内容。

Bagging和Boosting是两大集成学习框架。相比于Bagging中各个弱分类器可以独立地进行训练，Boosting中的弱分类器需要依次生成。在每一轮迭代中，基于已经生成的弱分类器集合（即当前模型）的预测结果，新的弱分类器器会重点关注那些还没有被正确预测的样本。

Gradient Boosting是Boosting中的一大类算法，其基本思想是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中。算法1描述了Gradient Boosting算法的基本流程，在每一轮迭代中，首先计算当前模型在所有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合计算并计算出该弱分类器的权重，最终实现模型的更新。Gradient Boosting算法的伪代码如图12.6所示。

参考：/zhangbaoanhadoop/article/details/79904916

注意：这个参考资料很好

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力较强的算法。GBDT中的树是回归树（不是分类树），GBDT用来做回归预测，调整后也可以用于分类。

GBDT的思想使其具有天然优势可以发现多种有区分性的特征以及特征组合。业界中，Facebook使用其来自动发现有效的特征、特征组合，来作为LR模型中的特征，以提高 CTR预估（Click-Through Rate Prediction）的准确性（详见参考文献5、6）；GBDT在淘宝的搜索及预测业务上也发挥了重要作用（详见参考文献7）。

示例：

举个例子，参考自一篇博客（参考文献 4），该博客举出的例子较直观地展现出多棵决策树线性求和过程以及残差的意义。

  训练一个提升树模型来预测年龄：

  训练集是4个人，A，B，C，D年龄分别是14，16，24，26。样本中有购物金额、上网时长、经常到百度知道提问等特征。提升树的过程如下：

该例子很直观的能看到，预测值等于所有树值得累加，如A的预测值 = 树1左节点 值 15 + 树2左节点 -1 = 14。

因此，给定当前模型 fm-1(x)，只需要简单的拟合当前模型的残差。现将回归问题的提升树算法叙述如下：

由于GBDT是利用残差训练的，在预测的过程中，我们也需要把所有树的预测值加起来，得到最终的预测结果。

GBDT使用梯度提升（Gradient Boosting）作为训练方法，而在逻辑回归或者神经网络的训练过程中往往采用梯度下降（Gradient Descent）作为训练方法，二者之间有什么联系和区别吗？

梯度提升和梯度下降的区别和联系是什么？

表12.1是梯度提升算法和梯度下降算法的对比情况。可以发现，两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新，只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型类型。

GBDT的优点和局限性有哪些？

第一，预测阶段的计算速度快，树与树之间可以并行化计算。

第二，在分布稠密的数据集上，泛化能力和表达能力都很好，这使得GBDT在kaggle的众多竞赛中，经常名列榜首。

第三，采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系，并且也不需要对数据进行特殊的预处理如归一化等。

局限性：

第一，GBDT在高维稀疏的数据集上表现不如支持向量机或者神经网络。

第二，GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显。

第三，训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。

XGBoost和GBDT的联系和区别有哪些？

原始的GBDT算法基于经验损失函数的负梯度来构造新的决策树，只是在决策树构建完成后再进行剪枝。而XGBoost在决策树构建阶段就加入了正则项，即，

.........

XGBoost 是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进，被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并取得了不错的成绩。

ID3算法采用信息增益，C4.5算法为了克服信息增益中容易偏向取值较多的特征而采用信息增益比，CART算法使用基尼指数和平方误差，XGBoost也有特定的准则选取最优分裂。通过将预测值带入到损失函数中可求得损失函数的最小值。容易计算出分裂前后损失函数的差值。

XGBoost采用最大化这个差值作为准则来进行决策树的构建，通过遍历所有特征的所有取值，寻找使得损失函数前后相差最大时对应的分裂方式。此外，由于损失函数前后存在一定为正的限制，此时gamma参数起到了一定预剪枝的效果。

.........................

除了算法上与传统的GBDT有一些不同之外，XGBoost还在工程实践上做了大量的优化。总的来说，两者的区别和联系可以总结成一下几个方面。

第一，GBDT是机器学习算法，XGBoost是该算法的工程实现。

第二，在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。

第三，GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。

第四，传统的GBDT使用CART作为基分类器，XGBoost支持多种类型的基分类器，例如线性分离器。

第五，传统的GBDT在每轮迭代式使用全部的数据，XGBoost则采用了与随机森林类似的策略，支持对数据进行采样。

第六，传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。