Set Learning for Accurate and Calibrated Models

Thank you very much for your positive review! We appreciate it and agree that substantial benefits for calibration could be of great significance to both academia and industry. Hence, we are glad to see that you think likewise. Here are our responses to your questions:

1.) We agree in principle that this would be interesting, and when performing the experiments in the paper we did indeed account for this: To determine the maximal number of update steps to use in our experiments, we performed an extensive grid search using the vanilla baseline. We then used that number for all experiments in our paper. We additionally used an early stopping training criterion, meaning we stopped training when the training process converged (no more improvements on a held-out validation set). Thus, all methods converged before hitting the maximal number of iterations. This means that increasing the number of update steps would not change the outcome (at least not substantially).

2.) We ran a full battery of ablation experiments for comparing hard and soft losses on our various training settings. We elaborate on this more thoroughly (and report our findings) in the general response to all reviewers (see above). We will add results, plots, and an additional section on the intuition behind soft vs. hard loss differences to the Appendix of our manuscript early next week!

We ran additional ablation experiments to compare the hard and the soft loss optimizations against each other. We added plots showing the results from these experiments to a new section F.5 in the Appendix. We compare test set accuracy and calibration performance across all training settings (class-balanced and heavy-tailed) and for all datasets (our findings are outlined in the comment above). In addition, we added a subsection as part of this new section on "Why soft loss optimization produces less accurate classifiers?" to provide a well-informed intuition about why the soft loss produces worse classifiers than the hard loss. This subsection can be found in F.5.1. See the general response for more details.

Thank you for your thorough review! We appreciate that you took the time to give us constructive feedback.

Regarding the weaknesses:

• We will improve the presentation of our contributions in the next update of the manuscript (which we will post early next week). See point two in the general response for how we plan to do this.

• The idea behind OKO is to identify the majority class of a set of inputs. Here we focus on the special case where the sets consist of 2 examples from the majority class and 1 example from the minority ($k=1$). We demonstrated empirically that this setting generalizes to other settings. For space reasons we had to move these experiments to Appendix F.4. That section shows that the conclusions generalize (the particular value of $k$ rarely matters but setting $k>0$ is crucial.). We thus decided to focus on $k=1$ in our main paper because we think that this is the setting that is most relevant to practitioners.

For your specific questions:

The "set learning" problem you mention in the introduction is not formally defined, nor is the odd-one-out scheme in Section 2.

In these sections, we avoided a more formal introduction specifically because we also want to talk about related work, which does not necessarily share the same formalisms as we do. Rather, we want to talk broadly about other methods that use set learning. A very formal introduction (needed for the proofs) can be found in the Appendix.

As far as I understand, OKO consists in transforming the classification problem into a binary classification problem, as made in the "error-correcting output coding" decomposition strategy. Could you explain the difference between OKO and ECOC?

This is a very interesting question. We had not seen the connection to ECOC, thank you for pointing it out! We will include it into our related works discussion. The idea behind ECOC is to look at multiclass classification by training several different binary classifiers. In contrast, with OKO one trains just a single final classification model (not several), and that model still makes a multiclass prediction (in ECOC, every model makes a binary decision). OKO is also focused on delivering well-calibrated models, which AFAIK is not a main goal of ECOC.

In Section 3, you explain how to construct a training example for the OKO setting. I assume this operation is repeated. Could you elucidate how instance generation can be repeated in the global OKO setting ?

Algorithm 1 shows how to construct a single training example for OKO. By running this algorithm repeatedly (for multiple steps), one can construct a whole dataset of sets --- which we refer to as $\mathcal{D}^{\prime}$ --- for using OKO.

Could you provide information on the results obtained using the soft loss, and/or insights regarding why the hard loss would give better results than the soft loss?

Please see our general response where we provide an answer to this. We will add a new section in a revised version of the manuscript.

Section 4 is very short. Theorem 1 seems to be limited to the example discussed. The section seems to call for a discussion on the different natures of uncertainty (i.e., aleatory vs epistemic uncertainty) and on the different treatments to be applied accordingly.

Theorem 1 is just meant to give some intuition about how OKO behaves in a particular setting and help explain why it may exhibit good calibration. It indicates that, for the setting in Theorem 1, input regions with fewer samples, which may be interpreted as a higher degree of epistemic uncertainty, manifest as aleatoric uncertainty in the OKO test time outputs. While it is conceivable that such regions indeed have low aleatoric uncertainty, and that the few samples do indeed characterize the entire region, in safety-critical applications it is often desirable for the network to err towards uncertainty. We will include this point with an explanation of aleatoric and epistemic uncertainty in the next draft.

