HITSCIR-TM zkli-李泽魁 March. 24, 2015 Bagging & Boosting HITSCIR-TM zkli-李泽魁 March. 24, 2015

Outline Ensemble Methods Bagging Boosting Random Forests Gradient Boosting Decision Trees

Outline Ensemble Methods Bagging Boosting Random Forests Gradient Boosting Decision Trees

Ensemble Methods 求助现场观众？ 了解集成学习之前

Ensemble learning——Train Basic idea: if one classifier works well, why not use multiple classifiers! Training model 1 learning alg model 2 learning alg Training Data … model m learning alg

Ensemble learning——Test Basic idea: if one classifier works well, why not use multiple classifiers! Testing model 1 prediction 1 example to label model 2 prediction 2 take majority vote if they output probabilities, take a weighted vote … model m prediction m

Benefits of ensemble learning Assume each classifier makes a mistake with some probability (e.g. 0.4, that is a 40% error rate) model 1 model 2 model 3 prob C .6*.6*.6=0.216 I .6*.6*.4=0.144 .6*.4*.6=0.144 .6*.4*.4=0.096 .4*.6*.6=0.144 .4*.6*.4=0.096 .4*.4*.6=0.096 .4*.4*.4=0.064 错误率为0.4 0.096+ 0.064 = 35% error!

Given enough classifiers… 刚才是三个model 如果给足够多的model的话 错误率会随之不断下降 最后200个model r = 0.4

三个臭皮匠顶个诸葛亮 通过集成学习提高分类器的整体泛化能力是有条件的: 分类器之间应该具有差异性 分类器的精度，每个个体分类器的分类精度必须大于0.5 分类器之间应该具有差异性，想想看啊，如果使用的是同一个分类器，那么集成起来的分类结果是不会有变化的。 分类器的精度，每个个体分类器的分类精度必须大于0.5。如下面的图，可以看到如果p<0.5,那么随着集成规模的增加，分类精度会下降，但是如果大于5的话，那么最终分类精准度是可以趋于1的。

Obtaining independent classifiers model 1 learning alg model 2 learning alg Training Data … model m learning alg Where to we get m independent classifiers?

Idea 1: different learning methods decision tree model 1 learning alg 1 k-nn model 2 learning alg 2 perceptron Training Data … naïve bayes gradient descent variant 1 model m learning alg 3 那么我们首先就想到了用不同的机器学习算法训练模型 gradient descent variant 2 Pros/cons? …

Idea 1: different learning methods Pros: Lots of existing classifiers already Can work well for some problems Cons/concerns: Often, classifiers are not independent, that is, they make the same mistakes! e.g. many of these classifiers are linear models voting won’t help us if they’re making the same mistakes

Idea 2: split up training data model 1 part 1 learning alg model 2 part 2 learning alg Training Data … … model m 既然用不同的分类器不好使 我们可以尝试方案二，将数据分几部分 每部分用学出一个模型 part m learning alg Use the same learning algorithm, but train on different parts of the training data

Idea 2: split up training data Pros: Learning from different data, so can’t overfit to same examples Easy to implement fast Cons/concerns: Each classifier is only training on a small amount of data Not clear why this would do any better than training on full data and using good regularization 优点不易过拟合 缺点显而易见 数据量不足导致训练出的模型不具有普适性，推广能力较差

Outline Ensemble Methods Bagging Boosting Random Forests Gradient Boosting Decision Trees

Idea 3: bagging … … Training Data 1 Training Data Training Data m model 1 learning alg … Training Data … 也是将数据分成M部分 这个M部分与刚才的分成m份有什么不同呢 model m learning alg Training Data m

sampling with replacements bagging sampling with replacements “Training” data 1 “Training” data 2 … 他是有放回抽取 用抽样方法模拟training data的分布 Training data Use training data as a proxy for the data generating distribution

