一、提升算法概论

Boosting(提升)是一族可将弱学习器提升为强学习器的算法。提升算法基于这样一种思想：对于一个复杂的任务，将多个专家的判断总和得出的结果要比任何一个专家单独的判断好。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器表现对训练样本分布进行调整，是的先前基学习器做错的样本在后续收到更多关注（赋予做错的样本更大的权值），然后基于调整后的样本分布来训练下一个基学习器，一直反复进行，直到达到指定值。boosting方法通过分步迭代（stage-wise）的方式来构建模型，在迭代的每一步构建的弱学习器都是为了弥补已有模型的不足。（个体学习器之间存在强依赖关系。）

对样本加权的过程如下：

上图中被放大的点是被加权的样本，样本加权后，在下一次的学习中就会收到更多的关注。

也就是说提升算法对分类错误的样本更为关注，通过改变错误样本所占的权值来改变分类边界，从而一步步提升算法的准确度。

 

二、AdaBoost算法

AdaBoost算法是提升算法中最具代表性的。其中AdaBoost是Adaptive Boosting的缩写， 正如上面所说的，在AdaBoost算法中会提高前一轮分类器分类错误的样本的权值，而降低那些被分类正确样本的权值。对于弱分类器的组合，AdaBoost算法采取加权多数表决的方法。具体的说就是加大分类误差率小的弱分类器的权值，使其在表决中起到较大的作用；减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

主要解决的问题：目前对AdaBoost算法的研究以及应用大多集中于分类问题，同时近年也出现了一些在回归问题上的应用。就其应用adaBoost系列主要解决了: 两类问题、多类单标签问题、多类多标签问题、大类单标签问题，回归问题。

 

1.    为数据集里的每个样本赋予相同的权重（一般情况），然后开始依据一定的分类标准来对该数据集分类，从而得到第一个Classifier[1]（弱分类器）。同时由此可得此次分类中被分错的样本，提高他们的权重，用于下一个Classifier[2]的训练。

2.    依据上一次Classifier训练更新样本权重后的样本集，来训练此次Classifier[2]。其中可以依据样本权重来影响此次训练的错误率来使此次Classifier[2]足够重视之前错分的样本。这样我们可以得到对于上次分错的样本有较好分类能力的Classifier[2]，然后提高本次分类中被分错的样本的权重。重复此过程，得到若干的弱分类器Classifier[i]。

3.    为1、2步中得到的Classifier[i]确定在最终的强分类器中的权重（此权重的确定也可以在1、2步中确定）。Strong_Classifier = ∑（ weight[i] *Classifier[i]）（弱分类器的线性组合），计算Strong_Classifier的错误率，然后综合考虑程序迭代次数来判断是否继续重复1-3步迭代训练。

 

对于这个算法需要介绍的是： 
1. 算法开始前，需要将每个样本的权重初始化为1/m,这样一开始每个样本都是等概率的分布，每个分类器都会公正对待。 
2. 开始迭代后，需要计算每个弱分类器的分类错误的误差，误差等于各个分错样本的权重和，这里就体现了样本权重的作用。如果一个分类器正确分类了一个权重大的样本，那么这个分类器的误差就会小，否则就会大。这样就对分类错误的样本更大的关注。 
3. 获取最优分类器后，需要计算这个分类器的权重，然后再更新各个样本的权重，然后再归一化。 
4. 算法迭代的次数一般不超过弱分类器的个数，如果弱分类器的个数非常之多，那么可以权衡自己性价比来折中选择。 
5. 迭代完成后，最后的分类器是由迭代过程中选择的弱分类器线性加权得到的。

弱分类器（单层决策树）

Adaboost一般使用单层决策树作为其弱分类器。单层决策树是决策树的最简化版本，只有一个决策点，也就是说，如果训练数据有多维特征，单层决策树也只能选择其中一维特征来做决策，并且还有一个关键点，决策的阈值也需要考虑。

关于单层决策树的决策点，来看几个例子。比如特征只有一个维度时，可以以小于7的分为一类，标记为+1，大于（等于）7的分为另一类，标记为-1。当然也可以以13作为决策点，决策方向是大于13的分为+1类，小于（等于）13的分为-1类。在单层决策树中，一共只有一个决策点，所以下图的两个决策点不能同时选取。

同样的道理，当特征有两个维度时，可以以纵坐标7作为决策点，决策方向是小于7分为+1类，大于（等于）7分类-1类。当然还可以以横坐标13作为决策点，决策方向是大于13的分为+1类，小于13的分为-1类。在单层决策树中，一共只有一个决策点，所以下图的两个决策点不能同时选取。

扩展到三维、四维、N维都是一样，在单层决策树中，一共只有一个决策点，所以只能在其中一个维度中选择一个合适的决策阈值作为决策点。

