提升方法之AdaBoost、提升树（GBDT）

引言

提升方法是一种常用的学习方法（确切来说是一种基于统计的学习方法），并且广泛有效，基本思想是：不需针对学习任务（分类或者回归，为叙述方便，后文中以分类为例）直接学习出一个模型，而是先学习出一个模型，对样本进行分类，在该模型无法准确分类的样本上学习第二个模型，以此类推，直到所有样本都被准确的分类，最终的模型是将之前学习到的模型进行线性组合，可看做是“分而治之”的思想。

AdaBoost

强弱学习器

强学习器亦叫做强可学习：是指一个模型针对学习任务结果具有很高的准确性；

弱学习器亦叫做弱可学习：是指一个模型针对学习任务的结果比随机猜测的准确性好。

所以提升方法中学习到的一系列学习器都是弱学习器，那为什么不直接学习出强学习器，反而要去学习一些准确性不高的弱学习器呢？因为困难啊，很多任务无法或者很困难去学习出一个好的强学习器，我们就退而求其次，先学习出一些弱学习器，明显，学习出一个弱学习器比学习出一个强学习容易得多得多啊！然后想办法将这些弱学习器提升成强学习器，这也就是提升方法这个名词的由来，在提升方法中，下一轮关注的样本始终是上一次学习器未能准确分类的样本集合，为了使这些样本在下一轮的学习中获得更多关注，往往我们会加大这些错误分类样本的权重，使之受到更大的重视程度，而降低已经被正确分类的样本权重。

AdaBoost算法

不是一般性，我们这里考虑一个二分问题。假定一个二分训练数据集：

T={(x1,y1),(x2,y2)...(xn,yn)}

其中， x∈χ∈Rn , y∈{−1,+1} , χ 是实例空间， y 是标记(label)，AdaBoost按照一下算法步骤完成一系列弱学习器的学习，并进行线性组合提升为强学习其。

AdaBoost算法步骤：

输入： 训练集{(x_1,y_1),(x_2,y_2)...(x_n,y_n)}
     弱学习器法
输出： 最终分类器G(x)
(). 初始化训练样本的权值(weight)分布
    D_1 = (w_11, ... w_1i,...w_1N), w1i=/N, i=,,..N