bagging create m “new” training data sets by sampling with replacement from the original training data set (called m “bootstrap” samples) train a classifier on each of these data sets to classify, take the majority vote from the m classifiers

Bootstraping pull up by your own bootstraps 自助法、自举法、拔靴法。。。 简单理解： 现有100个数据, 但是100个数据没办法真实反映样本的全貌, 就把这100个数据重新随机的SAMPLING 1000次, 这样你就有了100*1000个数据点了，这样样本量就会增大很多 在已知数据的基础上, 通过用计算机来模拟N趋近于无穷大时候的情况, 把已知的DATA不断的重新SAMPLING, 从而在新的数据中得出原始数据的信息

bagging overlap … Training Data 1 Won’t these all be basically the same? Training Data … On average, a randomly sampled data set will only contain 63% of the examples in the original 因为是随机抽取，那么每个样本被抽到的概率有多少呢？ 那么这样的抽样到底重合度有多少呢 Training Data m

probability of overlap 𝑃 𝑛𝑜𝑡_𝑐ℎ𝑜𝑜𝑠𝑒 = 1− 1 𝑛 n = 1 𝑒 y=(1-1/n)^n 则lny=nln(1-1/n) 令t=1/n则n->∞时t->0 lim(n→∞)nln(1-1/n)=lim(t→0)[ln(1-t)]/t 由罗毕达法则lim(t→0)[ln(1-t)]/t=lim(t→0)[ln(1-t)]/t =lim(t→0)1/(t-1) =-1 所以lim(n→∞)(1-1/n)^n=1/e Converges very quickly to 1-1/e ≈ 63%

When does bagging work Let’s say 10% of our examples are noisy (i.e. don’t provide good information) When bagging sampling data, a third of the original noisy examples not use for training For some classifiers that have trouble with noisy classifiers, this can help 比如我们提供的数据有部分错误 标语料的时候饿了标错了 那么我们bootstrapping的时候会避免其中的三分之一的噪声

When does bagging work Bagging tends to reduce the variance of the classifier By voting, the classifiers are more robust to noisy examples Bagging is most useful for classifiers that are: Unstable: small changes in the training set produce very different models Prone to overfitting 可以降低模型们的方差 更不易受噪声影响 Bagging广泛用在 不稳定的模型； 倾向于过拟合的模型；

Bagging与CART的实验效果对比 ……

Review: Idea 1: different learning methods decision tree model 1 learning alg k-nn model 2 learning alg perceptron Training Data … naïve bayes gradient descent variant 1 model m learning alg gradient descent variant 2 classifiers are not independent? …

Review: Idea 2: split up training data model 1 part 1 learning alg model 2 part 2 learning alg Training Data … … model m part m learning alg Use the same learning algorithm, but train on different parts of the training data Each classifier is only training on a small amount of data

Review: Idea 3: bagging … … Training Data 1 Training Data Training model 1 learning alg … Training Data … model m learning alg Training Data m more robust to noisy examples

Outline Ensemble Methods Bagging Boosting Random Forests Gradient Boosting Decision Trees

Idea 4: boosting 通过改变样本分布，使得分类器不断增加对分错样本的重视程度，即他们的权重

Boosting(提升方法) 提升方法是一个迭代的过程 通过改变样本分布，使得分类器聚集在那些很难分的样本上，对那些容易错分的数据加强学习，增加错分数据的权重 这样错分的数据再下一轮的迭代就有更大的作用（对错分数据进行惩罚）

boosting basics Start with equal weighted examples Weights: Examples: E1 E2 E3 E4 E5 weak 1 Learn a weak classifier:

Boosting classified correct classified incorrect Weights: Examples: E1 E2 E3 E4 E5 两个分错 我们怎么变权重呢 weak 1 We want to reweight the examples and then learn another weak classifier How should we change the example weights?

Boosting Learn another weak classifier: weak 2 Weights: Examples: E1

Boosting Weights: Examples: E1 E2 E3 E4 E5 还有一个分错 weak 2

