Rejection via Learning Density Ratios

Summary

The paper proposes a distributional perspective to build abstaining classifiers. By considering an idealized distribution, the authors show that this translates into optimizing a loss risk with a $\varphi$-divergence regularization term. Moreover, they provide results when considering $\alpha$-divergences, a specific family of $\varphi$-divergences. Empirical evaluation is performed over clean and noisy datasets.

Strengths

The main strengths of the paper are: i) the paper is clearly written, with clear contributions advancing the state of the art in abstaining classifiers ii) the theoretical contributions seem sound; iii) the proposed method is original and bridges DROs with Learning to Reject.

Weaknesses

The main weaknesses of the paper are: i) there is no related work section explicitly dedicated to learning with a reject option. See, e.g., [a] for a recent survey. ii) the empirical evaluation can be improved: * for instance, the paper considers only four baselines (mainly from Learning to Defer literature) and ignores popular alternatives such as softmax response [26] * the method is tested only on three datasets, which seem easy to solve. In particular, MNIST might be too easy to evaluate abstaining classifiers (an accuracy of 100% is easy to achieve with relatively few rejections). A more interesting dataset collection could be MedMNIST [b], which contains medical images from real data tasks. [a] Hendrickx, Kilian, Lorenzo Perini, Dries Van der Plas, Wannes Meert, and Jesse Davis. "Machine learning with a reject option: A survey." Machine Learning 113, no. 5 (2024): 3073-3110.\ [b] Yang, Jiancheng, Rui Shi, and Bingbing Ni. "Medmnist classification decathlon: A lightweight automl benchmark for medical image analysis." In 2021 IEEE 18th International Symposium on Biomedical Imaging (ISBI), pp. 191-195. IEEE, 2021.

Questions

I have a few questions for the authors: 1) is there a reason why you did not compare with the simplest (and often the best) abstaining classifier, i.e. the softmax response? In [c], the authors show that the classifier built using this strategy can be optimal. Moreover, recent empirical works [d,e] show that score-based approaches outperform other abstaining classifiers. 2) how did you train DEFER, without access to human predictions? As far as I know, the surrogate loss also requires specific human predictions; however, I could not find in the Appendix how this is done in practice. [c] Franc, Vojtech, Daniel Prusa, and Vaclav Voracek. "Optimal strategies for reject option classifiers." Journal of Machine Learning Research 24, no. 11 (2023): 1-49.\ [d] Jaeger, Paul F., Carsten Tim Lüth, Lukas Klein, and Till J. Bungert. "A Call to Reflect on Evaluation Practices for Failure Detection in Image Classification." In The Eleventh International Conference on Learning Representations. (2023)\ [e] Pugnana, Andrea, Lorenzo Perini, Jesse Davis, and Salvatore Ruggieri. "Deep neural network benchmarks for selective classification." arXiv preprint arXiv:2401.12708 (2024).

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

The authors discuss the limitations of their approach.

Summary

Classification with rejection emerges as a learning paradigm that allows models to abstain from making predictions. Traditional rejection learning methods typically modify the loss function, enabling models to explicitly reject making predictions when they are inaccurate or uncertain. These methods rely on providing good class probability estimates and often require training models from scratch. This paper proposes an interesting perspective to reconsider rejection not from the standpoint of the loss function, but rather from the perspective of distributions. By optimizing the risk of the loss with a $\varphi$-divergence regularization term, it seeks an idealized data distribution that maximizes the performance of pretrained models.

Strengths

1. This paper takes a more interesting approach to rejection compared to previous papers. 2. In theory, approaching from the perspective of distributions holds better prospects compared to considering single probabilities alone. 3. The theoretical richness of this paper provides strong evidence for its claims.

Weaknesses

1. For high-dimensional data, estimating density ratios and computing idealized distributions can be very challenging, implying that this method may only address low-dimensional data and its application scenarios are limited. 2. This method involves a large number of hyperparameters: $\lambda$, $\tau$, $\alpha$, $T$, which pose a significant burden for optimization. 3. The experiments in the paper may only be conducted on specific datasets and under certain conditions (some simple datasets), which could limit their generalizability to broader scenarios.

Questions

