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]:
In the last 10 years, boosted trees have been considered as the best performing algorithm for large scale data with numerical features (though this may change with deep learning). However, why they perform so well has never been fully understood, especially as the boosting and the tree parts of the algorithm tend to be optimized separately. This is all the more true in the multi-class setting, where boosted tree implementations are full of ad-hoc patches.

This paper offers a model where the construction of the tree is part of the boosting algorithm in a full multi-class setting, and I assume this is novel. It matches the performance of SVMs on small tasks where they were traditionally superior to boosting, and the performance of the best previous multi-class booting implementation. This is a well written paper of high technical quality with extensive and rigorous experiments, and effective descriptions of the algorithm implementations.

The main issue I found is how this algorithm scales: boosted trees are used for large scale problems, and addressing this issue is critical for significance. The authors only report large scale experiments in very vague terms, without any comparisons or training times (the authors do not report any numerical results and do not give reference. I do not know what to make for instance of the claim that it won the recent Interspeech challenge). The cost per iteration appears linear in the number of features, examples and dimensions, which is standard, but what about the number of iterations? My experience is that discrete Adaboost is quite slow on larger datasets compared to real-value prediction or gradient-based boosting.

This paper packs a lot of technical contributions in 9 pages, to the point that the authors had to take a few short cuts that impact clarity, but I would only recommend to cut comments that are not understandable by non-expert in boosting, or expand them (for instance all the references to the weak learning condition, which is never explained).

I noticed there was not a single boosting paper at ICLR’13, while this is probably still the most widely used class of machine learning algorithms. Through the greedy selection of weak classifier, boosting offers a way to learn representation that is different from deep learning, but highly practical for many problems.
The same author has submitted another paper that targets specifically the choice of the features for boosting (correlation-base construction of neighborhood and edge features), however, I find this paper the most worthy to be accepted.

Detailed comments:
-	Authors should better explain the weak learning condition.
-	In section 3, there is a single alpha, so the subscript j in “alpha_j” must be a typo.
-	Section 3: choice of font for h_j should be consistent.
-	I do not see how one can get O(nKd log(N)) if the tree is balanced: I assume one still has to run TREEBASE, which calls BASE N times, and BASE is O(nKd)???
-	Section 2.2: the case against Adaboost.M1 used in a multiclass setting that would lead to an error rate of (K-1)/K sounds strange. I thought one would use K separate Adaboost.M1 in a 1-vs-other setting?