DOS: Diverse Outlier Sampling for Out-of-Distribution Detection

Response to Reviewer BvLD

We appreciate the reviewer for the insightful and detailed comments. Please find our response below: ## 1. Novelty and theoretical analysis [W1] Yes, the factor of diversity has been explored in the context of active learning, where the goal is to select **in-distribution data** for better generalization. In this work, we select **outlier examples** as auxiliary data to improve OOD detection, which is different from active learning. In other words, the problem setting of this work is different from those methods for active learning. To the best of our knowledge, this work is **the first to investigate the benefits of diversity in outlier sampling for OOD detection**, as recognized by Reviewer HJAj. In the literature, previous works proposed random selection [1,4,5,6] and greedy sampling [2,3] strategies to build the auxiliary OOD dataset. As shown in Section 5, our proposed method achieves substantial improvements over previous methods and enjoys fast convergence. This work also provides unique insights compared to the diverse sampling of active learning. In active learning, diverse sampling aims to find a collection of samples that can approximate the entire data distribution (ID). In this work, we propose the importance of diversity in alleviating the sampling bias of greedy sampling (See Subsection 2.2). As suggested by reviewer HJAj, we provide a formal definition of diversity (see response to reviewer HJAj), which is different from that of active learning. Lastly, we would like to clarify that outlier exposure is not directly linked to the generalization bound, which is usually analyzed in active learning. The goal of outlier exposure is to increase the differentiation between ID and OOD inputs, while we only have access to a finite OOD dataset from the infinite OOD feature space. As far as we know, there is no general theoretical framework in existing works to analyze outlier exposure. Instead, **we provide in-depth analysis to show the advantages of DOS from various perspectives**, as appreciated by all reviewers. ## 2. Comparison with K-means++ clustering algorithm [Q1] Thank you for the great suggestion. To investigate the importance of the clustering step in diverse sampling, we conduct sensitivity analysis to compare the performance of various clustering algorithms, including Agglomerative [7], K-Means++ seeding [8,9], Spherical K-Means, moVMF soft, and moVMF hard [10,11]. The experiments are conducted with a large benchmark (In10-IN990). We keep the same training setting as in the manuscript. In addition to the OOD detection performance, we also present clustering time in each iteration, which is also a key factor in choosing a clustering algorithm. As shown in the Table below, K-means (our choice) achieves the best performance among the compared algorithms. In addition, the two algorithms based on moVMF require too much time in each iteration, making it non-trivial to implement in this case. The resting algorithms cannot achieve comparable performance to ours, while the three obtain a little higher efficiency. We add the empirical results to Appendix D of the manuscript. | Metric | Agglomerative | K-Means++ seeding | Spherical K-Means | moVMF soft | moVMF hard | K-Means (Ours) | |:----------------------:|:-------------:|:-----------------:|:-----------------:|:----------:|:----------:|:--------------:| | FPR95 $\downarrow$ | 38.39 | 48.19 | 24.11 | - | - | **20.71** | | Time Cost $\downarrow$ | **0.05s** | 2.0s | 3.1s | 242.1s | 243.0s | 4.5s | ## 3. Typo in the euqation 2 [W2] Thank you for pointing it out. We have fixed it in the updated version. [1] Deep Anomaly Detection with Outlier Exposure. ICLR'19. [2] Background Data Resampling for Outlier-aware Classification. CVPR'20. [3] ATOM: Robustifying Out-of-distribution Detection Using Outlier Mining. ECML-PKDD'21. [4] Self-supervised Learning for Generalizable Out-of-distribution Detection. AAAI'20. [5] Energy-based Out-of-distribution Detection. NeurIPS'20. [6] Breaking down Out-of-distribution Detection: Many Methods based on OOD Training Data Estimate a Combination of the Same Core Quantities. ICML'22. [7] Ward’s Hierarchical Agglomerative Clustering Method: Which Algorithms Implement Ward’s Criterion? Journal of Classification 2014. [8] K-Means++: The Advantages of Careful Seeding. SODA'07. [9] Deep Anomaly Detection under Labeling Budget Constraints. ICML'23. [10] Clustering on the Unit Hypersphere using von Mises-Fisher Distributions. JMLR'05. [11] On PyTorch Implementation of Density Estimators for von Mises-Fisher and Its Mixture. arXiv'21.