Boosting decrease the weight for those we’re getting correct Weights: Examples: E1 E2 E3 E4 E5 decrease the weight for those we’re getting correct increase the weight for those we’re getting incorrect

Classifying weak 1 prediction 1 weighted vote based on how well they classify the training data weak 2 prediction 2 同时将不同的分类器加权投票 对weak2给更大的权重，因为他至分错一个样本 weak_2_vote > weak_1_vote since it got more right …

Boosting Weight 数据的权重有两个作用 Boosting算法之一：AdaBoost算法 使用这些权值作为抽样分布，进行对数据的抽样 分类器可以使用权值学习有利于高权重样本的分类器。把一个弱分类器提升为一个强分类器 Boosting算法之一：AdaBoost算法

AdaBoost: train for k = 1 to iterations: classifierk = learn a weak classifier based on weights calculate weighted error for this classifier(加权分类误差) calculate “score” for this classifier(分类器的系数) change the example weights(权值的更新) K=0 初始化weight 计算每个样本的分类误差，前面乘以weight，组成加权分类误差 weighted error 根据分类误差计算分类器的系数 即给分类器打的分值，可以看出，误差越小，权值越大 更新权重公式，见下图

AdaBoost: train update the example weights Remember, we want to enforce: Z为归一化因子 两个约束条件 normalizing constant (i.e. the sum of the “new” wi):

AdaBoost: train update the example weights correct positive incorrect negative 这里label为实际值 Classifier(x)为预测结果 如果两者不同，为负值 整体权重值大 每次更新都是基于前一步的wi，而非基于全局更新 correct small value incorrect large value Note: only change weights based on current classifier (not all previous classifiers)

AdaBoost例题 Weak Classifier是Decision Stump 根据x>v和x<v来分类 序号 1 2 3 4 5 6 7 8 9 10 x y -1 Weak Classifier是Decision Stump 根据x>v和x<v来分类

在权值分布为D1的训练数据上，阈值v取2.5时误差率最低 序号 1 2 3 4 5 6 7 8 9 10 x y -1 w1i 0.1 初始化训练数据的权值分布, W1i = 0.1 在权值分布为D1的训练数据上，阈值v取2.5时误差率最低 故基本分类器为： 那么这时候误差率应该是0.3 分类器为以2.5分隔线

分类器sign(f1(x))在训练数据集上有3个误分类点 序号 1 2 3 4 5 6 7 8 9 10 x y -1 w1i 0.1 计算Classifier1的系数 更新训练数据的权值分布 D2=(0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715) f1(x)=0.4236*Classifier1(x) 分类器sign(f1(x))在训练数据集上有3个误分类点 计算classifier系数 更新样本权值

在权值分布为D2的训练数据上，阈值v取8.5时误差率最低，故基本分类器为： 序号 1 2 3 4 5 6 7 8 9 10 x y -1 w2i 0.0715 0.1666 M=2 在权值分布为D2的训练数据上，阈值v取8.5时误差率最低，故基本分类器为： Classifier2(x)在训练数据集上的误差率𝜀2 计算Classifier2(x)的系数𝛼2 按照公式计算权值分布D3 D3=(0.0455, 0.0455, ……0.0455) f2(x)=0.4236*Classifier1(x) + 0.6496*Classifier2(x) 分类器sign(f2(x))在训练数据集上有3个误分类点

分类器sign(f3(x))在训练数据集上有0个误分类点 序号 1 2 3 4 5 6 7 8 9 10 x y -1 w3i 0.0455 0.1667 0.1060 M=3 …… 直至分类器对所有样本分类正确 f3(x)=0.4236*Classifier1(x) + 0.6496*Classifier2(x)+0.7514*Classifier3(x) 分类器sign(f3(x))在训练数据集上有0个误分类点

