8.1 个体与集成
集合个体应该和而不同，
①和指个体学习器的泛化误差应该小于随机误差，以二分类问题为例，就是指误差
?
\epsilon
?<0.5
②不同指的是，个体学习器之间应该有所差异，这样集成学习才有意义
收敛条件的两个结论：
①个体学习器越多越好，能降低集成错误率
②
?
≠
\epsilon\neq
??= 0.5
8.2 Boosting
8.2.1Boosting介绍
Boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器的数目达到事先指定的指T，最终将这T个基学习器进行加权结合。
8.2.2AdaBoost算法
Boosting族最著名的代表是AdaBoost，其描述如下图所示，其中
y
i
∈
{
?
1
,
1
}
,
f
y_i\in\{-1,1\},f
yi?∈{?1,1},f是真值函数。
AdaBoost算法有多种推导方式，比较容易理解的是基于“加性模型”，即基学习的线性组合
H
(
x
)
=
∑
t
=
1
T
a
t
h
t
(
x
)
H(x)=\sum_{t=1}^{T}a_th_t(x)
H(x)=t=1∑T?at?ht?(x)
来最小化指数损失函数
?
exp
?
(
H
∣
D
)
=
E
x
～
D
[
e
?
f
(
x
)
H
(
x
)
]
\ell_{\exp}(H|D)=\mathbb{E}_{x\thicksim D}[e^{-f(x)H(x)}]
?exp?(H∣D)=Ex～D?[e?f(x)H(x)]
若
H
(
x
)
H(x)
H(x)令指数损失函数最小化，则考虑损失函数对其的偏导
?
?
exp
?
(
H
∣
D
)
?
H
(
x
)
=
1
2
l
n
P
(
f
(
x
)
=
1
∣
x
)
P
(
f
(
x
)
=
?
1
∣
x
)
,
\frac{\partial\ell_{\exp}(H|D)}{\partial H(x)}=\frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)},
?H(x)??exp?(H∣D)?=21?lnP(f(x)=?1∣x)P(f(x)=1∣x)?,因此，有
s
i
g
n
(
H
(
x
)
)
=
s
i
g
n
(
1
2
l
n
P
(
f
(
x
)
=
1
∣
x
)
P
(
f
(
x
)
=
?
1
∣
x
)
)
=
arg?max
?
y
∈
{
?
1
,
1
}
P
(
f
(
x
)
=
y
∣
x
)
sign(H(x))=sign(\frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)}) \\ =\argmax_{y \in\{-1,1\}}P(f(x)=y|x)
sign(H(x))=sign(21?lnP(f(x)=?1∣x)P(f(x)=1∣x)?)=y∈{?1,1}argmax?P(f(x)=y∣x)
这意味着sign(H(x))达到了贝叶斯最优错误率，换言之，若指数损失函数最小化。则分类错误率也将最小化；这说明指数损失函数是分类任务原本0/1损失函数的一致的替代损失函数。由于这个替代函数有更好的数学性质，例如他是连续可微函数，因此我们用它代替0/1损失函数。作为优化目标。
在AdaBoost算法中，第一个基分类器
h
1
h_1
h1?是通过直接将基学习算法用于初始数据分布而得；此后迭代地生成
h
t
h_t
ht?和
a
t
a_t
at?，当基分类器
h
t
h_t
ht?基于分布
D
t
D_t
Dt?产生后，该基分类器的权重
a
t
a_t
at?应使得
a
t
h
t
a_th_t
at?ht?最小化指数损失函数。
?
exp
?
(
a
t
h
t
∣
D
t
)
=
E
x
～
D
t
[
e
?
f
(
x
)
a
t
h
t
(
x
)
]
=
e
?
a
t
(
1
?
?
t
)
+
e
a
t
?
t
\ell_{\exp}(a_th_t|D_t)=\mathbb{E}_{x\thicksim D_t}[e^{-f(x)a_th_t(x)}]\\ =e^{-a_t}(1-\epsilon_t)+e^{a_t}\epsilon_t
?exp?(at?ht?∣Dt?)=Ex～Dt??[e?f(x)at?ht?(x)]=e?at?(1??t?)+eat??t?
其中
?
t
=
P
x
～
D
t
(
h
t
(
x
)
≠
f
(
x
)
)
.
\epsilon_t=P_{x\thicksim D_t}(h_t(x)\neq f(x)).
?t?=Px～Dt??(ht?(x)?=f(x)).考虑指数损失函数的导数
?
?
exp
?
(
a
t
h
t
∣
D
t
)
?
a
t
=
?
e
?
a
t
(
1
?
?
T
)
+
e
a
t
?
t
\frac{\partial\ell_{\exp}(a_th_t|D_t)}{\partial a_t}=-e^{-a_t}(1-\epsilon_T)+e^{a_t}\epsilon_t
?at???exp?(at?ht?∣Dt?)?=?e?at?(1??T?)+eat??t?
令其为零可得
a
t
=
1
2
l
n
(
1
?
?
t
?
t
)
a_t=\frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t})
at?=21?ln(?t?1??t??)
这恰是算法图中第六行的分类器权重更新公式。
AdaBoost算法在获得
H
t
?
1
H_{t-1}
Ht?1?之后样本分布将进行调整，使下一轮的基学习器
h
t
h_t
ht?能纠正
H
t
?
1
H_{t-1}
Ht?1?的一些错误.理想的
h
t
h_t
ht?能纠正
H
t
?
1
H_{t-1}
Ht?1?的全部错误，即最小化
?
exp
?
(
H
t
?
1
+
h
t
∣
D
)
=
E
x
～
D
t
[
e
?
f
(
x
)
(
H
t
?
1
(
x
)
+
h
t
(
x
)
)
]
=
E
x
～
D
t
[
e
?
f
(
x
)
H
t
?
1
(
x
)
e
?
f
(
x
)
h
t
(
x
)
]
\ell_{\exp}(H_{t-1}+h_t|D)=\mathbb{E}_{x\thicksim D_t}[e^{-f(x)(H_{t-1}(x)+h_t(x))}]\\=\mathbb{E}_{x\thicksim D_t}[e^{-f(x)H_{t-1}(x)}e^{-f(x)h_t(x)}]
?exp?(Ht?1?+ht?∣D)=Ex～Dt??[e?f(x)(Ht?1?(x)+ht?(x))]=Ex～Dt??[e?f(x)Ht?1?(x)e?f(x)ht?(x)]
注意到
f
2
(
x
)
=
h
t
2
(
x
)
=
1
f^2(x)=h_t^2(x)=1
f2(x)=ht2?(x)=1上式可用
e
?
f
(
x
)
h
t
(
x
)
e^{-f(x)h_t(x)}
e?f(x)ht?(x)的泰勒展开近似为
?
exp
?
(
H
t
?
1
+
h
t
∣
D
)
=
E
x
～
D
t
[
e
?
f
(
x
)
H
t
?
1
(
x
)
（
1
?
f
(
x
)
h
t
(
x
)
+
f
2
(
x
)
h
t
2
(
x
)
2
)
]
=
E
x
～
D
t
[
e
?
f
(
x
)
H
t
?
1
(
x
)
（
1
?
f
(
x
)
h
t
(
x
)
+
1
2
)
]
\ell_{\exp}(H_{t-1}+h_t|D)\\=\mathbb{E}_{x\thicksim D_t}[e^{-f(x)H_{t-1}(x)}（1-f(x)h_t(x)+\frac{f^2(x)h_t^2(x)}{2})]\\ =\mathbb{E}_{x\thicksim D_t}[e^{-f(x)H_{t-1}(x)}（1-f(x)h_t(x)+\frac{1}{2})]
?exp?(Ht?1?+ht?∣D)=Ex～Dt??[e?f(x)Ht?1?(x)（1?f(x)ht?(x)+2f2(x)ht2?(x)?)]=Ex～Dt??[e?f(x)Ht?1?(x)（1?f(x)ht?(x)+21?)]
于是，理想的基学习器
h
t
(
x
)
=
arg?max
?
h
?
exp
?
(
H
t
?
1
+
h
∣
D
)
=
arg?min
?
h
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
(
1
?
f
(
x
)
h
(
x
)
+
1
2
)
]
=
arg?max
?
h
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
f
(
x
)
h
(
x
)
]
=
arg?max
?
h
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
]
f
(
x
)
h
(
x
)
]
h_t(x)=\argmax_h\ell_{\exp}(H_{t-1}+h|D)\\ =\argmin_h\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t-1}(x)}(1-f(x)h(x)+\frac{1}{2})]\\ =\argmax_h\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t-1}(x)}f(x)h(x)]\\ =\argmax_h\mathbb{E}_{x\thicksim D}[\frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t-1}(x)}]}f(x)h(x)]
ht?(x)=hargmax??exp?(Ht?1?+h∣D)=hargmin?Ex～D?[e?f(x)Ht?1?(x)(1?f(x)h(x)+21?)]=hargmax?Ex～D?[e?f(x)Ht?1?(x)f(x)h(x)]=hargmax?Ex～D?[Ex～D?[e?f(x)Ht?1?(x)]e?f(x)Ht?1?(x)?f(x)h(x)]
注意到
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
]
\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t-1}(x)}]
Ex～D?[e?f(x)Ht?1?(x)]是一个常数。令
D
t
D_t
Dt?表示一个分布
D
t
(
x
)
=
D
(
x
)
e
?
f
(
x
)
H
t
?
1
(
x
)
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
]
D_t(x)=\frac{D(x)e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t-1}(x)}]}
Dt?(x)=Ex～D?[e?f(x)Ht?1?(x)]D(x)e?f(x)Ht?1?(x)?则根据数学期望的定义这等价于令
h
t
(
x
)
=
arg?max
?
h
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
]
f
(
x
)
h
(
x
)
]
=
arg?max
?
h
E
x
～
D
[
f
(
x
)
h
(
x
)
]
h_t(x)=\argmax_h\mathbb{E}_{x\thicksim D}[\frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t-1}(x)}]}f(x)h(x)]\\ =\argmax_h\mathbb{E}_{x\thicksim D}[f(x)h(x)]
ht?(x)=hargmax?Ex～D?[Ex～D?[e?f(x)Ht?1?(x)]e?f(x)Ht?1?(x)?f(x)h(x)]=hargmax?Ex～D?[f(x)h(x)]
由
f
(
x
)
,
h
(
x
)
∈
{
?
1
,
+
1
}
f(x),h(x)\in\{-1,+1\}
f(x),h(x)∈{?1,+1},有
f
(
x
)
h
(
x
)
=
1
?
2
∏
(
f
(
x
)
≠
h
(
x
)
)
f(x)h(x)=1-2∏(f(x)\neq h(x))
f(x)h(x)=1?2∏(f(x)?=h(x))
则理想的学习器
h
t
(
x
)
=
arg?max
?
h
E
x
～
D
[
∏
(
f
(
x
)
≠
h
(
x
)
]
h_t(x)=\argmax_h\mathbb{E}_{x\thicksim D}[∏(f(x)\neq h(x)]
ht?(x)=hargmax?Ex～D?[∏(f(x)?=h(x)]
由此可见，理想的
h
t
h_t
ht?将在分布
D
t
D_t
Dt?下最小化分类误差。因此弱分类器将基于分布
D
t
D_t
Dt?来训练，且针对
D
t
D_t
Dt?的分类误差应小于0.5，这在一定程度上类似“残差逼近”的思想。考虑到
D
t
D_t
Dt?和
D
t
+
1
D_{t+1}
Dt+1?的关系有
D
t
+
1
=
D
(
x
)
e
?
f
(
x
)
H
t
(
x
)
E
x
～
D
[
e
?
f
(
x
)
H
t
(
x
)
]
=
D
(
x
)
e
?
f
(
x
)
H
t
?
1
(
x
)
e
?
f
(
x
)
a
t
h
t
(
x
)
E
x
～
D
[
e
?
f
(
x
)
H
t
(
x
)
]
=
D
t
(
x
)
e
?
f
(
x
)
a
t
h
t
(
x
)
E
x
～
D
[
e
?
f
(
x
)
H
t
?
1
(
x
)
]
E
x
～
D
[
e
?
f
(
x
)
H
t
(
x
)
]
D_{t+1}=\frac{D(x)e^{-f(x)H_{t}(x)}}{\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t}(x)}]}\\ =\frac{D(x)e^{-f(x)H_{t-1}(x)}e^{-f(x)a_th_t(x)}}{\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t}(x)}]}\\ =D_t(x)e^{-f(x)a_th_t(x)}\frac{\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t-1}(x)}]}{\mathbb{E}_{x\thicksim D}[e^{-f(x)H_{t}(x)}]}
Dt+1?=Ex～D?[e?f(x)Ht?(x)]D(x)e?f(x)Ht?(x)?=Ex～D?[e?f(x)Ht?(x)]D(x)e?f(x)Ht?1?(x)e?f(x)at?ht?(x)?=Dt?(x)e?f(x)at?ht?(x)Ex～D?[e?f(x)Ht?(x)]Ex～D?[e?f(x)Ht?1?(x)]?
这恰是图中算法第七行的样本分布更新公式。
于是，我们从基于加性模型迭代式优化指数损失函数的角度推导出了AdaBoost算法。
?以上内容源于周志华《机器学习》（西瓜书），笔者以自己的理解写了这篇笔记，如有错误欢迎指正
?