关于Adaboost的两种权重

Adaboost算法中有两种权重，一种是数据的权重，另一种是弱分类器的权重。其中，数据的权重主要用于弱分类器寻找其分类误差最小的决策点，找到之后用这个最小误差计算出该弱分类器的权重（发言权），分类器权重越大说明该弱分类器在最终决策时拥有更大的发言权。

Adaboost数据权重与弱分类器

刚刚已经介绍了单层决策树的原理，这里有一个问题，如果训练数据保持不变，那么单层决策树找到的最佳决策点每一次必然都是一样的，为什么呢？因为单层决策树是把所有可能的决策点都找了一遍然后选择了最好的，如果训练数据不变，那么每次找到的最好的点当然都是同一个点了。

所以，这里Adaboost数据权重就派上用场了，所谓“数据的权重主要用于弱分类器寻找其分类误差最小的点”，其实，在单层决策树计算误差时，Adaboost要求其乘上权重，即计算带权重的误差。

举个例子，在以前没有权重时（其实是平局权重时），一共10个点时，对应每个点的权重都是0.1，分错1个，错误率就加0.1；分错3个，错误率就是0.3。现在，每个点的权重不一样了，还是10个点，权重依次是[0.01,0.01,0.01,0.01,0.01,0.01, 0.01,0.01,0.01,0.91]，如果分错了第1一个点，那么错误率是0.01，如果分错了第3个点，那么错误率是0.01，要是分错了最后一个点，那么错误率就是0.91。这样，在选择决策点的时候自然是要尽量把权重大的点（本例中是最后一个点）分对才能降低误差率。由此可见，权重分布影响着单层决策树决策点的选择，权重大的点得到更多的关注，权重小的点得到更少的关注。

在Adaboost算法中，每训练完一个弱分类器都就会调整权重，上一轮训练中被误分类的点的权重会增加，在本轮训练中，由于权重影响，本轮的弱分类器将更有可能把上一轮的误分类点分对，如果还是没有分对，那么分错的点的权重将继续增加，下一个弱分类器将更加关注这个点，尽量将其分对。

这样，达到“你分不对的我来分”，下一个分类器主要关注上一个分类器没分对的点，每个分类器都各有侧重。

Adaboost分类器的权重

由于Adaboost中若干个分类器的关系是第N个分类器更可能分对第N-1个分类器没分对的数据，而不能保证以前分对的数据也能同时分对。所以在Adaboost中，每个弱分类器都有各自最关注的点，每个弱分类器都只关注整个数据集的中一部分数据，所以它们必然是共同组合在一起才能发挥出作用。所以最终投票表决时，需要根据弱分类器的权重来进行加权投票，权重大小是根据弱分类器的分类错误率计算得出的，总的规律就是弱分类器错误率越低，其权重就越高。

 

如图所示为Adaboost分类器的整体结构。从右到左，可见最终的求和与符号函数，再看到左边求和之前，图中的虚线表示不同轮次的迭代效果，第1次迭代时，只有第1行的结构，第2次迭代时，包括第1行与第2行的结构，每次迭代增加一行结构，图下方的“云”表示不断迭代结构的省略。

第i轮迭代要做这么几件事： 
1. 新增弱分类器WeakClassifier(i)与弱分类器权重alpha(i) 
2. 通过数据集data与数据权重W(i)训练弱分类器WeakClassifier(i)，并得出其分类错误率，以此计算出其弱分类器权重alpha(i) 
3. 通过加权投票表决的方法，让所有弱分类器进行加权投票表决的方法得到最终预测输出，计算最终分类错误率，如果最终错误率低于设定阈值（比如5%），那么迭代结束；如果最终错误率高于设定阈值，那么更新数据权重得到W(i+1)

 

对于boosting算法，存在两个问题： 　 
1. 如何调整训练集，使得在训练集上训练的弱分类器得以进行； 　　 
2. 如何将训练得到的各个弱分类器联合起来形成强分类器。 

针对以上两个问题，AdaBoost算法进行了调整： 　 
1. 使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上； 　　 
2. 将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。　　

 

Adaboost实例解析<1>

例１.　Adaboost的一个例子 
下面，给定下列训练样本，请用AdaBoost算法学习一个强分类器。 
 
求解过程： 
　　初始化训练数据的权值分布，令每个权值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, …, 10，然后分别对于m = 1,2,3, …等值进行迭代。 
　　拿到这10个数据的训练样本后，根据 X 和 Y 的对应关系，要把这10个数据分为两类，一类是“1”，一类是“-1”，根据数据的特点发现：“0 1 2”这3个数据对应的类是“1”，“3 4 5”这3个数据对应的类是“-1”，“6 7 8”这3个数据对应的类是“1”，9是比较孤独的，对应类“-1”。抛开孤独的9不讲，“0 1 2”、“3 4 5”、“6 7 8”这是3类不同的数据，分别对应的类是1、-1、1，直观上推测可知，可以找到对应的数据分界点，比如2.5、5.5、8.5 将那几类数据分成两类。当然，这只是主观臆测，下面实际计算下这个过程。 

