On the Learnability of Out-of-distribution Detection
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryOut-of-Distribution DetectionOut of Distribution (OOD) DetectionPAC learningSimilar Papers 제목 키워드 기반
A Closer Look at the Learnability of Out-of-Distribution (OOD) Detection
Machine learning algorithms often encounter different or "out-of-distribution" (OOD) data at deployment time, and OOD detection is frequently employed to detect these examples. While it works reasonably well in practice,…
Learning TheoryOut of Distribution (OOD) DetectionPAC learningIs Out-of-Distribution Detection Learnable?
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-dist…
DiversityLearning TheoryOut-of-Distribution DetectionOut of Distribution (OOD) Detection+1Distribution Learnability and Robustness
We examine the relationship between learnability and robust (or agnostic) learnability for the problem of distribution learning. We show that, contrary to other learning settings (e.g., PAC learning of function classes),…
PAC learningHow Out-of-Distribution Detection Learning Theory Enhances Transformer: Learnability and Reliability
Transformers excel in natural language processing and computer vision tasks. However, they still face challenges in generalizing to Out-of-Distribution (OOD) datasets, i.e. data whose distribution differs from that seen …
Image ClassificationLearning TheoryOut-of-Distribution DetectionOn the Learnability of Distribution Classes with Adaptive Adversaries
We consider the question of learnability of distribution classes in the presence of adaptive adversaries -- that is, adversaries capable of intercepting the samples requested by a learner and applying manipulations with …