面对一个机器学习的问题，通常有两种策略，一种是研发人员尝试各种模型，选择其中表现最好的模型做重点调参优化。这种策略类似于奥运比赛，通过强强竞争来选拔最优的运动员，并逐步提高成绩。另一种重要策略是集各家之长，如同贤明的君主广泛听取众多谋臣的建议，然后综合考虑，得到最终决策。后一种策略的核心，是将多个分类器的结果统一成一个最终的决策。使用这类策略的机器学习方法统称为集成学习。其中的每个单独的分类器称为基分类器。
一句话总结:“三个臭皮匠，顶一个诸葛亮”。
集成学习一般分为两大类，分别是boosting和bagging.
- boosting：训练基分类器时采用串行的方式。各个分类器之间有依赖。它的基本思想是：基分类器层层叠加，每一层在训练时，对前一层基分类器分错的样本给予更高的权值。测试时，根据各层分类器的结果的加权得到最终结果。boosting方法的主要思想是：迭代式学习。这类似于人类的学习，第一遍学习的时候，我们会记住一部分知识，但往往会犯错。对这些错误知识，我们的印象会更深。第二遍学习时，我们会针对错误加强学习，以减少类似错误的发生。以此迭代多次，最后我们会得到较低的错误率。
- bagging:该方法在训练的过程中，各基分类器之间无强依赖，可以进行并行训练。其中最著名的算法之一是基于决策树基分类器的随机森林(Random forest)。为了让基分类器之间互相独立，将训练集分为若干子集(当训练样本数量较少时，子集之间可能有重叠)。
基分类器
基分类器的选择是集成学习主要步骤中的第一步，也是非常重要的一步。常用的基分类器是什么？
最常用的基分类器是决策树，主要有以下3个方面的原因： - 1.决策树可以较为方便地将样本的权重整合到训练过程中，而不需要使用过采样地方法来调整样本的权重
- 2.决策树的表达能力和泛化能力，可以通过调节树的层数来做折中。
3.数据样本的扰动对于决策树的影响较大，因此不同子样本集合成的决策树基分类器随机性较大。这样的”不稳定学习器”更适合作为基分类器。此外在决策树节点分裂的时候，随机地选择一个特征子集，从中找出最优分裂属性，很好地引入随机性。
除了决策树外，神经网络模型也适合作为基分类器，主要由于神经网络也比较”不稳定”，而且还可以通过调整神经元数量、连接方式、网络层数、初始权值等方式引入随机性。随机森林属于Bagging类的集成学习。Bagging的主要好处是集成后的分类器的方差比基分类器的方差小。Bagging所采用的基分类器，最好是本身对样本分布较为敏感的(即所谓不稳定的分类器)，这样Bagging才能有用武之地。线性分类器或者K近邻都是较为稳定的分类器，本身方差就不大，所以以它们为基分类器使用Bagging并不能在原有基分类器的基础上获得更好的表现，甚至可能因为Bagging的采样，而导致它们在训练中更难收敛，从而增大了集成分类器的偏差。
如何从减少方差和偏差的角度解释Boosting和Bagging的原理
简单回答就是:Bagging能够提高弱分类器性能的原因是降低了方差，Boosting能够提升弱分类器性能的原因是降低了偏差。
Bagging要对样本集进行再抽样，然后再每个小样本集上训练出来的模型进行平均。假设有n个随机变量，方差记为$\sigma^2$，两两变量之间的相关性为$\rho$,则n个随机变量的均值$\frac{\sum X_i}{n}$的方差为$\rho×\sigma^2+(1-\rho)× \sigma^2/n $.在随机变量完全独立的情况下，n个随机变量的方差为$\sigma^2/n$,也就是说方差减小到了原来的$\frac{1}{n}$
Boosting 的训练过程，在训练好一个弱分类器后，我们需要计算弱分类器的错误或残差，作为下一个分类器的输入。这个过程本身就是在不断减小损失函数，来使模型不断逼近”靶心”,使得模型的偏差不断降低。但Boosting的过程并不会显著降低方差。这是因为Boosting的训练过程使得各弱分类器之间是强相关的，缺乏独立性，所以并不会对降低方差有作用。
GBDT(Gradient Boosting Decision Tree)
GBDT是Boosting算法中非常流形的模型，也是近来在机器学习竞赛、商业应用中表现都非常优秀的模型。GBDT非常好地体现了”从错误中学习”的理念，基于决策树预测的残差进行迭代的学习。
GBDT
1:以一个常数值初始化模型
$F_0(x)=arg min_{\rho}\sum_{i=1}^NL(y_i,\rho)$
2:For m=1 to M do:
3: $\hat{y_i}=-[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}]_ {F(x)=F_{m-1}(x)}$, i=1,…,M
4: $a_m=argmin_{a,β}\sum_{i=1}^N[\hat{y_i}-βh(x_i;a)]^2$
5:$\rho_m=argmin_{\rho}\sum_{i=1}^NL(y_i,F_{m-1}(x_i)+\rho h(x_i;a_m))$
6: $F_m(x)=F_{m-1}(x)+\rho_mh(x;a_m)$
7:end format
8:end Algorithm
通俗来讲就是，采用分层学习的方法，通过m个步骤来得到最终模型F,其中第m步学习到一个较弱的模型$F_m$，在第m+1步时，不直接优化$F_m$，而是学习一个基本模型h(x),使得其拟合残差项y-$F_m$,这样就会使m+1步的模型预测值$F_{m+1}=F_m+h(x)$更接近于真实值y,因而目标变成了如何找到$h(x)=F_{m+1}-F_m$,最终就是要找到某类函数空间中的一组h(x)使得$F(x)=\sum_{i=1}^Mh_i(x)+const$
具体算法将负梯度作为残差值来学习基本模型$h_m(x)$
采用决策树作为弱分类器的Gradient Boosting算法被称为GBDT,有时又被称未MART(Multiple Additive Regression Tree).GBDT中使用的决策树通常为CART.
由于GBDT是利用残差训练的，在预测过程中，我们也需要把所有树的预测值加起来，得到最终的预测结果。
GBDT使用梯度提升(Gradient Boosting)作为训练方法，而在逻辑回归或者神经网络的训练过程中往往采用梯度下降(Gradient Descent)作为训练方法，二者之间有什么联系和区别
梯度提升和梯度下降的区别和联系是什么？
注意区分这里的梯度提升是gradient boosting 不是gradient ascend
在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。
梯度提升|函数空间F|$F=F_{t-1}-\rho_t▽_ FL|_ {F=F_{i-1}}$|$L=\sum_il(y_i,F(x_i))$
梯度下降|参数空间W|$w_t=w_{t-1}-\rho_t▽_ wL|_ {w=w_{t-1}}$|$L=\sum_il(y_i,f_w(w_i))$
GBDT的优点和局限性有哪些？
- 优点：
(1)预测阶段 的计算速度快，树与树之间可并行化计算。
(2)在 分布稠密的数据集上，泛化能力和表达能力都很好，使得GBDT在Kaggle的众多竞赛中，经常名列榜首
(3)采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系，并且也不需要对数据进行特殊的预处理如归一化等。 - 局限性:
(1)GBDT在 高维稀疏 的数据集上，表现不如支持向量机或者神经网络。
(2)GBDT在 处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显。
(3)训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。
XGBoost
被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并取得了不错的成绩。
XGBoost 与GBDT的联系和区别有哪些？
原始的GBDT算法基于经验损失函数的负梯度来构造新的决策树，只是在决策树构建完成后再进行剪枝。而XGBoost在决策树构建阶段就加入了正则项，则
其中$F_{t-1}(x_i)$表示现有的t-1棵树最优解。关于树结构的正则项定义为:
其中T为叶子节点个数，$w_j$表示第j个叶子节点的预测值。对该损失函数在$F_{t-1}$处进行二阶泰勒展开可以推导出
其中T为决策树$f_t$中叶子节点的个数，$G_j=\sum_{i∈I_j}▽_ {F_{t-1}}l(y_i,F_{t-1}(x_i)),H_j=\sum_{j∈I_j}▽_ {F_{t-1}}^2l(y_i,F_{t-1}(x_i))$,$I_j$表示所有属于叶子节点j的样本的索引的结合。
假设决策树的结构已知，通过令损失函数相对于$w_j$的导数为0可以求出在最小化损失函数的情况下各个叶子节点上的预测值
然而从所有的树结构中寻找最优的树结构是一个NP-hard问题，因此在实际中往往采用贪心法来构建出一个次优的树结构，基本思想是从根节点开始，每次对一个叶子节点进行分裂，针对每一种可能的分裂，根据特定的准则选取最优的分裂。不同的决策树算法采用不同的准则，如ID3算法采用信息增益，C4.5算法为了克服信息增益中容易偏向取值较多的特征而采用信息增益比，CART算法使用基尼指数和平方误差，XGBoost也有特定的准则来选取最优分裂。
通过将预测值代入到损失函数中可求得损失函数得最小值：
容易计算出分裂前后损失函数的差值为:
XGBoost采用最大化这个差值作为准则来进行决策树的构建，通过遍历所有特征的所有取值，寻找使得损失函数前后相差最大时对应的分裂方式。此外由于损失函数前后存在差值一定为正的限制，此时γ起到了一定的预剪枝效果。
除恶了算法上与传统的GBDT有一些不同外，XGBoost还在工程实现上做了大量的优化。总得来说，两者之间的区别和联系可以总结成以下几个方面:
(1)GBDT是机器学习算法，XGBoost是该算法的 工程实现
(2)在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
(3)GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数使用二阶泰勒展开，可以同时使用一阶和二阶导数
(4)传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器
(5)传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采用。
(6)传统的GBDT没有设计对缺失值的进行处理，XGBoost能够自动学习出缺失值的处理策略