内容发布更新时间 : 2024/11/5 22:38:51星期一 下面是文章的全部内容请认真阅读。

第六章 提升算法

6.1 引言

当做重要决定时，大家可能都会考虑吸取多个专家而不是一个人的意见。机器学习处理问题时也是如此，这就是提升算法背后的思路，提升算法是对其它算法进行组合的一种方式，接下来我们将对提升算法，以及提升算法中最流行的一个算法AdaBoost算法进行介绍，并对提升树以及简单的基于单层决策树的Adaboost算法进行讨论。

提升方法是一种常用的统计学习方法，应用广泛且有效，在分类问题上，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。一个分类器在训练数据上能够获得比其他分类器更好的拟合，但是在训练数据外的数据集上却不能很好的拟合数据，这时就称为该分类器出现了过拟合（overfitting）。提升算法能够有效地防止过拟合现象的发生。

图1 过拟合现象示意图

提升算法是一种为了拟合自适应基函数模型（adaptive basis-function models, ABM）的贪心算法，自适应基函数模型可表达为：

f?X??w0??wm?m?X? （6-1）

m?1M其中，?m是一种分类算法或者回归算法，被称为弱分类器（weak learner）或者基分类器（base learner）。也可以表达为如下形式：

f(X)???mb(X;?m) （6-2）

m?1M提升算法的目的是对以下公式的优化：

min?L(yi,f(xi)) （6-3）

fi?1N?)称为损失函数（loss function）其中，L(y,y，f是ABM模型。不同的损失函数有着不同

的性质，对应不同的提升算法，如表1所示。

将(2)式代入(3)式可得如下表达式：

M??min?L?yi,??m?(xi;?m)? （6-4） ?m,?mi?1?m?1?N因为学习的是加法模型，如果能够从前向后，每一步只学习一个基分类器及其系数，那

么就可以简化优化的复杂度，具体推导过程如下所示：

?m,?mmin?L?yi,?m?(xi;?m)? （6-5）

i?1N表1 常见损失函数以及相应提升算法

名称 平方误差 绝对误差 指数损失 对数损失

损失函数

1(yi?f(xi))2 2yi?f(xi)

导数

yi?f(xi)

f*

算法 L2Boosting Gradient boosting AdaBoost LogitBoost

??y|xi?

sgn(yi?f(xi))

median(y|xi)

exp?yif(xi)

log1?e?yifi???yiexp?yif(xi)

???1logi21??i?1logi21??iN

??

yi??i

f0(X)?argmin?L(yi,f(xi;?)) （6-6）

?i?1(?m,?m)?argmin?L(yi,fm?1(xi)???(xi;?)) （6-7）

?,?i?1Nfm(X)?fm?1(X)??m?(X;?m) （6-8）

算法不进行回溯对参数进行修改，因此该算法称为前向分步算法。

6.2 AdaBoost算法

AdaBoost（Adaptive boosting）算法，也称为自适应提升算法。训练数据中的每个样本，并赋予其一个权重，这些权重构成向量D。一开始，这些权重都初始化为相等值，首先

在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。再次训练分类器的过程中，将会重新调整每个样本的权重，其中上一次分对的样本权重会降低，而上一次分错的样本权重会提高。

图2 AdaBoost算法示意图

xN,yN)}给定一个二类分类的训练数据集T?{(x1,y1),(x2,y2),,(，其中，每个样本点由实例

与标记组成，实例xi???Rn，标记yi?Y?{?1,?1}，?是实例空间，Y是标记集合。损失函数可以表达为：

Lm(?)??exp[?yi(fm?1(xi)???(xi))]??wi,mexp(??yi?(xi)) （6-9）

i?1i?1NN其中，wi,mexp(?yifm?1(xi))，yi???1,?1?，则可以有如下推导：

Lm(?)?e??1?errm1其中，?m?log2errmyi?(xi)??wi,m?e?Nyi?(xi)??wi,m?e??e?????wi,mI(yi??(xi))?e???wi,mi?1i?1NN （6-10）

?wI(y??(x))，errm?i?1i,mNimi，err称为分类误差率。则可以得到第

?i?1wi,mmm个分类器：

fm(X)?fm?1(X)??m?(X) （6-11）

计算第m+1个分类器的参数可以通过下式得到：

wi,m?1?wi,me??myi?m(xi)?wi,me?m(2I(yi??m(xi))?1)?wi,me2?mI(yi??m(xi))e??m （6-12）

总结起来Adaboost算法主要有以下7步。 1 wi?1N 2 for m?1:Mdo

3 Fit a classifier ?m(X) to the training set using weights w

?wI(y??(x))4 Compute errm?i?1i,mNimi

?i?1wi5 Compute ?m?log6 Set wi?wie?1?errm(?m?2?m) errmNmI(yi??m(xi))