1.简介
boosting本质即通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。
提升方法即从弱学习算法出发，得到一系列弱分类器，构成一个强分类器。
大多数提升方法通过改变训练数据的概率分布，针对不同的训练数据分布调用弱学习算法学习一系列弱分析器
2.核心问题
a.如何改变训练数据的权值或概率分布
b.如何将弱分类器组合成强分类器
a.提高前一轮弱分类器错误分类样本的权值，降低正确分类样本的权值。
b.采用加权多数表决的方法，加大分类误差率小的弱分类器的权值，减少误差率大的弱分类器的权值
3.Adaboost算法
- 输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) . . . ( x n , y n ) } T=\{(x_1,y_1),(x_2,y_2)...(x_n,y_n)\} T={(x1,y1),(x2,y2)...(xn,yn)}, y i ∈ { − 1 , 1 } y_i\in\{-1,1\} yi∈{−1,1}弱学习算法
- 输出：最终分类器G(x)
步骤： - 初始化训练数据的权值分布 D 1 D_1 D1，对每个数据加权重
- 使用具有权值分布Dm的训练数据集学习，得到基本分类器
- 计算 G m ( x ) G_m(x) Gm(x)在训练数据集上的分类误差率
- e m = ∑ 1 N P ( G ( x i ) ≠ y i ) = ∑ w m i I e_m=\sum^N_1{P(G(x_i)≠y_i)}=\sum{w_miI} em=∑1NP(G(xi)=yi)=∑wmiI
- 计算 G m ( x ) G_m(x) Gm(x)的系数
- α m = 1 2 l o g 1 − e m e m α_m=\frac{1}{2}log\frac{1-e_m}{e_m} αm=21logem1−em
- 更新训练数据集的权值分布（提高错误分布的权值，通过构造概率分布，使得错误分布的权值加大）
- 分布 Z m = ∑ w m i e x p ( − a m y i G m ( x i ) ) Z_m=\sum{w_{mi}exp(-a_my_iG_m(x_i))} Zm=∑wmiexp(−amyiGm(xi))
- w m + 1 , i = w m i Z m e x p ( − a m y i G m ( x i ) w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-a_my_iG_m(x_i) wm+1,i=Zmwmiexp(−amyiGm(xi)
- 构建基本分类器的线性组合(将弱分类器进行组合，使得分类效果越好的权重越大）
- f ( x ) = ∑ 1 M α m G m ( x ) f(x)=\sum^M_1{α_mG_m(x)} f(x)=∑1MαmGm(x)
4.AdaBoost算法的训练误差分析
1
N
∑
1
N
I
(
G
(
x
i
)
≠
y
i
)
≤
1
N
∑
e
x
p
(
−
y
i
f
(
x
i
)
)
=
∏
m
Z
m
\frac{1}{N}\sum^N_1I(G(x_i)≠y_i)\le\frac{1}{N}\sum{exp(-y_if(x_i))}=\prod_m{Z_m}
N1∑1NI(G(xi)=yi)≤N1∑exp(−yif(xi))=∏mZm
当为二分类问题时
∏
m
Z
m
=
∏
m
(
1
−
4
(
1
2
−
e
m
)
2
)
1
2
≤
e
x
p
(
−
2
∑
(
1
2
−
e
m
)
2
)
\prod_m{Z_m}=\prod_m{(1-4(\frac{1}{2}-e_m)^2)^\frac{1}{2}}\le{exp(-2\sum{(\frac{1}{2}-e_m})^2)}
∏mZm=∏m(1−4(21−em)2)21≤exp(−2∑(21−em)2)
如果存在γ使得所有
1
2
−
e
m
>
=
γ
\frac{1}{2}-e_m >=\gamma
21−em>=γ,则上界以指数速率下降，即训练误差以指数速率下降
5.新的解释
将AdaBoost模型认为是加法模型，损失函数为指数函数，学习算法为前向分步算法的二分类学习方法
5.1前向分步算法
- 输入：训练数据集T,损失函数L 以及基函数的集合{b(x;γ)}
- 输出：加法模型f(x)
- 初始化 f 0 = 0 f_0=0 f0=0
- 对m=1，2，…，M
- 极小化损失函数
- ( β m , γ m ) = a r g m i n β , γ ∑ L ( y i , f m − 1 ( x i ) + β b ( x i ; γ ) ) (\beta_m,\gamma_m)=arg min_{\beta,\gamma}\sum{L(y_i,f_{m-1}(x_i)+\beta{b}(x_i;\gamma))} (βm,γm)=argminβ,γ∑L(yi,fm−1(xi)+βb(xi;γ))得到参数
- 更新 f m ( x ) = f m − 1 ( x ) + β b ( x ; γ m ) f_m(x)=f_{m-1}(x)+\beta{b(x;\gamma_m)} fm(x)=fm−1(x)+βb(x;γm)
- 重复，直到得到加法模型
6.提升树
以决策树为基函数的提升方法称为提升树
回归问题的提升树即学习新的回归树以拟合残差，直到符合误差要求
梯度提升算法即利用损失函数在当前模型的负梯度值求得新树