When and How Does In-Distribution Label Help Out-of-Distribution Detection?

Xuefeng Du, Yiyou Sun, Yixuan Li

Overview

This paper provides the first rigorous theoretical framework to explain how and when class labels for in-distribution (ID) data improve out-of-distribution (OOD) detection. Using a graph-theoretic approach, the authors prove that ID labels are most beneficial in "near OOD" scenarios—where OOD samples are semantically similar to training data—by forcing the model to learn more distinct, separable feature representations.

The Problem: Anomaly vs. OOD Detection

In the real world, machine learning models often encounter "out-of-distribution" (OOD) data—inputs that differ significantly from the training set. Reliably detecting these is crucial for safety and robustness.

Historically, two fields have tackled this: Anomaly Detection, which typically ignores class labels and treats all training data as a single "normal" class, and OOD Detection, which leverages supervised learning and class labels. While researchers intuitively felt that knowing class labels should help the model understand the boundaries of "normalcy," there was no formal mathematical proof explaining when and how these labels actually provide an advantage. This paper bridges that gap, delineating the specific conditions under which ID labels enhance OOD detection.

Methodology: A Graph-Theoretic Approach

The authors employ a graph-theoretic approach to model data representations:

  1. Graph Formulation: They represent the ID data as a graph where vertices are data points and edges encode similarity (e.g., through data augmentations).
  2. Spectral Decomposition: They characterize the features learned by neural networks as the top-$k$ eigenvectors of the graph's normalized adjacency matrix. This elegantly links graph theory to modern contrastive learning objectives.
  3. Perturbation Analysis: To understand the impact of labels, they treat the addition of ID labels as a "perturbation" to the unlabeled graph. Labels add "supervised connectivity," strengthening the bonds between points in the same class and effectively creating distinct connected sub-graphs.
  4. Provable Error Bounds: They derive a closed-form error bound that compares OOD detection performance (measured by linear probing error) with and without ID labels.

Key Insights and Ideas

Near vs. Far OOD Scenarios
  • The "Near OOD" Advantage: The most significant insight is that labels matter most when the OOD data is semantically close to the ID data. Without labels, the model might "smear" ID and OOD representations together. Labels force the model to partition the ID space into distinct clusters, making the "intruder" OOD samples much easier to spot.
  • Diminishing Returns for Far OOD: In "Far OOD" scenarios (e.g., identifying a house number from a dataset of animals), the unsupervised features are often already distinct enough. In these cases, adding class labels provides marginal benefit.
  • Sparsity is Key: Labels are most helpful when the ID data is naturally "sparse" or poorly clustered in an unlabeled setting. The supervisory signal acts as a structural reinforcement, carving out clear boundaries that didn't exist before.
  • Bridging Two Fields: By showing that supervised OOD detection and unsupervised anomaly detection are two ends of the same spectral decomposition spectrum, the paper provides a unified language for researchers in both fields.

Key Results

OOD Detection Performance Table

The authors validated their theory using a mix of simulated and real-world benchmarks (e.g., CIFAR-10/100 as ID; SVHN, Textures, Places365 as Far OOD).

  • Quantitative Gains: On CIFAR-100 (Near OOD), using ID labels improved the AUROC (Area Under the Receiver Operating Characteristic) significantly compared to the unlabeled approach.
  • Far OOD Stability: On SVHN (Far OOD), the improvement was negligible, confirming the theory that labels are less critical when the distributions are already vastly different.
  • Theoretical Validation: The empirical results consistently aligned with the derived lower bounds. For instance, as the Frobenius norm of the OOD-ID adjacency matrix (a measure of similarity) increased, the performance gap between labeled and unlabeled models grew.

Limitations and Future Work

While the paper provides a landmark theoretical foundation, some limitations remain:

  • Computational Complexity: The spectral decomposition approach is elegant for theory but can be computationally expensive to calculate directly for massive, billion-scale datasets.
  • Specific Objectives: The analysis focuses on representations learned via spectral contrastive learning; extending this to other architectures (like Vision Transformers) or other loss functions (like Cross-Entropy) remains an open area.
  • Outlier Exposure: The current work focuses on how ID labels help. A natural next step is to theoretically analyze the impact of having access to a small set of OOD examples during training (known as outlier exposure).

Summary updated

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.
BibTeX
@inproceedings{du2024when,
  author = {Xuefeng Du and Yiyou Sun and Yixuan Li},
  title = {{When and How Does In-Distribution Label Help Out-of-Distribution Detection?}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=knhbhDLdry},
}
Figure