1. Although theoretically estimating the distribution $P(y|x)$ holds more promise than estimating a single probability $\max P(y|x)$, in practical situations, estimating the distribution seems less feasible compared to single probability estimates, especially given the various calibration methods available for single probabilities. 2. How did you design the expert in the experiments where you compared methods [1] from Learning to Defer？ 3. Since comparing with [1], it seems more reasonable to compare with [2], which is more relevant to the focus of this study. [1] Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. ICML 2020. [2] Cao Y, Cai T, Feng L, et al. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. NeurIPS, 2022.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A.

Summary

This paper proposes a novel method for classification with rejection based on density ratio estimation. Density ratio is estimated between the data distribution P and the "idealized" distribution Q, where Q is a distribution such that the model can have good prediction performance, while this distribution is still similar to the original data distribution P. The objective function is proposed to formulated as a risk minimization with a $\phi$-divergence regularization. Theoretical analysis is also provided to justify the soundness of the proposed method. The experiment shows that the proposed method is effective compared with well-known existing approaches.

Strengths

1. Proposed method is theoretically guaranteed and can support multiclass classification case. To me, it is not that straightforward to use density ratio estimation approach for multiclass classification with rejection and I appreciate this strength of the paper. 2. The proposed method and formulation discussed in the paper is quite general, and the discussion for Regression case also provided in appendix, suggesting the generality of the proposed method. Divergence that studies in this paper is not only KL-divergence, but different divergences were also studied.

Weaknesses