You emphasize the similarity between the relative cross-entropy for calibration you use and the KL divergence. Can you elucidate the advantages of RCE for calibration over KL divergence?

These questions were raised by several reviewers. Therefore, we discuss it in the general response.

You set k = 1 for all experiments: this seems to correspond to a very special case of OKO. Could you explain the impact of this choice? This mitigates the conclusions that can be drawn from the experimental part, as it seems difficult to generalize them. Can you elaborate?

We did not have space to include detailed results about this in the main text, but Appendix Section F.4 answers this question. The section shows through empirical evidence that this special case generalizes well to more general cases because the particular choice of $k$ does not matter but $k>0$ is crucial.

Typos and writing:

Thank you for pointing these out. We will fix these and upload a new version asap! :)

Thank you for your response and for raising your score!

9.) We can see your point and where you are coming from, but we would still like to disagree here: It is indeed true that on average, OKO converges sooner, because it processes more information per update step. However, we made sure that every method could run until convergence, so we are very confident that more examples would not have helped the baselines improve their performance. Also, recall that $n$ does not change. So, if you train each method until convergence, it does not matter how often a model has seen the same image.

10.) In Figure 4, we show the distribution of entropies of the predicted probability distributions for individual test data points (i.e., at inference time) partitioned into correct and incorrect predictions respectively. The $x$-axis represents correct vs. incorrect predictions (hence, its label is binary), and the $y$-axis represents the entropy, or uncertainty if you will, of the model’s softmax outputs, and therefore its label is continuous. The range of the entropies goes from $\log(1) = 0$ to $\log(C)$ where $C$ is the number of classes in the data.

11.) Thank you for this feedback. After seeing your and the other reviewer’s reaction, we agree that our claims were too strong in this regard. Please see the general response above for more details about how we intend to fix this.

12.) Thank you for pointing this out. We will fix this accordingly.

13.) Thank you for the blunt feedback, we appreciate the honesty. As we addressed in the general response to the reviewers, we agree that our claims about the theoretical contributions were too strong. We toned them down, and improved the presentation of our results, and the general flow of our text. We would kindly ask you to take a look at the revised version of the PDF that we will upload early next week: You seem to agree that our approach is interesting and our empirical results look good. So, we would kindly ask you to consider whether the results we present here are truly something the ICLR community is not interested in.

We hope that this answers your questions! Let us know if there’s anything else you’d like to know or that we can do to increase your rating.

Thank you for your feedback! Below are our responses to all of your 13 questions:

1.) Maybe “shared latent information” might indeed be a better word for what we’re trying to express. We think OKO is better able to tease out such information because it allows the model to compare data points (both from the same set as well as among different sets), so that every gradient descent step is influenced by more than just a single data point. Judging by our empirical results, we think it’s fair to say that our model, indeed, appears to learn more sensible decision boundaries wrt. Calibration.

2.) The pair class is chosen uniformly at random from the total number of classes. So the probability of each class being drawn goes to one as the number of samples goes to infinity. In more practical terms: we are confident that all classes are drawn equally often as pair classes.

3.) This is an interesting observation! We now give an exact comparison of hard vs. soft loss in the Common Responses to all reviewers. We included plots and analyses in the Appendix of our manuscript.

4.) The connection to Multi-Instance Learning (MIL) for $k=0$ is reasonable. Thank you for pointing it out! We agree that one can have more than $2$ instances from the majority class. Appendix Section F.4 contains ablation for various settings of $k$, including $k=0$. As stated in the main text, the particular choice of $k$ does not matter much but $k > 0$ is substantially better than $k=0$ across all training settings (see Section F.4 in the Appendix). In preliminary experiments, we tried larger numbers of images for the majority class when $k=0$ and did not observe substantial differences between 2, 3, and 4 images in the majority class when $k=0$. Hence, we conclude that $k > 0$ is important but not its particular value. Of course, one could try different combinations of the number of images in the majority class and $k$ but this is an exponentially large combinatorial problem and we leave this to future analyses.

5.) The desirability of the phenomenon highlighted in Theorem 1 is dependent on the application. It is most desirable when one would like to err towards uncertainty for regions of the input space that are sparsely sampled. This might be beneficial for a safety-critical setting where it would be better for the network to indicate less certainty in sample regions with little data rather than having the network assign high certainty from just a sample or two. We can include this point in the next draft, if you want.

6.) We will connect RC better with OKO and how RC helps understand the empirical fact that OKO produces greater entropy predictions by showing that the cross entropy vs entropy diff is more centered at zero (see our general response).

