Variance reduction trends on ‘boosted’ classifiers

摘要

Ensemble classification techniques such asbagging, (Breiman, 1996a),boosting(Freund & Schapire, 1997) andarcingalgorithms (Breiman, 1997) have received much attention in recent literature. Such techniques have been shown to lead to reducedclassification error on unseen cases. Even when the ensemble is trained wellbeyond zero training set error, the ensemble continues to exhibit improved classificationerror on unseen cases. Despite many studies and conjectures, the reasons behindthis improved performance and understanding of the underlying probabilistic structuresremain open and challenging problems. More recently, diagnostics such asedgeandmargin(Breiman, 1997; Freund & Schapire, 1997; Schapire et al., 1998) have been used toexplain the improvements made when ensemble classifiers are built. This paper presentssome interesting results from an empirical study performed on a set of representativedatasets using the decision tree learner C4.5 (Quinlan, 1993). An exponential-like decayin the variance of the edge is observed as the number of boosting trials is increased.i.e. boosting appears to ‘homogenise’ the edge. Some initial theory is presented whichindicates that a lack of correlation between the errors of individual classifiers is a keyfactor in this variance reduction.