Boosting Tips Performance of AdaBoost depends on data and weak learner Consistent with theory, AdaBoost can fail if weak classifier too complex– overfitting weak classifier too weak -- underfitting Empirically, AdaBoost seems especially susceptible to uniform noise susceptible to uniform noise 拟合噪声 Adaboost效果取决于数据质量以及弱分类器准确率 如果weak classifier过于复杂，容易过拟合 如果过于简单，欠拟合 Adaboost在某些任务上会过拟合

Other Boosting Method 不同的损失函数和极小化损失函数方法决定了boosting的最终效果 （图自 Machine Learning A Probabilistic Perspective）

Boosting与其他方法对比

Bagging和Boosting对比 ——取样方式不同 Items Bagging Boosting 采样算法 均匀取样 根据错误率来取样 各轮训练集选取 随机的 与前面各轮的学习结果有关 预测函数权重 没有权重 有权重 并行性 各个预测函数可以并行生成 只能顺序生成 准确性 没有boosting高 在大多数数据集中，高 过拟合 不会 在有些数据集中，会 Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分类精度要优于Bagging。 Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boostlng的各轮训练集的选择与前面各轮的学习结果有关； Bagging的各个预测函数没有权重，而Boosting是有权重的； Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging可通过并行训练节省大量时间开销。 bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化--- Overfit。

Ensemble Methods 的应用 在介绍之前接下来的任务之前 贴一下周志华的boosting 25年的Slides截图

Outline Ensemble Methods Bagging Boosting Random Forests Gradient Boosting Decision Trees

Ensemble Methods 的应用 Random Forests Gradient Boosting Decision Trees 这里简单介绍一下 没有深入公式推理

Random Forests The term came from random decision forests that was first proposed by Tin Kam Ho of Bell Labs in 1995 The method combines Breiman's "bagging" idea and the random selection of features 1995年提出概念 对Bagging方法青出于蓝而胜于蓝

Random Forests 顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的 在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树投票预测分类结果

Random Forests ——两个随机采样的过程 行采样 采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本 假设输入样本为N个，那么采样的样本也为N个(Bagging idea) 这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting

Random Forests ——两个随机采样的过程 列采样(random selection of features) 对树的每一个节点，从M个feature中选择m维(m << M) ，并计算最适合的分类点 Splits are chosen according to a purity measure: squared error (regression) Gini index (classification) ……

Random Forests ——完全分裂 完全分裂 无需剪枝 决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类 无需剪枝 由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting

RF的一个比喻 每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习） 这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果

Compared with Boosting Pros: It is more robust. It is faster to train (no reweighting, each split is on a small subset of data and feature). Can handle missing/partial data. Is easier to extend to online version. The feature selection process is not explicit. Feature fusion is also less obvious. Has weaker performance on small size training data. Cons: fusion 融合 有bagging的优点： 鲁棒性强、容错能力强 同时新优点：训练速度快，采样创新点； 可以并行训练tree 缺点；feature采样的时候不可控制，小样本效果不好

Gradient Boost Decision Tree GBDT、Treelink、 GBRT(Gradient Boost Regression Tree)、Tree Net、MART(Multiple Additive Regression Tree) 由多棵决策树构成，通常都是上百棵树，而且每棵树规模都较小（即树的深度会比较浅） 模型预测的时候，对于输入的一个样本实例，然后会遍历每一棵决策树，每棵树都会对预测值进行调整修正，最后得到预测的结果 那么另外一个应用GBDT就名字多了去了 这里要注意的是 GBDT是个回归树，DT指的是DT中的回归树 决策树分为回归树和分类树 回归树预测楼市房价 分类树预测楼有没有卖出去

Gradient Boost Decision Tree F0是设置的初值， Ti是一棵一棵的决策树 对于不同的问题和选择不同的损失函数，初值的设定是不同的 比如回归问题并且选择高斯损失函数，那么这个初值就是训练样本的目标的均值 初值问题