7.) The definition of proper was, unfortunately, moved to the Appendix and we will also move that sentence as well. A proper score is essentially a score that is maximized in expectation when labels are from the same distribution as the calibrating distribution. However, since RC has an expectation of 0 on the same distribution, and it can be positive, or negative, it is in fact not a proper scoring rule.

8.) The objective of the 2nd head is cross entropy between the odd class label $(y_{i})$ and the logits of the odd class representation $(x_{i})$. In other words, the full loss function in this case was $L_{\text{oko}}^{\text{hard}}(S_y, f_\theta (S_x)) + y_i \log \theta(x_i)$. We will clarify this in the next version of the manuscript.

We would like to thank the reviewer for their thoughtful review, for agreeing that this is an important research question, and for supporting us in our work. We can see that you invested a lot of time to understand what is going on with OKO. Therefore, we have taken your feedback very seriously. Please find our answers to your questions below:

1.) The desirability of the phenomenon highlighted in Theorem 1 is certainly dependent on the application. It is most desirable when one would like to err towards uncertainty for regions of the input space that are sparsely sampled. This might be beneficial for a safety-critical setting where it would be better for the network to indicate less certainty in sample regions with little data rather than having the network assign high certainty from just a sample or two. We can include this point in an updated version of our manuscript, as well as Proposition 3, in the main text in the next draft. When one minimizes a function like $f(x,y) = -x-y+(-x+y)^{2}$, that has negative slope for $f(t,t)$, but is strictly convex with a unique minimizer when $x$ or $y$ is fixed, gradient descent will typically follow a zig-zagging path that slows its divergence to $(\inf,\inf)$, unlike a function like $f’(x,y) = -x^{3}-y^{3}$ that will directly shoot of to $(\inf, \inf)$. We suspect this zig-zagging phenomenon helps keep the logits from diverging so quickly with OKO. We can include these example functions along with a plot of the gradient descent path to illustrate this. Again this isn’t a completely definitive characterization of OKO’s optimization path, but we feel this is still somewhat elucidating.

2.) We note that since both cross entropy $H(P, Q)$ and KL divergence are not symmetric, our definition of relative cross entropy is not the same as the reverse KL divergence, which is $H(Q, P) - H(Q)$. In fact, the RC can be negative and as we have shown in Lemma 2, the expected RC is 0 for calibrated classifiers. For Lemma 1, this is claiming that for data points where the predictor is wrong and overconfident, with the correct label being predicted with less than random chance, the RC value is positive and captures the overconfidence. We will clarify this and also strengthen the theorem.

We hope that this addresses your concerns. Let us know if there’s anything else you’d like to know. We will update our manuscript to better clarify these points asap.

We have added some discussion (after Proposition 2) and a figure (Figure 6 in the Appendix) to help elucidate Proposition 2 (see updated PDF of the manuscript). Please let us know if we can do more to help explain this result.

Unfortunately, it is not feasible to move Proposition 3 to the main text. We are already very tight on space and the proposition and the contextualization that is necessary for it will require a rather large amount of space (alas, there is no extra page for rebuttal or camera-ready).

Dear Reviewers,

as promised, we have just updated the PDF of our manuscript to incorporate your feedback. Specifically, we applied the following changes to our submission,

• Hard vs. soft loss optimization: We ran additional ablation experiments to compare the hard and the soft loss optimizations against each other. We added plots, showing the results from these experiments, to a new section F.5 in the Appendix. We compare test set accuracy and calibration performance across all training settings (class-balanced and heavy-tailed) and for all datasets (our findings are outlined in the comment above). In addition, we added a subsection as part of this new section on "Why soft loss optimization produces less accurate classifiers?" to provide a well-informed intuition about why the soft loss produces worse classifiers than the hard loss. This subsection can be found in F.5.1.

• Better presentation of the theory: We changed the wording in the abstract, updated the introduction/contributions, and the conclusion, to reflect the reviewers' criticisms about how some parts of the theory were presented, and applied the changes that we outlined above in Fitting Theory to the Empirical Results to our manuscript. In addition, to better clarify Theorem 1, we added a new paragraph to the main text (see Theorem 1 on page 5). To help elucidate Proposition 2 (as pointed out by Reviewer se1z), we added a figure demonstrating how a function that is convex in $x$ and $y$ meanders (see Figure 6 in the Appendix).

• Related works: We added two sentences + references about error-correcting output coding (ECOC) to the related works section, as suggested by Reviewer S9eW.

• Typos / writing: We fixed all typos (and ambiguity in the notation) that the reviewers pointed out.

The Authors