1. Unfortunately, I found the experiment section writing and result is not quite well-written compared with other sections. Perhaps there is a better way to analyse and understand practical behavior of the proposed method. - The figure shows in the paper does not really show the superiority of the method except in HAR (clean) and Gas Drift (clean). It is also quite hard to see since the starting point of each method is different. Perhaps table representation or different way to show the result might help. - Only three simple datasets were used in this paper and the discussion using these datasets still look difficult to conclude something as several methods are competitive. - In my understanding, KL and $\alpha$ divergence give almost exactly the same performance in all cases. Is this really the case? The study of hyperparameter sensitivity can also be beneficial to practitioners - Analysis of what kind of dataset characteristic makes the proposed distributional method more effective than the traditional method would be very useful. I feel existing methods such as CSS or the classifier-rejector approach might feel more like a direct approach to solving classification with rejection. Nevertheless, it is great to explore other approaches. - As a result, I believe revising the experiment section can significantly improve the paper. 2. I found the writing and organization of this paper can be significantly improved. It takes until page 4 to state the proposed method, leaving only a small space for the experiment section. Perhaps some discussion of theory for $\alpha-divergence and background of (DVI, DRO) can be wrapped up more compactly and defer to the appendix to make the paper more self-contained and provide sufficient discussion on experiments. - For reading experience, it might also be useful to highlight the final objective function (or use a latex Algorithm environment) to outline what exactly we need to do to use the proposed method so that practitioners can quickly understand how the method works. I found section 4 is quite difficult to follow. In this form, we have to go through the whole paper and mix all the ingredients to get an idea how to implement the proposed method (e.g., Normalization, how to get a(x), inverse function of $\varphi$.

Questions

1. Is there any superiority of $\alpha=3$ divergence over KL-divergence? I might have missed it. 2. Is it written in the main body of the paper what $\varphi'$ is (Eq. 11)? I believe it is a derivative of $\varphi$ over X? I am sorry if I missed it. If it is not written it should be so because for example, "'" can mean different things like how L' is used in this paper. 3. It seems the proposed method is quite weak under noisy data. Is there any possible explanation why this is the case? 4. The Theorem 4.2 (informal) states that there exists a threshold to achieve Chow's rule if original $h$ is correct looks quite restrictive to me in the sense that if h is really optimal, then we can just use h to achieve Chow's rule and there is no need to consider density ratio estimation. Can we say anything when h is not optimal? Minor comment: I think it is more common to call "classification-rejection" approach, a classifier-rejector approach (like Ni et al., 2019 [44]), or predictor-rejector approach (Mao et al., 2024) [39].

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Limitations about the need to estimate P(Y|X) with model h were discussed, suggesting that this approach requires estimating class-posterior probability. (Minor) broader impacts were discussed in Appendix L and perhaps it is better to put them in the main body if possible. Overall, I found the discussion about limitations is appropriate.

Summary

This paper propose a new classification algorithm with abstention by learning a density ratio between an "idealized" distribution to the data distribution: if the density ratio is small, the classifier rejects to predict. The proposed learning framework is general, and is a function of the choice of $f$-divergence. The paper studies two concrete choices of divergences: KL- and $\a$-divergences, which admit a closed form rejector. The paper provides some experimental supports for the proposed ideas with neural-net classifiers.

Strengths

The paper studies an important problem of classification with abstention. The proposed mathematical framework is quite neat and has nice connections with GVI and DRO. The math is quite crisp throughout the paper.

Weaknesses

While the proposed method sounds reasonable, I have some concerns/questions in the presentation. Please see questions and suggestions below.

Questions

**Questions** - What is the meaning of "The maximization is adversarial over the marginal label distribution" in line 128? - I had hard time to understanding the meaning of the "idealized rejection distribution" (as called. in line 157), especially because the following sentence was extremely confusing: ``` Given Definition 3.1 for idealized distribution, small values of $\rho(x)$ corresponds to regions of the input space $\mathcal{X}$ where having lower data probability would decrease the expected risk of the model. ``` I can't follow this sentence. Can you please elaborate this? - Further, I can't understand why does it make sense not to reject where $P(x)$ is relatively small? If the likelihood of occurrence is small, shouldn't we also avoid prediction at that point as the classification will be likely wrong? Or is the argument that we do not need to care the small probability mass in the first place as it won't incur a significant loss in expectation? - In the experiments, the proposed algorithms seem to perform well in the high-coverage regime, while dominated by existing methods in the low-coverage regime. Do you have any explanation on this? **Suggestions** - Compared to the quality of math, there are way too many typos and grammatical errors. To spot a very few: - line 23: "While" some approaches avoid... - line 25: ... approach aim**s**... - line 74: ... an addition**al**... There are too many of these throughout, so please revise them carefully. - Please consider moving lines 84-85 after line 76. - Please put subsections in Section 4 for readability.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Limitations of the framework are noted by the authors.

Response to the Rebuttal

I thank the authors for their rebuttal, and I hope they found the references to the MedMNIST collection helpful. I would like to add a small comment on the following: > The component of SR that we are missing is the calculation of the threshold according to a desired coverage guarantee. This would be a nice direction for future work to automatically prescribe $\tau$. Some approaches, as noted by the authors in the response to Reviewer MrTu, add a coverage constraint to the loss that is minimized. However, empirical evidence does not support using these models vs. SoftMax Response (see again e.g. [a,b]). In any case, given a target coverage $c$, both approaches require a calibration set and estimate the threshold $\tau$, considering the $(1-c)$ quantile of the confidence on the calibration set. Another option is resorting to cross-fitting to estimate the $\tau$ without the extra calibration set but exploiting test folds and stacking confidences (see, e.g., [c]). To conclude, I think this paper should be considered for acceptance. [a] - Feng, Leo, Mohamed Osama Ahmed, Hossein Hajimirsadeghi, and Amir H. Abdi. "Towards Better Selective Classification." In The Eleventh International Conference on Learning Representations. [b] - Pugnana, Andrea, Lorenzo Perini, Jesse Davis, and Salvatore Ruggieri. "Deep neural network benchmarks for selective classification." arXiv preprint arXiv:2401.12708 (2024). [c] - Pugnana, Andrea, and Salvatore Ruggieri. "A model-agnostic heuristics for selective classification." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 8, pp. 9461-9469. 2023.

Response

Thank you for your elaborated response to my review. I understand that the author's work is interesting and meaningful, but I still maintain my concerns about its validity on high-dimensional datasets (despite the addition of experiments using MedMNIST). As we are now gradually entering the era of large models, could you provide some more experiments on high-dimensional data, such as CIFAR10, regardless of the results? I hope this will help to better understand the limitations of the method.

Thank you for your feedback

Thank you for the author's rebuttal. I also have read other reviews. Given the fact that the organization will be modified as mentioned in the rebuttal and additional experiments provided, I would like to raise the score to 6 (Weak accept). I am aware of the concern of the high-dimensionality problem suggested by other reviewers. I believe the approach taken by this paper is innovative and it is also interesting to design other algorithms that follow this principle of identifying idealized distribution to use it as a criterion for rejection, which could be preferable to the current method in the high dimensionality regime.