AdaBoost算法原理

看了一下AdaBoost算法

提升方法

提升(Boosting)方法是一种常用的统计学习方法。是集成学习的一种子方法,集成学习通过构建并结合多个学习器来完成学习任务,有时也被称为多分类器系统、基于委员会的学习等。集成学习通过将多个学习器进行结合,常可获得比单一学习器显著优越的泛化性能。
对于一个复杂任务来说,将多个专家的判断进行适当的综合得出的判断会比其中任何一个判断要强。

一个分类,如果存在一个多项式算法能够学习他,并得到很高的正确率,那么这个算法称为强学习器,反之如果正确率只是稍大于随机猜测(50%),则称为弱学习器。在实际情况中,我们往往会发现弱学习器比强学习器更容易获得,所以就有了能否把弱学习器提升(boosting)为强学习器的疑问。

大多数boost方法会改变数据的概率分布(改变数据权值),具体而言就是提高前一轮训练中被错分类的数据的权值,降低正确分类数据的权值,使得被错误分类的数据在下轮的训练中更受关注;然后根据不同分布调用弱学习算法得到一系列弱学习器实现的,再将这些学习器线性组合,具体组合方法是误差率小的学习器会被增大权值,误差率大的学习器会被减小权值,典型代表adaboost算法。

AdaBoost算法

现在给定一个二分类训练集:

其中

算法步骤如下:

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

(2) 指定生成T个学习器,即进行t=1,2,…,T迭代。

(3)对于第t次迭代,根据前一次迭代得到的权值分布训练数据集,得到弱分类器

(4)计算在训练数据上的分类误差率:

(5)计算当前学习器的权值

这个权值是用在最后线性组合时乘在分类器前的,仔细观察这个函数式不难发现当时,,并且随着的减小而增大,也就是说分类误差越小分类器的权值越大,这里还可以看出可以看出权值分布Dt通过影响来影响了,这是Dt的第一个影响。

(6)更新权值分布更新式如下:

(7)构建最终的分类器

一个例子

给定数据集

0 1 2 3 4 5 6 7 8 9
1 1 1 -1 -1 -1 1 1 1 -1

数据集共有10条数据,根据x的输入得到的y可以分类两类。首先初始化权值分布,因为是第一轮,故所有样本的权重相同。

对m=1,

(a)当阈值2.5时分类误差率最低,基本分类器为:

(b)在训练集的误差率为

(c)计算系数

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

分类器在上有3个误分类点。

对m=2,
(a)当阈值8.5时分类误差率最低,基本分类器为:

(b)在训练集的误差率为

(c)计算系数

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

分类器在上有3个误分类点。

对m=3,
(a)当阈值5.5时分类误差率最低,基本分类器为:

(b)在训练集的误差率为

(c)计算系数

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

分类器在上有0个误分类点。
得到最终分类器

总结

Adaboost算法是可以看作模型为加法模型,损失函数为指数函数,学习算法为向前分布算法。
考虑加法模型

其中为基函数,为基函数参数,为基函数系数。

Adaboost算法优缺点

优点

(1)Adaboost提供一种框架,在框架内可以使用各种方法构建子分类器。可以使用简单的弱分类器,不用对特征进行筛选,也不存在过拟合的现象。

(2)Adaboost算法不需要弱分类器的先验知识,最后得到的强分类器的分类精度依赖于所有弱分类器。无论是应用于人造数据还是真实数据,Adaboost都能显著的提高学习精度。

(3)Adaboost算法不需要预先知道弱分类器的错误率上限,且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度,可以深挖分类器的能力。Adaboost可以根据弱分类器的反馈,自适应地调整假定的错误率,执行的效率高。

(4)Adaboost可以在不改变训练数据,只改变数据权值分布,使得数据在不同学习器中产生不同作用,类似于重采样。

缺点

在Adaboost训练过程中,Adaboost会使得难于分类样本的权值呈指数增长,训练将会过于偏向这类困难的样本,导致Adaboost算法易受噪声干扰。此外,Adaboost依赖于弱分类器,而弱分类器的训练时间往往很长。

Boost算法簇当中,Adaboost算法作为入门级算法,在平时使用中,GBDT(梯度提升树),xgboost和lightGBM等都是常用算法框架。

接下来回去看看其他传统机器学习十大算法再总结。