迭代过程1 
(1) 对于m=1，在权值分布为D1（10个数据，每个数据的权值皆初始化为0.1）的训练数据上，经过计算可得：

• 阈值v取2.5时误差率为0.3（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.3），
• 阈值v取5.5时误差率最低为0.4（x < 5.5时取1，x > 5.5时取-1，则3 4 5 6 7 8皆分错，误差率0.6大于0.5，不可取。故令x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.4），
• 阈值v取8.5时误差率为0.3（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.3）。

所以无论阈值v取2.5，还是8.5，总得分错3个样本，故可任取其中任意一个如2.5，够成第一个基本分类器为： 

• 上面说阈值v取2.5时则6 7 8分错，所以误差率为0.3，更加详细的解释是：因为样本集中0 1 2对应的类（Y）是1，因它们本身都小于2.5，所以被G1(x)分在了相应的类“1”中，分对了。
• 3 4 5本身对应的类（Y）是-1，因它们本身都大于2.5，所以被G1(x)分在了相应的类“-1”中，分对了。
• 但6 7 8本身对应类（Y）是1，却因它们本身大于2.5而被G1(x)分在了类”-1”中，所以这3个样本被分错了。
• 9本身对应的类（Y）是-1，因它本身大于2.5，所以被G1(x)分在了相应的类“-1”中，分对了。

(2) 从而得到G1(x)在训练数据集上的误差率（被G1(x)误分类样本“6 7 8”的权值之和）e1=P(G1(xi)≠yi) = 3*0.1 = 0.3。然后根据误差率e1计算G1的系数： 

这个a1代表G1(x)在最终的分类函数中所占的权重为0.4236。 
(3) 接着更新训练数据的权值分布，用于下一轮迭代。 
 
　　值得一提的是，由权值更新的公式可知，每个样本的新权值是变大还是变小，取决于它是被分错还是被分正确。即如果某个样本被分错了，则yi * Gm(xi)为负，负负等正，结果使得整个式子变大（样本权值变大），否则变小。 
(４) 第一轮迭代后，最后得到各个数据新的权值分布： 
       D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)。 
      由此可以看出，因为样本中是数据“6 7 8”被G1(x)分错了，所以它们的权值由之前的0.1增大到0.1666，反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到0.0715。 
(5) 分类函数：f1(x)= a1*G1(x) = 0.4236G1(x)。

此时，得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点（即6 7 8）。从上述第一轮的整个迭代过程可以看出：被误分类样本的权值之和影响误差率，误差率影响基本分类器在最终分类器中所占的权重。

 
迭代过程2 
(1) 对于m=2，在权值分布为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的训练数据上，经过计算可得：

• 阈值v取2.5时误差率为0.1666*3（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.1666*3），
• 阈值v取5.5时误差率最低为0.0715*4（x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.0715*3 + 0.0715），
• 阈值v取8.5时误差率为0.0715*3（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.0715*3）。

所以，阈值v取8.5时误差率最低，故第二个基本分类器为： 

(2) 面对的还是下述样本： 
 
很明显，G2(x)把样本“3 4 5”分错了，根据D2可知它们的权值为0.0715, 0.0715, 0.0715，所以G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。 
计算G2的系数： 

(3) 更新训练数据的权值分布： 
D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。 
被分错的样本“3 4 5”的权值变大，其它被分对的样本的权值变小。 
(4) f2(x)=0.4236G1(x) + 0.6496G2(x) 
此时，得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点（即3 4 5）

迭代过程3 
(1) 对于m=3，在权值分布为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的训练数据上，经过计算可得：

• 阈值v取2.5时误差率为0.1060*3（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.1060*3），
• 阈值v取5.5时误差率最低为0.0455*4（x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.0455*3 + 0.0715），
• 阈值v取8.5时误差率为0.1667*3（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.1667*3）。

所以阈值v取5.5时误差率最低，故第三个基本分类器为： 

(2) 依然还是原样本： 
 
此时，被误分类的样本是：0 1 2 9，这4个样本所对应的权值皆为0.0455， 所以G3(x)在训练数据集上的误差率e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820。 
计算G3的系数： 

(3) 更新训练数据的权值分布： 
D4 = (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)。 
被分错的样本“0 1 2 9”的权值变大，其它被分对的样本的权值变小。 
(4) f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) 
此时，得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此，整个训练过程结束。 
 

