Open Category Detection with PAC Guarantees

Introduction

Most machine learning systems implicitly or explicitly assume that their training experience is representative of their test experience. This assumption is rarely true in real-world deployments of machine learning, where “unknown unknowns”, or “alien” data, can arise without warning. Ignoring the potential for such aliens can lead to serious safety concerns in many applications and significantly degrade the accuracy of test set predictions in others. For example, consider a scientific application where a classifier is trained to recognize specific categories of insects in freshwater samples in order to detect important environmental changes (Lytle et al., 2010). Test samples will typically contain some fraction of specimens belonging to species not represented in the training data. A classifier that is unaware of these new species will misclassify the specimens as belonging to existing species. This will produce incorrect scientific conclusions.

The problem of open category detection is to detect such alien examples at test time. An ideal algorithm for this problem would guarantee a user-specified alien-detection rate (e.g., 95%), while attempting to minimize the false alarm rate. Unfortunately, no existing algorithm provides such guarantees under general conditions. In addition, empirical evaluations of existing algorithms for open category detection typically do not directly evaluate alien detection rates, which are perhaps the most relevant for safety-critical applications. Overall, our current theoretical and practical understanding of open category detection is lacking from a safety and accuracy perspective.

Is it possible to achieve open category detection with guarantees? In this paper, we take a step toward answering this question by studying a simplified, but practically relevant, problem setting. To motivate our setting, consider the above insect identification problem. At training time it is reasonable to expect that a clean training set is available that contains only the insect categories of interest. At test time, a new sample will include insects from the training categories along with some percentage of insects from new alien categories. Further, scientists may have reasonable estimates for this percentage based on their scientific knowledge and practical experience. We would like to guarantee that the system is able to raise an alarm for, say, 95% of the insects from alien classes, with each alarm being examined by a scientist. At the same time, we would like to avoid as many “false alarms” as possible, since each alarm requires scientist effort.

To formalize the example, our setting assumes two training sets: a clean training dataset involving a finite set of categories and a contaminated dataset that contains a fraction $\alpha$ of aliens. Our first contribution is to show that, in this setting, theoretical guarantees are possible given knowledge of an upper bound on $\alpha$. In particular, we give an algorithm that uses this knowledge to provide Probably Approximately Correct (PAC) guarantees for achieving a user-specified alien detection rate. While knowledge of a non-trivial upper bound on $\alpha$ may not always be possible, in many situations it will be possible to select a reasonable value based on domain knowledge, prior data, or by inspecting a sample of the test data.

The key idea behind our algorithm is to leverage modern anomaly detectors, which are trained on the clean data. Our algorithm combines the anomaly-score distributions over the clean and contaminated training data in order to derive an alarm threshold that achieves the desired guarantee on the alien detection rate on new test queries. In theory the detection rate guarantee will be met regardless of the quality of the anomaly detector. The quality of the detector, however, has a significant impact on the false alarm rate, with better detectors leading to fewer false alarms.

We carry out experimentsCode for reproducing our experiments can be found at https://github.com/liusi2019/ocd. on synthetic and benchmark datasets using a state-of-the-art anomaly detector, the Isolation Forest (Liu et al., 2008). We vary the amount of training data, the fraction $\alpha$ of alien data points, along with the accuracy of the upper bound on $\alpha$ provided to our algorithm. The results indicate that our algorithm can achieve the guaranteed performance when enough data is available, as predicted by the theory. The results also show that for the considered benchmarks, the Isolation Forest anomaly detector is able to support non-trivial false positive rates given enough data. The results also illustrate the inherent difficulty of the problem for small datasets and/or small values of $\alpha$. Overall, our results provide a useful baseline for driving future work on open category detection with guarantees.

Related Work

Open category detection is related to the problem of one-class classification, which aims to detect outliers relative to a single training class. One-class SVMs (OCSVMs) (Schölkopf et al., 2001) are popular for this problem. However, they have been found to perform poorly for open category detection due to poor generalization (Zhou & Huang, 2003), which has been partly addressed by later work (Manevitz & Yousef, 2002; Wu & Ye, 2009; Jin et al., 2004; Cevikalp & Triggs, 2012). OCSVMs have been employed in a multi-class setting similar to open category detection (Heflin et al., 2012; Pritsos & Stamatatos, 2013). However, there are no direct mechanisms to control the alien detection rate of these methods, which is a key requirement for our problem setting.

