PaperlayerView exact revision on arXiv

Source-linked AI summary

Out-of-Distribution Detection with Deep Nearest Neighbors

Yiyou Sun, Yifei Ming, Xiaojin Zhu, Yixuan Li

arXiv:2204.06507v3cs.LGcs.CV

TL;DR

OOD detection must identify unknown inputs, while prior distance-based approaches rely on feature-space distributional assumptions. The paper evaluates non-parametric nearest-neighbor distance instead, finding superior benchmark performance and greater flexibility.

  • Problem

    Prior distance-based OOD methods impose distributional assumptions on the feature space, although those assumptions may not hold.

  • Method

    The paper uses normalized deep nearest-neighbor distances and threshold-based level-set estimation for OOD detection.

  • Results

    24.77% lower FPR@TPR95 than SSD+ is reported under the same ImageNet-1k-trained model.

  • Takeaways & Limitations

    Nearest-neighbor OOD detection provides a flexible, distribution-assumption-free approach with superior results across several benchmarks.

  • Takeaways & Limitations

    Experiments approximate universal OOD using a diverse but finite collection of datasets.

Abstract

from arXiv · show

Out-of-distribution (OOD) detection is a critical task for deploying machine learning models in the open world. Distance-based methods have demonstrated promise, where testing samples are detected as OOD if they are relatively far away from in-distribution (ID) data. However, prior methods impose a strong distributional assumption of the underlying feature space, which may not always hold. In this paper, we explore the efficacy of non-parametric nearest-neighbor distance for OOD detection, which has been largely overlooked in the literature. Unlike prior works, our method does not impose any distributional assumption, hence providing stronger flexibility and generality. We demonstrate the effectiveness of nearest-neighbor-based OOD detection on several benchmarks and establish superior performance. Under the same model trained on ImageNet-1k, our method substantially reduces the false positive rate (FPR@TPR95) by 24.77% compared to a strong baseline SSD+, which uses a parametric approach Mahalanobis distance in detection. Code is available: https://github.com/deeplearning-wisc/knn-ood.

1. Introduction

OOD detection is needed for reliable open-world deployment, but prior distance-based methods assume a particular feature-space distribution. This paper studies non-parametric deep nearest neighbors, reports strong benchmark performance, and provides empirical and theoretical support.

  • OOD detection distinguishes familiar ID inputs from unknown OOD inputs so classifiers can take precautions during deployment.
  • Prior distance-based methods assume OOD samples lie relatively far from ID data and may model features with multivariate Gaussian distributions.
  • Non-parametric nearest-neighbor detection avoids distributional assumptions about the feature space, offering greater flexibility and generality.
  • KNN partitions ID and OOD data using the k-th nearest-neighbor distance computed from penultimate feature embeddings.
  • KNN demonstrates superior performance across OOD benchmarks, model architectures, and training losses.
  • 24.77% lower FPR@TPR95 is reported against SSD+ under the same ImageNet-1k-trained model.
  • The paper also studies feature normalization and compact representations, and theoretically analyzes rejection relative to the Bayes optimal estimator.

2. Preliminaries

The preliminaries formulate OOD detection as deciding whether a test input belongs to the training distribution. A score and threshold define the ID-versus-OOD decision.

  • The supervised setup uses input space X, label space Y, and a training set sampled independently from the joint distribution PXY.
  • A neural network f maps inputs to logits used to predict class labels.
  • OOD detection complements classification by identifying inputs outside the known distribution as unknown.
  • At test time, detection decides whether x belongs to the in-distribution marginal Pin or is OOD.
  • A level-set rule classifies samples with higher scores S(x) as ID and uses λ as the decision threshold.

3. Deep Nearest Neighbor for OOD detection

The method uses normalized deep feature embeddings and k-th nearest-neighbor distances for threshold-based OOD detection. It avoids distributional assumptions, uses only ID data for thresholding, and is intended to work across models and datasets.

  • Distance-based OOD detection uses model feature embeddings and assumes OOD samples are relatively far from ID data.
  • KNN computes the k-th nearest-neighbor distance from a test embedding to training embeddings and applies a threshold-based decision.
  • The method normalizes penultimate features before calculating Euclidean distances to training embeddings.
  • The threshold is typically selected so that a high fraction of ID data, such as 95%, is correctly classified, without using OOD data.
  • KNN makes no distributional assumption and remains applicable when features do not follow a mixture of Gaussians.
  • Approximate nearest-neighbor search supports millisecond-scale processing for databases containing billions of images.
  • The testing procedure is model-agnostic across architectures including CNNs and Transformer-based ViT models.

