Boosting Conditional Probability Estimators.
Dan Gutfreund, Aryeh Kontorovich, Ran Levy, Michal Rosen‐Zvi · 2014
In the standard agnostic multiclass model, pairs are sampled independently from some un-derlying distribution. This distribution induces a condi-tional probability over the labels given an instance, and our goal in this paper is to learn this conditional dis-tribution. Since even unconditional densities are quite challenging to learn, we give our learner access to pairs. Assuming a base learner oracle in this model, we might seek a boost-ing algorithm for constructing a strong learner. Un-fortunately, without further assumptions, this is prov-ably impossible. However, we give a new boosting al-gorithm that succeeds in the following sense: given a base learner guaranteed to achieve some average accu-racy (i.e., risk), we efficiently construct a learner that achieves the same level of accuracy with arbitrarily high probability. We give generalization guarantees of sev-eral different kinds, including distribution-free accuracy and risk bounds. None of our estimates depend on the number of boosting rounds and some of them admit dimension-free formulations.