提升方法-Adaboost算法

浏览: 1473

image.png

总第85篇

01|基本概念:

提升方法的基本思想:对于任何一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比任何一个专家单独的判断好。

先来看两个概念:强可学习和弱可学习。

在概率近似正确学习的框架中(简称PAC),一个概念(类),如果存在一个多项式的学习算法能够学习它,并且正确率很高,那么就称这个概念是强可学习的;一个概念,如果存在一个多项式的学习算法能够学习它,学习的正确率仅比随机猜测略好,那么就称这个概念是弱可学习的。

弱可学习与强可学习之间是有一定的差距,如果已经发现弱可学习算法,那么能否将它提到强可学习算法,这里的如何提升就是提升方法需要解决的问题。最具代表性的就是AdaBoost算法。

对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比求精确地分类规则(强分类器)容易的多。提升方法就是从弱学习算法,反复学习,得到一系列分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

这样,对于提升方法来说,有两个问题需要解决:一是在每一轮如何改变训练数据的权值或概率分布;二是如何将弱分类器组成一个强分类器

对于第一个问题,AdaBoost的做法是,提高那些被前一轮弱分类器错分类样本的权值,而降低那些被正确分类样本的权值。这样一来,那些没有得到正确分类的数据,由于其权值加大而受到后一轮的弱分类器的更大关注。于是,分类问题被一系列的弱分类器“分而治之”。至于第二个问题,即弱分类器的组合,AdaBoost采取加权多数表决的方法。具体地,加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用,减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。

02|AdaBoost算法:


假设给定一个二分类的训练数据集

image.png

其中,每个样本点由实例和标记组成。x是实例空间,y是标记集合。AdaBoost利用以下算法,从训练数据集中学习一系列弱分类器或基本分类器,并将这些弱分类器线性组合成一个强分类器。

算法步骤:

1.初始化训练数据的权值分布,让训练数据集中的每一个样本均等于1/N。    

image.png

2.对m=1,2,...,M(m表示反复训练的次数)

(a)使用具有权值分布的 Dm的训练数据集学习,得到基本分类器

            image.png

(b)计算Gm(x)在训练数据集上的分类误差率(误分类样本权值之和

image.png

上式中image.png表示第m轮中第i个实例的权值。

(c)计算Gm(x)的系数

                image.png

上式中的对数为自然对数,上式的结果是该分类器在最终分类器的所占的权重,即多项式的系数。

image.png

(d)更新训练数据集的权值分布

           image.png

                  

这里,是规范化因子

          image.png

3.构建基本分类器线性组合

image.png

得到的最终分类器

image.png

image.png


03|前向分布算法:

考虑加法模型(每一轮迭代的分类函数的加和)

image.png

image.png

在给定训练数据及损失函数L(y,f(x))的条件下,学习加法模型f(x)成为经验风险极小化即损失函数最小化问题:

image.png

通常这是一个复杂的优化问题。前向分步算法求解这一优化问题的想法是:因学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数,那么就可以简化优化的复杂度。具体地,每步只需要优化如下目标函数:

image.png

前向分步算法步骤:


image.png

image.png

04|前向分步算法与AdaBoost关系:

AdaBoost 算法可以认为是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。

image.png

推荐 1
本文由 张俊红 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册