STEP: Out-of-Distribution Detection in the Presence of Limited In-Distribution Labeled Data

Zhi Zhou, Lan-Zhe Guo, Zhanzhan Cheng, Yu-Feng Li, Shiliang PuNeurIPS 2021 · OpenReview

Introduction

In the ideal world of machine learning, we have access to massive, fully labeled datasets. In the slightly less ideal world of Semi-Supervised Learning (SSL), we have a few labels and a lot of unlabeled data, but we generally assume they all come from the same distribution.

Reality, however, is messier. In critical applications like medical diagnosis or autonomous driving, the unlabeled data pool is often "polluted" with Out-of-Distribution (OOD) samples—data from categories the model has never seen and shouldn't try to classify.

This paper addresses a specific and challenging gap: Semi-supervised OOD detection. Most existing OOD detectors rely on large labeled sets to estimate class statistics (like the Mahalanobis distance). When labels are extremely scarce (e.g., only 25 images per class), these statistical estimates collapse, making it nearly impossible to distinguish a "seen" class from an "unseen" one. To solve this, the authors introduce STEP (STructure-keEP), a novel framework that successfully detects OOD samples even when labeled data is extremely limited.

The STEP Approach

The authors propose a three-stage pipeline centered around a novel concept called Structure-Keep Unzipping.

  1. Backbone Pre-training: The process begins by using SimCLR, a popular self-supervised contrastive learning method, to train a feature extractor on the entire pool of data (both labeled and unlabeled). This ensures the model learns a rich, foundational representation of the data's features without requiring any labels.
  2. Structure-Keep Unzipping: This is the core innovation of the paper. The authors argue that while global statistics (like covariance matrices) cannot be trusted in low-data regimes, local relationships can be trusted.
Structure-Keep Unzipping process separating ID and OOD data

To leverage this, they learn a projection matrix that transforms the feature space based on two competing goals:

  • Keep: Maintain the local topological structure. If two points were neighbors in the original space, they should remain at a similar distance in the new space.
  • Unzip: Maximize the distance between all other pairs of points.

Imagine a crumpled piece of paper; "unzipping" is akin to pulling the edges apart while ensuring the local fibers don't tear. This creates a large margin that cleanly separates distinct clusters of In-Distribution (ID) and OOD data.

  1. OOD Scoring: In this newly "unzipped" space, the model simply uses the Euclidean (L2) distance to the nearest class center as the OOD confidence score.

Experimental Setup

The researchers evaluated STEP using standard computer vision benchmarks:

  • In-Distribution (ID): CIFAR-10 (with only 250 labels) and CIFAR-100 (with 400 labels).
  • Out-of-Distribution (OOD): Tiny ImageNet (TIN) and LSUN. They utilized both "cropped" and "resized" versions of these datasets to ensure the model was detecting true semantic differences rather than just low-level resizing artifacts.

Key Findings and Results

STEP demonstrates a massive performance leap over baselines like ODIN and standard Mahalanobis detectors, particularly highlighting the brittleness of global statistical metrics in low-data regimes.

  • Accuracy Boost: On CIFAR-10 versus Tiny ImageNet (cropped), STEP achieved an outstanding AUROC of 99.99%, compared to 81.00% for ODIN and 90.46% for a basic semi-supervised OOD baseline (UOOD).
  • Low Label Robustness: Even when the number of labeled samples was reduced to extreme levels, STEP’s performance remained remarkably stable, whereas competing methods saw their performance plummet.
  • Unseen OOD Generalization: Many OOD methods use a small "known" OOD validation set to tune parameters, which introduces a severe bias and causes failures when encountering different types of OOD data. STEP avoids this trap entirely.
AUROC performance comparison on Known vs. Unknown OOD datasets

In experiments where models were exposed to one OOD set (known) but tested on another (unknown), STEP maintained high performance across the board. Competing methods that relied on OOD validation sets suffered significant performance drops on the unknown data.

Limitations and Future Work

While the empirical results are highly compelling, the authors acknowledge a few areas for future improvement:

  • Theoretical Grounding: The paper currently lacks a rigorous theoretical proof explaining exactly why the "unzipping" optimization guarantees OOD separation.
  • Computational Complexity: Building a K-Nearest Neighbor (KNN) graph for the unzipping process scales quadratically ($O(n^2d)$). Although they use the Faiss library for acceleration, it remains a potential bottleneck for massive datasets.
  • Future Directions: Expanding the theoretical understanding of this phenomenon and applying the "unzipping" logic to other domains, such as Natural Language Processing (NLP), represent exciting next steps.

Summary updated

Abstract

Existing semi-supervised learning (SSL) studies typically assume that unlabeled and test data are drawn from the same distribution as labeled data. However, in many real-world applications, it is desirable to have SSL algorithms that not only classify the samples drawn from the same distribution of labeled data but also detect out-of-distribution (OOD) samples drawn from an unknown distribution. In this paper, we study a setting called semi-supervised OOD detection. Two main challenges compared with previous OOD detection settings are i) the lack of labeled data and in-distribution data; ii) OOD samples could be unseen during training. Efforts on this direction remain limited. In this paper, we present an approach STEP significantly improving OOD detection performance by introducing a new technique: Structure-Keep Unzipping. It learns a new representation space in which OOD samples could be separated well. An efficient optimization algorithm is derived to solve the objective. Comprehensive experiments across various OOD detection benchmarks clearly show that our STEP approach outperforms other methods by a large margin and achieves remarkable detection performance on several benchmarks.
BibTeX
@inproceedings{zhou2021step,
  author = {Zhi Zhou and Lan-Zhe Guo and Zhanzhan Cheng and Yu-Feng Li and Shiliang Pu},
  title = {{STEP: Out-of-Distribution Detection in the Presence of Limited In-Distribution Labeled Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=p9dySshcS0q},
}
Figure