训练结束 
G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ]， 
将上面计算得到的a1、a2、a3各值代入G(x)中，得到最终的分类器为： 
G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]

 

        毫无疑问这个模型的最大的一个优点是可以自动的组合弱分类器，这在实际应用中的便利之处十分明显。算法本身简单，高效，易于编写而且训练过程是没有参数需要调节的。 但是adaboost也是有缺点的，并不是所有问题都能搞定，从wiki上介绍的来看，adaboost对于噪音数据和异常数据是十分敏感的。

 

图示说明adaboost的实现过程<2>

图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。 
第一步： 

根据分类的正确率，得到一个新的样本分布D2­，一个子分类器h1。

其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本做了加权。 
也许你对上面的ɛ1，ɑ1怎么算的也不是很理解。下面我们算一下，算法最开始给了一个均匀分布 D 。所以h1 里的每个点的值是0.1。ok，当划分后，有三个点划分错了，根据算法误差表达式ε1=Pri∼Dt[ht(xi)≠yi]ε1=Pri∼Dt[ht(xi)≠yi]，得到误差为分错了的三个点的值之和，所以ɛ1=(0.1+0.1+0.1)=0.3，而ɑ1 根据表达式的可以算出来为0.42. 然后就根据算法把分错的点权值变大。如此迭代，最终完成Adaboost算法。 

第二步： 

根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2。 
第三步： 

得到一个子分类器h3

整合所有子分类器：

因此可以得到整合的结果，从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果，在例子中所有的。

       而a是关于误差的表达式，到这里就可以得到比较清晰的答案了，所有的一切都指向了误差。提高错误点的权值，当下一次分类器再次分错了这些点之后，会提高整体的错误率，这样就导致 a 变的很小，最终导致这个分类器在整个混合分类器的权值变低。也就是说，这个算法让优秀的分类器占整体的权值更高，而挫的分类器权值更低。这个就很符合常理了。

 

三、GBDT(Gradient Boosting Decision Tree) 梯度提升决策树算法

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力较强的算法。

GBDT是一种基于boosting集成学习（ensemble method）的算法，但和传统的Adaboost有很大不同。在Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。GBDT的训练过程如下： 

 

GBDT中的树是回归树（不是分类树），GBDT用来做回归预测，调整后也可以用于分类。

GBDT主要由三个概念组成：

Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (算法的一个重要演进分枝，目前大部分源码都按该版本实现）。搞定这三个概念后就能明白GBDT是如何工作的。

1. DT：回归树 Regression Decision Tree

提起决策树（DT, Decision Tree) 绝大部分人首先想到的就是C4.5分类决策树。但如果一开始就把GBDT中的树想成分类树，那就错了。千万不要以为GBDT是很多棵分类树。决策树分为两大类，回归树和分类树。前者用于预测实数值，如明天的温度、用户的年龄、网页的相关程度；后者用于分类标签值，如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面。这里要强调的是，前者的结果加减是有意义的，如10岁+5岁-3岁=12岁，后者则无意义，如男+男+女=到底是男是女？GBDT的核心在于累加所有树的结果作为最终结果，就像前面对年龄的累加（-3是加负3），而分类树的结果显然是没办法累加的，所以GBDT中的树都是回归树，不是分类树，这点对理解GBDT相当重要（尽管GBDT调整后也可用于分类但不代表GBDT的树是分类树）。

回归树总体流程类似于分类树，区别在于，回归树的每一个节点都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化平方误差。也就是被预测出错的人数越多，错的越离谱，平方误差就越大，通过最小化平方误差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

 

回归树算法如下图（截图来自《统计学习方法》5.5.1 CART生成）：

 

 

 

2. GB：梯度迭代 Gradient Boosting

梯度提升（Gradient boosting）是一种用于回归、分类和排序任务的机器学习技术，属于Boosting算法族的一部分。Boosting是一族可将弱学习器提升为强学习器的算法，属于集成学习（ensemble learning）的范畴。Boosting方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断要好。通俗地说，就是“三个臭皮匠顶个诸葛亮”的道理。梯度提升同其他boosting方法一样，通过集成（ensemble）多个弱学习器，通常是决策树，来构建最终的预测模型。

Boosting、bagging和stacking是集成学习的三种主要方法。

不同于bagging方法，boosting方法通过分步迭代（stage-wise）的方式来构建模型，在迭代的每一步构建的弱学习器都是为了弥补已有模型的不足。Boosting族算法的著名代表是AdaBoost。AdaBoost算法通过给已有模型预测错误的样本更高的权重，使得先前的学习器做错的训练样本在后续受到更多的关注的方式来弥补已有模型的不足。

虽然同属于Boosting族，但是梯度提升方法的优点比较多。

相比于AdaBoost，梯度提升方法的优点:

