Open Category Detection with PAC Guarantees

By Si Liu, Risheek Garrepalli, Thomas G. Dietterich, Alan Fern, Dan Hendrycks. 2018

90 citations recorded by the source corpus.

Open category detection is the problem of detecting "alien" test instances that belong to categories or classes that were not present in the training data. In many applications, reliably detecting such aliens is central to ensuring the safety and accuracy of test set predictions. Unfortunately, there are no algorithms that provide theoretical guarantees on their ability to detect aliens under general assumptions. Further, while there are algorithms for open category detection, there are few empirical results that directly report alien detection rates. Thus, there are significant theoretical and empirical gaps in our understanding of open category detection. In this paper, we take a step toward addressing this gap by studying a simple, but practically-relevant variant of open category detection. In our setting, we are provided with a "clean" training set that contains only the target categories of interest and an unlabeled "contaminated" training set that contains a fraction $\alpha$ of alien examples. Under the assumption that we know an upper bound on $\alpha$, we develop an algorithm with PAC-style guarantees on the alien detection rate, while aiming to minimize false alarms. Empirical results on synthetic and standard benchmark datasets demonstrate the regimes in which the algorithm can be effective and provide a baseline for further advancements.

Subfields: Artificial Intelligence, Anomaly & Outlier Detection, Statistical Learning Theory

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

In Anomaly & Outlier Detection

In Statistical Learning Theory

Citations in the corpus

Benchmarking Neural Network Robustness to Common Corruptions and Perturbations (2019, background): “…has focused on the important challenges of robustness to adversarial examples (Szegedy et al., 2014; Carlini & Wagner, 2017; 2016), unknown unknowns (Hendrycks et al., 2019; Hendrycks & Gimpel, 2017b; Liu et al., 2018), and model or data poisoning (Steinhardt et al., 2017; Hendrycks et al., 2018).”
Using Pre-Training Can Improve Model Robustness and Uncertainty (2019, background): “In the problem of out-of-distribution detection (Hendrycks & Gimpel, 2017b; Hendrycks et al., 2019; Lee et al., 2018a;b; Liu et al., 2018), models are tasked with (Chen et al., 2018).”
Towards neural networks that provably know when they don't know (2019, methodology): “A generalization guarantee for an out-of-distribution detection scheme is provided in Liu et al. (2018).”
Deep Anomaly Detection with Outlier Exposure (2018, background): “Recently, Liu et al. (2018) provide theoretical guarantees for detecting out-of-distribution examples under the assumption that a suitably powerful anomaly detector is available.”
Recent Advances in Open Set Recognition: A Survey (2018, background): “Some related works in other research communities can be found in [116], [151], [152], [153], [154].”
Does Your Model Know the Digit 6 Is Not a Cat? A Less Biased Evaluation of "Outlier" Detectors (2018, background): “[27] provide theoretical analysis for open-set recognition in a special setting where they wish to identify alien samples in a fixed mixture of distributions.”
A Unifying Review of Deep and Shallow Anomaly Detection (2020, background): “Nonetheless, researchers have developed a separate set of methods for open set recognition [240], [497]–[501], and an important goal for future research is to evaluate these methods from the AD perspective and to evaluate AD algorithms from the open set perspective.”
Learning Bounds for Open-Set Learning (2021, background): “Liu et al. (2018) ﬁrst proposed the PAC guarantees for open-set detection.”
Benchmarking Neural Network Robustness to Common Corruptions and Surface Variations (2018, background): “Most work on robustness in deep learning methods for vision has focused on the important challenges of robustness to adversarial examples [53, 6, 7], unknown unknowns [20, 41, 22], and model or data poisoning [4, 52, 23].”
Anomalous Instance Detection in Deep Learning: A Survey (2020, methodology): “In [22], the algorithm uses the knowledge of the upper bound on the number of anomaly examples in the training dataset to provide Probably Approximately Correct (PAC) guarantees for achieving a desired anomaly detection rate.”