On the Learnability of Out-of-distribution Detection

Zhen Fang, Yixuan Li, Feng Liu*, Bo Han, Jie Lu*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

Abstract

Supervised learning aims to train a classifier under the assumption that training and test data are from the same distribution. To ease the above assumption, researchers have studied a more realistic setting: out-of-distribution (OOD) detection, where test data may come from classes that are unknown during training (i.e., OOD data). Due to the unavailability and diversity of OOD data, good generalization ability is crucial for effective OOD detection algorithms, and corresponding learning theory is still an open problem. To study the generalization of OOD detection, this paper investigates the probably approximately correct (PAC) learning theory of OOD detection that fits the commonly used evaluation metrics in the literature. First, we find a necessary condition for the learnability of OOD detection. Then, using this condition, we prove several impossibility theorems for the learnability of OOD detection under some scenarios. Although the impossibility theorems are frustrating, we find that some conditions of these impossibility theorems may not hold in some practical scenarios. Based on this observation, we next give several necessary and sufficient conditions to characterize the learnability of OOD detection in some practical scenarios. Lastly, we offer theoretical support for representative OOD detection works based on our OOD theory.
Original languageEnglish
Pages (from-to)1-83
Number of pages83
JournalJournal of Machine Learning Research
Volume25
Issue number84
Publication statusPublished - Apr 2024

User-Defined Keywords

  • out-of-distribution detection
  • weakly supervised learning
  • learnability

Fingerprint

Dive into the research topics of 'On the Learnability of Out-of-distribution Detection'. Together they form a unique fingerprint.

Cite this