(). 对m=,..,M
   a.使用具有训练权值分布Dm的训练数据集学习，得到基本分类器：
           G_m(x)->{-,+}
   b.计算Gm(x)在训练数据集上的分类错误率
           e_m=P(G_m（x_i)!=y_i)=sum(w_mi*I(G_m(xi)!=y_i))
   c.计算G_m(x)的系数
           a_m=/*log((-e_m)/e_m)
   d.更新训练权值
           D_m+=(w_m+1_,w_m+1_i,...,w_m+1_N)
           w_m+1_i=(w_mi/Z_m)exp(-a_m*y_i*G_m(x_i))
     这里Z_m是规范化因子
           Zm=SUM(w_mi*exp(-a_m*y_i*G_m(x_i))
(). 构建线性组合
           f(x)=sum(a_m*G_m(x))
得到最终的分类器：
           G(x)=sign(f(x))=sign(sum(a_m*G_m(x)))

           

步骤分析：

step1 . 初始化权重为均匀分布，表示所有的样本在初始化时的作用是一样的；

step2 . 对M个学习器进行学习，每一步包括一下内容：

a . 通过加权样本学习到本轮学习器 Gm(x)

b . 计算学习器 Gm(x) 的错误率 em=p(Gm(xi)≠yi)=∑Gm(xi)≠yiwmi

可见，错误率是所有学习器学习结果与标记结果不等的样本权重之和。

c . 计算 Gm 系数 αm , αm 表示 Gm 在最终模型中的重要性，注意到 αm 的计算方法： αm=12log1−emem

当 em≤12 时， αm≥0 , 并且 αm 随着 em 的减小而增大，也就是说，错误率越低的学习器在最后的模型中占有比较大的权重。

d . 更新权重，为下一个学习器 Gm+1 做准备。

step3 . 归一化学习器权重 αm ，并把 Gm(x) 加入到已有的模型中，作为最后模型的组成部分。

前向分步式算法

考虑AdaBoost的模型可表示为: ∑m=1Mβmb(x;γm)

b(x;γm) 表示基学习器， γm 表示学习器自身的参数， βm 表示学习器的权重。显然，这是一个加法模型。在给定损失函数 L(y,f(x)) 的条件下，学习加法模型的 f(x) 的应当满足经验风险最小化即损失函数最小化： minβm,γm∑i=1NL(yi,∑m=1Mβmb(xi;γm))

如果直接求解问题是比较困难的，注意到模型是一个加法模型，那么大可以将模型的求解转化到每一步加法中，只需要在每一学习器学习的过程中，使损失函数最小，则最后总体的损失函数也便是最小的。具体来说，每一步只需要最小化下面的损失函数： minβ,γ∑i=1NL(yi,βb(x;y))

这边是前向分步式算法。 前向分步式算法的一般步骤如下：

> input: 训练集 T={(x1,y1),(x2,y2)...(xn,yn)} ，损失函数 L(y,f(x)) ,基函数集 {b(x:γ)}

> output: 加法模型 f(x)

> (1). 初始化 f0(x)=0

> (2). 对 m=1,2,...,M :

> a. 极小化损失函数 (βm,γm)=argminβ,γ∑i=1NL(yi,fm−1(xi)+βb(xi;γ))

得到参数 βm,γm

> b. 更新： fm(x)=fm−1(x)+βmb(x;γm)

> (3). 得到加法模型： f(x)=fM(x)=∑m=1Mβmb(x;γm)

AdaBoost其实就是特殊的前向分步算法，用到的损失函数是指数函数。具体证明请参考相关资料(《统计学习方法》 李航）。

提升树模型（GBDT）

提升树是以决策树为基学习器的加法模型，在分类问题时用的是二叉分类树，在回归问题时用的二叉回归树，最简单的回归树可看做是一个根节点连接的左右子树的二叉树，即所谓的决策树桩。提升树的模型可表示为：

fM(x)=∑m=1MT(x;θm)

其中， T(x;θm)表示决策树， \theta_m 是决策树的参数， M$是决策树的数量。

提升树算法

由于提升树是加法模型，则依然可以用前向分步式算法进行模型的求取，首先确定 f0(x)=0 ，第 m 步的模型可表示为：

fm(x)=fm−1(x)+T(x;θm)

通过经验风险最小化确定下一棵树的参数 θm 。

θ∗m=argminθm∑i=1NL(yi,fm−1(xi)+T(xi;θm)

对于分类问题，只需要将上述的AdaBoost的基学习器限定为二分类树，其余的和上述的AdaBoost内容无差。对于回归问题，可看做是对输入空间 χ 划分为 J 个不相交的区域，在每个区域上输出的常量为Cj，那么树可以表示为：

T(x;θ)=∑j=1JCjI(x∈Rj)

其中 θ={(R1,C1),(R2,C2),...,(RJ,CJ)} 表示树的区域和区域上的常数， J 表示区域的个数。对于回归树的前向分步式算法有：f0(x)=0

fm(x)=fm−1(x)+T(x;θ),m=1,2,...,M

fM(x)=∑m=1MT(x;θm)

在前向分步式算法的第 m 步，给定m−1步的情况，需要求解： θ∗m=argminθm∑i=1NL(yi,fm−1(xi)+T(xi;θm)

得到第 m 颗树的参数。这里我们采用平方误差拟合回归问题，则：L(y,f(x)=(y−f(x))2

其损失变为： L(y,fm−1(x)+T(x;θm))=[y−fm−1(x)−T(x:θm)]2

=[r−T(x;θm)]2

其中 r=y−fm−1(x) ,是当前拟合的残差，而目前我们的学习任务也仅仅是拟合这个残差,整个算法的步骤：

(1). 初始化$f_0(x)=0

(2). 对 m=1,2,..,M :

a . 计算残差 r=y−fm−1(x)

b . 拟合残差，学习一个回归树，得到 T(x;θm)

c . 更新 fm(x)=fm−1(x)+T(x;θm)

(3). 得到回归提升树

fM(x)=∑m=1MT(x;θm)

梯度提升方法

前面用到的损失函数都有比较好的性质，如平方误差、指数函数等，但对于一般的函数来说，问题可能会变得复杂些，针对这一问题Freidman提出了梯度提升（Gradient Boosting），这是利用最速下降的近似方法，其关键是利用损失函数的负梯度在当前模型的值

−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)

作为近似残差，拟合一个回归树。

算法步骤：

(1). 初始化

f0(x)=argminc∑i=1NL(yi,c)

(2). 对 m=1,2,..,M :

a . 对于 i=1,2,...,N , 计算 rmi=−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)

b . 拟合 rmi ，学习一个回归树的叶节点区域 Rmj,j=1,2,...,J

c . 对 j=1,2,...,J 计算 Cmj=argminc∑xi∈RmjL(yi,fm−1(xi)+C)

d . 更新 fm(x)=fm−1(x)+∑Jj=1CmjI(x∈Rmj)

(3). 得到回归树： f(x)∗=fM(x)=∑m=1M∑j=1JCmjI(x∈Rmj)

参考文献

[1] 《统计学习方法》李航

[2].http://www.jianshu.com/c/415a64b18dcc?utm_source=desktop&utm_medium=notes-included-collection