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

AdaBoost

2条评论4,607次浏览

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篇
  • 评论总数:402条
  • 分类总数:31个
  • 标签总数:44个
  • 运行时间:1013天

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

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

最新评论
  • 晴子: 在主节点初始化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?
  • linxh: 班门弄斧一下: ssh host cmd 和直接ssh上后cmd结果不一样是因为ssh直接运行远程命令 是非交互非登录模式与ssh上去得到一个登录交互式Shell二 者加载的环境变量不一样。
  • 匿名: 其实文本分类和数字分类是一样的,只是文本分类需要多一个步骤, 就是计算它的tf-idf值将其转换为double类型
  • yurnom: 可能苹果最近又改变了返回值吧,最近没做测试了。 BadDeviceToken一般测试环境和正式环境弄错的情况 下会出现。
  • Anonymous: :razz: 博主,良心贴啊, 最近也在弄apns推送。 有个问题想请教你一下啊。 你博客中写的 Unregistered 错误,有准确的说明吗, 我看你博客中写的:...
  • 一波清泉: 回复邮箱: 1004161699@qq.com 多谢
  • Anonymous: 17/02/09 01:15:02 WARN Utils: Service ‘SparkUI’ could not bind on port 4040. Attempting port...
  • pacificLee: :twisted:
  • 小码: 为什么没有后面的呢,只有前10个
  • Anonymous: :lol:
  • Anonymous: :razz: 楼主是属于会聊天的。 我想问,sqoop发了几个版本了,应该没这些问题了吧。
  • Anonymous: Config.kafkaConfig.kafkaGroupI d 这个是指自己配置的group id 还是从 import org.apache.kafka.common.config .Config 这个类...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 那个方法是在 spark-streaming_2.10 中 kafka...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 你确定 kafka 里面有这个类 ? 个人在kafka 最新 稳定版...
  • Anonymous: :roll:
  • Anonymous: 很不错,试问有java版的吗?
  • Anonymous: 赞
  • Anonymous: 哈哈 看楼主的吐槽乐死了 where子句是可以写的 同样找不到资料 一点点试出来的 select id from xxxx where ${CONDITIONS} and 1=1 and 2=2 limit 4