Work on classification with rejection/abstaining options (Chow, 1970; Wegkamp, 2007; Tax & Duin, 2008; Pietraszek, 2005; Geifman & El-Yaniv, 2017) allows classifiers to abstain from making predictions when they are not confident. While loosely related to open category detection, these approaches do not directly consider the possibility of novel categories, but rather focus on assessing confidence with respect to the known categories. Due to their closed-world discriminative nature, it is easy to construct scenarios where such methods are incorrectly confident about the class of an alien and do not abstain.

A variety of prior work has addressed variants of open category detection. This includes work on formalizing the concept of “open space” to characterize the region of the feature space outside of the support of the training set (Scheirer et al., 2013). Variants of SVMs have also been developed, such as the One-vs-Set Machine (Scheirer et al., 2013) and the Weibull-calibrated SVM (Scheirer et al., 2014). Additional work has addressed open category detection by tuning the decision boundary based on unlabeled data which contains data from novel categories (Da et al., 2014). Approaches based on nearest neighbor methods have also been proposed (Mendes Júnior et al., 2017). None of these methods, however, allow for the direct control of alien detection rates, nor do they provide theoretical guarantees.

There is also recent interest in open category detection for deep neural networks applied to vision and text classification (Bendale & Boult, 2016; Shu et al., 2017). These methods usually train a neural network in a standard closed-world setting, but then analyze various activations in the network in order to detect aliens. Another related line of work is detection of out-of-distribution instances, which is similar to open category detection but assumes that the test data come from a completely different distribution compared to the training distribution (Hendrycks & Gimpel, 2017; Liang et al., 2018). All of this work is quite specialized to deep neural networks and does not provide direct control of alien detection rates or theoretical guarantees.

Problem Setup

We consider open category detection where there is an unknown nominal data distribution $D_{0}$ over labeled examples from a known set of category labels. We receive as input a “clean” nominal training set $S_{0}$ containing $k$ i.i.d. draws from $D_{0}$. In practice, $S_{0}$ will correspond to some curated labeled data that contains only known categories of interest.

We also receive as input an unlabeled “mixture” dataset $S_{m}$ that contains $n$ points drawn i.i.d. from a mixture distribution $D_{m}$. Specifically, the mixture distribution $D_{m}$ is a combination of the nominal distribution $D_{0}$ and an unknown alien distribution $D_{a}$, which is a distribution over novel categories (alien data points). We assume that $D_{a}$ is stationary, so that all alien points that appear as future test queries will also be drawn from $D_{a}$.

At training time, we assume that $D_{m}$ is a mixture distribution, with probability $\alpha$ of generating an alien data point from $D_{a}$ and probability of $1-\alpha$ of generating a nominal point. Our results hold even if the test queries come from a mixture with a different value of $\alpha$ as long as the alien test points are drawn from $D_{a}$.

Given these datasets, our problem is to label test instances from $D_{m}$ as either “alien” or “nominal”. In particular, we wish to achieve a specified alien detection rate, which is the fraction of alien data points in $D_{m}$ that are classified as “alien” (e.g., 95%). At the same time we would like the false positive rate to be small, which is the fraction of nominal data points incorrectly classified as aliens.

Our approach to this problem assumes the availability of an anomaly detector that is trained on $S_{0}$ and assigns anomaly scores to all data points in both $S_{0}$ and $S_{m}$. Intuitively, the anomaly scores order the test examples according to how anomalous they appear relative to the nominal data (higher scores being more anomalous). An ideal detector would rank all alien data points higher than all nominals, though in practice, the ordering will not be so clean. Our approach labels data in $S_{m}$ by selecting a threshold on the anomaly scores and labeling all data points with scores above the threshold as aliens and the remaining points as nominals. Our key challenge is to select a threshold that provides a guarantee on the alien detection rate.

Algorithms for Open Category Detection

In order to obtain theoretical guarantees, our algorithm assumes knowledge of the alien mixture probability $\alpha$ that generates the mixture data $S_{m}$. Later, we will show that knowing an upper bound on $\alpha$ is sufficient to obtain a guarantee.

