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

设有集成模型

HT(x)={1if ∑ht>0−1if ∑ht≤0

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)=k∑i=1CiT(1−ε)iεk−i

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

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

P(C(HT(x))≤T2)=T2∑i=1CiT(1−ε)iεk−i

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

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

取 (ε−λ)T=T2 代入上式消去 λ ，有

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

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

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

即，

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

化简有，

T>−2lnε(1−2ε)2

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

Q.E.D.

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

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