paper（9）
?&&要明确Adaboost是一种算法。
?&&介绍一下Adaboost的历史。
Adaboost的前身的Boosting算法。
Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于Valiant提出的PAC(Probably Approximately Correct)学习模型。Valiant和Kearns提出了弱学习和强学习的概念,识别错误率小于1/2,也即准确率仅比随机猜测略高的学习算法称为弱学习算法;识别准确率很高并能在多项式时间内完成的学习算法称为强学习算法。同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题，即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法?如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。
1990年, Schapire最先构造出一种多项式级的算法,对该问题做了肯定的证明,这就是最初的Boosting算法。一年后,Freund提出了一种效率更高的Boosting算法。但是,这两种算法存在共同的实践上的缺陷,那就是都要求事先知道弱学习算法学习正确率的下限。
1995年, Freund和schapire改进了Boosting算法,提出了AdaBoost(Adaptive Boosting)算法[5],该算法效率和Freund于1991年提出的Boosting算法几乎相同,但不需要任何关于弱学习器的先验知识,因而更容易应用到实际问题当中。之后,Freund和schapire进一步提出了改变Boosting投票权重的AdaBoost.M1,AdaBoost.M2等算法,在机器学习领域受到了极大的关注。&
?&&Adaboost详解
Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。
其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训练数据特征，并将关键放在关键的训练数据上面。&& &
?&&在线训练阶段流程图：
最终出来的结构应该是这样的：
N级分类器，每个分类器带一个自己的阈值；N个分类器的权重比例；整个强分类器的阈值
?&&离线检测阶段流程图：
算法的流程理解了，可是要将这个算法完全自己实现，难度还是很大的。幸好已经有人做了这方面的工作。
1.&&&&&&如果要训练的是Haar特征，opencv的cvHaarTraining就足够了，什么adaboost，cascade，神马都不用管，按格式写好文件，等着结果就行了。
2.&&&&&&OPENCV的cvBoost，主要有这么几个函数
bool&(。。。);
CvBoost::load（。。。）
float CvBoost::predict（。。。）
opencv的sample中有一个多类分类的问题，可以参考一下，不过读文件那块写得真烂。。。
3.&&&&&&强烈推荐！！！GML AdaBoost Matlab Toolbox
莫斯科大学的一个学生写得，很赞。里面有三种adaboost的实现，详细的说明文档，Examples。而且检测部分有c++的源码及工程。
有兴趣的朋友们看看说明文档就一目了然了，very good!!!
这就是我对adaboost的理解~~~
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：16257次
排名：千里之外
原创：53篇
转载：23篇
(1)(1)(1)(7)(5)(22)(1)(11)(4)(1)(1)(2)(2)(4)(10)(3)(2)一、Boosting算法的发展历史
　　Boosting算法是一种把若干个分类器整合为一个分类器的方法，在boosting算法产生之前，还出现过两种比较重要的将多个分类器整合
为一个分类器的方法，即boostrapping方法和bagging方法。我们先简要介绍一下bootstrapping方法和bagging方法。
　　1）bootstrapping方法的主要过程
　　主要步骤：
　　i)重复地从一个样本集合D中采样n个样本
　　ii)针对每次采样的子样本集，进行统计学习，获得假设Hi
　　iii)将若干个假设进行组合，形成最终的假设Hfinal
　　iv)将最终的假设用于具体的分类任务
　　2）bagging方法的主要过程 &-----bagging可以有多种抽取方法
　　主要思路：
　　i)训练分类器
　　从整体样本集合中，抽样n*
针对抽样的集合训练分类器Ci
　　ii)分类器进行投票，最终的结果是分类器投票的优胜结果
　　但是，上述这两种方法，都只是将分类器进行简单的组合，实际上，并没有发挥出分类器组合的威力来。直到1989年，Yoav
Freund与 Robert
Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖（Godel price）。
　　Schapire还提出了一种早期的boosting算法，其主要过程如下：
　　i)从样本整体集合D中，不放回的随机抽样n1 & n个样本，得到集合
　　训练弱分类器C1
　　ii)从样本整体集合D中，抽取 n2 &
n个样本，其中合并进一半被C1
分类错误的样本。得到样本集合 D2
　　训练弱分类器C2
　　iii)抽取D样本集合中，C1 和 C2
分类不一致样本，组成D3
　　训练弱分类器C3
　　iv)用三个分类器做投票，得到最后分类结果
　　到了1995年，Freund and schapire提出了现在的adaboost算法，其主要框架可以描述为：
　　i)循环迭代多次
　　更新样本分布
　　寻找当前分布下的最优弱分类器
　　计算弱分类器误差率
　　ii)聚合多次训练的弱分类器
　　在下图中可以看到完整的adaboost算法：
图1.1& adaboost算法过程
　　现在，boost算法有了很大的发展，出现了很多的其他boost算法，例如：logitboost算法，gentleboost算法等等。在这次报告中，我们将着重介绍adaboost算法的过程和特性。
二、Adaboost算法及分析
　　从图1.1中，我们可以看到adaboost的一个详细的算法过程。Adaboost是一种比较有特点的算法，可以总结如下：
　　1）每次迭代改变的是样本的分布，而不是重复采样（re weight)
　　2）样本分布的改变取决于样本是否被正确分类
　　 & & &
& &总是分类正确的样本权值低
　　 & & &
& &总是分类错误的样本权值高（通常是边界附近的样本）
　　3）最终的结果是弱分类器的加权组合
　　 & & &
& &权值表示该弱分类器的性能
　　简单来说，Adaboost有很多优点:
　　1)adaboost是一种有很高精度的分类器
　　2)可以使用各种方法构建子分类器，adaboost算法提供的是框架
　　3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单
　　4)简单，不用做特征筛选
　　5)不用担心overfitting！
　　总之：adaboost是简单，有效。
　　下面我们举一个简单的例子来看看adaboost的实现过程：
　　图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。
　　第一步：
　　根据分类的正确率，得到一个新的样本分布D2-，一个子分类器h1
　　其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本做了加权。
　　第二步：
　　根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2
　　第三步：
　　得到一个子分类器h3
　　整合所有子分类器：
　　因此可以得到整合的结果，从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果，在例子中所有的。
　　Adaboost算法的某些特性是非常好的，在我们的报告中，主要介绍adaboost的两个特性。
一是训练的错误率上界，随着迭代次数的增加，会逐渐下降；
二是adaboost算法即使训练次数很多，也不会出现过拟合的问题。
　　下面主要通过证明过程和图表来描述这两个特性：
　　1）错误率上界下降的特性
　　从而可以看出，随着迭代次数的增加，实际上错误率上界在下降。
　　2）不会出现过拟合现象
　　通常，过拟合现象指的是下图描述的这种现象，即随着模型训练误差的下降，实际上，模型的泛化误差（测试误差）在上升。横轴表示迭代的次数，纵轴表示训练误差的值。
而实际上，并没有观察到adaboost算法出现这样的情况，即当训练误差小到一定程度以后，继续训练，返回误差仍然不会增加。
　　对这种现象的解释，要借助margin的概念，其中margin表示如下：
　　通过引入margin的概念，我们可以观察到下图所出现的现象：
　　从图上左边的子图可以看到，随着训练次数的增加，test的误差率并没有升高，同时对应着右边的子图可以看到，随着训练次数的增
加，margin一直在增加。这就是说，在训练误差下降到一定程度以后，更多的训练，会增加分类器的分类margin，这个过程也能够防止测试误差的上
三、多分类adaboost
　　在日常任务中，我们通常需要去解决多分类的问题。而前面的介绍中，adaboost算法只能适用于二分类的情况。因此，在这一小节中，我们着重介绍如何将adaboost算法调整到适合处理多分类任务的方法。
　　目前有三种比较常用的将二分类adaboost方法。
　　1、adaboost M1方法
　　主要思路： adaboost组合的若干个弱分类器本身就是多分类的分类器。
　　在训练的时候，样本权重空间的计算方法，仍然为：
　　在解码的时候，选择一个最有可能的分类
　　2、adaboost MH方法
　　主要思路：
组合的弱分类器仍然是二分类的分类器，将分类label和分类样例组合，生成N个样本，在这个新的样本空间上训练分类器。
　　可以用下图来表示其原理：
　　3、对多分类输出进行二进制编码
　　主要思路：对N个label进行二进制编码，例如用m位二进制数表示一个label。然后训练m个二分类分类器，在解码时生成m位的二进制数。从而对应到一个label上。
　　最后，我们可以总结下adaboost算法的一些实际可以使用的场景：
　　1）用于二分类或多分类的应用场景
　　2）用于做分类任务的baseline
&无脑化，简单，不会overfitting，不用调分类器
　　3）用于特征选择（feature selection)
　　4）Boosting框架用于对badcase的修正
&只需要增加新的分类器，不需要变动原有分类器
　　由于adaboost算法是一种实现简单，应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器，同时具有分类错误率上界随着训练增加而稳定下降，不会过拟合等的性质，应该说是一种很适合于在各种分类场景下应用的算法。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。HOG特征+adaboost算法，应该选择何种弱分类器？
[问题点数：35分，结帖人hondef]
HOG特征+adaboost算法，应该选择何种弱分类器？
[问题点数：35分，结帖人hondef]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
本帖子已过去太久远了，不再提供回复功能。adboost, NN 等分类器模型介绍_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
adboost, NN 等分类器模型介绍
上传于||暂无简介
大小：11.72MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢1010人阅读
机器学习&数据挖掘（5）
1、算法简介：
&&&&&& AdaBoost（Adaptive Boosting）算法是一种原理简单的有监督的机器学习算法。它的发展与一个非常有趣的理论有关，即强学习算法与弱学习算法的等价性问题，能否使用弱分类器和多个实例来构建一个强分类器。这里的“弱”是指分类器的性能比随机猜测略好，但也不会好太多；而“强”是指识别错误率很高并能在多项式时间内完成。可以分析的是，如果以上猜想成立，即二者等价，那么只需找到一个弱分类器，就可以构建出我们所期望的强分类器。AdaBoost算法正是脱胎于以上理论。而本文介绍的知识最流行的一个版本的AdaBoost。
2、原理介绍：
&&&&&& AdaBoost算法是基于迭代思想，针对同一个训练集，训练不同的弱分类器，然后统筹各个弱分类器的结果，构成一个强分类器。
其具体实现是这样的：首先对于训练数据的每个样本，会分配一个权重（权重和为1，初始化为相等值，每个样本的权重会随训练过程而改变），对于每次的弱分类器的训练，该分类器会对样本产生相应的预测值，进一步的基于权重求和得到错误率（预测错误的样本的权重和），基于错误率会计算得到该若分类器在最后的强分类器的权重，错误率越高，其权重自然越低，计算公式下文会具体说明。而以上说到的样本的权重，会在每次预测之后加以修改，算法降低分类正确的样本的权重，而提高分类错误的样本的权重。几个关键的需要注意的因素就是每次训练中样本权重向量的计算更新（下文会说明更新方式），每个弱分类器的分类错误率，每个弱分类器在最终强分类器的比重。
&& AdaBoost算法不断重复训练，每次更新权重向量直到训练错误率为0或弱分类器数目达到用户指定值为止。
3、算法实现：
1）给定训练集：，其中&，表示（样本特征向量）的正确的类别标签，；
2）初始化样本权重向量：
3）寻找弱分类器：
对于每个样本中的第j个特征，可以得到一个弱分类器，即可得到阈值和方向，使得达到最小，而弱分类器为：
其中决定不等式的方向, 只有+1和-1两种情况
4）将所有特征(j)中挑选出一个具有最小误差的弱分类器，即为本轮训练中所需要的弱分类器，计算该弱分类器在最终的强分类器中所占的权重：
5）对所有的样本权重进行更新：
其中是归一化因子，使。
对于上式进一步说明，我们前面提到，对于正确分类的样本会降低其权重，错误分类的样本会增大其权重，通过以上式子即可实现。注意到对于分类正确的样本，分类错误的样本，则对于正确的样本有：
错误的样本有：
经分析知道，分别可以达到降低与增大权重的效果。
6）重复以上步骤直到算法终止，得到每轮训练中最优的弱分类器，此时基于每次迭代的弱分类器及其权重组成一个强分类器：
至此算法步骤描述完毕。
4、算法分析
AdaBoost算法的优点可以概括如下：
泛化错误率低，即分类准确度较高；容易编码实现；可以应用于大部分分类器上，其子分类器可以是任意分类器，而AdaBoost只是基于子分类器搭建的框架。
然而另一方面，AdaBoost也存在对离群点敏感的问题。
AdaBoost主要应用解决：两类问题、多类单标签问题、多类多标签问题、大类单标签问题，回归问题。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：70250次
积分：1614
积分：1614
排名：第17123名
原创：94篇
(1)(1)(22)(4)(2)(9)(1)(30)(4)(19)(4)(4)(1)}