天天看点

统计学习方法笔记 -- Boosting方法

adaboost算法

基本思想是,对于一个复杂的问题,单独用一个分类算法判断比较困难,那么我们就用一组分类器来进行综合判断,得到结果,“三个臭皮匠顶一个诸葛亮”

专业的说法,

强可学习(strongly learnable),存在一个多项式算法可以学习,并且准确率很高 

弱可学习(weakly learnable),存在一个多项式算法可以学习,但准确率略高于随机猜测

并且可以证明强可学习和弱可学习是等价的

那么发现一个弱可学习算法是很容易的,如果将弱可学习算法boosting到强可学习算法?

adaboost就是这样的算法,通过反复学习,得到一组弱分类器,通过组合这些弱分类器得到强分类器

问题就是如果得到一组弱分类器?

当然你可以用不同的分类算法来训练 

也可以用不同的训练集,比如bagging,对训练集进行m次随机抽样,得到m个新的训练集

adaboost采用的方法是,用相同的算法和训练集,但改变每个训练样本的weight,因为在求解分类器时的目标函数是,加权误差最小,所以不同的权值会得到不同的分类器参数 

具体的规则,是每轮分类后, 增大分错的样本的权值,减小分对样本的权值,所有样本权值和为1 

这样下一轮分类器求解,就会更关注上一轮分错的这样样本点,达到分而治之的目的

需要注意,可以想到,这个算法对离群值比较敏感,容易overfitting

并且每个弱分类器也有个weight,代表该分类器的误差率,最终用加权多数表决的方式来得到最终结果

具体算法,

统计学习方法笔记 -- Boosting方法

1. 初始化训练样本的权值,平均分布,每个样本的概率相同

统计学习方法笔记 -- Boosting方法

2. 反复迭代学习得到m个弱分类器,对于第m个弱分类器,

2.1 对于训练集,以加权误差最小为目标,求出分类器,gm

统计学习方法笔记 -- Boosting方法

2.2 算出,该弱分类器的加权误差

统计学习方法笔记 -- Boosting方法

2.3 算出该弱分类器的权值,log函数,可见误差越小,权值越高,即在最终强分类器中的作用越大

统计学习方法笔记 -- Boosting方法

2.4 关键的一步,更新训练样本的权值

统计学习方法笔记 -- Boosting方法
统计学习方法笔记 -- Boosting方法

其中,第一个式子其实是,

统计学习方法笔记 -- Boosting方法

指数分布,小于0,取值在(0,1),大于0,取值大于1 

所以意思就是,当gm(x)=y的时候,即判断正确的样本,减小权值 

判断错误的样本,增加权值 

之所以要除以zm,是因为所有权值的和要为1,用zm来进行规范化

3. 上面我们就得到m个弱分类器,如何组合出强分类器,

统计学习方法笔记 -- Boosting方法
统计学习方法笔记 -- Boosting方法

很简单的,加权多数表决 

其中sign函数,取值-1(x<0),0,1(x>0)

本文章摘自博客园,原文发布日期: 2014-08-26

继续阅读