4. Experiments

The experiments evaluate KNN-based OOD detection across datasets, model architectures, training losses, and design choices. Results show strong performance against parametric and non-parametric baselines, including on hard OOD tasks and ImageNet.

  • Evaluation setup: The evaluation covers comparisons with parametric and non-parametric OOD methods across common, hard, and large-scale benchmarks.Metrics include FPR95, AUROC, ID accuracy, and per-image inference time.
  • Training losses: KNN is evaluated with cross-entropy and supervised contrastive losses to test compatibility with different training procedures.KNN denotes the CE-trained method, while KNN+ denotes the SupCon-trained variant.
  • Common benchmarks: 29.15% average FPR95 for KNN versus 37.94% for Mahalanobis under the same cross-entropy-trained model.This comparison isolates the non-parametric KNN method from the parametric Mahalanobis baseline.
  • Common benchmarks: KNN+ reduces average FPR95 by 5.45%, a relative 32.99% error reduction, compared with SSD+ under the same SupCon-trained model.Both methods use contrastively learned representations, but SSD+ applies a class-conditional Gaussian and Mahalanobis-distance model.
  • Hard OOD tasks: KNN+ outperforms alternative non-parametric methods by a large margin and consistently outperforms SSD+ on hard OOD datasets.The hard-task evaluation uses LSUN-FIX, ImageNet-FIX, ImageNet-R, and CIFAR-100.
  • Large-scale ImageNet task: On ImageNet, KNN+ outperforms the best baseline by 18.01% in FPR95 and reduces FPR95 versus SSD+ by 24.77% while maintaining comparable inference speed.Using 1% randomly sampled training data yields similar performance to using the full dataset.
  • Model architectures: The nearest-neighbor method also consistently outperforms Mahalanobis on a ViT-B/16 model fine-tuned on ImageNet-1k with cross-entropy loss.This extends the evaluation beyond convolutional architectures.

5. A Closer Look at KNN-based OOD Detection

The analysis identifies feature normalization as critical for KNN-based OOD detection and examines design choices affecting performance, including feature layers, activation rectification, and distance variants.

  • Feature normalization is critical: 61.05%: Feature normalization improves FPR95 compared with using unnormalized features.Normalization mitigates misleading Euclidean distances caused by differing feature norms between ID and OOD data.
  • Feature normalization is critical: ID features can have larger L2 norms than OOD features, making unnormalized ID-to-ID distances large and weakening nearest-neighbor separation.Figure 4 compares feature norms and k-NN distance distributions before and after normalization.
  • Feature representations: Penultimate-layer features outperform projection-head features across all tested OOD datasets.The paper attributes this result to the penultimate layer preserving more information and having higher dimensionality.
  • Activation rectification: Activation rectification further improves KNN-based OOD detection by suppressing overly high activations in OOD samples.The comparison is reported in Table 6 using ImageNet-1k ID data and averages across test OOD datasets.
  • Distance variants: K-th-nearest-neighbor and averaged-k-nearest-neighbor distances achieve similar average performance across four OOD datasets.The k-th-neighbor distance is retained despite similar performance because the paper indicates it has a simpler practical advantage.

6. Theoretical Justification

The theoretical analysis models OOD detection in feature space without strong OOD prior information and shows that thresholded KNN distance can reproduce an estimated Bayesian decision rule.

  • Setup: The analysis treats OOD detection as binary classification between ID and OOD samples in an embedding space.The setup uses labels 0 for OOD and 1 for ID, with testing samples drawn from a joint distribution.
  • Setup: The theory uses a Huber contamination model to represent test data containing both ID and OOD samples.The mixture fraction ε controls the proportion of OOD samples at test time.
  • OOD modeling: OOD samples are modeled as having equal chance to occur outside the high-density region of the ID distribution.This assumption reflects the lack of strong prior knowledge about the OOD distribution.
  • KNN decision rule: KNN distance serves as a non-parametric density estimate and defines the decision rule through a threshold on the k-th-nearest-neighbor distance.The rule classifies a sample as ID when its negative KNN distance exceeds threshold λ.
  • Main result: KNN-based OOD detection can reject inputs equivalently to an estimated Bayesian binary decision function.The analysis connects small KNN distances with high estimated ID probability.
  • Scope: The experiments approximate universal OOD using a diverse but finite collection of datasets, making the theory complementary to rather than identical with the experiments.This is an explicit scope boundary of the empirical evaluation.

