Summary
This submission studies the problem of making set-valued predictions, in which the classifier should strive for an optimal balance between the correctness (the true class is among the candidates) and the precision (the candidates are not too many) of its prediction.
Yet, this submission mentions one method for this purpose [1], which predicts, for each query instance, a Bayes-optimal set valued prediction optimizing the F-measure. It seems to miss a discussion on (several) related methods, which are constructed based on both the probability theory and imprecise probability, e.g., the ones discussed in [3, 4, 6] and references therein.
On the abstract level, the inflated argmax presented in Section 3.2 might be seen as a way to distort/imprecise the given singleton conditional probability distribution. It might enlarge the set of existing approaches targeting similar purposes, such as the ones discussed in [2, 5] and references therein, meaningfully.
The proposed algorithm is compared with a variant of LeNet-5, implemented in PyTorch [PGML19] tutorials as GarmentClassifier(), and its ensemble version on the Fashion-MNIST data set. Empirical evidence suggests that the proposed algorithm provides better $\beta_{\text{prec}}$ than the single classifier, but worse than the ensemble version. The average set size produced by the proposed algorithm seems to be reasonably small. Results on the selection instability $\delta_j$ defined in (4), i.e., an approximate of the loss version of the stability $\delta$ defined in (1), which essentially measures the robustness of the set-valued predictions under tiny changes in the training data set, seems to be in favor of the proposed algorithm.
[1] Del Coz, J. J., Díez, J., & Bahamonde, A. (2009). Learning Nondeterministic Classifiers. Journal of Machine Learning Research, 10(10).
[2] Montes, I., Miranda, E., & Destercke, S. (2020). Unifying neighbourhood and distortion models: part I–new results on old models. International Journal of General Systems, 49(6), 602-635.
[3] Mortier, T., Wydmuch, M., Dembczyński, K., Hüllermeier, E., & Waegeman, W. (2021). Efficient set-valued prediction in multi-class classification. Data Mining and Knowledge Discovery, 35(4), 1435-1469.
[4] Nguyen, V. L., Destercke, S., Masson, M. H., & Hüllermeier, E. (2018, July). Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty. In 27th International Joint Conference on Artificial Intelligence (IJCAI 2018) (pp. 5089-5095).
[5] Nguyen, V. L., Zhang, H., & Destercke, S. (2023, September). Learning Sets of Probabilities Through Ensemble Methods. In European Conference on Symbolic and Quantitative Approaches with Uncertainty (pp. 270-283). Cham: Springer Nature Switzerland.
[6] Troffaes, M. C. (2007). Decision making under uncertainty using imprecise probabilities. International journal of approximate reasoning, 45(1), 17-29.
Strengths
S1: I think taking into account the instability, due to tiny changes in the training data set, when making set-valued prediction is interesting. Yet, assessing this aspect of classifiers seems to be costly, i.e., requiring a sufficiently large number of leave-one-out models.
S2: Empirical evidence seems to be promising. For example, $\beta_{\text{prec}}$ seems to suggest that the proposed algorithm tends to produce a reasonably high proportion of correct singleton predictions. The average set size seems to suggest that the set-valued predictions produced by the proposed algorithms are reasonably small. Empirical evidence regarding the instability defined in (4) seems to be in favor of the proposed algorithm.
Weaknesses
W1: I think adding a few more competitors would be useful in assessing the potential advantages of the proposed algorithms. For example, threshold-based algorithms, which produce Bayes-optimal predictions of F-measure [1], and $U_{65}$ and $U_{80}$ [3], would be a good choice. They would cost $O(L\log(L))$ time to sort the labels according to the decreasing order of the predicted conditional probability masses and select the optimal threshold.
W2: Assessing the classifiers with respect to utility-discounted predictive accuracies, such as $U_{65}$ and $U_{80}$ which respectively give small and large rewards for being cautious [7] , would help to further highlight the potential (dis)advantages of the classifiers.
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].
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.
[1] Del Coz, J. J., Díez, J., & Bahamonde, A. (2009). Learning Nondeterministic Classifiers. Journal of Machine Learning Research, 10(10).
[3] Mortier, T., Wydmuch, M., Dembczyński, K., Hüllermeier, E., & Waegeman, W. (2021). Efficient set-valued prediction in multi-class classification. Data Mining and Knowledge Discovery, 35(4), 1435-1469.
[4] Nguyen, V. L., Destercke, S., Masson, M. H., & Hüllermeier, E. (2018, July). Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty. In 27th International Joint Conference on Artificial Intelligence (IJCAI 2018) (pp. 5089-5095).
[7] Zaffalon, M., Corani, G., & Mauá, D. (2012). Evaluating credal classifiers by utility-discounted predictive accuracy. International Journal of Approximate Reasoning, 53(8), 1282-1301.
Questions
Q1: Please refer to "Weaknesses" for detailed comments and suggestions for further revision.
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 $1 - \delta_j$ are smaller than $\delta$.
Q3: I guess re-defining (4) as $\delta_j = \frac{1}{500}\sum_{k=1}^{500} 1{s(\hat{p}(\tilde{X}_j)) \cap s(\hat{p}^{\setminus i_k}(\tilde{X}_j)) = \emptyset}$ 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.
Limitations
L1: Discussions on related work might need to be extended.
L2: the empirical study might need to be enlarged with closely related algorithms.
Please refer to "Weaknesses" for detailed comments and suggestions for further revision.