Our approach is based on considering the cumulative distribution functions (CDFs) over anomaly scores of a fixed anomaly detector. Let $F_{0},F_{a}$, and $F_{m}$ be the CDFs of anomaly scores for the nominal data distribution $D_{0}$, alien distribution $D_{a}$, and mixture distribution $D_{m}$ respectively. Since $D_{m}$ is a simple mixture of $D_{0}$ and $D_{a}$, we can write $F_{m}$ as

From this we can derive the CDF for $F_{a}$ in terms of $F_{m}$ and $F_{0}$:

Given the ability to derive $F_{a}$, it is straightforward to achieve an alien detection rate of $1-q$ (e.g. 95%) by selecting an anomaly score threshold $\tau_{q}$ that is the $q$ quantile of $F_{a}$ and raising an alarm on all test queries whose anomaly score is greater than $\tau_{q}$.

In reality, we do not have access to $F_{m}$ or $F_{0}$ and hence cannot exactly determine $F_{a}$. Rather, we have samples $S_{m}$ and $S_{0}$. Thus, our algorithm works with the empirical CDFs $\hat{F}_{0}$ and $\hat{F}_{m}$, which are simple step-wise constant approximations, and estimates an empirical CDF over aliens:

Our algorithm computes the above estimate of $\hat{F}_{a}$ and uses it to select a threshold $\hat{\tau}_{q}$ to be the largest threshold such that $\hat{F}_{a}(\hat{\tau}_{q})\leq q$, where $1-q$ is the target alien detection rate. This choice will minimize the number of false alarms. The steps of this algorithm are as follows.

Although $\hat{F}_{m}$ and $\hat{F}_{0}$ are both legal CDFs, the estimate for $\hat{F}_{a}$ from step 3 may not be a legal CDF, because it is the difference of two noisy estimates—it may not increase monotonically and it may even be negative. A good technique for dealing with this problem is to employ isotonization (Barlow & Brunk, 1972) and clipping. Isotonization finds the monotonically increasing function $\hat{F}_{a}^{*}$ closest to $\hat{F}_{a}$ in squared error. To convert $\hat{F}_{a}$ into a legal CDF, define $\check{F}_{a}=\min\{\max\{\hat{F}_{a}^{*},{\bf 0}\},{\bf 1}\}$, where the min and max operators are applied pointwise to their arguments. We performed experiments (shown in the supplementary materials) to test whether using $\check{F}_{a}$ in Step 4 would improve the performance of the overall algorithm. We found that it did not.

Finite Sample Guarantee

In the limit of infinite data (both nominal and mixture) and perfect knowledge of $\alpha$, $\hat{F}_{a}$ will converge to the true alien CDF, and our algorithm will achieve the desired alien detection rate. In this section, we consider the finite data case where $|S_{0}|=|S_{m}|=n$. We derive a value for the sample size $n$ that guarantees with high probability over random draws of $S_{0}$ and $S_{m}$, that fraction $1-q-\epsilon$ of the alien test points will be detected, where $\epsilon$ is an additional error incurred because of the finite sample size $n$.

Our key theoretical tool is a finite sample result on the uniform convergence of empirical CDF functions (Massart, 1990). To use this result, we make the reasonable technical assumption that the nominal and alien CDFs, $F_{0}$ and $F_{a}$, are continuous. In the following, let $\eta$ be the target alien detection rate, $q$ be the input to Algorithm 1, $\hat{\tau}_{q}$ be the estimated $q$-quantile of the alien CDF (step 4 of Alg. 1), and $\epsilon$ be an error parameter. The following theorem gives the sample complexity for guaranteeing that $1-\eta$ of the alien examples will be detected using threshold $\hat{\tau}_{q}$.

Let $S_{0}$ and $S_{m}$ be nominal and mixture datasets containing $n$ i.i.d. samples from the nominal and mixture data distributions respectively. For any $\epsilon\in(0,1-q)$ and $\delta\in(0,1)$, if

then with probability at least $1-\delta$, Algorithm 1 will return a threshold $\hat{\tau}_{q}$ that achieves an alien detection rate of at least $1-\eta$, where $\eta=q+\epsilon$.