• 1、与AdaBoost算法不同，梯度提升方法在迭代的每一步构建一个能够沿着梯度最陡的方向降低损失（steepest-descent）的学习器来弥补已有模型的不足。
• 2、经典的AdaBoost算法只能处理采用指数损失函数的二分类学习任务，而梯度提升方法通过设置不同的可微损失函数可以处理各类学习任务（多分类、回归、Ranking等），应用范围大大扩展。
• 3、AdaBoost算法对异常点（outlier）比较敏感，而梯度提升算法通过引入bagging思想、加入正则项等方法能够有效地抵御训练数据中的噪音，具有更好的健壮性。

     提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树，残差的意义如公式：残差 = 真实值 - 预测值 。提升树即是整个迭代过程生成的回归树的累加。

GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。

 

3. Gradient Boosting Decision Tree：梯度提升决策树

为什么梯度提升方法倾向于选择决策树（通常是CART树）作为基学习器呢？

这与决策树算法自身的优点有很大的关系：

1. 决策树可以认为是if-then规则的集合，易于理解，可解释性强，预测速度快；
2. 决策树算法相比于其他的算法需要更少的特征工程，比如可以不用做特征标准化，可以很好的处理字段缺失的数据，也可以不用关心特征间是否相互依赖等
3. 决策树能够自动组合多个特征，它可以毫无压力地处理特征间的交互关系并且是非参数化的，因此你不必担心异常值或者数据是否线性可分。举个例子，西瓜a（乌黑色、纹路清晰）可能是好瓜，西瓜b（青绿色，纹路清晰）的也可能是好瓜。决策树一样可以处理。

决策树有优点，自然也有缺点，不过，可以通过梯度提升方法解决这个缺点。单独使用决策树算法时，有容易过拟合缺点。

怎么解决呢？

• 通过各种方法，抑制决策树的复杂性，降低单棵决策树的拟合能力
• 通过梯度提升的方法集成多个决策树，则预测效果上来的同时，也能够很好的解决过拟合的问题。
  （这一点具有bagging的思想，降低单个学习器的拟合能力，提高方法的泛化能力。）

由此可见，梯度提升方法和决策树学习算法可以互相取长补短，是一对完美的搭档。

怎么降低单棵决策树的复杂度？

抑制单颗决策树的复杂度的方法有很多：

• 限制树的最大深度、限制叶子节点的最少样本数量、限制节点分裂时的最少样本数量
• 吸收bagging的思想对训练样本采样（subsample），在学习单颗决策树时只使用一部分训练样本
• 借鉴随机森林的思路在学习单颗决策树时只采样一部分特征
• 在目标函数中添加正则项惩罚复杂的树结构等。

现在主流的GBDT算法实现中这些方法基本上都有实现，因此GBDT算法的超参数还是比较多的，应用过程中需要精心调参，并用交叉验证的方法选择最佳参数。

提升树利用加法模型和前向分步算法实现学习的优化过程。当损失函数时平方损失和指数损失函数时，每一步的优化很简单，如平方损失函数学习残差回归树。

 

前向分布算法(Forward stagewise additive modeling)

提升方法其实是一个比adaboost概念更大的算法，因为adaboost可以表示为boosting的前向分布算法(Forward stagewise additive modeling)的一个特例，boosting最终可以表示为：

其中的w是权重，Φ是弱分类器(回归器)的集合,其实就是一个加法模型(即基函数的线性组合)

前向分布算法实际上是一个贪心的算法，也就是在每一步求解弱分类器Φ(m)和其参数w(m)的时候不去修改之前已经求好的分类器和参数：

前向分布算法 来自《统计学习方法》

为了表示方便，我们以后用β代替w进行描述了，图中的b是之前说的Φ弱分类器

OK，这也就是提升方法（之前向分布算法）的大致结构了，可以看到其中存在变数的部分其实就是极小化损失函数 这关键的一步了，如何选择损失函数决定了算法的最终效果(名字)……这一步你可以看出算法的“趋势”，以后再单独把“趋势”拿出来说吧，因为我感觉理解算法的关键之一就是理解算法公式的“趋势”

各种提升方法

不同的损失函数和极小化损失函数方法决定了boosting的最终效果，我们现在来说几个常见的boosting：

广义上来讲，所谓的Gradient Boosting 其实就是在更新的时候选择梯度下降的方向来保证最后的结果最好，一些书上讲的“残差” 方法其实就是L2Boosting吧，因为它所定义的残差其实就是L2Boosting的Derivative，接下来我们着重讲一下弱回归器是决策树的情况，也就是GBDT。

加法模型（additive model）

GBDT算法可以看成是由K棵树组成的加法模型：

