AdaBoost--从原理到实现

一.引入

对于Adaboost,可以说是久闻大名,据说在Deep Learning出来之前,SVM和Adaboost是效果最好的 两个算法,而Adaboost是提升树(boosting tree),所谓“提升树”就是把“弱学习算法”提升(boost)为“强学习算法”(语自《统计学习方法》),而其中最具代表性的也就是Adaboost了,貌似Adaboost的结构还和Neural Network有几分神似,我倒没有深究过,不知道是不是有什么干货

Boosting 算法的起源

boost 算法系列的起源来自于PAC Learnability(PAC 可学习性)。这套理论主要研究的是什么时候一个问题是可被学习的,当然也会探讨针对可学习的问题的具体的学习算法。这套理论是由Valiant提出来的,也因此(还有其他贡献哈)他获得了2010年的图灵奖。

PAC 定义了学习算法的强弱

弱学习算法---识别错误率小于1/2(即准确率仅比随机猜测略高的学习算法)

强学习算法---识别准确率很高并能在多项式时间内完成的学习算法

同时 ,Valiant和 Kearns首次提出了 PAC学习模型中弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果二者等价 ,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法 ,而不必寻找很难获得的强学习算法。 也就是这种猜测,让无数牛人去设计算法来验证PAC理论的正确性。

不过很长一段时间都没有一个切实可行的办法来实现这个理想。细节决定成败,再好的理论也需要有效的算法来执行。终于功夫不负有心人, Schapire在1996年提出一个有效的算法真正实现了这个夙愿,它的名字叫AdaBoost。AdaBoost把多个不同的决策树用一种非随机的方式组合起来,表现出惊人的性能!第一,把决策树的准确率大大提高,可以与SVM媲美。第二,速度快,且基本不用调参数。第三,几乎不Overfitting。我估计当时Breiman和Friedman肯定高兴坏了,因为眼看着他们提出的CART正在被SVM比下去的时候,AdaBoost让决策树起死回生!Breiman情不自禁地在他的论文里赞扬AdaBoost是最好的现货方法(off-the-shelf,即“拿下了就可以用”的意思)。(这段话摘自统计学习那些事)

了解了这段有意思的起源,下面来看adaboost算法应该会兴趣大增。

Boosting算法的发展历史

Boosting算法是一种把若干个分类器整合为一个分类器的方法,在boosting算法产生之前,还出现过两种比较重要的将多个分类器整合 为一个分类器的方法,即boostrapping方法和bagging方法。我们先简要介绍一下bootstrapping方法和bagging方法。

  1)bootstrapping方法的主要过程

  主要步骤:

  i)重复地从一个样本集合D中采样n个样本

  ii)针对每次采样的子样本集,进行统计学习,获得假设Hi

  iii)将若干个假设进行组合,形成最终的假设Hfinal

  iv)将最终的假设用于具体的分类任务

  2)bagging方法的主要过程 -----bagging可以有多种抽取方法

  主要思路:

  i)训练分类器

  从整体样本集合中,抽样n* < N个样本 针对抽样的集合训练分类器Ci

  ii)分类器进行投票,最终的结果是分类器投票的优胜结果

  但是,上述这两种方法,都只是将分类器进行简单的组合,实际上,并没有发挥出分类器组合的威力来。直到1989年,Yoav Freund与 Robert Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖(Godel price)。

  Schapire还提出了一种早期的boosting算法,其主要过程如下:

  i)从样本整体集合D中,不放回的随机抽样n1 < n个样本,得到集合 D1

  训练弱分类器C1

  ii)从样本整体集合D中,抽取 n2 < n个样本,其中合并进一半被C1 分类错误的样本。得到样本集合D2

  训练弱分类器C2

  iii)抽取D样本集合中,C1 和 C2 分类不一致样本,组成D3

  训练弱分类器C3

  iv)用三个分类器做投票,得到最后分类结果

  到了1995年,Freund and schapire提出了现在的adaboost算法,其主要框架可以描述为:

  i)循环迭代多次

  更新样本分布

  寻找当前分布下的最优弱分类器

  计算弱分类器误差率

  ii)聚合多次训练的弱分类器

Adaboost 算法

AdaBoost 是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器,即弱分类器,然后把这些弱分类器集合起来,构造一个更强的最终分类器。(很多博客里说的三个臭皮匠赛过诸葛亮)

算法本身是改变数据分布实现的,它根据每次训练集之中的每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。将修改权值的新数据送给下层分类器进行训练,然后将每次训练得到的分类器融合起来,作为最后的决策分类器。

完整的adaboost算法如下

简单来说,Adaboost有很多优点: 1)adaboost是一种有很高精度的分类器   2)可以使用各种方法构建子分类器,adaboost算法提供的是框架   3)当使用简单分类器时,计算出的结果是可以理解的。而且弱分类器构造极其简单   4)简单,不用做特征筛选   5)不用担心overfitting!

Adaboost 举例

也许你看了上面的介绍或许还是对adaboost算法云里雾里的,没关系,百度大牛举了一个很简单的例子,你看了就会对这个算法整体上很清晰了。

  下面我们举一个简单的例子来看看adaboost的实现过程:

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

  第一步:

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

  其中划圈的样本表示被分错的。在右边的途中,比较大的“+”表示对该样本做了加权。

