Adaboost
什么是集成学习
在机器学习的有监督问题中，我们的目标是通过学习获得一个正确率很高的模型（强可学习）。但往往我们无法获得效果这么好的模型，只能得到一个学习率仅比随机猜测略好的模型（弱可学习）。Schapire证明，强可学习和弱可学习是等价的。因此，问题变成了，如何将我们容易获得的弱可学习模型变为强可学习模型。而集合学习便是这样一种方法，他通过多个弱可学习模型的组合得到一个强可学习模型。
集成学习主要分为以下几类：Bagging,Boosting和Stacking。
Bagging
Bagging是bootstrap aggregating的简写。在Bagging方法中，利用bootstrap方法从整体数据集中采取有放回抽样得到N个数据集，在每个数据集上学习出一个模型，最后的预测结果利用N个模型的输出得到，具体地：分类问题采用N个模型预测投票的方式，回归问题采用N个模型预测平均的方式。
Boosting
Boosting也是学习一系列弱可学习模型然后组成一个强可学习模型。与Bagging不同的是，Boosting通过改变训练数据的概率分布（训练数据的权值分布），学习出一系列弱可学习模型，再组合为一个强可学习模型。AdaBoost是其中最具代表性的，下文也将详细讲解。
Stacking
Stacking方法是指训练一个模型用于组合其他各个模型。首先我们先训练多个不同的模型，然后把之前训练的各个模型的输出为输入来训练一个模型，以得到一个最终的输出。理论上，Stacking可以表示上面提到的两种Ensemble方法，只要我们采用合适的模型组合策略即可。但在实际中，我们通常使用logistic回归作为组合策略。
Adaboost算法详解（针对分类问题）
基本思路
对于一个提升方法（Boosting），需要解决两个问题。
- 在每一轮如何改变数据的权值或概率分布；
- 如何将弱分类器组合成一个强分类器。
AdaBoost的做法是：
- 提高被上一轮弱分类器错误分类的样本的权值，降低那些被正确分类的样本的权值；
- 加大分类误差较小的弱分类器的权值，减小分类误差较大的弱分类器的权值。
AdaBoost算法
输入：训练数据集 $ T = \lbrace (x_1,y_1),(x_2,y_2),…,(x_n,y_n)\rbrace $ ，其中
x
i
∈
X
,
y
i
∈
Y
x_i \in X ,y_i \in Y
xi∈X,yi∈Y
输出： 最终弱分类器
G
(
x
)
G(x)
G(x) 。
步骤：
- 初始化训练集权值分布
D 1 = ( w 11 , w 12 , . . . , w 1 N ) , w 1 i = 1 N , i = 1 , 2 , 3... , N D_1 = (w_{11},w_{12},...,w_{1N}),\quad w_{1i} = \frac{1}{N} , \quad i = 1, 2,3...,N D1=(w11,w12,...,w1N),w1i=N1,i=1,2,3...,N - 对 m = 1,2,…,M(m = epoch)
(a) 使用具有权值分布的 D m D_m Dm训练数据集学习，得到弱分类器 G m ( x ) G_m(x) Gm(x)
(b) 计算 G m ( x ) G_m(x) Gm(x)在训练数据集上的分类误差 e m = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) e_m = \sum_{i=1}^{N}w_{mi}I(G_m(x_i)\neq y_i) em=i=1∑NwmiI(Gm(xi)=yi)
© 计算 G m ( x ) G_m(x) Gm(x)的系数 α m = 1 2 l o g 1 − e m e m \alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m} αm=21logem1−em
(d)更新数据集的权值分布 D m + 1 = ( w m + 1 , 1 , . . . w m + 1 , i , . . . w m + 1. N ) D_{m+1} = (w_{m+1,1},...w_{m+1,i},...w_{m+1.N}) Dm+1=(wm+1,1,...wm+1,i,...wm+1.N) w m + 1 , i = w m i Z m e x p ( − α m y i G m ( x i ) ) , i = 1 , 2 , , . . . , N w_{m+1,i}=\frac {w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)),\quad i=1,2,,...,N wm+1,i=Zmwmiexp(−αmyiGm(xi)),i=1,2,,...,N
其中， Z m Z_m Zm是规范因子：
Z m = ∑ i = 1 N w m i e x p ( − α m y i G m ( x i ) ) Z_m = \sum_{i=1}^{N}w_{mi}exp(-\alpha_my_iG_m(x_i)) Zm=i=1∑Nwmiexp(−αmyiGm(xi))
可以理解为 S o f t M a x SoftMax SoftMax的变形
- 构建弱分类器的线性组合
f
(
x
)
=
∑
m
=
1
M
α
m
G
m
(
x
)
f(x)=\sum_{m=1}^{M}\alpha_mG_m(x)
f(x)=m=1∑MαmGm(x)最终分类器即为：
G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ m = 1 M α m G m ( x ) ) G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_mG_m(x)) G(x)=sign(f(x))=sign(m=1∑MαmGm(x))
AdaBoost例子
数据集
| 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| y | 1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | -1 | -1 | 1 |
解： 初始化数据权值分布 D 1 = ( w 11 , w 12 , . . . , w 112 ) D_1 =(w_{11},w_{12},...,w_{112}) D1=(w11,w12,...,w112) w 1 I = 1 12 , i = 1 , 2 , . . . 12 w_{1I}=\frac{1}{12},i =1,2,...12 w1I=121,i=1,2,...12
对m=1
(1) 在
D
1
D1
D1的权值分布上，
v
v
v取3.5时分类误差率最低，所以
G
1
(
x
)
G_1(x)
G1(x)为：
G
1
(
x
)
=
{
1
,
x
<
3.5
−
1
,
x
>
3.5
G_1(x)=\begin{cases} \ \ \ 1,\quad x<3.5\\ -1, \quad x>3.5\\ \end{cases}
G1(x)={ 1,x<3.5−1,x>3.5
(2)
G
1
(
x
)
G_1(x)
G1(x)的误差率为
e
1
=
0.333
e_1=0.333
e1=0.333
(3) 计算
G
1
(
x
)
G_1(x)
G1(x)的系数：$\alpha_1 = \frac{1}{2}ln\frac{1-e_1}{e_1}=0.3465 $
(4) 更新权值分布
w
2
i
=
w
1
i
Z
1
e
x
p
(
−
α
1
y
i
G
1
(
x
)
)
,
x
=
1
,
2...
,
12
w_{2i}=\frac{w_{1i}}{Z_1}exp(-\alpha_1y_iG_1(x)),\quad x=1,2...,12
w2i=Z1w1iexp(−α1yiG1(x)),x=1,2...,12
D
2
=
(
w
21
,
w
22
,
.
.
.
,
w
212
)
D_2=(w_{21},w_{22},...,w_{212})
D2=(w21,w22,...,w212)
=
(
0.0625
,
0.0625
,
0.0625
,
0.0625
,
0.0625
,
0.0625
,
0.125
,
0.125
,
0.125
,
0.0625
,
0.0625
,
0.125
)
=(0.0625,0.0625,0.0625,0.0625,0.0625,0.0625,0.125,0.125,0.125,0.0625,0.0625,0.125)
=(0.0625,0.0625,0.0625,0.0625,0.0625,0.0625,0.125,0.125,0.125,0.0625,0.0625,0.125)
f
1
(
x
)
=
0.3465
G
1
(
x
)
f_1(x)=0.3465G_1(x)
f1(x)=0.3465G1(x)
分类器
G
1
(
x
)
G_1(x)
G1(x)在训练集上有三个误分类点。
对m=2
- 在
D
2
D2
D2的权值分布上，
v
v
v取9.5时分类误差率最低，所以
G
2
(
x
)
G_2(x)
G2(x)为：
G
2
(
x
)
=
{
1
,
x
<
9.5
−
1
,
x
>
9.5
G_2(x)=\begin{cases} \ \ \ 1,\quad x<9.5\\ -1, \quad x>9.5\\ \end{cases}
G2(x)={ 1,x<9.5−1,x>9.5
(2) G 2 ( x ) G_2(x) G2(x)的误差率为 e 2 = 0.3125 e_2=0.3125 e2=0.3125
(3) 计算 G 1 ( x ) G_1(x) G1(x)的系数：$\alpha_2 = \frac{1}{2}ln\frac{1-e_2}{e_2}=0.3942 $
(4) 更新权值分布 w 3 i = w 2 i Z 2 e x p ( − α 2 y i G 2 ( x ) ) , x = 1 , 2... , 12 w_{3i}=\frac{w_{2i}}{Z_2}exp(-\alpha_2y_iG_2(x)),\quad x=1,2...,12 w3i=Z2w2iexp(−α2yiG2(x)),x=1,2...,12 D 3 = ( w 。 21 , w 22 , . . . , w 212 ) D_3=(w_。{21},w_{22},...,w_{212}) D3=(w。21,w22,...,w212) = ( 0.0431 , 0.0431 , 0.0431 , 0.0948 , 0.0948 , 0.0948 , 0.0862 , 0.0862 , 0.0862 , 0.0948 , 0.0431 , 0.1896 ) =(0.0431, 0.0431, 0.0431, 0.0948, 0.0948, 0.0948, 0.0862, 0.0862, 0.0862, 0.0948, 0.0431, 0.1896) =(0.0431,0.0431,0.0431,0.0948,0.0948,0.0948,0.0862,0.0862,0.0862,0.0948,0.0431,0.1896) f 2 ( x ) = 0.3465 G 1 ( x ) + 0.3942 G 2 ( x ) f_2(x)=0.3465G_1(x)+0.3942G_2(x) f2(x)=0.3465G1(x)+0.3942G2(x)
分类器 G 2 ( x ) G_2(x) G2(x)在训练集上有三个误分类点。
对于m = 3,4,…重复迭代上述过程，直到 G m ( x ) G_m(x) Gm(x)没有误分类点。
最终分类器为
G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ m = 1 M α m G m ( x ) ) G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_mG_m(x)) G(x)=sign(f(x))=sign(m=1∑MαmGm(x))