The proof is in the Appendix. Note that $n$ grows as $O(\frac{1}{\epsilon^{2}\alpha^{2}}\log{\frac{1}{\delta}})$. Hence, this guarantee is polynomial in all relevant parameters, which we believe is the first such guarantee for open category detection. The result can be generalized to the case where $n_{0}<n_{m}$; in practice, the larger the mixture sample $S_{m}$ is, the easier it is to estimate $\tau_{q}$, because this provides more alien points for estimating the $q$-th quantile of $F_{a}$.

The theorem gives us flexibility in setting $\epsilon$ and $q$ (the algorithm input) to achieve a guarantee of $1-\eta$. The $\epsilon$ parameter controls a trade-off between sample size and false alarm rate. To minimize the false alarm rate, we want to make $q$ large (to obtain a larger threshold), so we want to set $q$ close to $\eta$. But, as $q\rightarrow\eta$, $\epsilon\rightarrow 0$, and $n\rightarrow\infty$. To minimize the sample size $n$, we want to make $q$ as small as possible, because that allows $\epsilon$ to be larger and hence $n$ becomes smaller. The optimal setting of $\epsilon$ depends on how the false alarm rate grows with $\tau_{q}$, which in turn depends on the relative shape of $F_{0}$ and $F_{a}$. In a real safety application, we can estimate these from $S_{0}$ and $S_{m}$ and choose an appropriate $q$ value.

Consider running Algorithm 1 using an upper bound $\alpha^{\prime}$ on the true $\alpha$. Under the same assumptions as Theorem 1, if the anomaly detector is admissible and

then with probability at least $1-\delta$, Algorithm 1 will return a threshold $\hat{\tau}_{q}$ that achieves an alien detection rate of at least $1-\eta$, where $\eta=q+\epsilon$.

The proof is in the Appendix. While we can achieve a guarantee using an upper bound on $\alpha^{\prime}$, the returned threshold will be more conservative (smaller) than if we had used the true $\alpha$. This will result in higher false alarm rates, since more nominal points will be above the threshold. Thus it is desirable to use a value of $\alpha^{\prime}$ that is as close to $\alpha$ as possible.

Experiments

We performed experiments to answer four questions. Question Q1: how accurate is our estimate of $\hat{\tau}_{q}$ as a function of $n$ and $\alpha$? Question Q2: how loose are the bounds from Theorem 1? Question Q3: what are typical values of the false alarm rates for various settings of $n$ and $\alpha$ on real datasets? Question Q4: how do these observed values change if we employ an overestimate $\alpha^{\prime}>\alpha$?

All of our experiments employ the Isolation Forest anomaly detector (Liu et al., 2008), which has been demonstrated to be a state-of-the-art detector in recent empirical studies (Emmott et al., 2013). In the Supplementary Materials we show similar results with the LODA anomaly detector (Pevný, 2015).

To address Q1 and Q2, we run controlled experiments on synthetic data. The data points are generated from 9-dimensional normal distributions. The dimensions of the nominal distribution $D_{0}$ are independently distributed as $N(0,1)$. The alien distribution is similar, but with probability 0.4, 3 of the 9 dimensions (chosen uniformly at random) are distributed as $N(3,1)$ and with probability 0.6, 4 of the 9 dimensions (chosen uniformly at random) follow $N(3,1)$. This ensures that the anomalies are not highly similar to each other and models the situation in which there are many different kinds of alien objects, not just a single alien class forming a tight cluster.

In each experiment, the nominal dataset and the mixture dataset are of the same size $n$, and the mixture dataset contains a proportion $\alpha$ of anomaly points. We fixed the target quantile to be $q=0.05$. The experiments are carried out for $n\in\{100,500,1\text{K},5\text{K},10\text{K}\}$ and $\alpha\in\{0.01,0.05,0.10,0.20,0.50\}$. For testing, we create two large datasets $G_{0}$ and $G_{a}$, with $G_{0}$ being a pure nominal dataset, $G_{a}$ being a pure alien dataset, and $|G_{0}|=|G_{a}|=20K$. The Isolation Forest algorithm computes $1000$ full depth isolation trees on the nominal data. Each tree is grown on a randomly-selected 20% subsample of the clean data points. We compute anomaly scores for the nominal points via out-of-bag estimates and anomaly scores for the mixture points, $G_{0}$, and $G_{a}$ using the full isolation forest. For each combination of $n$ and $\alpha$, we repeat the experiment $100$ times. We measure the fraction of aliens detected (the “recall”) and the fraction of nominal points declared to be alien (the “false positive rate”) by applying the $\hat{\tau}_{q}$ estimate to threshold the anomaly scores in $G_{0}$ and $G_{a}$.

