第六章 提升算法
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))