Kind reminder to Reviewer BvLD

Dear Reviewer BvLD, Sorry to disturb you. We sincerely appreciate your valuable comments. We understand that you may be too busy to check our rebuttal. To avoid ambiguity, we would like to further provide a comparison of rigorous definitions of diversity, to show the novelty. Regarding the novelty, we would like to clarify the difference between our method and diverse sampling in active learning from the following perspectives: - **Problem Setting**: We select outlier examples as auxiliary data to improve OOD detection, while active learning aims to select in-distribution data for better generalization. - **Definition of Diversity**: Given a set of all examples $\mathcal{D} = { \lbrace \mathbf{x}\_i\rbrace }^{N}\_{i=1}$, we define that the selected subset $\mathcal{S}$ is diverse, if $\mathcal{S}$ satisfies the condition: $$\delta(\mathcal{S}) = \frac{1}{K}\sum\_{x\_{i} \in \mathcal{S}} \min \_{j \neq i} d\left(x\_{i}, x\_{j}\right) \geq C,$$ where $d$ denotes a distance function in the space, $C$ is a constant that controls the degree of diversity (see response to reviewer HJAj for more details). Our goal is to increase the lower bound $C$ while keeping the informativeness. Differently, the diversity sampling in active learning usually aims to minimize the following objective to construct $\mathcal{S}$: $$f(\mathcal{S})=\sum_{x_i \in \mathcal{D}} \min _{x_j \in \mathcal{S}} d\left(x_i, x_j\right).$$ Their goal is to minimize the $f(\mathcal{S})$ so that the subset $\mathcal{S}$ is sufficiently representative to replace $\mathcal{D}$. - **Insight**: In active learning, diverse sampling aims to find a collection of samples that can approximate the entire data distribution (ID). In this work, we propose the importance of diversity in alleviating the sampling bias of greedy sampling (See Subsection 2.2). In addition, we have fixed the typo in equation 2 and conducted additional sensitivity analysis to compare the performance of various clustering algorithms, as you suggested. We show that K-means (our choice) achieves the best performance among the compared algorithms. The detailed results can be found in Appendix D. We sincerely hope that the above answers can address your concerns. We look forward to your response and are willing to answer any questions.

Response to Reviewer HJAj (1/2)

