A Boosting-Type Convergence Result for AdaBoost.MH with Factorized Multi-Class Classifiers

Abstract

A DA B OOST is a well-known algorithm in boosting. Schapire and Singer propose, an extension of A DA B OOST , named A DA B OOST .MH, for multi-class classification problems. Kégl shows empirically that A DA B OOST .MH works better when the classical one-against-all base classifiers are replaced by factorized base classifiers containing a binary classifier and a vote (or code) vector. However, the factorization makes it much more difficult to provide a convergence result for the factorized version of A DA B OOST .MH. Then, Kégl raises an open problem in COLT 2014 to look for a convergence result for the factorized A DA B OOST .MH. In this work, we resolve this open problem by presenting a convergence result for A DA B OOST .MH with factorized multi-class classifiers.