程序员的自我修养
Home » 机器学习 » AdaBoost

AdaBoost

2条评论5,330次浏览

Boosting(提升)方法是一种常用的统计学习方法,其中最具有代表性的算法是AdaBoost。AdaBoost起源于PAC可学习性(probably approximately correct learnability)的研究。历史上,Valiant和Kearns首先提出了强可学习(strongly learnable)和弱可学习(weakly learnable)。在PAC框架下,若一个算法的识别准确率很高并能在多项式时间内完成则为强可学习;若一个算法的错误率仅仅比随机猜测略低,则称之为弱可学习。后来Schapire证明强可学习和弱可学习是等价的:在PAC学习的框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的。如此,问题就变成了:如果已经发现了一个弱学习算法,是否能够将其提升(boosting)为一个强学习算法。

关于提升方法的研究很多,例如:boostrapping,将多个弱分类器分配不同的权值来组成强分类器;bagging,根据多个弱分类器的投票结果来确定最后的分类结果。这些提升方法中,最有效最具有代表性的则是AdaBoost。

AdaBoost算法过程

AdaBoost通过每一轮的分类结果来改变每个样本的权值,使得分类错误的样本权值变大,分类正确的样本权值变小,这样使得没有正确分类的数据获得更高的关注。对于多个弱分类器,AdaBoost通过加权多数表决来组合,误差率小的分类器权值大,反之,则权值小。具体算法如下:

  1. 初始化训练数据的权值分布
    \(D_1=(w_{11},w_{12},..,w_{1N}), {w_{iN}={1\over N}}, i=1,2,..,N\)
  2. 对m=1, 2, .., M
    1. 使用具有权值 \(D_m\) 的训练数据集学习,得到基本分类器 \(G_m(x)\)
    2. 计算 \(G_m(x)\) 在数据集上的分类误差率, \(e_m=P(G_m(x_i)\neq y_i)=\sum_i^N{w_{mi}I(G_m(x_i)\neq y_i)}\)
    3. 计算 \(G_m(x)\) 的系数 \(\alpha_m={1\over 2}ln{{1-e_m}\over e_m}\)
    4. 更新数据集的权值分布 \(D_{m+1}=(w_{m+1,1},w_{m+1,2},..,w_{m_1,N})\) ,其中 \(w_{m+1,i}={w_{mi}\over Z_m}e^{-\alpha_my_iG_m(x_i)}\)\(Z_m=\sum_i^N{w_{mi}e^{-\alpha_my_iG_m(x_i)}}\)
    5. 构建基本分类器的线性组合 \(f(x)=\sum_m^M \alpha_mG_m(x)\)
  3. 得到最终的分类器 \(G(x)=sign(f(x))\)

AdaBoost例子

复(sang)杂(xin)难(bing)懂(kuang)的数学公式太不直观了,下面看个AdaBoost例子。

数据集

序号 1 2 3 4 5 6 7 8 9 10
x 0 1 2 3 4 5 6 7 8 9
y 1 1 1 -1 -1 -1 1 1 1 -1

弱分类器

假设弱分类器由x<v或x>v产生,v将数据集划分分两个部分,这两个部分的误差率最低。

计算过程

  1. 初始化权值分布 \(D_1=(w_{11},w_{12},..,w_{110}),w_{1i}=0.1\)
  2. 对m=1
    1. v=2.5时误差率为0.3,最小,基本分类器为 \(G_1=\begin{equation}\begin{cases}1, x<2.5\\-1, x>2.5\end{cases}\end{equation}\)
    2. \(G_1(x)\) 的误差率为0.3,其系数为 \(\alpha_1={1\over 2}ln{{1-0.3}\over 0.3}=0.4236\)
    3. 计算 \(Z_1={1\over 10}(7e^{-0.4236}+3e^{0.4236})=0.9165\)
      正确分类的样本 \(w_{2i}={w_{1i}\over Z_1}e^{-\alpha_1y_i}={0.1\over 0.9165}e^{-0.4236}=0.0715\)
      未正确分类的样本 \(w_{2i}={0.1\over 0.9165}e^{0.4236}=0.1666\)
      更新权值分布为 \(D_2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)\)

    4. \(f_1(x)=0.4236G_1(x)\) ,在 \(sign(f_1(x))\) 上有3个误差点
  3. 对m=2
    1. 2.5处的误差率为3×0.1666(6,7,8三个点分类错误),8.5处的错误率为3×0.0715=0.2145,所以8.5处有最小误差率,基本分类器为 \(G_2=\begin{equation}\begin{cases}1, x<8.5\\-1, x>8.5\end{cases}\end{equation}\)
    2. \(G_2(x)\) 的误差率为0.2145,其系数为 \(\alpha_2={1\over 2}ln{{1-0.2145}\over 0.2145}=0.6496\)
    3. 更新权值分布,同上,得 \(D_2=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.04555)\)
    4. \(f_2(x)=0.4236G_1(x)+0.6496G_2(x)\) ,在 \(sign(f_2(x))\) 上有3个误差点
  4. 对m=3,计算方法同上,最后得到 \(f_3(x)=0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)\) ,在 \(sign(f_3(x))\) 上有0个误差点,其中 \(G_3=\begin{equation}\begin{cases}1, x<5.5\\-1, x>5.5\end{cases}\end{equation}\)
  5. 至此计算结束,得到最终分类器 \(G(x)=sign(f_3(x))=sign(0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x))\)