也许你对上面的ɛ1,ɑ1怎么算的也不是很理解。下面我们算一下,不要嫌我啰嗦,我最开始就是这样思考的,只有自己把算法演算一遍,你才会真正的懂这个算法的核心,后面我会再次提到这个。

算法最开始给了一个均匀分布 D 。所以h1 里的每个点的值是0.1。ok,当划分后,有三个点划分错了,根据算法误差表达式

得到 误差为分错了的三个点的值之和,所以ɛ1=(0.1+0.1+0.1)=0.3,而ɑ1 根据表达式

的可以算出来为0.42. 然后就根据算法 把分错的点权值变大。如此迭代,最终完成adaboost算法。

  第二步:

  根据分类的正确率,得到一个新的样本分布D3,一个子分类器h2

  第三步:

  得到一个子分类器h3

  整合所有子分类器:

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

Adaboost 疑惑和思考

到这里,也许你已经对adaboost算法有了大致的理解。但是也许你会有个问题,为什么每次迭代都要把分错的点的权值变大呢?这样有什么好处呢?不这样不行吗? 这就是我当时的想法,为什么呢?我看了好几篇介绍adaboost 的博客,都没有解答我的疑惑,也许大牛认为太简单了,不值一提,或者他们并没有意识到这个问题而一笔带过了。然后我仔细一想,也许提高错误点可以让后面的分类器权值更高。然后看了adaboost算法,和我最初的想法很接近,但不全是。 注意到算法最后的表到式为

这里面的a 表示的权值,是由

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

  最后,我们可以总结下adaboost算法的一些实际可以使用的场景:

  1)用于二分类或多分类的应用场景

  2)用于做分类任务的baseline

  无脑化,简单,不会overfitting,不用调分类器

  3)用于特征选择(feature selection)

  4)Boosting框架用于对badcase的修正

  只需要增加新的分类器,不需要变动原有分类器

  由于adaboost算法是一种实现简单,应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器,同时具有分类错误率上界随着训练增加而稳定下降,不会过拟合等的性质,应该说是一种很适合于在各种分类场景下应用的算法。

二.过程

(from PRML)

这就是Adaboost的结构,最后的分类器YM是由数个弱分类器(weak classifier)组合而成的,相当于最后m个弱分类器来投票决定分类,而且每个弱分类器的“话语权”α不一样。

这里阐述下算法的具体过程:

1.初始化所有训练样例的权重为1 / N,其中N是样例数

2.for m=1,……M:

a).训练弱分类器ym(),使其最小化权重误差函数(weighted error function):

b)接下来计算该弱分类器的话语权α:

c)更新权重:

其中Zm:

是规范化因子,使所有w的和为1。(这里公式稍微有点乱)

3.得到最后的分类器:

三.原理

可以看到整个过程就是和最上面那张图一样,前一个分类器改变权重w,同时组成最后的分类器

如果一个训练样例 在前一个分类其中被误分,那么它的权重会被加重,相应地,被正确分类的样例的权重会降低

使得下一个分类器 会更在意被误分的样例,那么其中那些α和w的更新是怎么来的呢?

下面我们从前项分步算法模型的角度来看看Adaboost:

直接将前项分步加法模型具体到adaboost上:

其中 fm是前m个分类器的结合

此时我们要最小化E,同时要考虑α和yl,

但现在我们假设前m-1个α和y都已经fixed了:那么

其中

,可以被看做一个常量,因为它里面没有αm和ym:

接下来:

其中Tm表示正分类的集合,Mm表示误分类的集合,这一步其实就是把上面那个式子拆开,没什么复杂的东西

然后就是找ym了,就是最小化下式的过程,其实就是我们训练弱分类器

有了ym,α也就可以找了,然后继续就可以找到更新w的公式了(注意这里得到的w公式是没有加规范化因子Z的公式,为了计算方便我们加了个Z进去)

因为这里算出来直接就是上面过程里的公式,就不再赘述了,有兴趣你可以自己算一算

四.实现

终于到实现了,本次实现代码基本基于《统计学习方法》,比如有些符号(弱分类器是G(x),训练样例的目标是y而不是上文所述的t)差异。

