Abstract
Detecting data points deviating from the training distribution is pivotal for ensuring reliable machine learning. Extensive research has been dedicated to the challenge, spanning classical anomaly detection techniques to contemporary out-of-distribution (OOD) detection approaches. While OOD detection commonly relies on supervised learning from a labeled in-distribution (ID) dataset, anomaly detection may treat the entire ID data as a single class and disregard ID labels. This fundamental distinction raises a significant question that has yet to be rigorously explored: when and how does ID label help OOD detection? This paper bridges this gap by offering a formal understanding to theoretically delineate the impact of ID labels on OOD detection. We employ a graph-theoretic approach, rigorously analyzing the separability of ID data from OOD data in a closed-form manner. Key to our approach is the characterization of data representations through spectral decomposition on the graph. Leveraging these representations, we establish a provable error bound that compares the OOD detection performance with and without ID labels, unveiling conditions for achieving enhanced OOD detection. Lastly, we present empirical results on both simulated and real datasets, validating theoretical guarantees and reinforcing our insights.
Introduction
In real-world deployments, machine learning models frequently encounter inputs that fall outside their training distribution. This challenge, known as Out-of-Distribution (OOD) detection, has historically been approached from two distinct angles: unsupervised anomaly detection, which treats training data as a monolithic mass, and supervised OOD detection, which leverages class labels. Despite the widespread use of labels in modern OOD detection, the precise theoretical benefit they provide—and the conditions under which they are most effective—has remained poorly understood. This research investigates whether knowing the fine-grained differences between in-distribution classes (e.g., different cat breeds) aids in identifying outliers (e.g., a different breed or a completely different animal).
Theoretical Framework
The authors utilize a graph-theoretic approach to model how data representations are learned. By treating data points as vertices in a graph where edges denote similarity, they can analyze the feature space through spectral decomposition of the normalized adjacency matrix.
A critical technical insight of this work is the proof that minimizing standard contrastive learning objectives is theoretically equivalent to performing spectral decomposition on this data graph. This allows for a closed-form analysis of the "separability" of ID and OOD data. The performance of OOD detection is quantified using "linear probing error," which measures how effectively a simple linear boundary can distinguish ID features from OOD features.
Key Insights and Ideas
The study reveals that the utility of ID labels is highly dependent on the "distance" of the OOD data from the training distribution.
- The "Near OOD" Advantage: Labels are most transformative when OOD samples are semantically similar to ID data. In these "Near OOD" scenarios, unsupervised methods often produce overlapping clusters. ID labels act as a supervisory signal that "stretches" the ID representations into distinct class-specific components, creating clear gaps where OOD data can be identified.
- Diminishing Returns for "Far OOD": When OOD data is naturally distinct (e.g., a dog vs. cats), self-supervised features are typically sufficient for separation. In these cases, adding labels provides negligible improvement because the structural differences are already captured by the model.
- Structural Robustness: Labels force the model to learn a multi-component sub-graph structure. Theorem 1 in the paper formalizes this, showing that the benefit of labels is a function of the density of ID connections versus the sparsity of OOD-to-ID connections.
Key Results
The theoretical framework was validated using standard benchmarks, including CIFAR-10/100 as ID data and various datasets like SVHN and Textures as OOD data.
The empirical findings strongly align with the theory:
- Near OOD Performance: On CIFAR-100, incorporating ID labels improved the AUROC by 12.3% when detecting CIFAR-10 (Near OOD).
- Far OOD Performance: Conversely, for Far OOD detection (e.g., SVHN), the improvement was a marginal 0.02%.
- Model Alignment: Experiments using ResNet-18 architectures confirmed that the Frobenius norm of the adjacency matrices serves as a reliable predictor of detection performance, mirroring the theoretical bounds.
Discussion and Future Work
While this work provides a rigorous foundation for understanding the role of labels, it focuses on post-hoc detection where the model is trained exclusively on ID data. It does not yet account for "OOD-aware" training or the use of non-linear OOD scoring functions like Energy-based scores. Furthermore, the quality of the learned representations remains dependent on the choice of data augmentations used to construct the initial graph. Future research could extend this spectral framework to "Open-World Learning" scenarios, where limited OOD samples might be available during the training phase.
Summary updated