集成学习 (Ensemble Learning)通过构建并结合多个学习器来完成学习任务,有时也被称为多分类器系统( Multi-classifier System)、基于委员会的学习( Committee-based Learning)等。
上图显示出集成学习的一般结构:先产生一组“个体学习器”),再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生,例如C4.5决策树算法、BP神经网络算法等,此时集成中只包含同种类型的个体学习器,例如“决策树集成”中全是决策树,“神经网络集成”中全是神经网络,这样的集成是“同质”
的。同质集成中的个体学习器亦称“基学习器”,相应的学习算法称为“基学习算法”。集成也可包含不同类型的个体学习器,例如同时包含决策树和神经网络,这样的集成是“异质”的。异质集成中的个体学习器由不同的学习算法生成,这时就不再有基学习算法;相应的,个体学习器一般不称为基学习器,常称为“组件学习器”或直接称为个体学习器。
集成学习通过将多个学习器进行结合,常可获得比单一学习器显著优越的泛化性能这对“弱学习器”尤为明显,因此集成学习的很多理论研究都是针对弱学习器进行的,而基学习器有时也被直接称为弱学习器。但需注意的是,虽然从理论上来说使用弱学习器集成足以获得好的性能,但在实践中出于种种考虑,例如希望使用较少的个体学习器,或是重用关于常见学习器的一些经验等,人们往往会使用比较强的学习器。在一般经验中,如果把好坏不等的东西掺到一起,那么通常结果会是比最坏的要好一些,比最好的要坏一些。但在集成学习中,把多个学习器结合起来,能获得比最好的单一学习器更好的性能。
考虑一个简单的例子:在二分类任务中,假定三个分类器在三个测试样本上的表现如下图所示,其中√表示分类正确,×表示分类错误,集成学习的结果通过投票法产生,即“少数服从多数”,在下图(a)中,每个分类器都只有66.6%的精度,但集成学习却达到了100%;在下图(b)中我们可以看到,三个分类器没有差别,集成之后性能没有提高;在下图(c)中,每个分类器的精度都只有33.3%,集成学习的结果变得更糟。这个简单的例子显示出:要获得好的集成,个体学习器应“好而不同”,即个体学习器要有一定的“准确性”,即学习器不能太坏,并且要有“多样性”,即学习器间具有差异。
考虑二分类问题
y
∈
{
1
,
−
1
}
y\in\{1, -1\}
y∈{1,−1}和真实函数
f
f
f,假定基分类器的错误率为
ϵ
\epsilon
ϵ,即对每个基分类器
h
i
h_i
hi有:
P
(
h
i
(
x
)
≠
f
(
x
)
)
=
ϵ
P(h_i(x)\neq f(x))=\epsilon
P(hi(x)=f(x))=ϵ
假设集成通过简单投票法结合
T
T
T个基分类器,若有超过半数的基分类器正确,则集成分类就正确:
H
(
x
)
=
sign
(
∑
i
=
1
T
h
i
(
x
)
)
H(x)=\text{sign}(\sum_{i=1}^Th_i(x))
H(x)=sign(i=1∑Thi(x))
假设基分类器的错误率相互独立,则由 Hoeffding不等式可知,集成的错误率为:
P
(
H
(
x
)
≠
f
(
x
)
)
=
∑
k
=
0
⌊
T
2
⌋
(
T
k
)
(
1
−
ϵ
)
k
ϵ
T
−
k
≤
e
−
1
2
T
(
1
−
2
ϵ
)
2
P(H(x)\neq f(x))=\sum_{k=0}^{\lfloor\frac{T}{2}\rfloor}\binom{T}{k}(1-\epsilon)^k\epsilon^{T-k}\leq e^{-\frac{1}{2}T(1-2\epsilon)^2}
P(H(x)=f(x))=k=0∑⌊2T⌋(kT)(1−ϵ)kϵT−k≤e−21T(1−2ϵ)2
上式显示出,随着集成中个体分类器数目 T T T的增大,集成的错误率将指数级下降,最终趋向于零然而我们必须注意到,上面的分析有一个关键假设:基学习器的误差相互独立。在现实任务中,个体学习器是为解决同一个问题训练出来的,它们显然不可能相互独立。事实上,个体学习器的“准确性”和“多样性”本身就存在冲突。一般的,准确性很高之后,要增加多样性就需牺牲准确性。事实上,如何产生并结合“好而不同”的个体学习器,恰是集成学习研究的核心根据个体学习器的生成方式,目前的集成学习方法大致可分为两大类,即体学习器间存在强依赖关系、必须串行生成的序列化方法,以及个体学习器间不存在强依赖关系、可同时生成的并行化方法;前者的代表是 Boosting,后者的代表是 Bagging。