提升方法AdaBoost算法学习笔记

前言

For xgboost：

为了好好学习xgboost，由于算法基础比较薄弱，曲线救国，从提升方法、提升树、GBDT一步步看起。手头有李航老师的《统计学习方法》以及周志华老师的西瓜书。对比来看，感觉李航老师的相对要好理解一些（步骤比较清晰，公式易懂，当然也有许多的不明白），周老师的西瓜书的算法介绍与公式推导更为直接（周老师喜欢用一些概率分布函数，公式抽象）。本文是依据《统计学习方法》一书做的AdaBoost算法学习笔记。

提升方法是一种统计学习方法，在分类问题中，通过改变训练样本的权重以及学习多个分类器，并将这些分类器进行线性组合，提高分类性能。因此AdaBoost算法是一种迭代型学习算法。

AdaBoost算法两大特点

1.针对训练样本，在每一轮学习过程中，对于前一轮分类错误的样本，在下一轮给予较大的权值使得该样本在下一次学习的过程中能获得分类器更多的关注。

2.针对多个弱分类器，AdaBoost采用加权多数表决的方法，即加大分类误差率小的弱分类器的权值，使其在分类表决中起较大的作用。

AdaBoost算法步骤

1.输入训练数据集：一个二分类的训练数据集，每个样本点由实例（x）与标记(y)组成，样本数为
N

从训练数据中学习一系列弱分类器，然后将这些弱分类器Gm(x)组合成一个强分类器G(x)。

2.初始化训练数据的权值分布Dm：最初每个样本的权值是相同的（w=1/N)

3.对（m=1,2,…,M）进行以下计算步骤

a.使用具有权值分布Dm的训练数据集学习，得到基本分类器

对于每个样本训练得出一个分类标签（-1或+1）。

b.计算Gm(x)在训练数据集上的分类误差率

即误分类样本的权值之和。

c.计算弱分类器Gm(x)的表决系数：这里的对数是自然对数

这个表决系数影响了该弱分类器Gm(x)在最终分类器中的表决作用。当分类误差率e<=1/2时，表决系数大于0，并且随着e的减少而增大；所以分类误差率越小的弱分类器在最终分类器中起的表决作用越大。

d.更新训练数据集的权值分布：.

其中Zm是规范化因子：这个规范因子不太明白，书上大致意思是使得Dm+1成为一个概率分布

权值分布更新也可表达成如下形式：

由上式可知，被误分类的样本的权值被扩大，正确分类的样本的权值则被缩小，相比而言（下式/上式）放大倍数为e/(1-e)。因此使得误分类样本在下一轮学习中起更大的作用，不改变所给的样本数据而不断改变权值分布。

4.构建弱分类器的线性组合：步骤2完成后得到M（m=1,2,…M）个弱分类器Gm(x)

得到最终的强分类器：

sign()为取符号函数：当x>0,sign(x)=1;当x=0,sign(x)=0;当x<0,sign(x)=-1;

注：f(x)中的表决系数之和并不为1，f(x)的符号决定了样本x的类别，f(x)的绝对值表示了分类的确信度。

AdaBoost算法的加法模型解释

1.前向分步算法：AdaBoost算法可以看做是一种前向分步加法算法（看作M个弱分类器的线性组合成的加法模型）

2.证明：AdaBoost算法，模型是由基本分类器组成的加法模型，损失函数是指数函数

a.AdaBoost算法的最终分类器为：

前向分步算法逐一学习基函数，这一过程与AdaBoost逐一学习基本分类器（m=1,2,…M）一致。

b.前向分步算法的损失函数是指数损失函数（exponential loss function）

时，其学习的具体操作等价于AdaBoost算法学习

假设经过m-1轮迭代前向分步算法已经得到：

在第m轮迭代得到：

最小化损失函数目标：

上式转化为：

因此原证明转换为证明使最小化函数达到最小时的两个参数与AdaBoost算法所得到的基本分类器Gm(x)(算法步骤3.a)与表决系数(算法步骤3.c)一致。

总结

比较粗略的学习了下AdaBoost算法和原理，对于算法步骤中的一些公式，能理解它的作用，但是还是不太清楚它为何是这样的（不知道作者当时是如何将那些奇妙思想转换成数学公式）,最后一节从前向分步算法的角度来分析好理解一些。同时还看了一下周老师西瓜书上相同章节的内容：

周老师对AdaBoost算法的步骤和推导跟直接一点，增加了一些细节和其它的理解。比如，在弱分类器的线性组合的时候说明了一下取符号细节：

此外还从偏差-方差角度进行了分析：