Building a stable classifier with the inflated argmax

1. “Experiments were quite weak in my opinion to highlight the effectiveness of inflated argmax. For example, more reasonable baseline that has larger than 1 𝛽_size could have been provided to show that inflated argmax is quite favorable if it allows to predict more than one class. Curreent baselines are restrictive in the sense that only one class can be chosen (argmax). Several improvements could also be done (please see the questions section for possible improvements).”

   Please see discussion point 1 in our global response.

2. “The proposed inflated argmax requires bagging, which can be quite computationally expensive, or prohibitive in some scenarios under limited resources or large dataset/model.”

   The inflated argmax operates on the predicted probabilities, so it does not require bagging per se. The inflated argmax on its own is very computationally efficient. Please see discussion point 2 in our global response for discussion on the computational cost of bagging.

3. “Can we also see the performance of inflated argmax without bagging in the experiment? In my understanding, this should also be possible with the proposed efficient algorithm. This can be useful to see how important the bagging method is needed for the proposed algorithm.”

   We have added this comparison—please see the pdf attached to our global response. As we can see, both bagging and the inflated argmax are important for selection stability.

4. “Visualizing the number of bags needed to perform reasonably in the experiment can also be useful. Because it can be expensive if we use more sophisticated algorithm or using larger dataset.”

   We have rerun the experiment with a larger number of bags—please see the pdf attached to our global response. As you can see, this dramatically improves selection stability, especially with the inflated argmax. In our revised appendix, we will investigate more thoroughly how the number of bags impacts stability in practice.

5. “In deep learning, overconfident problem of probability can often be an issue when one wants to use probability score. How does this problem affect the proposed inflated argmax in practice?”

   This is an interesting question. Overconfident probability scores mean that the top label is ahead by a large margin, so the inflated argmax will frequently return a singleton if $\epsilon$ is sufficiently small. In our global response, per your suggestion, we have attached a pdf which shows the stability of the base algorithm with the inflated argmax. On its own, the inflated argmax does not lead to selection stability precisely because of overconfident probabilities. Bagging addresses the problem of overconfidence, and then the inflated argmax captures the fact that several labels have similar probability scores after bagging.

6. “Can we know that it is likely that the second class to be chosen as a candidate class is likely to be the second-largest probability class?”

   Yes, this is guaranteed by the 3rd statement of Proposition 9.

7. “Is it reasonable to say that precision is similar given different average precision and standard error provided (Lines 293--294)?”

   Yes, it is reasonable. For example, if we compare the average precision between argmax+subbagging and inflated-argmax+subbagging, the pooled Z-score is around 1.5, which is not statistically significant. Considering further that we’re making multiple comparisons in the table, it would be unreasonable to say the rates are very different.

8. “I was wondering if there are other possible baselines in related work that could be used in the experiments?” and “Suggestions on simple baselines 7.1 Top-2 class prediction, size of beta will be 2. 7.2 Predicting classes until sum of probability becomes a certain constant, e.g., if we set threshold = 0.8 and prediction probability vector is [0.1, 0.1, 0.1, 0.2, 0.6], then we will pick the last two classes (0.2 and 0.6). This simple idea looks intuitive and gives flexible set and this is the most simple baseline I had in mind that could be effective when I first read this paper. How do you think about this baseline?”

   We have added both of your suggestions and others. Please see discussion point 1 in our global response.

1. “The authors point out my primary concern in their discussion section, highlighting the practicality of the proposed framework. Notably, bagging is an computationally expensive procedure, and while the authors suggest that parallelization can mitigate this issue, I agree that this does not necessarily translate to a reduction in overall cost. This becomes particularly challenging when dealing with large datasets commonly encountered in modern classifiers (e.g., image classification), where the sheer scale of computation required can be prohibitively expensive even with multiple GPUs.” and “My other main question is related to practicality. I would like to know the author's thought more regarding that limitation.”

   Please see discussion point 2 in our global response, and let us know if you have any additional concerns regarding practicality.

2. “The experimental section relies heavily on a single dataset and classifier combination. To fully demonstrate the benefits of the proposed framework, I believe it would be necessary to conduct a more comprehensive set of experiments. Specifically, I suggest that the authors provide additional evidence through experimentation to illustrate how the slight tradeoff in precision is justified by the gained stability in practice.”

   We agree that additional experiments may be useful for a more detailed understanding of this tradeoff, and would be happy to add more experiments to the supplement to pose the same questions under different settings and different data generating processes, in our revision. However, we would like to point out that, in our view, this experimental comparison is not central to the main point of the paper. While from an empirical point of view, our method versus a competing method are simply two different points along the tradeoff between precision and stability, from the theoretical point of view they are not on equal footing at all: our method offers a theoretical guarantee of selection stability, and there is no guarantee of this type at all for competing options.

