Timezone: »

 
Poster
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
Nataly Brukhim · Amit Daniely · Yishay Mansour · Shay Moran

Thu Dec 14 08:45 AM -- 10:45 AM (PST) @ Great Hall & Hall B1+B2 #1715
in Poster Session 5 »

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 simplified algorithms and analysis compared to previous works.

Author Information

Nataly Brukhim (Princeton University)
Amit Daniely (Hebrew University and Google Research)
Yishay Mansour (Tel Aviv University / Google)
Shay Moran (Technion)

More from the Same Authors