AdaBoost算法及提升树

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/10/7,#,提升方法（,Boosting,）,方法的思想：,改变训练样本的权重（改变训练数据的概率分布）,学习多个分类器，将分类器进行线性组合，提高分类性能。,1,需要解决的问题,如何在每一轮改变训练数据的权值,如何将弱分类器组合成一个强分类器,2,AdaBoost,算法的解决方案,如何在每一轮改变训练数据的权值,提高前一轮弱分类器错误分类样本的权值，降低被正确分类样本的权值,如何将弱分类器组合成强分类器,增加分类误差率小的弱分类器的权值，使其起较大的决定作用，同时减小分类误差率大的弱分类器的权值。,3,AdaBoost,算法,4,系数,5,权值更新,当正确分类时， ，相应的权值会降低，相反相应的权值会增大,6,AdaBoost,误差分析,AdaBoost,算法最终分类器的训练误差界为,7,AdaBoost,误差分析,对于二分类问题,AdaBoost,训练误差界为,其中,8,不等式的证明，等价于证明,只需证明,采用做差、求导的方法即可证明,上式说明，,AdaBoost,的训练误差是以指数速率下降的！,AdaBoost,误差分析,9,10,前向分步算法,AdaBoost,算法中的基本分类器的线性组合为,这是一个加法模型。在给定训练数据及损失函数,L(y,f(x),条件下，学习加法模型,f(x),成为损失函数极小化问题,11,前向分步算法,但是求解这个问题非常复杂。而前向分步算法的思想是每次只学习一组参数，保证每一轮都最优，然后逐步逼近最优目标函数，即,注意前后两个公式的差别,12,前向分步算法,定理,8.3,的证明中，,8.21,、,8.22,。,13,提升树模型,以决策树为基函数的提升方法称为提升树。,二,叉分类树,二,叉决策树,14,提升树算法,仍然采用前向分步算法,不同问题的提升树学习算法，主要区别在于使用损失函数不同,比如回归树，采用平方误差损失函数，因此引入了残差。例题,8.2,。,15,例题,8.2,第二轮结果,16,例题,8.2,第六轮结果,17,