3. “From the definition of stability given in 4, it is evident that the authors trained the classifiers multiple times while removing training samples. How does the overall average of average precision look like in such cases? Such a metric might show the advantage the proposed framework.”

   In the table below, we compare $\beta_{\text{prec}}$ (as defined in the paper) to the "overall average of average precision" over all $500$ leave-one-out models. In this experiment, there is not a substantial difference between $\beta_{\text{prec}}$ (the original precision measure) and $\beta^{\text{LOO}}_{\text{prec}}$ (this new measure).

1. “The presentation of the proposed contribution can be improved.”

   a. “The core proposal of inflated argmax is introduced in section 3.2, which is too late.”

   Thank you for this feedback. We agree that introducing inflated argmax earlier in the paper would be better and will try to reorganize if possible in order to do so. However, we would like to point out that the framework of selection stability and its connections to classical algorithmic stability are core contributions, and these are given in Section 2 -- in other words, the inflated argmax definition is not the first novel contribution presented in the paper.

   b. “Bagging is not part of proposal, and shows low relation to the contribution, which can be demonstrated using fewer space.”

   While the section on bagging is indeed background material, in order to be able to use bagging as the first stage of our two-stage procedure, we need to recap the requisite tail stability result for bagging -- this is an essential ingredient of our selection stability framework. However, in our revision we will add a sentence to the start of this section to clarify that this is background material and explain its role in what follows.

   c. “Additional properties of the inflated argmax is also not directly related to the problem.”

   Section 3.2.2 (on additional properties of the inflated argmax) covers a lot of highly relevant material. We show how to compute our inflated argmax. The properties in Proposition 9 illustrate how the inflated argmax in many ways acts as a natural extension of the argmax. Our optimality result, Proposition 11, connects back to these additional properties by establishing that the inflated argmax is the most parsimonious $\epsilon$-compatible extension of the argmax. In our revision, we will add clarifications to the text to explain the significance of these results and how they relate to the main aims of the paper.

   d. “‘learning stability by leave-one-out data’ and ‘prediction stability when using argmax for similar probabilities’ seem to be mixed and not clearly addressed.”

   Neither of these phrases are used in the paper. Could you please clarify what you mean?

   e. “Some sentences such as workflow is fundamentally incompatible with the goal of algorithmic stability is too extreme, for example, simple streament using proper regularization terms can somehow mitigate the problem.”

   It may be possible that regularization can make the predicted probabilities more stable. However, as we point out in Sections 1.1 and 2.3, this is not enough to ensure selection stability because the argmax is discontinuous. The issue is that selection is unstable whenever the model is nearly equally confident in multiple classes.

2. “The demonstration of empirical evaluation does not match the last sentence in abstract.”

   The last sentence of the abstract states, "we demonstrate that the inflated argmax provides necessary protection against unstable classifiers, without loss of accuracy." This does match our empirical evaluation. In Figure 2 we see a dramatic improvement in stability (see also the revised Figure 2 attached as a pdf to the global rebuttal). While $\beta_{\text{prec}}$ in Table 1 decreases slightly with the inflated argmax, the difference is not statistically significant. Specifically, comparing the average precision between argmax+subbagging and inflated-argmax+subbagging, the pooled $Z$-score is around 1.5, which is not statistically significant. Despite having $N=10,000$ test samples, there is not a detectable difference in $\beta_{\text{prec}}$ before and after employing the inflated argmax. We will make this point more clearly in our revision.

   a. “The combination of 𝜖-inflated argmax on the base learning algorithm should be compared.”

   We have added this baseline to our table: please see discussion point 1 in our global response. We have also added it to the revised Figure 2, which is attached in our global response.

   b. “It is also nice to show results on at least two datasets.”

   We agree that additional experiments may be useful, and would be happy to add more experiments to the supplement to pose the same questions under different settings and different data generating processes, in our revision. However, the main contribution of our paper is theoretical: we show how to guarantee selection stability for any classifier on any dataset. Our emphasis is thus on the idea and the theoretical contribution. Our experiment in Section 4 and simulation in Section D.2 serve as illustrations of these results to show how they work in practice. That being said, we will add more experiments to the supplement to reinforce these results.

3. “How tail stability and selection stability relates to 𝜖-compatibility differently? To confirm, do bagging classfiers only satisfy tail stablity? Are there other algorithm designs satisfy these stabilities?”

   For the first question, we address the relationship between all three criteria in Proposition 4. We can expand the discussion around Proposition 4 in our revision to explain the relationship more clearly. For the latter two questions, other meta-algorithms may satisfy tail stability. This is an interesting open question.

