Adaboost算法流程和证明.docx

该【Adaboost算法流程和证明 】是由【飞行的大山】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【Adaboost算法流程和证明 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法
1、Adaboost算法简介
Adaboost算法是Freund和Schapire依据在线分派算法提出的,他
们详尽剖析了Adaboost算法错误率的上界,以及为了使强分类器达到
错误率,算法所需要的最多迭代次数等有关问题。与Boosting算法不
同的是,Adaboost算法不需要早先知道弱学习算法学习正确率的下限
即弱分类器的偏差,而且最后获得的强分类器的分类精度依靠于全部
弱分类器的分类精度,这样能够深入发掘弱分类器算法的能力。
2、Adaboost算法基来源理
Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练
不一样的分类器(弱分类器),而后把这些弱分类器会合起来,构成一个
更强的最后分类器(强分类器)。其算法自己是经过改变数据散布来实
现的,它依据每次训练集之中每个样本的分类能否正确,以及上一次的
整体分类的正确率,来确立每个样本的权值。将修悔过权值的新数据
集送给基层分类器进行训练,最后将每次训练获得的分类器最后交融
起来,作为最后的决议分类器。使用Adaboost分类器能够清除一些不
必需的训练数据特点,并将重点放在重点的训练数据上边。
Adaboost算法中不一样的训练集是经过调整每个样本对应的权重来
实现的。开始时,每个样本对应的权重是同样的,即此中n为样本个
数,在此样本散布下训练出一弱分类器。对于分类错误的样本,加大
其对应的权重;而对于分类正确的样本,降低其权重,这样分错的样
本就被突出出来,进而获得一个新的样本散布。在新的样本散布下,
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
再次对弱分类器进行训练,获得弱分类器。挨次类推,经过

T次循环,
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
获得

T

个弱分类器,把这

T个弱分类器按必定的权重叠加

(boost)

起
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
来,获得最后想要的强分类器。
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost

算法的详细步骤以下:
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
设输入的

n个训练样本为:{(x1,y1),(x2,y2),L

,(xn,yn)}

,此中

xi
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
是输入的训练样本,

yi

{0,1}

分别表示正样本和负样本,此中正样本
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
数为

l

,负样本数

m。

n

l

m,详细步骤以下:
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
⑴初始化每个样本的权重wi,iD(i);⑵对每个t1,L,T(T为弱分类器的个数):
①把权重归一化为一个概率散布
wt,i
wt,in
wt,j
j1
②对每个特点f,训练一个弱分类器hj计算对应全部特点的弱分
类器的加权错误率
n
j
wt(xi)hj(xi)yi
i
1
③选用最正确的弱分类器ht(拥有最小错误率):t
④依据这个最正确弱分类器,调整权重
wt1,i
1i
wt,it
此中i
0表示被正确地分类,i
1,表示被错误地分类
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
t
⑶最后的强分类器为:

t
1t
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
1
T
tht(x)
1T
t,tlog1
h(x)
t1
2t1
0
otherwise
t
3、Adaboost算法应用
跟着Adaboost算法的发展,当前Adaboost算法宽泛的应用于人
脸检测、目表记别等领域,此中有在人脸辨别、汽车辨别、驾驶员眨
眼识其他方面的应用和研究。
Discete-Adaboost算法
1、给定训练集:x1,y1
,L,
xN,yN,此中yi
1,
1
,表示xi的正确的
类型标签,i1,L,N,gj(xi
)表示第i副图像的第j
个特点值
2、训练集上样本的初始散布:D1
i
1
m
3、找寻弱分类器ht(t1,L,T)
⑴对于每个样本中的第
j个特点,能够获得一个弱分类器hj,即可
获得阈值j和方向pj,使得j
N
达到最小,而弱分类器
Dt(xi)hj(xi
)yi
i
1
hj为:
hj(x)
1
pjgj
(x)
pjj
1
other
此中pj决定不等式的方向,
只有
1两种状况。
4、将全部特点(j)中精选出一个拥有最小偏差
t的弱分类器ht。
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
5、对全部的样本权重进行更新
Dt1
Dtiexptyihtxi
i
Zt
N
此中Zt是使Dt1(xi)
1得归一化因子。
i1
6、经过T轮训练获得T个最优的弱分类器,此时构成一个强分类
器;
T
Hfinalxsignthtx
t1
在Adaboost算法的弱学习中,将产生错误率为
1,
2L
T的弱分类
器。假如每个错误率
t
1
,则强分类器的总错误率
e2
(1-)
2
t
t
全部都从强分类器的错误率开始
第一权值更新
D
t
iexp
t
yh
x
exp
t
tyi
ht(xi)
exp
yi
f(xi)
Dt1i
it
i
Zt
mtZt
m
Zt
t
此中
(
)
()
fxi
t
thtx
而后强分类器的错误率
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
1
trainingerror(H)
N
1
N
1
N

1ifyiH(xi)
0else
1ifyif(xi)0
0else
exp(yif(xi))
i
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
Dt1(i)Zt
it
使这个错误率迅速降落?
ZtDt(i)exp(tyiht(xi))
i
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
Zt为归一化因子。
转变为求Zt的最小值了!
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
Zt

Dt(xi

)exp(

tyiht

(xi))
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
i
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
Dt

(xi)exp(

t)

Dt

(xi)exp(

t)
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
i:yi

H(xi)

i:yi

H(xi)
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
(1

t)exp(

t)

texp(

t)
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
此时我们用贪婪算法求出Zt的一个局部最小值对Zt中的t求导[此时将t固定]
dZt
(1
t)exp(
t)
texp(t)
dt
令导数为零dZt
0解出
dt
t
1ln(1
t
)
2
t
此时
Zt2t(1t)
绘制Zt对于t的曲线图
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
从这幅图上我们能够看出,当错误率越小或许越大(只需不在中点处
彷徨)的时候Zt迅速收敛到0。
越小:说明错误越小的分类器能迅速辨别出正例。
越大:
说明错误越大的分类器也能迅速辨别出正例。
N
jDt(xi)hj(xi)yi
i1
既然最大,只需我把弱分类器取反,这样错误率就是最小,这样仍是收敛到0。
从以上的证明,我们知道只假如弱分类器的错误率都取最小,于是我们就能组合获得一个强分类器。
接下来我们就找出一个弱分类器h1(x)错误率1很小。找T个结合起来就获得了强分类器Hfinalx!
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
怎么找弱分类器?
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明
决议树ID3,,
ID3
生成树用(CIG类型属性增益法)

生成树用(GainRatio
增益比率法)
修剪树用(Rulepost-pruning
规则修剪)

生成树用(Giniindex
基尼指数)
修剪树用(CRAT回归树修剪)
而后给出YoavFreund
论文中给出的找寻方法
gj(x1),gj(x2)Lgj(xN)
排序
gj(x1),gj(x2)Lgj(xN)
令阈值
i
gj(xi)gj(xi1)
j
2
1
pjgj
(x)pj
j
,j
N
Dt(xi)hj(xi)yi
hj(x)
other
0
i1
Adaboost算法流程和证明
Adaboost算法流程和证明
Adaboost算法流程和证明