AdaBoost优点

  • AdaBoost是一种有很高精度的分类器
  • AdaBoost可以支持各种方式构建的弱分类器,如上文中的x<v这样的分类器,AdaBoost提供的是框架
  • 构造弱分类器简单,不用进行特征筛选
  • 不用担心过拟合

AdaBoost与决策树的结合则形成了提升树(boosting tree),AdaBoost使得决策树的准确率大大提高,可与SVM相媲美。

后记

关于AdaBoost的收敛性证明和用前向分步算法进行解释,个人认为属于理论研究的范围,作为一个生产者,我只要会用并且知道可以收敛并且能够理论上解释的通即可(其实是短时间内看不懂啊混蛋。。)。

参考资料

  • 《统计学习方法》李航,2012
(转载本站文章请注明作者和出处 程序员的自我修养 – SelfUp.cn ,请勿用于任何商业用途)
分类:机器学习
2条评论
  1. ArcherFem说道:

    写的很好,作为一个初学者,也能看到。
    关于“AdaBoost算法过程”,好像写错了,编号2-5的内容“5.构建基本分类器的线性组合 f(x)=∑ M m α m G m (x) ”,应该编号为3
    也有可能是我理解错了

发表评论


profile
  • 文章总数:79篇
  • 评论总数:280条
  • 分类总数:31个
  • 标签总数:44个
  • 运行时间:1130天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • 张瑞昌: 有很多,比较常见的是Jacob迭代法,一次迭代O(n^3), 迭代次数不清楚。 如果是手动算的话按照定义求就可以了
  • Anonymous: :mrgreen:
  • lc277: 你好 我想问下一般删除节点要多久,要删除的datanode大概用了 1t,解除授权已经30多小时还没完成,请问是出现什么问题了吗 麻烦告诉下谢谢 qq1844554123
  • Anonymous: 你好 我想问下一般删除节点要多久,要删除的datanode大概用了 1t,解除授权已经30多小时还没完成,请问是出现什么问题了吗
  • Anonymous: :smile: :grin: :eek:
  • 李雪璇: 想要完整代码,可以帮忙发给我吗
  • Anonymous: 请问一下,那个 user的推荐结果楼主查看了么? 为什么输入数据 最高是五分,输出结果都是7分8分啥的?怎么设置输出的分数的最 大值?
  • Anonymous: 那个 user的推荐结果楼主查看了么? 为什么输入数据 最高是五分,输出结果都是7分8分啥的?
  • Anonymous: stopGracefullyOnShutdown在yarn- client模式下我测试的无效,你的呢
  • Anonymous: 另外,import的lib包能否发个列表.
  • Anonymous: 部分程序已经无法使用, 另外 你的import代码 也应该放上来哈
  • wzq: 赞
  • 增达网: 受教了!呵呵!
  • Anonymous: :!: :smile: :oops: :grin: :eek: :shock:
  • 27: :razz: dsa会报错,rsa不会
  • Anonymous: 看错了 忽略我
  • Anonymous: UserSideCF这个类在哪里
  • 晴子: 在主节点初始化CM5数据库的时候报错误:Verifying that we can write to /opt/cm-5.9.0/etc/cloudera-scm -server log4j:ERROR Could not...
  • zhangnew: 就4题 :?:
  • linxh: “ 但要是遇到预先并不知道数组的长度而又需要获取正确的(或者称之 为原始的)split长度时,该如何处理呢。。? ” 印象中可以split函数参数传-1?