3
集成分类的有效性证明
source link: https://allenwind.github.io/blog/7464/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Mr.Feng Blog
NLP、深度学习、机器学习、Python、Go
集成分类的有效性证明
本文证明分类问题使用集成学习方法的有效性。
设有集成模型
HT(x)={1if ∑ht>0−1if ∑ht≤0HT(x)={1if ∑ht>0−1if ∑ht≤0TT 表示基分类器的个数。每个基分类器
ht(x)={1if x 判别为正类−1if x 判别为负类,t=1,…,Tht(x)={1if x 判别为正类−1if x 判别为负类,t=1,…,T每个基分类器分类错误的概率为
P(ht(x)≠f(x))=εtP(ht(x)≠f(x))=εt由于每个基分类器的分类性能大致相等，为化简起见，我们令所有基分类器的分类错误概率均为 ε<0.5ε<0.5 （弱可学习器）.
设 C(HT(x))C(HT(x)) 表示集成模型中，基分类器分类正确的数量，则根据二项分布有
P(C(HT(x))≤k)=k∑i=1CiT(1−ε)iεk−iP(C(HT(x))≤k)=∑i=1kCTi(1−ε)iεk−i上式表示分类正确的基分类器数量在 kk 范围内的概率。
为方便起见，集成模型的基分类器个数 TT 为偶数。因此，当 k≤T2k≤T2 时，集成模型分类错误，其误分类概率为
P(C(HT(x))≤T2)=T2∑i=1CiT(1−ε)iεk−iP(C(HT(x))≤T2)=∑i=1T2CTi(1−ε)iεk−i现在我们要评估这个概率的上限。根据 Hoeffding’s inequality ，有
P(C(HT(x))≤(ε−λ)T)≤exp(−2λ2T)P(C(HT(x))≤(ε−λ)T)≤exp(−2λ2T)取 (ε−λ)T=T2(ε−λ)T=T2 代入上式消去 λλ ，有
P(C(HT(x))≤T2)≤exp(−12(1−2ε)2T)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))=εP(C(HT(x))≤T2)≤exp(−12(1−2ε)2T)<P(ht(x)≠f(x))=ε exp(−12(1−2ε)2T)<εexp(−12(1−2ε)2T)<ε T>−2lnε(1−2ε)2T>−2lnε(1−2ε)2易知，任给 ε∈(0,0.5)ε∈(0,0.5) ，总能找到恰当的 TT 使上式成立。也就是说如果基分类器的分类正确率在 (0.5,1)(0.5,1) 区间，模型集成是有效的。
Q.E.D.
转载请包括本文地址：https://allenwind.github.io/blog/7464/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK