Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper suggests a definition for calibration in the multi-class setting named 'top label calibration'. The idea is to have only the most likely class calibrated. The small difference with previous definitions is that instead of conditioning only only the confidence value, the conditioning here is also on the identity of the class. The authors argue convincingly that this conditioning renders the definition more meaningful. 
The authors then observe that many definitions for multi-class calibration could be reduced to multiple instances of binary calibration and suggest an algorithmic framework where a binary calibrator is used as a black box to achieve the multi class calibrator. They then test this by instantiating it with histogram binning and measuring the corresponding notion of expected calibration error.
main_review: Strengths: The paper makes a convincing argument that on an individual level, confidence calibration may be misguided while their definition makes more sense. It is also true that a natural algorithm to achieve many notions of multi-label calibration is to reduce it to the binary case, as the paper suggests.
Weaknesses: I think the definition also has obvious drawbacks that the authors do not discuss. In particular I am not convinced that calibrating only the top label makes sense. In practice it just means that you partition the data by the top label and then calibrate each partition separately (as the algorithm they suggest effectively does). The predictions outside the top label make no difference. It should be noted that satisfying this requirement is very easy. Pick the most common label and assign to all points the expectation of that label. Thus, the point of calibration is to do it to an existing classifier *with out* sacrificing other good properties such as loss minimization. Since the top label doesn't change by the calibrator the accuracy is unchanged, but the typical loss function for multi-class is cross entropy. 

Detailed comments:
- Please explain better why calibrating only the top label is sufficient. Typically we assume that c(x) returns a vector of probabilities of dimension L, not just the top label out of the L.
- At the beginning of section 2, please define confidence better. The arg max of the expression is a class (a number in [L]), not a pair (c,h), so the definition is confusing. 
- I am not very familiar with confidence calibration as is defined here, but it must have some good properties no? Please discuss them and contrast with your definition as well.
- I'm not sure I fully understand the contribution of Section 3. Sure, some notions are reductions from binary classifiers, so lend themselves to be computed via binary calibrators. Is there anything more you can say? (for instance, is error being compounded?, is loss minimization being affected? are there computational tradeoffs?).
- In table 2 and 3 it is worth noting that scaling algorithms are not designed to bring down ECE or TL ECE.
summary_of_the_review: The provides a variation over  confidence calibration that takes into account the identity of the top label. This variation makes sense under some scenarios, but is still a quite a weak notion on its own. While it's an interesting notion to discuss, I think the contributions of the paper are too thin to justify publications.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors consider the problem of calibrated probabilistic outputs for multiclass classifiers. They consider the various types of calibrations previously studied, such as confidence calibration and class-wise calibration, and then propose a novel notion of calibration based on the choice of top-labels.
main_review: This paper is very well written, tackles an interesting area, proposes a novel calibration, and demonstrates the utility in empirical experiments.

Strengths:

- The proposed calibration results in a more intuitive interpretation than previous approaches and the authors argue so convincingly.
- Matching calibration algorithms and metrics places everything into a nice framework, and the experiments demonstrate clearly the value of matching the algrithm and metric.
- Histogram binning, within the appropriate algorithm, is shown to be a competitive post-hoc calibration technique.

Weaknesses:

- Only histogram binning is considered, though there are other post-hoc calibration methods that clearly fit in the algorithms described. It would have been good to see some results, or at least a discussion.
summary_of_the_review: Excellent paper with good results and clear practical applications. The work is also well placed within existing literature.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new method to fix confidence calibration by conditioning on the predicted label when formulating the calibration task (as well as on the class probability estimate for that label, as done in confidence calibration). This new approach is called "top-label" calibration. The paper shows how to modify the calibration process to achieve this by building a separate calibration model for each predicted class value. Experiments compare this approach, using binning as the calibration method, to confidence calibration as well as standard 1-vs-rest calibration (both with and without normalization in the latter method) based on calibration of pre-trained CIFAR-10/100 CNNs. Temperature scaling, vector scaling, and Dirichlet scaling are also included. Evaluation is performed using 1-vs-rest ECE, a new top-label ECE, and a maximum calibration error (MCE) variant of the latter. Surprisingly, the proposed approach does not perform as well as 1-vs-rest calibration when using the top-label variant of ECE; it does perform a lot better wrt the MCE variant on the CIFAR-10 data though. When considering 1-vs-rest ECE, the paper reports that 1-vs-rest *without* normalization performs better than the same approach with normalization, and also better than all scaling-based methods. The paper also explains how to adapt top-K-confidence calibration to obtain top-K-label calibration, but this is not evaluated.
main_review: The first seven pages of the paper are very nice, and I very much enjoyed reading this material. The problems start with the experiments:

1) Reading through the appendix, the authors are obviously aware that a calibration set is normally used to calibrate a model, before it is evaluated on the test set to compute ECE. However, there is no reference to how this is done for the experiments in the paper, which are based on pre-trained models. It seems that the validation set was perhaps used for both building the discretization-based calibration models and their evaluation, which seems highly problematic.

2) One of the three empirical observations on Page 9 states that the new TL-HB is the best performing method for 1-vs-rest ECE. In fact, it is the un-normalized variant of 1-vs-rest calibration that is shown in Table 3 and that performs best! Assuming this is just a typo and "TL-HB" in Observation (c) was meant to be "CW-HB", this is the most surprising and potentially most impactful finding in the paper. (The other two observations are about the behaviour wrt TL-ECE/MCE, which are the new, less obvious ECE metrics, and the results are also more mixed wrt these metrics.) However, there is no analysis at all in the paper why leaving out normalization in the 1-vs rest method (CW-HB) is so much better than using it (N-EB)!

3) There is no comparison to isotonic regression, which is trivially applied using the 1-vs-rest method, and like binning, is also a non-parameteric method. The scaling-based methods are all parameteric.

4) The number of datasets is very limited (CIFAR-10 and CIFAR-100).

5) The actual 1-vs-rest discretization-based calibration algorithm used in the paper (CW-HB) seems non-standard because a separate binning is applied for each class (see Algorithm 9 in Appendix C.1, assuming that Binary-histogram-binning performs equal-frequency binning as indicated elsewhere in the paper). My understanding is that normally, the same bin boundaries are used for all classes when this method is applied. The effect of this is unclear. Could it explain why normalization performs so poorly in Table 3?

The submission describes the discretization-based algorithms being evaluated as special instances of a general M2B "notion" for calibration of multi-class problems, and there is a corresponding "general-purpose" calibration algorithm that includes the evaluated algorithms as special cases. It is unclear how helpful this algorithm and the M2B "notion" are. This aspect of the paper seems somewhat trivial. There are no results or proofs regarding this general-purpose formulation of the algorithm.

Longer and longer appendices seem to be becoming the norm, but this submission is quite extreme in this regard, particularly because only some appendices are referred to in the main text (G, A, D.3, D.2, D.4, D.5, B, D.1) while others aren't: E (random forest experiments, extend Appendix B.2), C (CW-HB), F (canonical multi-class calibration, 8 pages). The role of appendix F in particular is mysterious: it is only tangentially related to what is presented in the main text. 

Other questions and comments: 

- Do the calibrated probabilities obtained using top-label calibration sum to 1?

- "However, the distribution of $g$ can be different for different labels, thus they should be treated differently" -- I don't understand the reason for having this sentence here. Is this to reinforce that point? I would delete it.

- Renumber the algorithms to follow the order in which they are discussed.

- "the expectation is over the calibration data" - isn't it trivial to fit the calibration data arbitrarily well? Why is this bound useful then?

- Is N-HB defined in the text or just in the caption?

- Why is CW-HB not included in Table 2? Is it obvious that it performs worse than TL-HB for these metrics? Conversely, doesn't it make sense to include TL-HB in Table 3?
summary_of_the_review: There are several problems with the empirical evaluation and the analysis. The submission (including the many appendices) also seems heavily overloaded, to the point that the main message becomes quite unclear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper discusses the topic of classifier calibration in multi-class classification. The focus is on obtaining well-calibrated probabilities for the top-predicted classes. The authors give arguments, examples and experimental results to show that the commonly-used confidence calibration method suffers a number of shortcomings that makes it less useful in practice. As an alternative, top-label calibration is proposed, where calibration is analyzed on a per-class basis, when a specific class is the top class. 

In addition, the authors discuss shortcomings of confidence reliability diagrams, and they propose multi-class to binary reductions for achieving top-label calibration. In the experiments several methods are compared on two classical image classification benchmarks.  
main_review: This is a pretty dense paper that contains a lot of material, but it is very well written. I do not consider myself an expert on the topic, but I could follow the flow of the paper quite well. 

