The return of AdaBoost.MH: multi-class Hamming trees
Authors: Balázs Kégl
ICLR 2014

Abstract: Within the framework of AdaBoost.MH, we propose to train vector-valued decision trees to optimize the multi-class edge without reducing the multi-class problem to $K$ binary one-against-all classifications. The key element of the method is a vector-valued decision stump, factorized into an input-independent vector of length $K$ and label-independent scalar classifier. At inner tree nodes, the label-dependent vector is discarded and the binary classifier can be used for partitioning the input space into two regions. The algorithm retains the conceptual elegance, power, and computational efficiency of binary AdaBoost. In experiments it is on par with support vector machines and with the best existing multi-class boosting algorithm AOSOLogitBoost, and it is significantly better than other known implementations of AdaBoost.MH.


Peer review:
[Review]:
The paper describes an Adaboost algorithm, with tree based learners, adapted to the multi-class setting. The claim is that direct multi-class algorithms cannot be used to grow tree base learners in Adaboost. The author proposes a factorization of the classifier into a product of 3 terms, one performing a binary separation of the input space, a second one projecting this binary value onto the  classes and the third being a confidence term. With this formulation, base tree learners can be grown using the binary separator corresponding tot the first term. Experiments are described on a series of UCI data sets and reach good results compared to a series of baselines.
The idea of factorizing the multiclass classifier is interesting and seems to lead to good results – even if the experiments have been performed on rather small size problems. The paper is relatively clear, but could be improved. In many places, there are shortcuts which will probably be hard to follow for non-specialists of multi-class Adaboost. Also there should be a description of the alternative multi-class Adaboost methods used in the experimental comparison, in order to appreciate the originality of this new proposition.
Overall, I think that this is a good paper. On the other hand, I am not sure that it is adapted to ICLR. It is not concerned with representation learning and would probably be better suited to a more general ML conference.