[python] view plaincopy

  1. # coding: UTF-8
  2. from __future__ import division
  3. import numpy as np
  4. import scipy as sp
  5. from weakclassify import WEAKC
  6. from dml.tool import sign
  7. class ADABC:
  8. def __init__(self,X,y,Weaker=WEAKC):
  9. '''''
  10. Weaker is a class of weak classifier
  11. It should have a train(self.W) method pass the weight parameter to train
  12. pred(test_set) method which return y formed by 1 or -1
  13. see detail in <统计学习方法>
  14. '''
  15. self.X=np.array(X)
  16. self.y=np.array(y)
  17. self.Weaker=Weaker
  18. self.sums=np.zeros(self.y.shape)
  19. self.W=np.ones((self.X.shape[1],1)).flatten(1)/self.X.shape[1]
  20. self.Q=0
  21. #print self.W
  22. def train(self,M=4):
  23. '''''
  24. M is the maximal Weaker classification
  25. '''
  26. self.G={}
  27. self.alpha={}
  28. for i in range(M):
  29. self.G.setdefault(i)
  30. self.alpha.setdefault(i)
  31. for i in range(M):
  32. self.G[i]=self.Weaker(self.X,self.y)
  33. e=self.G[i].train(self.W)
  34. #print self.G[i].t_val,self.G[i].t_b,e
  35. self.alpha[i]=1/2*np.log((1-e)/e)
  36. #print self.alpha[i]
  37. sg=self.G[i].pred(self.X)
  38. Z=self.W*np.exp(-self.alpha[i]*self.y*sg.transpose())
  39. self.W=(Z/Z.sum()).flatten(1)
  40. self.Q=i
  41. #print self.finalclassifer(i),'==========='
  42. if self.finalclassifer(i)==0:
  43. print i+1," weak classifier is enough to make the error to 0"
  44. break
  45. def finalclassifer(self,t):
  46. '''''
  47. the 1 to t weak classifer come together
  48. '''
  49. self.sums=self.sums+self.G[t].pred(self.X).flatten(1)*self.alpha[t]
  50. #print self.sums
  51. pre_y=sign(self.sums)
  52. #sums=np.zeros(self.y.shape)
  53. #for i in range(t+1):
  54. # sums=sums+self.G[i].pred(self.X).flatten(1)*self.alpha[i]
  55. # print sums
  56. #pre_y=sign(sums)
  57. t=(pre_y!=self.y).sum()
  58. return t
  59. def pred(self,test_set):
  60. sums=np.zeros(self.y.shape)
  61. for i in range(self.Q+1):
  62. sums=sums+self.G[i].pred(self.X).flatten(1)*self.alpha[i]
  63. #print sums
  64. pre_y=sign(sums)
  65. return pre_y

看train里面的过程和上文 阐述的一模一样,finalclassifier()函数是用来判断是否已经无误分类的点 的

当然这里用的Weak Classifier是比较基础的Decision Stump,是根据x>v和x<v来分类的,这个代码稍微烦一点,就不贴到这里了,在DML里也有

先试验下《统计学习方法》里面那个最简单的例子:

可以看到也是三个分类器就没有误分点了,权值的选择也是差不多的

其中后面那个-1 表示大于threshold分为负类,小于分为正类。1则相反

加一些其它数据试试:

结果:

我们把图画出来就是:

基本还是正确的,这是四个子分类器的图,不是最后总分类器的图啊~~~

Reference:

【1】 《Pattern Recognition And Machine Learning》

【2】 《统计学习方法》


原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-09-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

神经网络

如今,科学家正在努力探索人脑的奥秘,他们试图通过模仿人脑,来找到大数据的解决方案。

1.1K110
来自专栏大数据挖掘DT机器学习

用支持向量机预测第二天开盘趋势和股价的正负统计分析

监督式学习是机器学习的一个分支,可以通过训练样本而建立起一个输入和输出之间的函数,并以此对新的事件进行预测。 典型的监督学习流程如下: ? 支持向量机 是监督...

41040
来自专栏人工智能

宽度学习系统:一种不需要深度结构的高效增量学习系统

本文是对陈俊龙教授团队“Broad Learning System: An Effective and Efficient Incremental Learning ...

66250
来自专栏机器之心

计算机视觉这一年:这是最全的一份CV技术报告

33960
来自专栏用户2442861的专栏

AdaBoost--从原理到实现

对于Adaboost,可以说是久闻大名,据说在Deep Learning出来之前,SVM和Adaboost是效果最好的 两个算法,而Adaboost是提升树(...

9810
来自专栏新智元

斯坦福“黑盒学习”研究:使用神经变分推理的无向图模型,可替代“采样”

摘要 机器学习中的许多问题可以自然地用无向图模型的语言表达。在这里,我们提出了无向模型的黑箱学习和推理算法,优化了模型的对数似然的变分近似。我们的方法的核心是我...

38770
来自专栏数说工作室

【数说学院】机器学习分类大全

作者 | 冰 · 冰 本文及图的作者是两个人,她们是一个女子博士团体——冰 · 冰 ? 图中整理了机器学习的各种方法,大体分为监督式学习、半监督式学习、无监督式...

39260
来自专栏数据科学与人工智能

【陆勤学习】解读机器学习基础概念:VC维的来龙去脉

目录: 说说历史 Hoeffding不等式 Connection to Learning 学习可行的两个核心条件 Effective Number of Hyp...

73260
来自专栏CreateAMind

commaai自动驾驶的改进方法

15330
来自专栏Data Analysis & Viz

Text-CNN、Word2Vec、RNN、NLP、Keras、fast.ai-20180504

本文集仅为收录自己感兴趣、感觉不错的文章与资源,方便日后查找和阅读,所以排版可能会让人觉得乱。内容会不断更新与调整。文中涉及公众号的文章链接可以会失效,知道如何...

29320

扫码关注云+社区

领取腾讯云代金券