其中F为所有树组成的函数空间，以回归任务为例，回归树可以看作为一个把特征向量映射为某个score的函数。该模型的参数为：Θ = {f1, f2, ... , fk} 。于一般的机器学习算法不同的是，加法模型不是学习d维空间中的权重，而是直接学习函数（决策树）集合。上述加法模型的目标函数定义为：

其中Ω表示决策树的复杂度，那么该如何定义树的复杂度呢？比如，可以考虑树的节点数量、树的深度或者叶子节点所对应的分数的L2范数等等。

如何来学习加法模型呢？

解这一优化问题，可以用前向分布算法（forward stagewise algorithm）。因为学习的是加法模型，如果能够从前往后，每一步只学习一个基函数及其系数（结构），逐步逼近优化目标函数，那么就可以简化复杂度。这一学习过程称之为Boosting。具体地，我们从一个常量预测开始，每次学习一个新的函数，过程如下：

举个例子，参考自一篇博客, 该博客举出的例子较直观地展现出多棵决策树线性求和过程以及残差的意义。
还是年龄预测，简单起见训练集只有4个人，A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：

 

现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图2所示结果：

在第一棵树分枝和图1一样，由于A,B年龄较为相近，C,D年龄较为相近，他们被分为两拨，每拨用平均年龄作为预测值。此时计算残差（残差的意思就是： A的预测值 + A的残差 = A的实际值），所以A的残差就是15-16=-1（注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值）。进而得到A,B,C,D的残差分别为-1,1，-1,1。然后我们拿残差替代A,B,C,D的原值，到第二棵树去学习，如果我们的预测值和它们的残差相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的，第二棵树只有两个值1和-1，直接分成两个节点。此时所有人的残差都是0，即每个人都得到了真实的预测值。

换句话说，现在A,B,C,D的预测值都和真实年龄一致了。Perfect!：
A: 14岁高一学生，购物较少，经常问学长问题；预测年龄A = 15 – 1 = 14
B: 16岁高三学生；购物较少，经常被学弟问问题；预测年龄B = 15 + 1 = 16
C: 24岁应届毕业生；购物较多，经常问师兄问题；预测年龄C = 25 – 1 = 24
D: 26岁工作两年员工；购物较多，经常被师弟问问题；预测年龄D = 25 + 1 = 26

那么哪里体现了Gradient呢？其实回到第一棵树结束时想一想，无论此时的cost function是什么，是均方差还是均差，只要它以误差作为衡量标准，残差向量(-1, 1, -1, 1)都是它的全局最优方向，这就是Gradient。

讲到这里我们已经把GBDT最核心的概念、运算过程讲完了！没错就是这么简单。

该例子很直观的能看到，预测值等于所有树值得累加，如A的预测值 = 树1左节点 值 15 + 树2左节点 -1 = 14。
因此，给定当前模型 fm-1(x)，只需要简单的拟合当前模型的残差。现将回归问题的提升树算法叙述如下：

1）既然图1和图2 最终效果相同，为何还需要GBDT呢？

答案是过拟合。过拟合是指为了让训练集精度更高，学到了很多”仅在训练集上成立的规律“，导致换一个数据集当前规律就不适用了。其实只要允许一棵树的叶子节点足够多，训练集总是能训练到100%准确率的（大不了最后一个叶子上只有一个instance)。在训练精度和实际精度（或测试精度）之间，后者才是我们想要真正得到的。
我们发现图1为了达到100%精度使用了3个feature（上网时长、时段、网购金额），其中分枝“上网时长>1.1h” 很显然已经过拟合了，这个数据集上A,B也许恰好A每天上网1.09h, B上网1.05小时，但用上网时间是不是>1.1小时来判断所有人的年龄很显然是有悖常识的；
相对来说图2的boosting虽然用了两棵树 ，但其实只用了2个feature就搞定了，后一个feature是问答比例，显然图2的依据更靠谱。（当然，这里是LZ故意做的数据，所以才能靠谱得如此狗血。实际中靠谱不靠谱总是相对的） Boosting的最大好处在于，每一步的残差计算其实变相地增大了分错instance的权重，而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。就像我们做互联网，总是先解决60%用户的需求凑合着，再解决35%用户的需求，最后才关注那5%人的需求，这样就能逐渐把产品做好，因为不同类型用户需求可能完全不同，需要分别独立分析。如果反过来做，或者刚上来就一定要做到尽善尽美，往往最终会竹篮打水一场空。

4. Shrinkage

Shrinkage（缩减）的思想认为，每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。用方程来看更清晰，即
没用Shrinkage时：（yi表示第i棵树上y的预测值， y(1~i)表示前i棵树y的综合预测值）
y(i+1) = 残差(y1~yi)， 其中： 残差(y1~yi) = y真实值 - y(1 ~ i)
y(1 ~ i) = SUM(y1, ..., yi)
Shrinkage不改变第一个方程，只把第二个方程改为：
y(1 ~ i) = y(1 ~ i-1) + step * yi