To assess the accuracy of our $\hat{\tau}_{q}$ estimates (Q1), we could compare them to the true values. However, this comparison is hard to interpret, because $\tau$ is expressed on the scale of anomaly scores, which are somewhat arbitrary. Instead, Figure 1 plots the recall achieved by $\hat{\tau}_{q}$. If $\hat{\tau}_{q}$ had been estimated perfectly, the recall would always be $1-q=0.95$. However, we see that the recall is often less than 0.95, which indicates that $\hat{\tau}_{q}$ is over-estimated, especially when $n$ and $\alpha$ are small. This behavior is predicted by our theory, where we see that the sample size requirements grow inversely with $\alpha^{2}$. For larger $\alpha$ and $n$, the recall guarantee is generally achieved. Figure 2 compares the false positive rate of the true oracle $\tau_{q}$ to the false positive rate of the estimate $\hat{\tau}_{q}$. For each combination of $\alpha$ and $n$, we have 100 replications of the experiment and therefore 100 estimates $\hat{\tau}_{a}$ and 100 FPR rates. For each of these, the true FPR is computed using $G_{0}$. The error bars summarize the resulting 100 FPR values by the median and inter-quartile range. We see that for small $n$ and $\alpha$, the FPR can be quite different from the oracle rate, but for larger $n$ and $\alpha$, the estimates are very good.

To assess the looseness of the bounds (Q2), for each combination of $n$ and $\alpha$, we fix $\delta=0.05$ and compute the value of $\eta$ such that 95 of the 100 runs achieved a recall of at least $1-\eta$ (thus $\eta$ empirially achieves the $1-\delta$ guarantee). We then compute $\epsilon=\eta-q$ and the corresponding required sample size $n^{*}$ according to Theorem 1. Figure 3 shows a plot of $n^{*}$ versus the actual $n$. The distance of these points from the $n^{*}=n$ diagonal line show that the theory is fairly loose, although it becomes tighter as $n$ gets large.

Benchmark Data Experiments. To address our third and fourth questions, we performed experiments on six UCI multiclass datasets: Landsat, Opt.digits, pageb, Shuttle, Covertype and MNIST. In addition to these, we provide results for the Tiny ImageNet dataset. In each multiclass dataset, we split the classes into two groups: nominal and alien. For Tiny ImageNet, we train a deep neural network classifier on 200 nominal classes and treat the remaining 800 as aliens. The nominal classes for UCI datasets are MNIST(1,3,7), Landsat(1,7), OCR(1,3,4,5,7), pageb(1,5), Letter recognition(1,3), and Shuttle(1,4). We generated nominal and mixture datasets for various values of $\alpha$. The value of $n$ for each dataset is 1532 for Landsat,788 for Letter recognition, 568 for OCR, 4912 for pageb, 5000 for Shuttle, 13,624 for Covertype, 11,154 for MNIST, and 10,000 for Tiny ImageNet. Because we cannot create datasets with large $n$, we cannot measure the true value of $\tau_{q}$.

After computing the anomaly scores for both nominal and mixture datasets, we applied Algorithm 1 within a 10-fold cross validation. We divide the mixture data points at random into 10 groups. For each fold, we estimate $\hat{F}_{a}$ and $\hat{\tau}_{a}$ from 9 of the 10 groups and then score the mixture points in the held-out fold according to $\hat{\tau}_{a}$. In all other respects, the experimental protocol is the same as for the synthetic data. For Tiny ImageNet, the anomaly scores are obtained by applying a baseline method (Hendrycks & Gimpel, 2017).

