提升(boosting)方法是一种常用的统计学习方法。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。

  • 提升方法Adaboost算法
    • 提升方法基本思路
    • AdaBoost算法
    • Adaboost的例子
  • Adaboost算法的训练误差分析
  • Adaboost算法的解释
    • 前向分步算法
    • 前向分步算法与AdaBoost
  • 提升树
    • 提升树算法
  • 梯度提升

Valiant是哈佛大学的计算机科学家，他并不是唯一一位认为大脑与计算机之间基本等价的科学家。但是，他是最早正式研究二者关系的人之一：1984年，他的「可能近似正确模型 （probably approximately correct，PAC）」从数学上定义了一个机械系统在什么样的条件下可以被看做能够「学习」信息。由于Valiant的贡献有助于机器学习理论的进步，因此他赢得了图灵奖——这个奖通常被称为计算机界的诺贝尔奖。
提升方法-编程知识网

提升方法Adaboost算法

提升方法基本思路

在概率近似正确的框架（PAC）中
强可学习：
对于一个概念，如果存在一个多项式的学习算法能够学习它，且学习的正确率很高
弱可学习：
对于一个概念，如果存在一个多项式的学习算法能够学习它，且学习的正确率仅比随机猜测略好

一个概念是强可学习的充要条件是这个概念是弱可学习的
Adaboost就是将弱转化为强的算法

AdaBoost算法

采取加权多数表决的方法——
加大分类误差率小的弱分类器的权值，反之减少

算法：
输入：训练数据集T,其中xi∈χ⊆Rn,yi∈Y={−1,+1}
输出：最终分类器G(x)
1)初始化权值分布
D1=(w11,...,w1i,...,w1n),w1i=1N,i=1,2,...,N
2)对m=1,2,...,M

(a)使用具有权值分布Dm的训练数据集学习，得到基本分类器
Gm(x):χ→{−1,+1}

(b)计算Gm(x)在训练数据集上的分类误差率
em=P(Gm(xi)≠y1)=∑Ni=1wmiI(Gm(xi)≠yi)

(c)计算Gm(x)的系数
αm=12log1−emem

(d)更新权值分布
Dm+1=(wm+1,1,...,wm+1,i,wm+1.N)
wm+1,i=wmiZmexp(−αmyiGm(xi))
这里，Zm是规范因子—使Dm+1成为一个概率分布
Zm=∑Ni=1wmiexp(−αmyiGm(xi))

3)构造基本分类器的线性组合
f(x)=∑Mm=1α,Gm(x)
得到最终分类器
G(x)=sign(f(x))=sign(∑Mm=1αmGm(x))

提升方法-编程知识网

Adaboost的例子

1）
下面，给定下列训练样本，请用AdaBoost算法学习一个强分类器。

提升方法-编程知识网

求解过程：初始化训练数据的权值分布，令每个权值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, …, 10，然后分别对于m = 1,2,3, …等值进行迭代。

迭代过程1：对于m=1，在权值分布为D1的训练数据上，阈值v取2.5时误差率最低，故基本分类器为：
提升方法-编程知识网

从而可得G1(x)在训练数据集上的误差率e1=P(G1(xi)≠yi) = 0.3
然后计算G1的系数：

提升方法-编程知识网

接着更新训练数据的权值分布：
提升方法-编程知识网

最后得到各个数据的权值分布D2=(0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)，分类函数f1(x)=0.4236G1(x)，故最终得到的分类器sign(f1(x))在训练数据集上有3个误分类点。

迭代过程2：对于m=2，在权值分布为D2的训练数据上，阈值v取8.5时误差率最低，故基本分类器为：

提升方法-编程知识网

G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.2143

计算G2的系数：

提升方法-编程知识网

更新训练数据的权值分布：
提升方法-编程知识网

D3=(0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)
f2(x)=0.4236G1(x) + 0.6496G2(x)

分类器sign(f2(x))在训练数据集上有3个误分类点。

迭代过程3：对于m=3，在权值分布为D3的训练数据上，阈值v取5.5时误差率最低，故基本分类器为：

提升方法-编程知识网

G3(x)在训练数据集上的误差率e3=P(G3(xi)≠yi) = 0.1820
计算G3的系数：

提升方法-编程知识网

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

提升方法-编程知识网

D4=(0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)，f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)，分类器sign(f3(x))在训练数据集上有0个误分类点。

上述Adaboost算法对分类器阈值的选择是暴力搜索法

2）垂直和水平直线作为分类器

Adaboost算法的训练误差分析

Adaboost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率

定理1：
Adaboost算法最终分类器的训练误差界为：
1N∑Ni=1I(G(xi)≠yi)⩽1N∑iexp(−yif(xi))=∏mZm

这个定理很有问题，我觉得应该这样！！
1N∑Ni=1P(G(xi)≠yi)⩽1N∑Ni=1P(f(xi)≠yi)⩽1N∑iexp(−yif(xi))=∏mZm
首先1N∑Ni=1I(G(xi)≠yi)并不能代表训练误差界
其次 G(xi)≠yi时候，f(xi)≠yi并不知道

定理2：
二分类问题AdaBoost的训练误差界
∏MmZm=∏Mm[2em(1−em)−−−−−−−−−√]=∏Mm(1−4γ2)−−−−−−−−√⩽exp(−2∑Mm=1γ2m)
这里,γm=12−em

推论：
如果存在 γ>0,对所有m有γm⩾γ，则
1N∑Ni=1I(G(xi)≠yi)⩽exp(−2Mγ2)
表明在此条件下AdaBoost的训练误差是以指数速率下降的！

AdaBoost算法不需要知道下界γ.它具有适应性，即能适应弱分类器各自的训练误差率，这也是它的名称（适应的提升）的由来，Ada是Adaptive的简写

