Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
Nataly Brukhim Amit Daniely Yishay Mansour Shay Moran
We study a generalization of boosting to the multiclass setting. We introduce
a weak learning condition for multiclass classification that captures the
original notion of weak learnability as being "slightly better than random
guessing". We give a simple and efficient boosting algorithm, that does not
require realizability assumptions and its sample and oracle complexity bounds
are independent of the number of classes.
  In addition, we utilize our new boosting technique in several theoretical
applications within the context of List PAC Learning. First, we establish an
equivalence to weak PAC learning. Furthermore, we present a new result on
boosting for list learners, as well as provide a novel proof for the
characterization of multiclass PAC learning and List PAC learning. Notably, our
technique gives rise to a simplified analysis, and also implies an improved
error bound for large list sizes, compared to previous results.