首页 > 代码库 > 图像算法研究---Adaboost算法具体解释

图像算法研究---Adaboost算法具体解释

本篇文章先介绍了提升放法和AdaBoost算法。已经了解的可以直接跳过。后面给出了AdaBoost算法的两个样例。附有详细计算过程。

1、提升方法(来源于统计学习方法)

  提升方法是一种经常使用的统计学习方法,应用十分广泛且有效。在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类的性能。

提升算法基于这样一种思路:对于一个复杂任务来说,将多个专家的推断进行适当的综合所得出的推断。要比当中不论什么一个专家单独的推断好。

实际上。就是“三个臭皮匠顶个诸葛亮”的道理。 
  历史上,Kearns和Valiant首先提出了“强可学习(strongly learnable)”和“弱可学习(weakly learnable)”的概念。指出:在概率近似正确(probably approximately correct,PAC)学习框架中,一个概念(一个分类)。假设存在一个多项式的学习算法可以学习它,而且正确率非常高,那么就称这个概念是强可学习的。一个概念,假设存在一个多项式的学习算法可以学习它,学习的正确率仅比随机推測略好,那么就称这个概念是弱可学习的。非常有趣的是Schapire后来证明强可学习与弱可学习是等价的。也就是说。在PAC学习的框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的。 
  这样一来,问题便成为。在学习中。假设已经发现了“弱学习算法”,那么是否能将它提升(boost)为“强学习算法”。大家知道,发现弱学习算法通常要比发现强学习算法easy得多。那么怎样详细实施提升,便成为开发提升方法时所要解决的问题。

关于提升方法的研究非常多,有非常多算法被提出。最具代表性的是AdaBoost算法(AdaBoost algorithm)。 
  对于分类问题而言。给定一个训练样本集,求比較粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)easy得多。提升方法就是从弱学习算法出发,重复学习。得到一系列弱分类器。然后组合这些分类器,构成一个强分类器。 
  这样。对于提升算法来说。有两个问题须要回答:一是在每一轮怎样改变训练数据的权值分布。二是怎样将弱分类器组合成为一个强分类器。

2、AdaBoost算法

  对于上一小节末尾提出的提升方法的两个问题。AdaBoost算法的做法是:1、提高那些被前一轮弱分类器错误分类样本的权值。而减少那些被正确分类样本的权值。

2、採用加权多数表决的方法。详细的。加大分类误差率小的弱分类器的权值。使其在表决中起较大的作用,减小分类误差大的弱分类器的权值,使其在表决中起较小的作用。

 
  以下给出AdaBoost算法的公式:

输入:训练数据集,当中;弱学习算法。 
输出:终于分类器G(x)。

 
(1)初始化训练数据的权值分布 
   


   注:第一次训练弱分类器时各个样本的权值是相等的。

 
(2)对m=1,2。…,M     注:这里是个循环 
(a)使用具有权值分布的训练数据集学习,得到基本分类器


(b)计算在训练集上的分类误差率

注::不等函数I值为1.相等函数值为0。 
(c)计算的系数
这里的对数是自然对数。注:显然的调单减函数。这里就解释了为什么对于没有正确分类的数据要加大权值。

 
(d)更新训练数据集的权值分布 


这里,是规范化因子 
它使成为一个概率分布。 
注:自已比較的表达式。会发现这里的就是在对进行归一化工作。

 
(3)构建基本分类器的线性组合

得到终于分类器

注:对于增大分类错误数据的权值和分类误差计算的说明:

1、的系数

表示在终于分类器中的重要性。由的表达式可知。当时, ,而且随着的减小而增大。所以分类误差越小的基本分类器在终于分类器中的作用越大。 
2、计算基本分类器在加权训练数据集上的分类误差率:
,这里。表示第m轮中第i个实例的权值,(由于权值利用进行了归一化)。这表明,在加权的训练数据集上的分类误差是被误分类杨蓓的权值之和,由此可以看出数据权值分布与基本分类器的分类误差率的关系。

3、AdaBoost算法实例

以下提供一个样例帮助大家理解上面的概念。

 
给定例如以下表所看到的的训练数据。

假设弱分类器由产生,其阈值使该分类器在 训练数据集上分类误差率最低。试用AdaBoost算法学习一个强分类器

序号12345678910
x0123456789
y111-1-1-1111-1

解:初始化数据权值分布


对m=1。 
(a)在权值分布为的训练数据上,阈值v取2.5时分类误差率最低。故基本分类器为

(b)显然序号为7、8、9数据产生了错误。在训练数据集上的误差率等于将这3个数据的权值相加,即

注:表示当不等于时 函数I()的值为1,等于时值为0。

这里仅仅有i=7,8,9时函数I值为1。其余为0。 
(c)计算的系数


(d)更新训练数据的权值分布:
分类器在训练数据集上有3个误分点。 
对m=2, 
(a)在权值分布为的训练数据上,阈值v取8.5时分类误差率最低。故基本分类器为

(b)显然序号为4、5、6数据产生了错误。

在训练数据集上的误差率等于将这3个数据的权值相加,即


注:表示当不等于时 函数I()的值为1,等于时值为0。

这里仅仅有i=4,5,6时函数I值为1,其余为0。 
(c)计算的系数


(d)更新训练数据的权值分布:
分类器在训练数据集上有3个误分点。 
对m=3, 
(a)在权值分布为的训练数据上。阈值v取5.5时分类误差率最低,故基本分类器为

(b)显然序号为1、2、3、10的数据产生了错误。

在训练数据集上的误差率等于将这4个数据的权值相加,即


注:表示当不等于时 函数I()的值为1,等于时值为0。这里仅仅有i=1,2,3,10时函数I值为1。其余为0。 
(c)计算的系数

(d)更新训练数据的权值分布:
分类器在训练数据集上有0个误分点。 
于是终于分类器为:

图像算法研究---Adaboost算法具体解释