Is Out-of-Distribution Detection Learnable?

By Zhen Fang, Yixuan Li, Jie Lu, Jiahua Dong, Bo Han, Feng Liu. 2022

181 citations recorded by the source corpus.

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. To study the generalization of OOD detection, in this paper, we investigate the probably approximately correct (PAC) learning theory of OOD detection, which is proposed by researchers as an open problem. 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 also offer theoretical supports for several representative OOD detection works based on our OOD theory.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Tatsuya Konishi
2. Bin Liu
3. Gyuhak Kim
4. Changnan Xiao
5. Neil Zhenqiang Gong
6. Jinyuan Jia
7. Zixuan Ke

Citations in the corpus

• Learnability and Algorithm for Continual Learning (2023, methodology): “Note that Fang et al. (2022) showed that OOD detection is learnable under a compatibility condition for a single OOD detection problem and Definition 3.6 is about learnability with respect to an ensemble of multiple OOD detection problems.”
• Generalized Out-of-Distribution Detection: A Survey (2021, unknown): “5 (Zhang et al., 2023c).”