To answer Q3, Figures 4 and 6 plot the false positive rate as a function of $\alpha$ for the UCI and vision datasets, respectively. We see that the FPR ranges from 3.6% to 26.9% on UCI depending on the dataset and the level of $\alpha$. The vision datasets have higher FPR, especially MNIST, which has a large number of alien classes that are not distinguished well by the anomaly detector. The FPR depends primarily on the domain, because the key issue is how well the anomaly detector distinguishes between nominal and alien examples. The false alarm rate generally improves as $\alpha$ increases. In some applications, it may be possible to enrich $S_{m}$ so that $\alpha$ is larger on the training set to take advantage of this phenomenon. It is interesting to note that once $\hat{\tau}_{a}$ has been computed, it can be applied to test datasets having different (or unknown) values of $\alpha$.

Figures 5 and 7 plot the recall rate as a function of $\alpha$ for the UCI and vision datasets. We set $q=0.05$ in these experiments. Theorem 1 only guarantees a recall of $1-q-\epsilon$, where $\epsilon$ depends on $n$. Hence, it is nice to see that for three of the domains (Shuttle, Covertype, and Landsat) in UCI and for both vision datasets, the recall is very close to $1-q=0.95$. These are the domains with the largest values of $n$. The value of $\alpha$ has a bigger impact on recall than it does on FPR. This is because the effective number of alien training examples is $\alpha n$, which can be very small for some datasets when $\alpha=0.1$. This shows that in applications such as fraud detection, where $\alpha$ may be very small, the mixture dataset $S_{m}$ needs to be very large.

To answer Q4 regarding the impact of using an incorrect value $\alpha^{\prime}>\alpha$, we repeated these experiments with $\alpha^{\prime}=\alpha+\xi$, for $\xi\in\{0.002,0.004,0.006,0.008,0.010\}$. Figure 8 plots the change in false positive rate and recall as a function of $\alpha^{\prime}-\alpha$. Two points are plotted for each combination of $\alpha^{\prime}$ and dataset, the change in Recall and the change in FPR. We observe that the recall increases slightly (in the range from 0.01 to 0.05). However, the false positive rate increases by much larger amounts (from 0.01 to 0.336). This demonstrates that it is very important to determine the value of $\alpha$ accurately.

Summary

We have taken a step toward open category detection with guarantees by providing a PAC-style guarantee on the probability of detecting $1-\eta$ of the aliens on the test data. This is the first such guarantee under any similarly general conditions. We have shown that this guarantee is satisfied in our experiments, although the guarantee is somewhat loose, especially on small training sets. Obtaining a guarantee requires more data than standard PAC guarantees on expected prediction accuracy. This is because we must estimate the $q$ quantile of the alien anomaly score distribution, where $q$ is typically quite small. Nonetheless, our experiments show that our algorithm gives good recall performance and non-trivial false alarm rates on datasets of reasonable size.

It is important to note that the very formulation of a PAC-style guarantee on the probability of detecting aliens requires assuming that the aliens are drawn from a well-defined distribution $D_{a}$. While this is appropriate in some applications, such as the insect survey application described in the introduction, it is not appropriate for adversarial settings. In such settings, a PAC-style guarantee does not make sense, and some other form of safety guarantee needs to be formulated.

To obtain the guarantee, we employ two training datasets: a clean dataset that contains no aliens and an (unlabeled) contaminated dataset that contains a known fraction $\alpha$ of aliens. An important theoretical problem for future research is to develop a method that can estimate a tight upper bound on $\hat{\alpha}>\alpha$. We believe this is possible, but we have not yet found a method that guarantees that $\hat{\alpha}>\alpha$.

Our guarantee requires more data as $\alpha$ becomes small. Fortunately, when $\alpha$ is small, it may be possible in some applications to afford lower recall rates, since the frequency of aliens will be smaller. However, in safety-critical applications where a single undetected alien poses a serious threat, there is little recourse other than to collect more data or allow for higher false positive rates.

Acknowledgements

This research was supported by a gift from Huawei, Inc., and grants from the Future of Life Institute and the NSF Grant 1514550. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsors.

Appendix A Proof for Theorem 1

Suppose there are $n$ random variables which are i.i.d. from the distribution with CDF $F$ and let $\hat{F}_{n}$ be the empirical CDF calculated from this sample. Then Massart (1990) shows that

