Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
This work addresses the challenge of multiclass boosting for machine learning practitioners, offering theoretical advancements and improved bounds, though it is incremental in building on existing boosting frameworks.
The paper tackles the problem of generalizing boosting to multiclass classification by introducing a weak learning condition that extends the 'slightly better than random guessing' notion, resulting in a simple and efficient boosting algorithm with sample and oracle complexity bounds independent of the number of classes. It applies this technique to List PAC Learning, establishing equivalences, providing new results, and improving error bounds for large list sizes.
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.