4. “How to better interpreter the empirical evaluation results. With similar accuracy shown in Table 1, the proposed method should show better stability in Figure 2?”

   Our proposed method does show much better stability. Note in Figure 2 that smaller curves are more stable. In our revised Figure 2 (attached to our global response), the instability measure $\delta_j = 0$ for every test point for our proposed method.

We sincerely appreciate your constructive comments throughout this process. We look forward to integrating your suggestions into our revision.

1. “W1: I think adding a few more competitors would be useful in assessing the potential advantages of the proposed algorithms…”, “W2: Assessing the classifiers with respect to utility-discounted predictive accuracies, …” and “L2: the empirical study might need to be enlarged with closely related algorithms.”

   Please see discussion point 1 in our global response. Below we compare algorithms based on $u_{65}$ and $u_{80}$ per your suggestion in W2. However, we stress that the inflated argmax $\text{argmax}^\varepsilon$ is not meant to compete with any of these alternative set-valued classification methods, nor is it optimizing for $u_{65}$ or $u_{80}$. It is meant to improve upon the argmax by guaranteeing selection stability. None of these other methods have been shown to satisfy selection stability, and even if they were, ours satisfies the optimality result of Proposition 11.

2. “W3: Moreover, an imprecise classifier should abstain (i.e., provide set-valued predictions) on difficult cases, on which the precise classifier is likely to fail. This would be assessed in different ways. For example, one might consider reporting the correctness of the cautious classifiers in the case of abstention versus the accuracy of the precise classifiers [4].”

   The idea of "abstention" is a useful framework, but in fact, this does actually appear implicitly for any a set valued classifier — if we return the entire set $\hat{S} =$ {$1,\dots,L$}, this means that we are not able to say anything about the true value of the label, i.e., this is equivalent to an abstention. In fact, set-valued classification has the capacity to return strictly more information than a label-or-abstain scheme: if we always either return a label (i.e., $\hat{S} =$ {$y$} for some $y$) or an abstention (equivalently, $\hat{S} =$ {$1,\dots,L$}), we do not have the opportunity to express partial information (for example, $\hat{S} =$ {$y_1,y_2$} — this allows us to express that we have partial information about the true label for a particular sample $X$, i.e., we are allowing adaptivity to our level of uncertainty in different instances).

   Turning to the question of empirical comparison, in a label-or-abstain scheme, measuring the frequency of abstaining is equivalent to measuring how often $|\hat{S}|=1$, which is related to our precision measure in our experiments.

3. “W4: The tolerance $\epsilon$ is set to be .05. Please provide arguments supporting this choice. Yet, choosing this hyperparameter using a validation set might be challenging. Providing a sensitivity analysis on the choice of $\epsilon$ would be helpful.”

   The tolerance parameter $\epsilon$ has an intrinsic meaning; it is different from a tuning parameter such as the regularization parameter $\lambda$ for Lasso where there is no intrinsic meaning and therefore tuning is the only reasonable way to choose a value. In our setting, $\epsilon$ represents the margin by which we inflate the argmax — for example setting $\epsilon$ = 0.05 can, in a sense, be viewed as saying that an estimated probability of 0.45 versus 0.4 is sufficiently close to be ambiguous in terms of which label should be the “winner”. For this reason, it does not seem appropriate to perform a sensitivity analysis. (Of course, as we see in our theory, it’s also possible for the user to instead choose a desired value of $\delta$, and then specify $\epsilon$ accordingly via Theorem 5; again, here $\epsilon$ would then be determined by the user’s desired value of $\delta$, and does not need to be tuned.)

4. “Q2: The notion of selection stability $\delta$ at sample size $n$ seems to be interesting. I guess the experimental setting provides the necessary information to compute the value of the selection stability $\delta$ given in (1) . To provide an idea of how empirical evidence may differ from the theoretical results, it might be helpful to compute that value and report the proportion of test instances whose empirical values... are smaller than $\delta$.”

   Note that various $\delta_j$ range over different points in the test set $X_j$, and selection stability holds for all test points $x$. Thus, selection stability means that all of the $\delta_j$ are at most $\delta$. We will clarify this point in our discussion of the experiment results in our revision.

5. “Q3: I guess re-defining (4) as... and changing the description of Figure 2 accordingly (to be consistent with the notion of the selection stability $\delta$ defined in Definition 1) might make things a bit clearer.”

   Thank you for catching this—we will fix the definition in our revision.

6. “L1: Discussions on related work might need to be extended.”

   In discussion point 1 of our global response, we discuss other set-valued classification methods that we have added to the experiments. We will add discussion of these methods to the related work section, including all of the references you suggest. We also welcome any additional suggestions for related work that we should discuss.

