本文证明分类问题使用集成学习方法的有效性。

设有集成模型

HT(x)={1if ht>01if ht0

T 表示基分类器的个数。每个基分类器

ht(x)={1if x 判别为正类1if x 判别为负类,t=1,,T

每个基分类器分类错误的概率为

P(ht(x)f(x))=εt

由于每个基分类器的分类性能大致相等,为化简起见,我们令所有基分类器的分类错误概率均为 ε<0.5 (弱可学习器).

C(HT(x)) 表示集成模型中,基分类器分类正确的数量,则根据二项分布有

P(C(HT(x))k)=ki=1CiT(1ε)iεki

上式表示分类正确的基分类器数量在 k 范围内的概率。

为方便起见,集成模型的基分类器个数 T 为偶数。因此,当 kT2 时,集成模型分类错误,其误分类概率为

P(C(HT(x))T2)=T2i=1CiT(1ε)iεki

现在我们要评估这个概率的上限。根据 Hoeffding’s inequality ,有

P(C(HT(x))(ελ)T)exp(2λ2T)

(ελ)T=T2 代入上式消去 λ ,有

P(C(HT(x))T2)exp(12(12ε)2T)

也就是说,随着基分类器数量的增加,集成模型的误分类概率呈指数下降。那么,我们只需要证明集成模型的误分类概率小于基分类模型的即可

P(C(HT(x))T2)exp(12(12ε)2T)<P(ht(x)f(x))=ε

即,

exp(12(12ε)2T)<ε

化简有,

T>2lnε(12ε)2

易知,任给 ε(0,0.5) ,总能找到恰当的 T 使上式成立。也就是说如果基分类器的分类正确率在 (0.5,1) 区间,模型集成是有效的。

Q.E.D.

转载请包括本文地址:https://allenwind.github.io/blog/7464/

更多文章请参考:https://allenwind.github.io/blog/archives/