7. Related Work

Related work spans scoring functions, training-time regularization, representation learning, and anomaly detection. The paper distinguishes its KNN approach as non-parametric and focused on multi-class ID classification alongside OOD detection.

  • OOD detection: OOD scoring methods include OpenMax, maximum softmax probability, ODIN, deep ensembles, Mahalanobis distance, energy, activation rectification, and gradient-based scores.These methods construct scores for identifying OOD inputs during inference.
  • OOD detection: Training-time regularization methods modify model learning to encourage more suitable behavior on OOD inputs.The cited literature includes approaches based on uncertainty, prediction behavior, and related regularization strategies.
  • Representation learning: Representation-learning studies use augmentations and contrastive losses, while commonly applying Mahalanobis distance under Gaussian feature-space assumptions.The paper contrasts these parametric assumptions with its KNN detector.
  • Positioning: The proposed KNN method is non-parametric, imposes no prior on the ID distribution, and is reported to outperform SSD while remaining easy to use.The distinction concerns the OOD detection method, despite shared benefits from high-quality representations.
  • KNN for anomaly detection: KNN anomaly detection typically targets abnormal samples from one class, whereas OOD detection additionally requires multi-class classification for ID data.The paper positions its setting as distinct from tabular and one-class anomaly-detection applications.

8. Conclusion

The paper presents nearest-neighbor distance as a flexible, distribution-free approach to OOD detection and reports improved benchmark performance, while emphasizing representation quality and distance choice.

  • Conclusion: The paper presents the first study exploring and demonstrating non-parametric nearest-neighbor distance for OOD detection.The approach avoids distributional assumptions about the underlying feature space.
  • Conclusion: KNN-based OOD detection improves performance across several benchmarks and establishes superior results.The conclusion attributes success to both high-quality feature embeddings and a suitable distance measure.
  • Conclusion: High-quality feature embeddings and a suitable distance measure are described as indispensable components of OOD detection.This conclusion summarizes the paper’s central practical insight.

A. Theoretical Analysis

The analysis estimates ID and OOD probabilities from empirical nearest-neighbor density and combines them to estimate the posterior probability that a sample is ID. The theorem follows by substituting these empirical estimates under stated assumptions.

  • The proof sketch is provided for the key empirical estimation idea, while the convergence-rate lemma’s proof is referred to prior work.
  • The Bayesian posterior probability that a feature is ID combines estimated ID and OOD densities weighted by their respective class probabilities.
  • The neighborhood used for density estimation contains unit-sphere data points within a specified Euclidean radius of the feature vector.
  • The analysis assumes the density satisfies Lebesgue’s differentiation theorem so that the probability density can be attained from local neighborhoods.
  • The empirical ID density is estimated from the k-nearest-neighbor distance around each normalized feature vector.Normalized features lie on the surface of an m-dimensional unit sphere, where the local dimension is m − 1.
  • The OOD model assumes equal chance for samples to appear outside the high-density region of ID data because the OOD distribution is unknown.
  • The theorem is obtained by plugging the empirical ID and OOD estimates into the posterior expression, with the threshold chosen to satisfy the theorem.

B. Configurations

The paper compares several non-parametric anomaly-detection methods using specified implementation settings. It also reports that class-aware k-NN embeddings support both OOD detection and multi-class classification.

  • IForest uses 100 base estimators, 256 randomly drawn samples per estimator, and 512 features per estimator.
  • LOF defines its outlier score from k-NN distances with k = 50.
  • LODA combines multiple weaker binary classifiers in an ensemble and uses 10 histogram bins.
  • PCA calculates outlier scores using 50 components associated with directions having small eigenvalues.
  • OCSVM learns a density-level-set decision boundary with an RBF kernel using γ = 1/512 and a training-error upper bound of 0.5.
  • Class-aware k-NN distance can support both OOD detection and multi-class classification tasks.

C. Results on Different Architecture

The paper evaluates nearest-neighbor OOD detection on DenseNet-101 using results averaged across the OOD test datasets described in Section 4.1.

  • KNN’s strong performance holds on DenseNet-101, extending the reported competitive results beyond ResNet.
  • Table 7 compares OOD detection methods based on models trained only on ID data, with all values averaged across OOD test datasets and reported as percentages.
Loading 2204.06507v3…