Thanks for your detailed response. Additional empirical evidence and discussions indeed suggest more about the potential (dis)advantages of the proposed algorithms.

Based on the response, I think we might see $\beta_{\text{pre}}$ as an evaluation metric for classification with rejection, i.e., a predictor will only make a prediction for a query instance if it can make a precise/singleton prediction. This might also imply that whether the set-valued prediction covers the true class or not and whether the set size is large or not are not relevant. In this sense, I think it is fair to say that the proposed algorithms provide advantages, compared to top-2, Thresholding $\Gamma^*_{80}$ and NDC for $F_1$. From their definitions, it would be not hard to see that the set-valued predictions that optimize $u_{65}$, $F_1$, $u_{80}$ and a few other criteria, e.g., ones mentioned in [6], cover the top-ranked class, i.e., the output of $argmax$ (unless there are multiple classes with the highest score). By definition, optimizing $u_{65}$ would provide smaller set-valued predictions, compared to others, and therefore might naturally become a related competitor regarding $\beta_{\text{pre}}$.

Given the (set-valued) predictions on the test set, the test set can be partitioned into 2 parts, where the classifier/predictor makes precise predictions and set-valued predictions. As far as I understand from [7] (and [3]), $u_{65}$, $u_{80}$, and other utility-discounted predictive accuracies are designed to assess classifiers/predictors on the entire (test) data set. The additional results suggest that the proposed algorithms provide worse scores compared to NDC for $F_1$, which is also not designed to optimize both $u_{65}$ and $u_{80}$. If one opts for $u_{65}$ and $u_{80}$, I think it is reasonable to optimize them directly. Yet, I think it is difficult to find some specific evaluation criterion/criteria to assess multiple aspects of set-valued predictors. I think it is reasonable to expect a proposed set-valued predictor to demonstrate the advantages regarding at least a few criteria that assess the predictor on the entire (test) data set.

Regarding "W3: Moreover, an imprecise classifier should abstain (i.e., provide set-valued predictions) on difficult cases, on which the precise classifier is likely to fail. This would be assessed in different ways. For example, one might consider reporting the correctness of the cautious classifiers in the case of abstention versus the accuracy of the precise classifiers [4].", I guess I should make the point more explicit. As far as I understand, the correctness of the cautious classifiers is the proportion of the time the set-valued predictions cover the true classes. I think such a criterion is designed to assess the cost of making set-valued predictions, i.e., the cautious classifiers should (only) provide set-valued predictions on difficult cases, on which the precise classifier is likely to fail. In my opinion, this criterion should complement the $\beta_{\text{pre}}$, utility-discounted predictive accuracies, set size, and other evaluation criteria, which take into account both precise predictions and set-valued predictions.

Yet, I think the notion of selection stability is interesting (as I wrote in the initial review), and it might make the proposed algorithms differ from other cautious classifiers or set-valued predictors. The motivation to go with the proposed algorithms might need to be further elaborated. After due consideration, I keep my initial rating, but I appreciate any additional results and discussions that may strengthen the motivation to go with the proposed algorithms.

1. “The authors argue that the argmax is a hard operator… but the definition of stability used in the paper also uses the hard operator of the set union being equal to an empty set”

   The argmax does not satisfy $\epsilon$ compatibility. The point of the paper is to introduce an $\epsilon$ compatible relaxation of the argmax, which can be combined with bagging to stabilize any classifier. This relaxation is necessary even though the definition of stability uses a hard operator.

2. “The definition of the stable classifier … I struggle to find a good motivation for using this specific definition and focusing on it.” and “What are the specific applications benefiting from this notation of stability?”

   Selection stability controls the probability that our algorithm makes contradictory claims when dropping a single data point at random from the training set. In set-valued classification, $\hat{S}$ represents the set of candidate labels returned by the model. This set should not totally change just by dropping a single observation from the training set. In our revision, we will expand Section 2 of the paper with a more extensive discussion motivating this definition.

3. “The method requires bagging, what makes it difficult to apply with heavy architectures.”

   Please see discussion point 2 in our global response.

4. “The empirical results are limited to a single experiment.”

   The main contribution of our paper is theoretical: we show how to guarantee selection stability for any classifier. Our emphasis is thus on the idea and the theoretical contribution. Our experiment in Section 4 and simulation in Section D.2 serve merely as illustrations of these results to show how they work in practice.

5. “The empirical experiment uses baselines that do not work in the framework of set-valued prediction…” and “How does the introduced inflated argmax compare with other set-valued classifiers?”

   Please see discussion point 1 in our global response.

6. “‘The more recent literature…’ This statement needs citation.”

   We should have said ‘the more recent papers in this line of work’ to make it clear that we were referencing the specific citations in the previous sentence. We will make this clearer in the revision.