开发者社区> citibank> 正文

Adaboost算法

简介: 之前的博客中讲到了集成学习按照个体学习器之间是否存在依赖关系可以分为两类,第一个是个体学习器之间存在强依赖关系,另一类是个体学习器之间不存在强依赖关系。前者的代表算法就是是boosting系列算法。在boosting系列算法中, Adaboost是最著名的算法之一。
+关注继续查看

之前的博客中讲到了集成学习按照个体学习器之间是否存在依赖关系可以分为两类,第一个是个体学习器之间存在强依赖关系,另一类是个体学习器之间不存在强依赖关系。前者的代表算法就是是boosting系列算法。在boosting系列算法中, Adaboost是最著名的算法之一。Adaboost既可以用作分类,也可以用作回归。本文就对Adaboost算法做一个总结。
Adaboost算法推导:
Adaboost算法有多种推导方式,比较容易理解的是基于“加性模型”,即基学习器的线性组合:

$$ H(x)=\sum_{t=1}^{T}\alpha _{t}h_{t}(x) $$

来最小化指数损失函数:

$$ \iota _{exp}(H|D)=e^{-f(x)h(x)} $$

算法步骤如下:

image


若$H(x)$能令指数损失函数最小化,则损失函数对$H(x)$的偏导为:

$$ \frac{\alpha \iota _{exp}(H|D)}{\alpha H(x)} = e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x) $$

令其等于零,可解的:

$$ H(x)=\frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)} $$

因此,有:

image


这意味着$sign(H(x))$达到了贝叶斯最优错误率,换言之,若指数损失函数最小化,则分类错误率也将最小化,这说明指数损失函数式分类任务原本0/1损失函数的一致的替代损失函数,而且数学x性能好,我们那他来作为优化目标。
在Adaboost算法中,第一个基分类器$h_1$是通过直接将基学习算法用于初始数据分布而得,此后迭代第生成$h_t$和$\alpha _t$,当基分类器$h_t$基于分布$D_t$产生后,该基学习器的权重$\alpha _t$应使得$\alpha _th_t$最小化指数损失函数:

$$ \frac{\partial \iota _{exp}(\alpha _{t}h_t|D_t)}{\partial \alpha _{t}} = \frac{\partial e^{(-f(x)\alpha _th_{t}(x))}}{\partial \alpha _{t}}\\=e^{-\alpha _{t}}P(f(x)=h_{t}(x)) + e^{\alpha _{t}}P(f(x)\neq h_{t}(x))\\=e^{-\alpha _{t}}(1-\epsilon _{t})+e^{\alpha _{t}}\epsilon _{t} $$

其中,$\epsilon _{t}=P(h_{t}(x)\neq f(x))$。
令其等于零,可解得:

$$ \alpha _{t}=\frac{1}{2}ln\left ( \frac{1-\epsilon _{t}}{\epsilon _{t}} \right ) $$

这就是分类器权重更新公式。
Adboost算法在获得$H_{t-1}$之后样本分布进行调整,使下一轮的基学习器$h_t$能纠正$H_{t-1}$的一些错误,理想的$h_t$能纠正$H_{t-1}$的全部错误,即最小化:

$$ \iota _{exp}(H_{t-1}+h_{t}|D)=e^{-f(x)(H_{t-1}(x)+h_{t}(x))}=e^{-f(x)H_{t-1}(x)h_{t}(x)} $$

注意到$f^2(x)=h^2_t(x)=1$,k可使用$e^{-f(x)h_t(x)}$的泰勒展开式近似为:

image


于是,理想的基学习器

image


image
image


这就得到了样本分布的更新公式。
在《统计学习方法》中,没有对这部分给出详细说明,《机器学习》一书做出了详细的解释,上面推导将规范化因子替换后,二者就对应起来,规范化因子为:

$$ Z_m=\frac{e^{-f(x)(H_{t-1}(x))}}{e^{-f(x)H_{t1}(x)}}=e^{-\alpha _tf(x)h_t(x)} $$

adaboost在分类中的使用:
这里我们对AdaBoost二元分类问题算法流程做一个总结。
输入为样本集$T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$,输出为${-1, +1}$,弱分类器算法, 弱分类器迭代次数K。
输出为最终的强分类器$f(x)$
1) 初始化样本集权重为

$$ D(1) = (w_{11}, w_{12}, ...w_{1m}) ;\;\; w_{1i}=\frac{1}{m};\;\; i =1,2...m $$

2) 对于k=1,2,...K:

  • a) 使用具有权重$D_k$的样本集来训练数据,得到弱分类器$G_k(x)$
  • b)计算$h_k(x)$的分类误差率

$$ \epsilon _k = P(h_k(x_i) \neq y_i) = \sum\limits_{i=1}^{m}D_{ki}I(h_k(x_i) \neq y_i) $$

  • c) 计算弱分类器的系数

$$ \alpha_k = \frac{1}{2}log\frac{1-\epsilon _k}{\epsilon _k} $$

  • d) 更新样本集的权重分布

$$ D_{k+1,i} = \frac{D_{ki}}{Z_K}exp(-\alpha_kf_i(x)h_k(x_i)) \;\; i =1,2,...m $$

3) 构建最终分类器为:

$$ f(x) = sign(\sum\limits_{k=1}^{K}\alpha_kh_k(x)) $$

对于Adaboost多元分类算法,其实原理和二元分类类似,最主要区别在弱分类器的系数上。比如Adaboost SAMME算法,它的弱分类器的系数

$$ \alpha_k = \frac{1}{2}log\frac{1-\epsilon _k}{\epsilon _k} + log(R-1) $$

其中R为类别数。从上式可以看出,如果是二元分类,R=2,则上式和我们的二元分类算法中的弱分类器的系数一致。

参考:周志华《机器学习》
李航《统计学习方法》
刘建平:集成学习之Adaboost算法原理小结

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
10660 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
7613 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
15513 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
11352 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
17594 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
23604 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
18111 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
31897 0
+关注
77
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载