Adaboost算法的解释

可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习方法为前向分步算法时的二分类学习方法

前向分步算法

考虑加法模型
f(x)=∑Mm=1βmb(x;γm)
b(x;γm)为基函数，γm为基函数的参数，βm为基函数的系数

损失函数L(y,f(x))下—损失函数具体自行定义
加法模型显然成为经验风险极小化即损失函数极小化问题：
minβm,γm∑Ni=1L(yi,∑Mm=1βmb(xi;γm))

通常这是个复杂的优化问题.前向分步算法的思想是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就能大大简化优化的复杂度.具体地：
minβ,γ∑Ni=1L(yi,βmb(xi;γ))

算法
输入：训练数据集T={...,(xi,yi),...};损失函数L(y,f(x));基函数集{b(x;γ)}
输出：加法模型f(x)
1)初始化f0(x)=0

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

a)极小化损失函数
(βm,γm)=argminβ,γ∑Ni=1L(yi,fm−1(xi)+βb(xi;γ))
得到参数βm,γm

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

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

前向分步算法与AdaBoost

可以由前向分布算法推导出AdaBoost

定理：AdaBoost算法是前向分步加法算法的特例！这时，模型由基本分类器组成的加法模型，损失函数是指数函数
思路：前向分步算法学习的是加法模型，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器
f(x)=∑Mm=1αmGm(x)
证明：
令b(x;γm)为Gm(x),βm为αm

令L(y,f(x))=exp[−yf(x)]

fm(x)=α1G1(x)+...+αm−1Gm−1(x)=fm−1(x)+αmGm(x)

则(αm,Gm(x))=argminα,G∑Ni=1exp[−yi(fm−1(xi)+αG(xi))]

又可表示为
(αm,Gm(x))=argminα,G∑Ni=1w¯miexp[−yiαG(xi)]
w¯mi=exp[−yifm−1(xi)]

由wm+1,i=wmiZmexp(−αmyiGm(xi))，知

w¯mi不依赖这一步的α和G，所以与最小化无关！

1）对G∗m(x)

G∗m(x)=argminα,G∑Ni=1exp[−yif(xi)]

设w¯mi=exp[−yifm−1(xi)]

因∑Ni=1exp[−yif(xi)]=∑Ni=1w¯miexp[−yiαG(xi)]⩾∑Ni=1w¯miP(G(xi)≠yi)⩾∑Ni=1w¯miI(G(xi)≠yi)

则G∗m(x)=argminα,G∑Ni=1w¯miI(G(xi)≠yi)—我不认为非常正确

2）对α∗m(x)
∑Ni=1w¯miexp[−yiαG(xi)]
=∑yi=Gm(xi)w¯mie−α+∑yi≠Gm(xi)w¯mieα
=(eα−e−α)∑Ni=1w¯miP(G(xi)≠yi)+e−α∑Ni=1w¯mi
⩾(eα−e−α)∑Ni=1w¯miI(G(xi)≠yi)+e−α∑Ni=1w¯mi

设em=∑Ni=1w¯miI(G(xi)≠yi)∑Ni=1w¯mi=∑Ni=1wmiI(G(xi)≠yi)

原式求导=0，得到：
αm=12log1−emem

2）最后对权值的更新
由fm(x)=fm−1(x)+αmGm(x)
以及w¯mi=exp[−yifm−1(xi)]

得:
w¯m+1,i=w¯m,iexp[−yiαmGm(x)]

这与AdaBoost 算法权值的更新只相差规范因子，因而等价

我并不认为等价，由上述极小化求参数的放缩可以看出

提升树

提升树是以分类树或回归树为基本分类器的提升方法.提升书被认为是统计学习性能最好的方法之一

提升树算法

提升树模型：
fM(x)=∑Mm=1T(x;θm)
其中，T(x;θm)表示决策树;θm为决策树的参数;M为树的个数

回归树:
已知训练数据集T,,xi∈χ⊆Rn
弱国讲输入控件χ划分为J个不相交的区域R1,R2,...,Rj,并且在每个区域上确定书的常量cj,那么树可表示为
T(x;θ)=∑Jj=1cjI(x∈Rj)
其中，参数θ={(R1,c1),...,(RJ,cJ)}表示树的区域划分和各区域上的常数，J是回归树的复杂度即叶结点个数

算法：
输入：训练数据集T={...,(xi,yi),...}，损失函数为平方损失
输出：提升树fM(x)
1)初始化f_0(x)=0

2)对m=1,2,…,M

a)计算残差rmi
rmi=yi−fm−1(xi),i=1,2,...,N

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

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

3)得到回归问题提升树
fM(x)=∑Mm=1T(x;θm)

例子：
提升方法-编程知识网
提升方法-编程知识网
提升方法-编程知识网

容易看出，其实就是对残差进行迭代加法拟合
之前的阈值与此例的切分点，都采取的是暴力搜索法，我不太喜欢

梯度提升

提升树利用加法模型与前向分步算法实现学习的优化过程。损失函数是平方损失和指数损失时，每一步优化很简单。但对于一般损失函数而言，并非如此容易。对此，Freidman提出了梯度提升算法.这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值
−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)
作为回归问题提升树算法中残差的近似值，拟合一个回归树

算法：
输入：T和L
输出：回归树f^(x)

1）初始化
f0(x)=argminc∑Ni=1L(yi,c)
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拟合一个回归树，得到第m课树的叶结点区域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)=∑Mm=1∑Jj=1cmjI(x∈Rmj)

损失函数的负梯度作为残差的估计，对于平方损失函数，它就是通常所说的残差，对于一般损失函数，它就是残差的近似值。
很奇怪
当L(y,f(x))=(y−f(x))2
rmi=−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)
则rmi=2(y−f(x)),并不是之前的残差！