holds without any restriction on $\lambda$. Making use of this, and assuming we use the same sample size $n$ for both the mixture dataset and the clean data set, for any $\epsilon\in(0,1-q)$, we seek to determine how large $n$ needs to be in order to guarantee that with probability at least $1-\delta$ our quantile estimate $\hat{\tau}_{q}$ satisfies $F_{a}(\hat{\tau}_{q})\leq q+\epsilon$. To achieve this, we want to have

Now we have with probability at least $1-\delta$,

If this inequality holds, then for any value $\hat{\tau}_{q}$ such that $\hat{F}_{a}(\hat{\tau}_{q})\leq q$, we have

So we have with probability at least $1-\delta$, any $\hat{\tau}_{q}$ satisfying $\hat{F}_{a}(\hat{\tau}_{q})\leq q$ will satisfy $F_{a}(\hat{\tau}_{q})\leq q+\epsilon$. $\square$

Appendix B Proof for Corollary 1

If $\alpha^{\prime}\geq\alpha$, and if we write

then $F^{\prime}_{a}$ is still a legal CDF, because

and it is easy to show that $F^{\prime}_{a}$ is monotonically nondecreasing.

and because of this, if we let $\hat{\tau}^{\prime}_{q}$ denote the threshold we get from using $\alpha^{\prime}$, we will have $F_{a}(\hat{\tau}^{\prime}_{q})\leq F^{\prime}_{a}(\hat{\tau}^{\prime}_{q})$. By the proof of previous theorem, we know that when $n>\frac{1}{2}\ln{\frac{2}{1-\sqrt{1-\delta}}}(\frac{1}{\epsilon})^{2}(\frac{2-\alpha^{\prime}}{\alpha^{\prime}})^{2}$, we have with probability at least $1-\delta$, $F^{\prime}_{a}(\hat{\tau}^{\prime}_{q})\leq q+\epsilon$, and thus we have $F_{a}(\hat{\tau}^{\prime}_{q})\leq q+\epsilon$. $\square$

References

Appendix C Experimental Results from Synthetic Datasets

In this section we include the simulation results on synthetic datasets from using two different anomaly detectors, Isolation Forest and LODA in table 1-3 and 4-6 respectively. For using LODA, when training it on the nominal dataset, we build 1 000 random projections, and each of them is built using a bootstrap resample of the nominal dataset. After finishing building all projections, we calculate the anomaly score for each point in nominal dataset only using the projections that didn’t use this point, and calculate the anomaly scores for mixture dataset, $G_{0}$ and $G_{a}$ using all the projections. For all cases, we include results from targeting on different recalls which are $98\%$, $95\%$ and $90\%$. In table 1-6, the oracle FPR column is the mean of 100 oracle FPRs in each setting.

In table 7, we include the results we used for plotting figure 2. The results are the 1st quartile, median and 3rd quartile of FPR from experiments using Iforest with target recall $95\%$. Here the oracle FPR column is the median of 100 oracle FPRs.

Appendix D Experimental Results from UCI and Image Datasets

In this section we include results of performance on UCI benchmarks, MNIST and Tiny Imagenet and Tables 8-22 illustrate the results. The experimental protocol is similar to synthetic datasets and two state of the art anomaly detectors Isolation forest, LODA are applied. For Isolation forest we train Forest with 1000 trees on nominal dataset and use out of bag estimates of this dataset to estimate the nominal datasets anomaly score distribution. For LODA we build 1000 projections and similar to Isolation forest we get anomaly score for each point in nominal dataset using the projections that didn’t use this point.Tables 11-16 illustrate the results of LODA for 6 different datasets for varying values of $\eta$ and report the observed recall, False positive rate averaged over 100 runs of each experiment. Tables 17-22 report the results for Isolation Forest and it can be observed the performance of both LODA,Isolation Forest are similar.

For Image datasets we follow the same protocol as UCI for MNIST and apply Isolation Forest on the input image but for Tiny Imagenet the anomaly scores are obtained differently. We first train a Wide Residual Network (40-2) classifier on the 200 nominal classes of Tiny Imagenet and apply baseline method (Hendrycks & Gimpel, 2017) on validation data to get the nominal dataset distribution and later apply the same method on the mixture dataset which will have $\alpha$ proportion of aliens which are basically from 800 held out classes.Tables 8-10 illustrate the results for these datasets for target recall of 98%,95% and 90%.