Thank you for the constructive and elaborate feedback. Please find our response below: ## 1. Definition of diversity, mechanism of the clustering-based sampling [W2,Q4] Thank you for pointing out the ambiguous description. Here, we provide a rigorous definition of diversity and show how clustering-based sampling promotes diversity. Given a set of all OOD examples $\mathcal{D} = { \lbrace \mathbf{x}\_i \rbrace}^{N}\_{i=1}$, our goal is to select a subset of $K$ examples $\mathcal{S} \subseteq \mathcal{D}$ with $|\mathcal{S}| = K$. We define that the selected subset is diverse, if $\mathcal{S}$ satisfies the condition: $$\delta(\mathcal{S}) = \frac{1}{K}\sum\_{x\_{i} \in \mathcal{S}} \min _{j \neq i} d\left(x\_{i}, x\_{j}\right) \geq C,$$ where $d$ denotes a distance function in the space and $C$ is a constant that controls the degree of diversity. A larger value of $C$ reflects a stronger diversity of the subset. A greedy method to promote diversity is directly maximizing the left term $\delta(\mathcal{S})$ among all possible solutions. However, finding the optimal solution requires high computational complexity. And, it will be challenging to maintain the informativeness of selected examples, as you are concerned in W3. Therefore, we adopt the K-means clustering algorithm to keep the diversity of the selected subset. Intuitively, the clustering algorithm avoids repeatedly selecting examples in the same cluster, i.e., similar examples [1,2]. In particular, the distance between two examples from different clusters is lower bounded by the minimum distance between the boundary of the two clusters. By enlarging the separability of clusters (the goal of clustering), we can then increase the lower bound of $\delta(S)$, i.e., $\mathcal{C}$. In this way, we show the relationship between clustering and diversity. In addition, we adopt the Calinski-Harabasz (CH) index as a proxy to measure the diversity of the subset (see Figure 3). In particular, the CH index is the ratio of the between-cluster sum of squares (BCSS) and the within-cluster sum of squares (WCSS). A higher value of the CH index reflects a larger between-cluster distance and smaller within-cluster distance, leading to a higher value of $\mathcal{C}$. ## 2. Diversity may introduce easy outliers. [W3] Yes, promoting diversity in sampling would include some outliers that are easier than those selected by greedy sampling. As shown in Subsection 2.2, the hardest examples selected by the greedy sampling might be similar (See Figure 2a), leading to suboptimal performance in OOD detection (See Figure 2b). Therefore, we propose to sample **the hardest examples from different clusters**, which introduces diversity among the selected examples. Despite the fact that those diverse examples might not be the hardest globally, they are sufficiently informative to support the OOD detection task, as verified in Tables 1 and 2. ## 3. Convincing results for the bias of greedy sampling in Figure 1c [Q1] To support Figure 1c, we design an empirical analysis (see Subsection 2.2) to show the biased distribution caused by greedy sampling. As shown in Figure 2a, the greedy strategy leads to biased sampling, which exhibits an imbalanced distribution of outliers over the six clusters. To make it clearer, we add a note in the caption of Figure 1c. ## 4. Empirical evidence for the imbalanced OOD detection of biased sampling [Q2] Thank you for pointing out the ambiguous word. For clarification, we refer to "imbalanced" as "suboptimal" performance of OOD detection in the sentence. As shown in Figure 2b, the biased sampling leaves a large portion of OOD samples overconfident, which is suboptimal compared to the uniform sampling. In the revised version, we replace the "imbalanced" with "suboptimal" in Section 1. ## 5. The relationship between the cluster with diversity [Q3] We guess your concern is about how diverse clusters affect OOD detection. In Figure 2b, we provide an empirical analysis to show the advantage of uniform sampling, compared to biased sampling. The results show that the uniform strategy with max diversity achieves a much lower FPR95 than the biased strategy, which demonstrates the critical role of diversity in sampling.

Response to Reviewer bYrq

Thanks for your positive and valuable suggestions. Please find our response below: ## 1. Sensitivity analysis on clustering algorithms [W1] Thank you for the great suggestion. Here, we conduct sensitivity analysis to compare the performance of various clustering algorithms, including Agglomerative [1], K-Means++ seeding [2,3], Spherical K-Means, moVMF soft, and moVMF hard [4,5]. The experiments are conducted with the large benchmark (IN10-IN990). We keep the same training setting as in the manuscript. In addition to the OOD detection performance, we also present clustering time in each iteration, which is also a key factor of choosing clustering algorithm. As shown in the Table below, K-means (our choice) achieves the best performance among the compared algorithms. In addition, the two algorithms based on moVMF require too much time in each iteration, making it non-trivial to implement in this case. The resting algorithms cannot achieve comparable performance to ours, while they three obtains a little higher efficiency. We add the empirical results into Appendix D of the manuscript. | Metric | Agglomerative | K-Means++ seeding | Spherical K-Means | moVMF soft | moVMF hard | K-Means (Ours) | |:----------------------:|:-------------:|:-----------------:|:-----------------:|:----------:|:----------:|:--------------:| | FPR95 $\downarrow$ | 38.39 | 48.19 | 24.11 | - | - | **20.71** | | Time Cost $\downarrow$ | **0.05s** | 2.0s | 3.1s | 242.1s | 243.0s | 4.5s | ## 2. Presentation of error bars [W2] Thank you for pointing this out. We add the error bars in the revised version. [1] Ward’s Hierarchical Agglomerative Clustering Method: Which Algorithms Implement Ward’s Criterion? Journal of Classification 2014. [2] K-Means++: The Advantages of Careful Seeding. SODA'07. [3] Deep Anomaly Detection under Labeling Budget Constraints. ICML'23. [4] Clustering on the Unit Hypersphere using von Mises-Fisher Distributions. JMLR'05. [5] On PyTorch Implementation of Density Estimators for von Mises-Fisher and Its Mixture. arXiv'21.