Multiclass Boosting: Simple and Intuitive Weak Learning Criteria

Summary

This paper tackles the problem of multi-class boosting by proposing a novel definition for weak-learning based on list boosting. The authors define a weak-learning condition for multi-class learning based on the simple principle of slightly better than random guessing. This definition is then used as a stepping stone in order to filter the potential classes for a sample recursively, thus reaching a stage where either the binary weak-learning condition can be applied, or the weak-learning condition BRG leads to boostability. The authors propose several theoretical justifications and definitions for the results presented in the paper.

Strengths

# Motivation Multi-class boosting has received a lot of attention since the introduction of binary boosting, in particular since the extension of the weak-learning condition from binary to multi-class setting is tricky. As such, the novel definition of weak-learning introduced in this paper is quite interesting, especially since its simplicity mirrors the binary one. # Theoretical results The strongest point of this paper. The authors propose several theoretical justifications throughout the paper, and the generalization result in Theorem 2 is quite promising, same for the relation between weak PAC learning and list PAC learning in Theorem 3.

Weaknesses

# Existing frameworks There are several existing frameworks for multi-class boosting based on specific weak-learning conditions (some of which are cited in the paper). I strongly think that an actual comparison between the proposed framework and the existing ones should have been included. Particularly for methods such as Adaboost.MM and Adaboost.MR and their WL conditions, and the WL framework introduced in "Multiclass boosting and the cost of weak learning." [6]. # Experimental results I'm not entirely sure why no experimental results are proposed in the main paper. There are several multi-class boosting that have been successfully used in practice, despite their WL conditions, as such it is important for new/novel methods to be compared to state-of-the-art approaches. In particular how the proposed method fares against state-of-the-art ones both in accuracy (or other multi-class performance measures) and in runtime. The recursive nature of Algorithm 1 and its dependance on 3 hyper-parameters might lead to prohibitive runtimes, even though several optimizations have been mentioned in the main paper. # Conclusion and future works I strongly think that a section on the future works and possibilities would've been more appropriate than the proof of Theorem 2. More globally, the paper could benefit from a better global organization.

Questions

* How does the current framework compare to existing ones? Are the WL conditions introduced in [6] and [16] stronger than BRG? * Any experimental results available?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The limitation of have not been discussed.

Summary

Boosting algorithms is an important fundamental question in SLT starting with celebrated AdaBoost algorithm. While the original results consider binary setting and the condition on the weak learner is straightforward, it is not trivial to formulate the same result for classification with more than one classes. I did not have the chance to go through the proofs carefully due to time constraint. I do not see where there could be a potential mistake that cannot be fixed. I did not read through section 4 and I am not familiar with list learning. pros: - interesting fundamental problem - the paper is well written - a new condition for multiclass boosting - relatively simple proof - connection to list learning cons: - the only disadvantage I can see is that this paper would better fit other venues minor comments and questions: - should Theorem 1 be stated only for realizable case, since you relying on the compression scheme generalization bound? - it is better to refer to Theorem 30.2 (than to Corollary 30.3) in Shalev-Swartz and Ben-David since your "outer" risk is equal to zero only with probability close to one - perhaps this is obvious or I have missed it, but how does your condition compare to conditions of existing results for the multi-class boosting?

Strengths

-

Weaknesses

-

Questions

-

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

-

Summary

The paper proposes a novel treatment of traditional (non-gradient) boosting to multiclass prediction problems. In particular it shows that a novel relaxation of the weak learning criterion allows the definition of boosting algorithm with the usual success guarantee of reducing the empirical misclassification rate on the given data sample arbitrarily with high probability. This relaxation requires the base learner to also accept as “hint” a subset of labels and to, for each possible subset size k, to return a hypothesis that achieves an error rate better than 1-1/k with high probability. The proposed boosting algorithm makes use of this property by recursively eliminating candidate labels from the hints of each training example based on the hypotheses produced by previous iterations. Moreover, the paper shows a connection of the proposed theory to list-PAC learning and in particular gives a new characterisation of list-PAC learnability.

Strengths

- The paper develops a beautifully simple extension of boosting to the multiclass case that, in contrast to previous approaches, does actually work to define a successful strong learner - The connection to list learnability are very interesting - The paper is well written and accessible

Weaknesses

- Papers on classical boosting, in contrast to the additive ensembles produced by gradient boosting, feel rather narrow at this point. In particular, generalisations from misclassification rate to proper statistical loss functions are unclear. - There is no empirical performance investigation of the proposed recursive boosting algorithm

Questions

- In footnote 3 the authors state the assumption that m0 does only depend poly-logarithmically on m. It is unclear to me how strong an assumption that is and in fact also how sensitive the feasibility of the method is to violations of that assumption. - My other questions is how to address the potential limitation listed below.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

One potential limitation might be the definition of weak learners that satisfy the weak learning assumption. This is because it seems to require the restriction to different subsets of classes for different inputs. It is not immediately obvious to me how one would incorporate this, e.g., with a decision tree (if it depends on the concrete model at all).

Summary

This paper proposes a generalization of boosting to the multiclass setting. To this end, the authors introduce a new weak learning assumption for multiclass based on a ‘hint’, which takes the form of a list of $k$ labels, named ‘Better-than-Random Guess’ (BRG). the authors present a main boosting method and provide theoretical analysis for PAC guarantees. Finally, the authors demonstrate applications based on the framework of List PAC learning.

Strengths

- This paper proposes a new weak learning assumption, which encompasses both the binary case (i.e., $k=2$) as well as the cases with $k>2$. - The main method is well-written. - This paper provides abundant theoretical analyses.

Weaknesses

- Although this paper is based on theories, it lacks experiments, including synthetic ones, and there is no conclusion. - Due to the lack of experiments, there is insufficient comparison with previous works, with only half a page dedicated to it in section 1.2.

Questions

Could you provide some experiments, including synthetic ones? It would be very helpful to understand this paper.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

.