The authors have been able to convince me of the disadvantages of confidence calibration, and the advantages of the method they introduce. To this end, Example 1 and the case study in Figure 1 really helped. The experimental results also seem to support the claims of the authors. From a more conceptual perspective, the proposed algorithms are also appealing. 

However, I do see potential problems with the approach of the authors for classification problems with infrequent classes, like in extreme multi-class classification, where long-tail classes have very few observations. In such situations, confidence calibration will probably work much better, as one doesn't have to condition for rare classes. Conversely, for the approach of the authors, one needs much more observations per class. So, in this regard, the experiments are currently somewhat limited, and probably telling a too optimistic story. I would have liked to see some experiments with extreme classification datasets that have long-tail class distributions. 
summary_of_the_review: Interesting and well-motivated idea. Datasets in the experiments are quite simple.
review_title: null

Meta-review: The paper studies the problem of multi-class calibration, proposing new notion of "top-label calibration", and presenting and comparing new algorithms for multi-class calibration. Reviewers generally found the paper to be well-written, and tackling a foundational problem. There were some questions regarding the experiments:

(1) _Lack of explanation of why unnormalised beats normalised._ One of the paper's main empirical findings is that using an unnormalised predictor with histogram binning (CW-HB) can significantly outperform a normalised one (N-HB). There is however limited discussion prior to this of why such behaviour is expected.

(2) _Lack of comparison to isotonic regression._ One can apply isotonic regression in conjunction with one of the M2B algorithms in Sec 3. It is of interest whether isotonic regression + a suitable M2B wrapper compares to HB + an M2B wrapper.

(3) _Comparison to OVA calibration_. One reviewer raised the concern that the new algorithms proposed in this work are not too surprising; e.g., using a binary calibrator of one label vs everyone else appears natural.

(4) _Overloaded appendices_. One reviewer pointed out that some material in the Appendix is not referenced in the body, thus making the work not self-contained.

For point (1), the response indicates that the unnormalised model can obtain distribution-free guarantees. The lack of such a guarantee for the normalised model does not suggest that such a guarantee is impossible, however. Certainly the present work need not solve this issue in entirety, but if this is intended to be a main takeaway of the experiments, a little more discussion in the body seems advisable. 

On this note, from my reading, the experiments seek to demonstrate that suitable M2B reductions can dramatically improve the performance of HB. However, with the use of multiple evaluation metrics (Top-ECE, Top-MCE, Classwise-ECE) it is not clear if the authors intend to promote one specific M2B reduction as generally favourable; further, the text in Sec 3.2 suggests that N-HB is the method considered in prior works, which then seems to do better on top-label ECE than prior works. Which suggests that for this particular metric, one does not gain much from other M2B reductions?

For point (2), the response argued that "the main message of the paper is not about HB vs other binary calibrators, but proposing a single agnostic framework for achieving multiple notions of multiclass calibration using any binary calibrator". From my reading of the paper, I think this claim is accurate, and agree that the conceptual advance is the generic M2B framework itself

For point (3), the authors responded to suggest that while Algorithm 2 performs a natural one-versus-all calibration, this is different from Algorithm 1. Further, the latter is shown to be useful in Table 2 (bottom panel).

For point (4), the revision involved referencing relevant material in the Appendix. These seem better, though I would prefer if theorem statements (e.g., Theorem 1) appear in full or as sketches in the body.

Further to the above, I have a couple of minor suggestions:
- consider removing most hline's from Tables 1 -- 3

- keep the ordering of Algorithms 1 -- 4 the same as that in which methods are presented in Table 1.

**Summary**. The paper considers a foundational problem. It makes one simple yet interesting contribution in its definition of top-label calibration. Detailing the various multi-class calibrators in Section 3 is another contribution: albeit simple, it does illuminate the subtle issue of the role of normalisation in post-hoc calibration, which empirically is shown to have non-trivial impact. There are certainly avenues where the paper could be further strengthened, but overall I do see it as potentially being of broad interest to the community, and inspiring future work. My recommendation is thus for the authors to further incorporate the reviewers' detailed suggestions and the comments above, which can broaden the clarity, scope and impact of the work.
Decision: Accept (Poster)