举个栗子 一套房子的价格 特征有三个 由四棵决策树构成 初值设为价格的均值150万 房子的面积 是否在内环 是否学区房 由四棵决策树构成 Decision Stump 初值设为价格的均值150万 一个面积为120平的内环非学区房的价格预测值为150+20-10+30-10=180万

GBDT学习过程 插播前面说到的投票方法： GB过程与上面的区别？ 预测年龄 ABCD四颗决策树分类结果分别是10、0、20、10岁 我们就取平均值10岁做最终结论 GB过程与上面的区别？ 相信从刚才房价的例子相信大家已经对GBDT的特点拨云见日了 那么他区别于Bagging的地方是什么呢

GBDT学习过程 Boosting，迭代，即通过迭代多棵树来共同决策 每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量

GBDT学习过程——例子引入 比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁 如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄 如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学

GBDT学习过程——例子引入 ABCD四个人的年龄分别为15,19,23,27，分别为高中生、大学生、运动员和码农 传统的决策树： 生活费<2000 生活费>=2000 23,27 15.19 上课时间>=10.5h 休息时间>5h 休息时间<=5h 上课时间<10.5h 15 19 23 27

GBDT学习过程——例子引入 ABCD四个人的年龄分别为15,19,23,27，分别为高中生、大学生、运动员和码农 GBDT的学习过程： 21 [15,19,23,27] [-2,2,-2,2] 使用电脑时间<3h 生活费<2000 生活费>=2000 使用电脑时间>=3h 17 [15,19] 25 [23,27] -2 [-2,-2] 2 [2,2] 残差A=-2, B=2 残差C=-2, D=2 残差A=0, C=0 残差B=0, D=0

现在A,B,C,D的预测值都和真实年龄一致 A: 15岁高中学生，收入较少，天天没时间玩电脑；预测年龄A = 17– 2 = 15 B: 19岁大学生；收入较少，天天宅在宿舍玩电脑；预测年龄B = 17+ 2 = 19 C: 23岁运动员；收入较多，体育训练没时间玩电脑；预测年龄C = 25 – 2 = 23 D: 27岁码农；收入较多，长时间玩电脑；预测年龄D = 25 + 2 = 27

GBDT例子的几点问题 例子中决策树与GBDT相比结果相同，GBDT有何优点？ Gradient呢？ 防止过拟合(例子中的上课时间<10.5h) 每一步的残差计算其实变相地增大了分错instance的权重，而已经分对的instance则都趋向于0 Gradient呢？ A,B,C,D的残差分别为[-2,2,-2,2]，用它作为全局最优的绝对方向 那么有没有其他版本的GBDT 呢

GBDT的两种版本 残差版本把GBDT认为是一个残差迭代树 Gradient版本把 GBDT看作一个梯度迭代树 ELF Gradient版本把 GBDT看作一个梯度迭代树 使用梯度下降法求解，每一棵回归树在学习前N-1棵树的梯度下降值 LambdaMART中的MART

GBDT的两种版本 相同点： 都是迭代回归树，累加每颗树结果作为最终结果（Multiple Additive Regression Tree)，每棵树都在学习前N-1棵树尚存的不足，从总体流程和输入输出上两者是没有区别的 不同点： 迭代时是否用Gradient 残差版本 Gradient版本 求解方法 残差----残差是全局最优值 局部最优方向*步长 优化目标 让结果变成最好 让结果变成更好

RF vs. GBDT Testing by Mllib in Spark Model size

RF vs. GBDT Testing by Mllib in Spark Training data size

参考资料 A Course in Machine Learning, Hal Daumé III 统计学习方法, 李航 机器学习_任彬_20150323.PPT bootstrap, boosting, bagging, leijuan_apple Ensemble learning, GJS CART, Bagging, Random Forest, Boosting, Rachel-Zhang AdaBoost--从原理到实现, Dark_Scope Treelink模型测试报告, wujun Gbdt 迭代决策树入门教程, king Random Forests & Boosting in MLlib, Databricks Blog

Thank You!