集成分类的有效性证明
文章目录
本文证明分类问题使用集成学习方法的有效性。
设有集成模型
HT(x)={1if ∑ht>0−1if ∑ht≤0T 表示基分类器的个数。每个基分类器
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/