Boosting算法简介

1、Boosting算法的发展历史

　　Boosting算法是一种把若干个分类器整合为一个分类器的方法，在boosting算法产生以前，还出现过两种比较重要的将多个分类器整合为一个分类器的方法，即boostrapping方法和bagging方法。咱们先简要介绍一下bootstrapping方法和bagging方法。git

　　1）bootstrapping方法的主要过程算法

　　主要步骤：bootstrap

　　i)重复地从一个样本集合D中采样n个样本api

　　ii)针对每次采样的子样本集，进行统计学习，得到假设H_iapp

　　iii)将若干个假设进行组合，造成最终的假设H_final框架

　　iv)将最终的假设用于具体的分类任务ide

　　2）bagging方法的主要过程性能

　　主要思路：学习

　　i)训练分类器测试

　　从总体样本集合中，抽样n^* < N个样本 针对抽样的集合训练分类器C_i

　　ii)分类器进行投票，最终的结果是分类器投票的优胜结果

　　可是，上述这两种方法，都只是将分类器进行简单的组合，实际上，并无发挥出分类器组合的威力来。直到1989年，Yoav Freund与 Robert Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而得到了2003年的哥德尔奖（Godel price）。

　　Schapire还提出了一种早期的boosting算法，其主要过程以下：

　　i)从样本总体集合D中，不放回的随机抽样n₁ < n 个样本，获得集合 D₁

　　训练弱分类器C₁

　　ii)从样本总体集合D中，抽取 n₂ < n 个样本，其中合并进一半被 C₁ 分类错误的样本。获得样本集合 D₂

　　训练弱分类器C₂

　　iii)抽取D样本集合中，C₁ 和 C₂ 分类不一致样本，组成D₃

　　训练弱分类器C₃

　　iv)用三个分类器作投票，获得最后分类结果

　　到了1995年，Freund and schapire提出了如今的adaboost算法，其主要框架能够描述为：

　　i)循环迭代屡次

　　更新样本分布

　　寻找当前分布下的最优弱分类器

　　计算弱分类器偏差率

　　ii)聚合屡次训练的弱分类器

　　在下图中能够看到完整的adaboost算法：

图1.1  adaboost算法过程

　　如今，boost算法有了很大的发展，出现了不少的其余boost算法，例如：logitboost算法，gentleboost算法等等。在此次报告中，咱们将着重介绍adaboost算法的过程和特性。

2、Adaboost算法及分析

　　从图1.1中，咱们能够看到adaboost的一个详细的算法过程。Adaboost是一种比较有特色的算法，能够总结以下：

　　1）每次迭代改变的是样本的分布，而不是重复采样（re weight)

　　2）样本分布的改变取决于样本是否被正确分类

　　老是分类正确的样本权值低

　　老是分类错误的样本权值高（一般是边界附近的样本）

　　3）最终的结果是弱分类器的加权组合

　　权值表示该弱分类器的性能

　　简单来讲，Adaboost有不少优势:

　　1)adaboost是一种有很高精度的分类器

　　2)可使用各类方法构建子分类器，adaboost算法提供的是框架

　　3)当使用简单分类器时，计算出的结果是能够理解的。并且弱分类器构造极其简单

　　4)简单，不用作特征筛选

　　5)不用担忧overfitting！

　　总之：adaboost是简单，有效。

　　下面咱们举一个简单的例子来看看adaboost的实现过程：

 

　　图中，“+”和“-”分别表示两种类别，在这个过程当中，咱们使用水平或者垂直的直线做为分类器，来进行分类。

　　第一步：

 

　　根据分类的正确率，获得一个新的样本分布D_2­，一个子分类器h₁

　　其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本作了加权。

　　第二步：

 

　　根据分类的正确率，获得一个新的样本分布D₃，一个子分类器h₂

　　第三步：

 

　　获得一个子分类器h₃

　　整合全部子分类器：

 

　　所以能够获得整合的结果，从结果中看，及时简单的分类器，组合起来也能得到很好的分类效果，在例子中全部的。

　　Adaboost算法的某些特性是很是好的，在咱们的报告中，主要介绍adaboost的两个特性。一是训练的错误率上界，随着迭代次数的增长，会逐渐降低；二是adaboost算法即便训练次数不少，也不会出现过拟合的问题。

　　下面主要经过证实过程和图表来描述这两个特性：

　　1）错误率上界降低的特性

 

 

 

 

　　从而能够看出，随着迭代次数的增长，实际上错误率上界在降低。

　　2）不会出现过拟合现象

　　一般，过拟合现象指的是下图描述的这种现象，即随着模型训练偏差的降低，实际上，模型的泛化偏差（测试偏差）在上升。横轴表示迭代的次数，纵轴表示训练偏差的值。

 

而实际上，并无观察到adaboost算法出现这样的状况，即当训练偏差小到必定程度之后，继续训练，返回偏差仍然不会增长。

　　对这种现象的解释，要借助margin的概念，其中margin表示以下：

　　经过引入margin的概念，咱们能够观察到下图所出现的现象：

 

 

　　从图上左边的子图能够看到，随着训练次数的增长，test的偏差率并无升高，同时对应着右边的子图能够看到，随着训练次数的增长，margin一直在增长。这就是说，在训练偏差降低到必定程度之后，更多的训练，会增长分类器的分类margin，这个过程也可以防止测试偏差的上升。

3、多分类adaboost

　　在平常任务中，咱们一般须要去解决多分类的问题。而前面的介绍中，adaboost算法只能适用于二分类的状况。所以，在这一小节中，咱们着重介绍如何将adaboost算法调整到适合处理多分类任务的方法。

　　目前有三种比较经常使用的将二分类adaboost方法。

　　一、adaboost M1方法

　　主要思路： adaboost组合的若干个弱分类器自己就是多分类的分类器。

　　在训练的时候，样本权重空间的计算方法，仍然为：

 

　　在解码的时候，选择一个最有可能的分类

 

　　二、adaboost MH方法

　　主要思路： 组合的弱分类器仍然是二分类的分类器，将分类label和分类样例组合，生成N个样本，在这个新的样本空间上训练分类器。

　　能够用下图来表示其原理：

 

 

　　三、对多分类输出进行二进制编码

　　主要思路：对N个label进行二进制编码，例如用m位二进制数表示一个label。而后训练m个二分类分类器，在解码时生成m位的二进制数。从而对应到一个label上。

4、总结

　　最后，咱们能够总结下adaboost算法的一些实际可使用的场景：

　　1）用于二分类或多分类的应用场景

　　2）用于作分类任务的baseline

　　无脑化，简单，不会overfitting，不用调分类器

　　3）用于特征选择（feature selection)

　　4）Boosting框架用于对badcase的修正

　　只须要增长新的分类器，不须要变更原有分类器

　　因为adaboost算法是一种实现简单，应用也很简单的算法。Adaboost算法经过组合弱分类器而获得强分类器，同时具备分类错误率上界随着训练增长而稳定降低，不会过拟合等的性质，应该说是一种很适合于在各类分类场景下应用的算法。

by sep yangfan