|
Abstract:
Classical boosting algorithms construct a strong classifier by building a weighted ensemble of weak hypotheses. However, the number of weak classifiers in the final ensemble can grow quite large. One can restrict the number of rounds for which boosting is run, but this can result in significant underfitting. I'll talk about a simple modification to standard boosting algorithms which explicitly encourages small final ensembles. At each round, we compare the weighted error achieved by the weak learner with the weighted error achieved by the single best hypothesis in the ensemble so far. Unless the new hypothesis weighted error improves that of the best existing hypothesis by a finite margin, we do not include it in the ensemble. Instead, we add weight to the existing ensemble member which performs best on the current weighting of the data. For nonzero margins, this modified algorithm gives natural and explicit control over ensemble size.