即Shrinkage仍然以残差作为学习目标，但对于残差学习出来的结果，只累加一小部分（step残差）逐步逼近目标，step一般都比较小，如0.01~0.001（注意该step非gradient的step），导致各个树的残差是渐变的而不是陡变的。直觉上这也很好理解，不像直接用残差一步修复误差，而是只修复一点点，其实就是把大步切成了很多小步。本质上，Shrinkage为每棵树设置了一个weight，累加时要乘以这个weight，但和Gradient并没有关系*。 这个weight就是step。就像Adaboost一样，Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。

GBDT的适用范围

该版本GBDT几乎可用于所有回归问题（线性/非线性），相对logistic regression仅能用于线性回归，GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。

 

四、XGBoost算法

XGBoost ：eXtreme Gradient Boosting
项目地址：https://github.com/dmlc/xgboost

Gradient Boosting算法：xgboost，在计算速度和准确率上，较GBDT有明显的提升，xgboost 的全称是eXtreme Gradient Boosting，它是Gradient Boosting Machine的一个c++实现，作者为正在华盛顿大学研究机器学习的大牛陈天奇 (Tianqi Chen http://homes.cs.washington.edu/~tqchen/ )最初开发的实现可扩展，便携，分布式 gradient boosting (GBDT, GBRT or GBM) 算法的一个库，可以下载安装并应用于 C++，Python，R，Julia，Java，Scala，Hadoop，现在有很多协作者共同开发维护。

XGBoost最大的特点在于，它能够自动利用CPU的多线程进行并行，同时在算法上加以改进提高了精度。

XGBoost 所应用的算法就是 gradient boosting decision tree，既可以用于分类也可以用于回归问题中。

Gradient boosting 就是通过加入新的弱学习器，来努力纠正前面所有弱学习器的残差，最终这样多个学习器相加在一起用来进行最终预测，准确率就会比单独的一个要高。之所以称为 Gradient，是因为在添加新模型时使用了梯度下降算法来最小化的损失。

为什么要用 XGBoost？

前面已经知道，XGBoost 就是对 gradient boosting decision tree 的实现，但是一般来说，gradient boosting 的实现是比较慢的，因为每次都要先构造出一个树并添加到整个模型序列中。

而 XGBoost 的特点就是计算速度快，模型表现好，这两点也正是这个项目的目标。

表现快是因为它具有这样的设计：

• Parallelization：
  训练时可以用所有的 CPU 内核来并行化建树。
• Distributed Computing ：
  用分布式计算来训练非常大的模型。
• Out-of-Core Computing：
  对于非常大的数据集还可以进行 Out-of-Core Computing。
• Cache Optimization of data structures and algorithms：
  更好地利用硬件。

下图就是 XGBoost 与其它 gradient boosting 和 bagged decision trees 实现的效果比较，可以看出它比 R, Python，Spark，H2O 中的基准配置要更快。

另外一个优点就是在预测问题中模型表现非常好，下面是几个 kaggle winner 的赛后采访链接，可以看出 XGBoost 的在实战中的效果。

• Vlad Sandulescu, Mihai Chiru, 1st place of the KDD Cup 2016 competition. Link to the arxiv paper.
• Marios Michailidis, Mathias Müller and HJ van Veen, 1st place of the Dato Truely Native? competition. Link to the Kaggle interview.
• Vlad Mironov, Alexander Guschin, 1st place of the CERN LHCb experiment Flavour of Physics competition. Link to the Kaggle interview.

 

 

XGBoost对GBDT的改进

Xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）, 传统GBDT以CART作为基分类器，xgboost支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）

1 . 避免过拟合

目标函数之外加上了正则化项整体求最优解，用以权衡目标函数的下降和模型的复杂程度，避免过拟合。基学习为CART时，正则化项与树的叶子节点的数量T和叶子节点的值有关。

在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance trade-off角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

 

2 . 二阶的泰勒展开，精度更高

不同于传统的GBDT只利用了一阶的导数信息的方式，XGBoost对损失函数做了二阶的泰勒展开，精度更高。

第t次的损失函数：

对上式做二阶泰勒展开( g为一阶导数，h为二阶导数)：

3 . 树节点分裂优化

选择候选分割点针对GBDT进行了多个优化。正常的树节点分裂时公式如下：

对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。XGBoost树节点分裂时，虽然也是通过计算分裂后的某种值减去分裂前的某种值，从而得到增益。但是相比GBDT，它做了如下改进：

• 通过添加阈值gamma进行了剪枝来限制树的生成
• 通过添加系数lambda对叶子节点的值做了平滑，防止过拟合。
• 在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，XGBoost实现了一种近似的算法，即：根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
  • 特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。

xgboost算法的步骤和GB基本相同，都是首先初始化为一个常数，gb是根据一阶导数ri，xgboost是根据一阶导数gi和二阶导数hi，迭代生成基学习器，相加更新学习器。

 

xgboost与gdbt除了上述三点的不同，xgboost在实现时还做了许多优化：

• 在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
• xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍。
• 特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。
• 按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。
• xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

Xgboost和深度学习的关系

陈天奇在Quora上的解答如下：
不同的机器学习模型适用于不同类型的任务。深度神经网络通过对时空位置建模，能够很好地捕获图像、语音、文本等高维数据。而基于树模型的XGBoost则能很好地处理表格数据，同时还拥有一些深度神经网络所没有的特性（如：模型的可解释性、输入数据的不变性、更易于调参等）。
这两类模型都很重要，并广泛用于数据科学竞赛和工业界。举例来说，几乎所有采用机器学习技术的公司都在使用tree boosting，同时XGBoost已经给业界带来了很大的影响。

 

五、 XGboost/GBDT调参

推荐GBDT树的深度6；（横向比较：DecisionTree/RandomForest需要把树的深度调到15或更高）

以下摘自知乎上的一个问答（详见参考文献8），问题和回复都很好的阐述了这个参数设置的数学原理。

【问】xgboost/gbdt在调参时为什么树的深度很少就能达到很高的精度？
  用xgboost/gbdt在在调参的时候把树的最大深度调成6就有很高的精度了。但是用DecisionTree/RandomForest的时候需要把树的深度调到15或更高。用RandomForest所需要的树的深度和DecisionTree一样我能理解，因为它是用bagging的方法把DecisionTree组合在一起，相当于做了多次DecisionTree一样。但是xgboost/gbdt仅仅用梯度上升法就能用6个节点的深度达到很高的预测精度，使我惊讶到怀疑它是黑科技了。请问下xgboost/gbdt是怎么做到的？它的节点和一般的DecisionTree不同吗？

【答】这是一个非常好的问题，题主对各算法的学习非常细致透彻，问的问题也关系到这两个算法的本质。这个问题其实并不是一个很简单的问题，我尝试用我浅薄的机器学习知识对这个问题进行回答。
  一句话的解释，来自周志华老师的机器学习教科书（ 机器学习-周志华）：Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成；Bagging主要关注降低方差，因此它在不剪枝的决策树、神经网络等学习器上效用更为明显。
  随机森林(random forest)和GBDT都是属于集成学习（ensemble learning)的范畴。集成学习下有两个重要的策略Bagging和Boosting。
  Bagging算法是这样做的：每个分类器都随机从原样本中做有放回的采样，然后分别在这些采样后的样本上训练分类器，然后再把这些分类器组合起来。简单的多数投票一般就可以。其代表算法是随机森林。Boosting的意思是这样，他通过迭代地训练一系列的分类器，每个分类器采用的样本分布都和上一轮的学习结果有关。其代表算法是AdaBoost, GBDT。
  其实就机器学习算法来说，其泛化误差可以分解为两部分，偏差（bias)和方差(variance)。这个可由下图的式子导出（这里用到了概率论公式D(X)=E(X2)-[E(X)]2）。偏差指的是算法的期望预测与真实预测之间的偏差程度，反应了模型本身的拟合能力；方差度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。这个有点儿绕，不过你一定知道过拟合。
  如下图所示，当模型越复杂时，拟合的程度就越高，模型的训练偏差就越小。但此时如果换一组数据可能模型的变化就会很大，即模型的方差很大。所以模型过于复杂的时候会导致过拟合。
  当模型越简单时，即使我们再换一组数据，最后得出的学习器和之前的学习器的差别就不那么大，模型的方差很小。还是因为模型简单，所以偏差会很大。

 

模型复杂度与偏差方差的关系图

  也就是说，当我们训练一个模型时，偏差和方差都得照顾到，漏掉一个都不行。
  对于Bagging算法来说，由于我们会并行地训练很多不同的分类器的目的就是降低这个方差(variance) ,因为采用了相互独立的基分类器多了以后，h的值自然就会靠近.所以对于每个基分类器来说，目标就是如何降低这个偏差（bias),所以我们会采用深度很深甚至不剪枝的决策树。
  对于Boosting来说，每一步我们都会在上一轮的基础上更加拟合原数据，所以可以保证偏差（bias）,所以对于每个基分类器来说，问题就在于如何选择variance更小的分类器，即更简单的分类器，所以我们选择了深度很浅的决策树。

 

 

 

 

参考：

1. https://www.jianshu.com/p/6755107e816d
2. https://www.jianshu.com/p/a72539acafe5
3. https://blog.csdn.net/fengying2016/article/details/77239605