Unsupervised Anomaly Detection with Rejection
Authors: Lorenzo Perini
Jesse Davis
Venue: NeurIPS 2023 poster (2023)
Keywords: Anomaly Detection
Learning with Rejection
Unsupervised Learning

Abstract: Anomaly detection aims at detecting unexpected behaviours in the data. Because anomaly detection is usually an unsupervised task, traditional anomaly detectors learn a decision boundary by employing heuristics based on intuitions, which are hard to verify in practice. This introduces some uncertainty, especially close to the decision boundary, that may reduce the user trust in the detector's predictions. A way to combat this is by allowing the detector to reject predictions with high uncertainty (Learning to Reject). This requires employing a confidence metric that captures the distance to the decision boundary and setting a rejection threshold to reject low-confidence predictions. However, selecting a proper metric and setting the rejection threshold without labels are challenging tasks. In this paper, we solve these challenges by setting a constant rejection threshold on the stability metric computed by ExCeeD. Our insight relies on a theoretical analysis of such a metric. Moreover, setting a constant threshold results in strong guarantees: we estimate the test rejection rate, and derive a theoretical upper bound for both the rejection rate and the expected prediction cost. Experimentally, we show that our method outperforms some metric-based methods.

Unsupervised Anomaly Detection with Rejection
Lorenzo Perini DTAI lab Leuven.AI, KU Leuven, Belgium orrezzo. lorenzo.perini @kuleuven. be
Jesse Davis, DTAI lab Leuven.Al, KU Leuven, Belgium jesse. www.sswuwweeeeennncmmm
Abstract
Anomaly detection goal is detect unexpected behaviours in the data. Because anomaly detection is usually an unsupervised task, traditional anomaly detectors learn a decision boundary by employing heuristics based on intuitions, which are hard to verify in practice. This introduces some uncertainty, especially close to the decision boundary, which may reduce the user trust in the detector's predictions. A way to combat this is by allowing the detector to reject examples with high uncertainty (Learning Reject). This requires employing a confidence metric that captures the distance to the decision boundary and setting a rejection threshold to reject low-confidence predictions. However, selecting a proper metric and setting the rejection threshold without labels are challenging tasks. In this paper, we solve these challenges by setting a constant rejection threshold on the stability metric computed by EXCEED. Our insight relies on a theoretical analysis of this metric. Moreover, setting constant threshold results in strong guarantees: we estimate the test rejection rate, and derive a theoretical upper bound for both the rejection rate and the expected prediction cost. Experimentally, we show that our method outperforms some metric-based methods.
Introduction
Anomaly detection is the task of detecting unexpected behaviors in the data (6]. Often, these anomalies critical adverse events such the destruction alteration of proprietary
data (2), water leaks
in stores [50), breakdowns in gas [65] and wind [64] turbines, failures in petroleum extraction [45).
Usually, anomalies are associated with cost such as a monetary cost (e.g., maintenance, paying for
fraudulent purchases) or societal cost such as environmental damages (c.g. dispersion of petrolcum or gas). Hence, detecting anomalies
timely manner an important problem.
When using an anomaly detector for decision-making it is crucial that the user trusts the system. However, it is often hard impossible acquire labels for anomalies. Moreover, anomalies may not follow pattern. Therefore anomaly detection is typically treated as an unsupervised learning problem where traditional algorithms learn a decision boundary by employing heuristics based on intuitions [22 (55 61 41), such as that anomalies are far away from normal examples [ Because these intuitions are hard verify and may not hold some cases, some predictions may have high uncertainty, especially for examples close to the decision boundary 32 28
As result, the detector's s
predictions should be treated with some circumspection.
One way to increase user trust is to consider Learning to Reject 12 In this setting, the model does not always make prediction. Instead, it can abstain when is a heightened risk of making a mistake thereby improving its performance when it does offer prediction. Abstention has the drawback that no prediction made, which means that a person must intervene make decision. In the literature, two types of rejection have been identified [25]: novelty rejection allows the model abstain when given -ittr---isttibution (OOD) example, while ambiguity rejection enables abstention for a test example that is too close to the model's decision boundary. Because anomalies
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

often are OOD examples, novelty rejection does not align well with our setting as the model would
reject all OOD anomalies (i.e., a full class) [T] 63 30 On the other hand, current approaches for ambiguity rejection threshold what constitutes being too close to the decision boundary by evaluating the model's predictive performance on the examples for which makes a prediction (i.e., accepted), and those where it abstains from making prediction (i.e., rejected) (9] 44 [6]. Intuitively, the idea is to find a threshold where the model's predictive performance is (1) significantly lower on rejected examples than on accepted examples and (2) higher on accepted examples than on all examples (i.e., if it always makes a prediction). Unfortunately, existing learning to reject approaches that set a threshold in this manner require labeled data, which is not available in anomaly detection.
This paper fills this gap by proposing an approach to perform ambiguity rejection for anomaly detection in completely unsupervised manner. Specifically, we make three major contributions. First, we conduct a thorough novel theoretical analysis of a stability metric for anomaly detection [49] and show that it has several previously unknown properties that are of great importance in the context of learning to reject. Namely, it captures the uncertainty close to the detector's decision boundary, and only limited number of examples get stability value strictly lower than 1. Second, these enabls us to design an ambiguity rejection mechanism without any labeled data that offers strong guarantees which are often sought in Learning to Reject [12] 60 7 We can derive an accurate estimate of the rejected examples proportion, as well as a theoretical upper bound that is satisfied with high probability. Moreover, given cost function for different types of errors, upper bound on the expected cost at the prediction time. Third, we evaluate our approach on an extensive set of unsupervised detectors and benchmark datasets and conclude that (1) it performs better than several adapted baselines based on other unsupervised metrics, and (2) our theoretical results hold in practice.
provide estimated
2 Preliminaries and notation
We will introduce the relevant background on anomaly detection, learning to reject, and the EXCERD's metric that this paper builds upon.
Anomaly Detection. Let X' be a d dimensional input space and D = (xI,..... Zn be a training set, where each z; E X. The goal in anomaly detection is to train detector f: X - R that maps examples to a real-valued anomaly score, denoted by s. In practice, it is necessary to convert these soft scores to hard prediction, which requires setting a threshold A. Assuming that higher scores equate to being more anomalous, a predicted label 9 can be made for an example x as follows: 9 = 1 (anomaly) if s = fx) 2 X, while ý = 0 (normal) if s = f(x) < A. We let Ý be the random variable that denotes the predicted label. Because of the absence of labels, one usually sets the threshold such that y X n scores are 2 X, where 7 is the dataset's 's contamination factor (i.e., expected proportion of anomalies) [5] 50)
Learning to Reject. Learning to reject extends the output space of the model to include the symbol @. which means that the model abstains from making prediction. This entails learning second model r (the rejector) to determine when the model abstains. A canonical example of ambiguity rejection is when r consists of pair [confidence M.. rejection threshold 7] such that example is rejected if the detector's 's confidence is lower than the threshold. The model output becomes
1
if Mf >T; T;
1 =
je E 10.
i.
standard approach is to evaluate different values for T to find a balance between making too many incorrect predictions because is too low (i.e., ú +f y but M. > -) and rejecting correct predictions because 7 is too high (i.e., ÿ = y but M. < T) 9 16. Unfortunately, in an unsupervised setting, it is impossible to evaluate the threshold because it relies on having access to labeled data.
Ex CEED'S metric. Traditional confidence metrics (such as calibrated class probabilities) quantify how likely a prediction is to be correct, This obviously requires labels [9] which are unavailable in an unsupervised setting. Thus, one option is move the focus towards the concept of stability: given a fixed test example x with anomaly score perturbing the training data alters the model learning, which, in turn, affects the label prediction. Intuitively, the more stable a detector's 's output is for a test example, the less sensitive its predicted label is to changes in the training data. On the other hand, when IP(Ý = 1|s) R P(Ý 0|s) ~ 0.5 the prediction for z is highly unstable, training the

---

detector with slightly different examples would flip its prediction for the same test score s. Thus, stability-baa based confidence metric Mr, can be expressed as the margin between the two classes' probabilities:
M, |P( = 1|s) P(Y 0|s)] (2 = 1|s) -/,
where the lower M, the unstable the prediction.
Recently, Perini et al. introduced EXCEED estimate the detector's stability P(Ý 1|s). Roughly speaking, EXCEED uses Bayesian formulation that simulates bootstrapping the training set as a form of perturbation. Formally, it measures such stability for test score in two steps.
First, it computes the training frequency V/ KiSn: E [0,1], i.e. the proportion of training scores lower than This expresses how extreme the score ranks with respect to the training scores. Second, it computes the probability that the score will be predicted as an anomaly when randomly drawing training set of scores from the population of scores. In practice, this is the probability that the chosen threshold will be less than or equal to the score 8. The stability is therefore estimated as
P( = 1|s) =
Σ
72
+ nenn
) ( (n(1-V))) vn))
(1)
i
2 +
2 + n2
Assumption. EXCEED's Bayesian formulation requires assuming that YIs follows a Bernoulli distribution with parameter Ps P(S s). where is the detector's population of scores. Note that the stability metric a detector property and, therefore, is tied to the specific choice of the unsupervised detector f.
3
Methodology
This paper addresses the following problem:
Given: An unlabeled dataset D with contamination an unsupervised detector f. a cost function Do: Introduce reject option to f. i.e. find a pair (confidence, threshold) that minimizes the cost.
We propose an anomaly detector-agnostic approach for performing learning to reject that requires no labels. Our key contribution is a novel theoretical analysis of the EXCEED confidence metric that proves that only a limited number of examples have confidence lower than e (Sec. (Sec.3.TT. Intuitively, the detector's predictions for most examples would not be affected by slight perturbations of the training set: it is easy to identify the majority of normal examples and anomalies because they will strongly adhere to the data-driven heuristics that unsupervised anomaly detectors use. For example, using the data density as a measure of anomalousness [5] tends to identify all densely clustered normals and isolated anomalies, which constitute the majority of all examples. In contrast, only relatively few cases would be ambiguous and hence receive low confidence (e.g., small clusters of anomalies and normals at the edges of dense clusters).
Our approach called REJEX (Rejecting via ExCeeD) and simply computes the stability-based confidence metric M, and rejects any example with confidence that falls below threshold 7 1 E. Theoretically, this constant reject threshold provides several relevant guarantees. First, one often needs to control the proportion of rejections (namely, the rejection rate) to estimate the number of decisions left to the user. Thus, we propose an estimator that only uses training instances to estimate the rejection rate at test time. Second, because in some applications avoiding the risk of rejecting all the examples is a strict constraint, we provided an upper bound for the rejection rate (Sec. 3..) Finally, we compute theoretical upper bound for a given cost function that guarantees that using REJEX keeps the expected cost per example at test time low (Sec. 3.3
3.1 Setting the Rejection Threshold through a Novel Theoretical Analysis of EXCEED
Our novel theoretical analysis proves (1) that the stability metric by EXCEED is lower than e for a limited number of examples (Theorem 3.1 and (2) that such examples with low confidence are the ones close to the decision boundary (Corollay 3.2). Thus, we propose reject all these uncertain examples by setting rejection threshold
T 7=1-5= 1-2e 2T- for T 2 4,
3

---

where 2e- is the tolerance that excludes unlikely scenarios, and T 2 4 is required for Theorem 3.1
We motivate approach follows. Given an example x with score and the proportion of lower training scores Wa. Theorem 3.1 shows that the confidence M, is lower than 1 - -2. (for 7 2 4) if vh,, belongs the interval [4, 12]. By analyzing [41 12]. Corollary 3.2 proves that the closer example is to the decision boundary, the lower the confidence M., and that a score 8 = X (decision threshold) has confidence M. 0.
Remark, Perini et al. performed an asymptotic analysis of EXCEED that investigates the metric's behavior when the training set's size - +o0. In contrast, our novel analysis is finite-sample and hence provides more practical insights, as real-world scenarios involve having a finite dataset with size E N.
Theorem 3.1 (Analysis EXCEED). Let 8 be an anomaly score, and th E [0, 1] its training such that
T [0, 7, frequency, For T2 4, there exist 1 (1, 7,7 [0, 11, la 7,
Vo [2, M. S 2e
Proof. See the Supplement for the formal proof.
The interval [t, t2] has two relevant properties. First, it becomes narrower when increasing n (P1) and larger when increasing T (P2). This means that collecting more training data results in smaller rejection regions while decreasing the tolerance = 2c has the opposite effect. Second, it is centered (not symmetrically) on
(P3-P4), which means that examples with anomaly scores close to the decision threshold À are the ones with a low confidence score (P5). The next Corollary lists these properties.
Corollary 3.2. Given tı, 12 as in Theorem 3.1 the following properties hold for any n, T 2 4:
PI. limn-++od t = lima 1/ = 11
P2. li and l2 are, respectively, monotonic decreasing and increasing as functions T;
P3. the interval always contains 1 - 7,, i.e. t1 21-75- t2:
P4. for - oc, there exists s" with 4/n = [t1. tz) such that t ? and M, - [X u1, A u2). where un (n, 7; T), (n v, T) are positive functions.
P5. N/2 E [2) iff
Proof sketch. For Pl, it is enough to observe that t1, f2 + 1 for n + +oo. For P2 and P3, the result comes from simple algebraic steps. P4 follows from the surjectivity of Mr when - +00, the monotonicity of PP( dn [21 = E | (41), vi (f2)
1[8), from P1 with the squeeze theorem. Finally, P5 follows from
vr, is monotonic increasing, where e, is the inverse- image of vi,. Because for P3 7 E [t,, t2]. it holds that .. =(tt) I w ->) = A +o (t2).
This implies that E [A - #1, À + w2]. where u1
v. (11,, U2 = X (12).
3.2 Estimating and Bounding the Rejection Rate
It is important to have an estimate of the rejection rate, which is the proportion of examples for which the model will abstain from making a prediction. This is an important performance characteristic for differentiating among candidate models. Moreover, it is important that not all examples are rejected because such a model is useless practice. We propose way to estimate the rejection rate and Theorem 3.5 shows that our estimate approaches the true rate for large training sets. We strengthen our analysis and introduce an upper bound for the rejection rate, which guarantees that, with arbitrarily high probability, the rejection rate is kept lower than constant (Theorem (.66)
Definition 3.3 (Rejection rate). Given the confidence metric Ml, and the rejection threshold 7, the rejection rate R P( < T) is the probability that test example with score s gets rejected.
We propose the following estimator for the reject rate: Definition 3.4 (Rejection rate estimator). Given anomaly scores with training frequencies via let g: [0, 1] + [0, 1] be the function such that IP( 1|s) g(vn) (see Eq. []. We define the rejection rate estimator R. as
R= Fv.. (9-1 (1-e-7) ))) Fs.. (g Tc-
(2)

---

where g-1 is the inverse-image through 9, and, for u E [0, Foo empirical cumulative distribution of v/n.
Bi tha (u is the
Note that R can be computed in practice, as the thn has a distribution that is arbitrarily close to uniform, as stated by Theorem A.1 and A.2 2 in the Supplement.
Theorem 3.5 (Rejection rate estimate). Let g be as in Def. 3.4 Then, for high values n, R R R.
Proof. From the definition of rejection rate 3.3 follows
R P (M,, 1 2c 2)) (P(Ý E le 11-_-110- 11--- =P (g((i) E --- (1 F'p (e
-P 99 (e (1-
where Fr (.) Pt < is the theoretical cumulative distribution of th.. Because the true distribution thn for test examples is unknown, the estimator approximates Fos. using the training scores and computes the empirical F... As result,
R = Pri. (g (1---))) Fvt.
(c-)() = R.
Theorem 3.6 (Rejection rate upper bound). Let be an anomaly score, M, be its confidence value, and t = -e be the rejection threshold. For n E N, 7 E (0, 0.5), and small ö > O, there exists positive real function h(n, 7, T,T, 8) such that R. S h(n, 7, T),) with probability at least 1 - 6, i.e. the rejection rate bounded.
E [0, 1] such that the confidence is lower than r e/n E [2]. Moreover, Theorems A. and A.2 claim that th, has a distribution that is close to uniform with high probability (see the theorems and proofs in the Supplement). As a result, with probability at least 1 - 8, we find h(n, 7, T, 5) as follows:
Proof. Theorem 3.1 states that there exists two functions 1 t b),
and
R M. S 1-111111 2e 2T-T)=
PP (vn E (21,
Fv.. (t2) Fs. (t1)
In 2
In
Fx(t2)
(t((t) 2
n, (n, 7, +2
y, 7,,,,,T,0)
2n
2n
3.3 Upper Bounding the Expected Test Time Cost
In a learning with reject scenario, there are costs associated with three outcomes: false positives (Cfp > 0), false negatives (cfn 0), and rejection (c,) because abstaining typically involves having a person intervene. Estimating an expected per example prediction cost at test time can help with model selection and give sense of performance. Theorem 3.8 provides an upper bound on the expected per example cost when (1) using our estimated rejection rate (Theorem 3.5). and (2) setting the decision threshold
in Sec. [
Definition 3.7 (Cost function). Let Y be the true label random variable. Given the costs csp > 0.
Cyn > and Cr the cost function a function e: (0,1) x (0, 1, 3) - such that
c(Y, =y, + c))p((=]])=0)) + ((,
Note that defining a specific cost function requires domain knowledge. Following the learning to
reject literature, we set an additive cost function. Moreover, the rejection cost needs to satisfy the inequality c, < min((1 (1 7)cfp 7Cfn}. }. This avoids the possibility of predicting always anomaly
for an expected cost (1 7)p . or always normal with an expected cost of yCfn [52].
Theorem 3.8. Let be cost function defined in Def. 3.7 and be in Def. 3.4 Given (test)
example x with score s, the expected example-wise wise cost is bounded by
Eg [c] S min A A)cJn + -B)cJp + (B Ajer
(3)
where = Fe.. (g-1 (e-T) and B = Fs.. (g -1 (1 TT) are as in Theorem 3.5
5

---

Proof. We indicate the true label random variable as Y, and the non-rejected false positives and false negatives as, respectively,
FP = = - 1-2c-T) FN = PP ppppy - = 1, >14,>111 20
Using Theorem 3.5 results in
E [c]
En Conn FN Cpp FP c. = En een FN] + Ex CB - A)
where A - و P that setting a decision threshold À such that n scores are higher implies that, on expectation, the detector predicts proportion of positives equal to 7 = P( 1). Moreover, for e 2e-
Ps (g- -)) come from Theorem 3.5
Now we observe
FP F -1,, positive predictions;
>
- B as false positives must be less than total accepted
. FN S and FN < P ( M1 (...,>1-91 1
A, as you cannot have more false negatives than positives (7), nor than accepted negative predictions (A).
From these observations, conclude that Ez|c] I minfy,AAccs + -B)c2 + +(B A)c
Related work
There is no research on learning to reject in unsupervised anomaly detection. However, three main research lines are connected to this work.
1) Supervised methods. If some labels are available, one can use traditional supervised approaches to add the reject option into the detector [I] [3). Commonly, labels can be used to find the optimal rejection threshold in two ways: 1) by trading off the model performance (e.g., AUC)
the
accepted examples with its rejection rate 24 or 2) by minimizing a cost function [46] 77 a risk
function [18 [2)] error function 35 33 Alternatively,
include the reject option in the model and directly optimize during the learning phase 660 31.
2) Self-Supervised methods. labels are not available, one can leverage self-supervised ap- proaches to generate pscudo-labels in order to apply traditional supervised learning to reject meth- ods 266 59 19 37.. For example, one can employ any unsupervised anomaly detector to assign training labels, fit (semi- Jsppevisupe detector (such as DEEPSAD (57) or REPEN (47) the pseudo labels, compute a confidence metric [14, and find the optimal rejection threshold by minimizing the cost function treating the pseudo-labels as the ground truth.
3) Optimizing unsupervised metrics. There exist several unsupervised metrics (i.e., they be computed without labels) for quantifying detector quality [43. Because they do not need labels, one can find the rejection threshold by maximizing the margin between the detector's quality (computed using such metric) on the accepted and on the rejected examples (54). This allows us to obtain a model that performs well the accepted examples and poorly the rejected ones, which is exactly the same intuition that underlies the supervised approaches. Some examples of existing unsupervised metrics (see (43) are the following. EM and Mv [20] quantify the clusterness of inlier scores, where more compact scores indicate better models. STABILITY [48] measures the robustness of anomaly detectors' predictions by looking at how consistently they rank examples by anomalousness. UDR [1] is model-selection metric that selects the model with a hyperparameter setting that yields consistent results across various seeds, which can be used set the rejection threshold through the analogy [hyperparameter, seed] and [rejection threshold, detectors]. Finally, ENS [56] 67] measures the detector trustworthiness as ranking-based similarity (e.g., correlation) of detector's output to the "pseudo ground truth", computed via aggregating the output of an ensemble of detectors, which allows one to set the rejection threshold that maximizes the correlation between the detector's and the ensemble's 's outputs.

---

5 Experiments
We experimentally address the following research questions:
Q1. How does REJEX's cost compare to the baselines?
Q2 How does varying the cost function affect the results?
Q3. How does REJEX's CPU time compare to the baselines?
Q4. Do the theoretical results hold in practice?
QS. Would REJEX's performance significantly improve if it had access to training labels?
5.1 Experimental Setup
Methods. We compare REJEX
against baselines for setting the rejection threshold. These can be divided into three categories: no rejection, self-supervised, and unsupervised metric based.
We one method NOREJECT that always makes predictions and never rejects (no reject option).
We consider one self-supervised approach SS-REPE: 47 This uses (any) unsupervised detector to obtain pseudo labels for the training set. It then sets the rejection threshold as follows: 1) it creates a held-out validation set (20%), 2) it fits REPEN, state-of-the- -f-t-e-rr- jeppersuueee anomaly detector on the training set with the pseudo labels, 3) it computes on the validation set the confidence values as the margin between REPEN'S 's predicted class probabilities JIP(Y = 1|s) - IP(Y- = 0]s)], 4) finds
the optimal threshold by minimizing the total cost obtained on the validation set.
We consider 5 approaches that employ an existing unsupervised metric set the rejection threshold and hence do not require having access to labels. Mv [20). EM (20). and STABILITY [48 are unsupervised metric-based methods based on stand-alone internal evaluations that use single anomaly detector to measure its quality, UDR [1] and ENS (56] are unsupervised consensus-based metries that an ensemble of detectors (all 12 considered in our experiments) to measure detector's quality We apply each of these 5 baselines as follows. 1) We apply the unsupervised detector to assign an anomaly score to each train set example. 2) We convert these scores into class probabilities using (34] 3) We compute the confidence scores the training set as difference between these probabilities: [IP(Y = 1|s) P(Y 0|+)]. 4) We evaluate possible thresholds on this confidence by computing the considered unsupervised metric on the accepted and on the rejected examples and select the threshold that maximizes the difference in the metric's s value on these two sets of examples.
This aligns with the common learning to reject criteria for picking a threshold [9] [54 such that the model performs well on the accepted examples and poorly on the rejected ones.
Data. We earry out study on 34 publicly available benchmark datasets, widely used in the literature (23 These datasets cover many application domains, including healthcare (e.g.. disease diagnosis), audio and language processing (e.g., speech recognition), image processing (e.g., object identification), and finance (e.g., fraud detection). To limit the computational time, we randomly sub-sample 20, 000 examples from all large datasets. Table the Supplement provides further details.
Anomaly Detectors and Hyperparameters. We set our tolerance E = 27 with 32, Note that the exponential smooths out the effect of T > 4, which makes setting different T have little impact. We use a set of 12 unsupervised anomaly detectors implemented PYOD (66 with default hyperparameters
[62 because the unsupervised setting does not allow us to tune them:
KNN 3 FFOREST 42 LOF (5), OCSVM [58] AE [ HBOS (21. LODA (53), COPOD (39).
GMM 2 ECOD 40). KDE (36), INNE []. We set all the baselines' rejection threshold via Bayesian
Optimization with 50 calls 17.
Setup. For each [dataset, detector] pair, proceed as follows: (1) we split the dataset into training and test sets (80-20) using? fold cross- validatii; (2) we use the detector to assign the anomaly scores the training set; (3)
either REJEX baseline set the rejection threshold;
I 'Code availahle at: https: http:://ggttab..ccm/orrreeeee www../ooo//oooeeeeeeeee Pertssiioeoiiiieeeee........ "Sec. describes these approaches.
7

---

(4) we measure the total cost on the test set using the given cost function. We carry out total of
34 12 x 2040 experiments. All experiments were run on an Intel(R) Xeon(R) Silver 4214
CPU.
5.2
Experimental Results
Average Cost per Example
*
RejEx
SS-Repen
My
Ens
Udr
Em
Stability
NoReject
0.16
0.15
Average Ranks
5.
0.14
a.
V
7
7
*
*
iForest
Knn
Ecod
Ocsvm
Gmm
Copod
Lof
Kde
Inne
iForest
Hbos
Knn
Ecod
Ocsvm
Gmm
Copad
Loda
Kde
Figure 1: Average cost per example (left) and rank (right) aggregated detector (x-axis) over all
the datasets. Our method obtains the lowest (best) cost 9 of detectors and always has the
lowest (best) ranking position for Cfp Cfn 1, 7.
Q1: REJEx against the baselines. Figure the comparison between method and the baselines, grouped by detector, when setting the costs Cfp Cfn = and c. (see the Supplement for further details). REJEX achieves the lowest (best) cost per example for of 12 detectors (left-hand side) and similar values to SS-REPEN when using LODA, LOF and KDE. Averaging over the detectors, REJEX reduces the relative cost by more than 5% vs US-REPEN, 11% ENS, 13% vs Mv and UDR, 17% vs EM, 19% vs NOREJECT. Table 4 (Supplement) shows detailed breakdown.
For each experiment, rank all the methods from to 8, where position indicates the lowest (best) cost. The right-hand side of Figure shows that REJEX always obtains the lowest average ranking. We statistical analysis separately for each detector: the Friedman test rejects the null-hypothesis that all methods perform similarly (p-value < e 16) for all the detectors. The ranking- post-hoc Bonferroni-Dus statistical test [13] with 0.05 finds that REJEX significantly better than the baselines for detectors (INNE, IFOREST, HBOS, KNN, ECOD, OCSVM).
Average Cost per Example
RejEx
>>
SS-Repen
Mv
Ens
Udr
Em
Sta Sability
NoReject
Fm
10
0.9
min(l1 ylc VCm.
mln
yC-
*
0.7
ME
0.6
V
0.5
*
*
#
Hbos
iForest
Inne-
Ocsvm
Ecod
Copod
Knn
Ae-
Loda
Lof
Gmm
kde-
Hbos
IForest
Inne
Ocsvm
Ecod
Copod
Knn
Loda
Lof
Gmm-
Kde
Hbos
iForest
Inne
Ocsvm
Ecod
Copad
Knn
Loda
Lof
Gmm
Kde
Figure 2: Average cost per example aggregated by detector over the 34 datasets when varying the
three costs three representative cases: (left) false positives penalized more, (center) false
negatives are penalized more, (right) rejection has a lower cost than FPs and FNs.
Q2. Varying the costs Cfps Cfny The three costs Cyps Cfn. and c, are usually set based on domain knowledge: whether to penalize the false positives or the false negatives more depends on the application domain. Moreover, the rejection cost needs satisfy the constraint e, S mmnn(11

---

7)c/p: 7Cjx [52]. Therefore, we study their impact on three representative cases: (case 1) high false positive cost (Cpp 10, Cn = c, min 7), ?), (case 2) high false negative cost (cfp=1, = 1, Cfn = 10, = min - 7), 10y), and (case 3) same cost for both mispredictions but low rejection cost (Ctp = 5, Cfn = =5, Cr = ?). Note that scaling all the costs has no effect on the relative comparison between the methods, so the last case is equivalent to Csp = 1, CJn = 1, and C, = 7/5.
Figure 2 shows results for the three scenarios. Compared the unsupervised metric-based methods, the left plot shows that our method is clearly the best for high false positives cost: for 11 out of 12 detectors, REJEX obtains both the lowest (or similar for GMM) average cost and the lowest average ranking position. This indicates that using REJEX is suitable when false alarms are expensive. Similarly, the right plot illustrates that REJEX outperforms all the baselines for all the detectors when the rejection cost is low (w.r.t. the false positive and false negative costs). Even when the false negative cost is high (central plot), REJEX obtains the lowest average cost for detectors and has always the lowest average rank per detector. See the Supplement (Table (6 aland] 7 for more details.
Table 1: Average CPU time (in ms) per training example (# std) to set the rejection threshold aggregated over all the datasets when using IFOREST. HBOS, and COPOD as unsupervised anomaly detector. REJEX has lower time than all the methods but NOREJECT, which uses no reject option.
CPU time in ms (mean + std.)
DETECTOR
NOREJECT
REJEX
SS-REPEN
Mv
EM
UDR
EnS
STABILITY
IFOREST
0.010..0
0.06110.22
901168
891:128
1551161
120
12211355
91611000
0.010.0
0.13110.93
891:53
39.181
801
20011338
210.3588
142.1242
COPOD
0.0+0.0
0.04+00.04
844:53
21
81
119#131
123+138
140=248
Q3. Comparing the CPU time. Table | reports CPU time in milliseconds per training example aggregated over the 34 datasets needed for each method to set the rejection threshold on three unsupervised anomaly detectors (IFOREST, HBOS, COPOD). NOREJECT has CPU time equal to 0 because it does not use any reject option. REJEX takes just a little more time than NOREJECT because computing EXCEED has linear time while setting constant threshold has constant time. In contrast, all other methods take 1000 longer because they evaluate multiple thresholds. For some of these (e.g., STABILITY), this involves expensive internal procedure.
Theoretical Upper Bound
Empirical value
Theoretical Expected value
0.6 Cost per example
Rejection Rate
0.3
0.0
Fraud
Satimag
WDBC
Pendigi
Vowes
woverod
Mlmmoog
Glsss
Lymptio
WBC
Will
Letter
Wine
Shutie
Cardio
Census
Verteer
camband
Landii
wrBc
Donors
Salelli
Pima
Fault:
Praud
Census
Campaio
Atoi
Shartle
Salima
Puniigg
Opinigl
Hamnoogr
Warrlor
Anmbyr
Wilt
Musk-
Viomels
Letter
Cardiet
fault
Yeast
wIDOC
clase
WRC
Vensar- Lamphoog WPBC
Figure 3: Average cost per example (left) and average rejection rate (right) at test time aggregated
by dataset over the 12 detectors. both plots, the empirical value (circle) is always lower than the predicted upper bound (continuous black line), which makes it consistent with the theory. On the right, the expected rejection rates (stars) are almost identical to the empirical values.
Q4. Checking on the theoretical results. Section introduces three theoretical results: the rejection rate estimate (Theorem 3.5), and the upper bound for the rejection rate (Theorem 3.6) and for the cost (Theorem 3.8 We run experiments to verify whether they hold in practice. Figure shows the results aggregated over the detectors. The left-hand side confirms that the prediction cost per example (blue circle) is always S than the upper bound (black line). Note that the upper bound is sufficiently strict, as in some cases it equals the empirical cost (c.g., Census, Wilt, Optdigits).
9

---

The right-hand side shows that our rejection rate estimate (orange star) is almost identical to the empirical rejection rate (orange circle) for most of the datasets, especially the large ones. On the other hand, small datasets have the largest gap, e.g., Wine (n 129), Lymphography (n = 148), WPBC (n 198), Vertebral (n 240). Finally, the empirical rejection rate is always lower than the theoretical upper bound (black line), which we compute by using the empirical frequencies w).-
Table 2: Mean + std. for the cost per example (on the left) and the rejection rate (on the right) test time on a per detector basis and aggregated over the datasets.
COST PER EXAMPLE (MEAN + STD.) REJEX
REJECTION RATE (MEAN + STD.)
DETECTOR
ORACLE
REJEX
ORACLE
AE
0.126 + 0.139
0.126 + 0.139
0.131 # 0.132
0.118 + 0.125
COPOD
0.123 + 0.140
0.121 + 0.140
0 = 0.131
0.101 0.114
ECOD
0.119 - 0.138
0.118 0.138
0.125 0.130
GMM
0.123 + 0.135
0.122 + 0.134
=1199=0.14
HBOS
0.118 + 0.129
0.118 + 0.129
0.139 0.148
0.114
FFOEST
0.11&00.12
0.118 0.128
0.127 0.131
INNE
0.115 0.129
0.115 + 0.128
0.132 0.132
0.122 + 0.125
KDE
0.129 1 0.140
0.129 1 0.139
0.121 - 0.129
0.105 1 0.120
KNN
0.119 0.123
0.118 1 0.123
0.127 0.129
0.112 1 0.117
LODA
0.125 1 0.133
0.122 0.130
0.126 1 0.124
0.110 1 0.114
LOF
0.126 0.131
0.125 0.131
0.129 = 0.126
0.118 0.115
OCSVM
0.120 - 0.131
0.120 0.131
0.131
0.126 = 0.128
0.107 = 0.115
AVG.
0.122 4: 0.133
0.121 + 0.133
0.129 + 0.132
0.114 + 0.121
QS. Impact of training labels on REJEX. We simulate having access to the training labels and include an extra baseline: ORACLE uses EXCERD as confidence metric and sets the (optimal) rejection threshold by minimizing the cost function using the training labels. Table 2 shows the average cost and rejection rates at test time obtained by the two methods. Overall, REJEX obtains an average cost that is only 0.6% higher than ORACLE's cost. On per-detector basis, REJEX obtains 2.5% higher cost in the worst case (with LODA), while getting only a 0.08% increase in the best case (with KDE). Comparing the rejection rates, REJEX rejects average only 1.5 percentage points more examples than ORACLE (12.9% vs 11.4%). The supplement provides further details.
Conclusion and Limitations
This paper addressed learning reject in the context of unsupervised anomaly detection. The key challenge was how to set the rejection threshold without access to labels which are required by all existing approaches We proposed an approach REJEX that exploits our novel theoretical analysis of the EXCEED confidence metric. Our new analysis shows that it is possible to set constant rejection threshold and that doing so offers strong theoretical guarantees. First, we can estimate the proportion of rejected test examples and provide an upper bound for our estimate. Second, we can provide a thcoretical upper bound on the expected test-time prediction cost per example. Experimentally, compared REJEX against several (unsupervised) metric-based methods and showed that, for the majority of anomaly detectors, it obtained lower (better) cost. Moreover, we proved that our theoretical results hold in practice and that our rejection rate estimate is almost identical to the true value in the majority of cases.
Limitations. Because REJEX does not rely on labels, it can only give coarse -raiined view of performance. For example, in many applications anomalies will have varying costs (i.e., there are instance-specie costs) which we cannot account for. Moreover, REJEX has a strictly positive rejection rate, which may increase the cost of highly accurate detector. However, this happens only in s 5% of our experiments.
10

---

Acknowledgements
This research supported by an FB Ph.D. fellowship by TWO-Vlaanderen (grant 1166222N) [LP). the Flemish Government under the "Onderzoeksprogrammn Artificiéle Intelligentie (Al) Vlaanderen" programme [LP.ID], and KUL Research Fund iBOF/21/075 (JD].
References
[1] M. R. Abbas, M. S. A. Nadeem, A. Shaheen, A. A. Alshdadi, R. Alharbey, S.-O. Shim, and W. Aziz. Accuracy rejection normalized-cost curves (amecs): novel 3-dimensional framework for robust classification. IEEE Access, 7:160125-1600 160143, 2019.
[2] C. C. Aggarwal. An introduction to outlier analysis. In Outlier analysis, pages 1-34. Springer, 2017.
[3] F. Angiulli and C. Pizzuti. Fast outlier detection in high dimensional spaces. In European conference on principles of data mining and knowledge discovery, pages 15-27. Springer, 2002.
[4] T. R. Bandaragoda, K. M. Ting, D. Albrecht, F. T. Liu, Y. Zhu, and J. R. Wells. Isolation- based anomaly detection using nearest-neighhor ensembles. Computational Intelligence, 34(4): 968-998, 2018.
[5] M. M. Breunig, H.-P Kriegel, R. T. Ng, and J. Sander. Lof: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 93-104, 2000.
[6] V. Chandola, A. Banerjee, and V. Kumar. Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3) 2009.
[7] N. Charoenphakdee, Z. Cui, Y. Zhang, and M. Sugiyama. Classification with rejection based on cost-sensitive classification. International Conference on Machine Learning, pages 1507-1517. PMLR, 2021.
[8] Z. Chen, C. K. Yeo, B. S. Lee, and C. T. Lau. butoencoder-based network anomaly detection. In 2018 Wireless telecommunicationn symposium (WTS), pages 1-5, IEEE, 2018
[9] C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on information theory, 16(1):41-46, 1970.
[10] L. Coenen, A. K. Abdullah, and T. Guns. Probability of default estimation, with reject option. In 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pages 439-448. IEEE, 2020.
[11] D. Conte, P. Foggia. G. Percamnella, A. Saggese, and M. Vento. An ensemble of rejecting classifiers for anomaly detection of audio events. In 2012 IEEE Ninth International Conference on Advanced Video and Signal-Basc Baxed Surveillance, pages 76-81. IEFF, 2012.
[12] C. Cortes, G. DeSalvo, and M. Mohri. Learning with rejection. In International Conference on Algorithmic Learning Theory. Springer, 2016.
[13] Demšar. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research, 7:1-30, 2006.
[14] C. Denis and M. Hebiri. Consistency of plug-in confidence sets for classification in semi- supervised learning. Journal of Nonparametric Statistics, 32(1):42-72, 2020.
[15] Duan, L. Matthey, A. Saraiva, N. Watters, C. Burgess, A. Lerchner, and Higgins. Unsupervised model selection for variational disentangled representation leamnin.. arXiv preprint arXiv: /905. /2614 2019.
[16] R. El- Yaniv et al. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(5), 2010.
[17] P. I. Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811 2018

---

[18] Y. Geifman and R. El-Yaniv, Selectivenet: A deep neural network with an integrated reject option. In International conference on machine learning, pages 2151-2159. PMLR, 2019.
[19] M.-l. Georgescu, A. Barbalau, R. T. Ionescu, F, S. Khan, M. Popescu, and M. Shah. Anomaly detection in video via self-supervised and multi-task learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 12742-12752, 2021.
[20] N. Goix. How evaluate the quality of unsupervised anomaly detection algorithms? arXiv preprini arXiv: 1607.01 152, 2016.
[21] M. Goldstein and A. Dengel. Histogram-based outlier score (hbos): A fast unsupervised anomaly detection algorithm. KI-2012: poster and demo track, 9, 2012.
[22] D. Guthrie, L. Guthrie, B. Allison, and Y. Wilks. Unsupervised anomaly detection. In IJCAI, pages 1624-1628, 2007.
[23] S. Han, X. Hu, H. Huang, M. Jiang, and Y. Zhao. Adbench: Anomaly detection benchmark. In Neural Information Processing Systems (NeurIPS), 2022.
[24] B. Hanczar. Performance visualization spaces for classification with rejection option. Pattern Recognition, 96:106984, 2019.
[25] K. Hendrickx, L. Perini, D. Van der Plas, W. Meert, and J. Davis. Machine learning with a reject option: A survey. arXiv preprint arXiv:2 2021.
[26] H. Hojjati, T. K. K. Ho, and N. Armanfard. seff-superviee anomaly detection: survey and outlook. arXiv preprint arXiv:2205.0m 05113, 2022.
[27] L. Huang. C. Zhang, and H. Zhang. Self-adaptive training: beyond empirical risk minimization. Advances in neural information processing systems, 33:19365- 2020.
(28) E. Hüllermeier and W. Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine Learning, 110(3):457-066 2021.
[29] H. Jmila and M. I. Khedher. Adversarial machine learning for network intrusion detection: A comparative study. Computer Networks, page 109073, 2022.
[30] M. U. K. Khan, H.-S. Park, and C.-M. Kyung. Rejecting motion outliers for efficient crowd anomaly detection. IEEE Transactions on Information Forensics and Security, 14(2):541-556, 2018.
[31] M. A. Kocak, D. Ramirez, E. Erkip, and D. E. Shasha. Safepredict: A meta-algorithm for machine learning that uses refusals to guarantee correctness. IEFE Transactions on Puttern Analysis and Machine Intelligence, 43(2):663-617 678, 2019.
[32] B. Kompa, J. Snock, and A. L. Beam. Second opinion needed: communicating uncertainty in medical machine learning. NPJ Digital Medicine, 4(1):4, 2021.
[33] E.. Korycki, A. Cano, and B. Krawezyk. Active learning with abstaining classifiers for imbal- anced drifting data streams. In 2019 IEEE international conference on big data (big data), pages 2334-2343. IEEE, 2019.
[34] H.-P. Kriegel, P. Kroger, E. Schubert, and A. Zimek. Interpreting and unifying outlier scores. In Proceedings of the 201 SIAM International Conference on Data Mining, pages 13-24. SIAM, 2011.
[35] S. Laroui, X. Descombes, A. Vernay, F. Villiers, F. Villalba, and E. Debreuve. How to define rejection class based model learning? In 2020 25th International Conference Pattern Recognition (ICPR), pages 569-576. IEEE, 2021.
[36] I. J. Latecki, A. Lazarevic, and D. Pokrajac. Outlier detection with kernel density functions. In International Workshop on Machine Learning and Data Mining Pattern Recognition, pages 61-75. Springer, 2007.
12

---

[37] C.-L. Li, K. Sohn, J. Yoon, and T. Pfister. Cuipaste: Self-supervised learning for anomaly detection and localization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2021.
[38] S. Li, X. Ji, E. Dobriban, O. Sokolsky, and I. Lee. Pac-wrap: Semi-supervised pac anomaly detection, arXiv preprini arXiv:2205. 10798, 2022.
[39] Z. Li, Y. Zhao, N. Botta, C. lonescu, and X. Hu. Copod: copula- based outlier detection. In 2020 IEEE International Conference on Data Mining (ICDM), pages 1118-1123. IEEE, 2020.
[40] Z. Li, Y. Zhao, X. Hu, N. Botta, C. Ionescu, and G. Chen. Ecod: Unsupervised outlier detection using empirical cumulative distribution functions. IEEE Transactions on Knowledge and Data Engineering, 2022.
[41] O. Lindenbaum, Y. Aizenbud, and Y. Kluger. Probabilistic robust autoencoders for outlier detection. arXiv preprint 2rXiv:2110.00494, 2021.
[42] F. T. Liu, K. M. Ting, and Z.-H. Zhou. Isolation-based anomaly detection. ACM Transactions on Knowledge Discovery from Data (TKDD), 6(1):1-39, 2012.
[43] M. Q. Ma, Y. Zhao, X. Zhang, and L. Akoglu. A large-scale study on unsupervised outlier model selection: Do internal strategies suffice? arXiv preprint arXiv:2104.01422, 2021.
[44] C. Marrocco, M. Molinara, and F. Tortorella. An empirical comparison of ideal and empirical roc-based reject rules. In International Workshop on Machine Learning and Data Mining in Pattern Recognition, pages 47-60. Springer, 2007.
[45] L. Martí, N. Sanchez-Pa Pi, J. M. Molina, and A. C. B. Garcia. Anomaly detection based on sensor data in petroleum industry applications. Sensors, 2015.
[46] V.-L. Nguyen and E. Hullermeier. Reliable multilabel classification: Prediction with partial abstention, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5264-5271, 2020.
[47] G. Pang. Cao, I.. Chen, and H. Liu. Learning representations of altrahigh-dimensionn data for random distance-based outlier detection. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2041-2055 2018
[48] L. Perini, C.
Galvin, and V. Vereruyssen. A ranking stability measure for quantifying the robustness of anomaly detection methods. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 397-408. Springer, 2020.
[49] I.. Perini, V. Vercruyssen, and J. Davis. Quantifying the confidence of anomaly detectors in their example-wise predictions. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 227-243 Springer, 2020.
[50] L. Perini, V. Vercruyssen, and J. Davis. Transferring the contamination factor between anomaly detection domains by shape similarity. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4128-4136, 2022.
[51] I.. Perini, P.-C. Bürkner, and A. Klami. Estimating the contamination factor's distribution in unsupervised anomaly detection. In International Conference on Machine Learning, pages PMLR, 2023.
[52] L. Perini, D. Giannuzzi, and J. Davis. How to allocate your label budget? choosing between active learning and learning to reject in anomaly detection. arXiv preprint arXiv:2301.02909, 2023.
[53] T. Pevný. Loda: Lightweight on-line detector of anomalies. Machine Learning, 102(2):755-304, 2016.
[54] A. Pugnana and Ruggieri. Auc-based selective classification. International Conference on Artificial Intelligence and Statistics, pages 2494-2514, PMLR, 2023.
13

---

[55] C. Qiu, T. Pfrommer, M. Kloft, S. Mandt, and M. Rudolph. Neural transformation learning for deep anomaly detection beyond images. In International Conference on Machine Learning. pages 8703-8714 PMLR R, 2021.
[56] S. Rayana and L. Akoglu. Less is more: Building selective anomaly ensembles, Acm transac- tions on knowledge discovery from data (tkdd), 10(4):1-33, 2016.
[57] L. Ruff, R. A. Vandermeulen, N. Görnitz, A. Binder, E. Müller, K.-R. Mäller, and M. Kloft. Deep semi-supervissed anomaly detection. arXiv preprint /96.02490, 2019.
[58] B. Schölkopf. J. C. Platt, Shawo-Taylor, A. Smola, and C. Williamson. Estimating the support of a high-dimensional distribution. Neural computation, 13(7): (37)):14331141,, 2001.
[59] V. Sehwag, M. Chiang, and P. Mittal. Ssd: A unified framework for self-supervised outlier detection, arXiv preprint arXiv:2 103. /205/, 2021.
[60] Shekhar, M. Ghavamzadeh, and T. Javidi. Binary classification with bounded abstention rate. arXiv preprint 190.0966,
[61] T. Shenkar and L. Wolf. Anomaly detection for tabular data with internal contrastive learning. In International Conference on Learning Representations, 2021.
[62] J. Soenen, E. Van Wolputte, L. Perini, V. Vercruyssen, W. Meert, J. Davis, and H. Blockeel. The effect of hyperparameter tuning on the comparative evaluation of unsupervised anomaly detection methods. In Proceedings of the KDD, volume 21, pages 1-9, 2021.
[63] D. Van der Plas, W. Meert, J. Verbraecken, and J. Davis. A reject option for automated sleep stage scoring. Workshop on Interpretable ML. Healthcare at International Conference on Machine Learning (ICML), 2021.
[64] L. Xiang, X. Yang, A. Hu, H. Su, and P. Wang. Condition monitoring and anomaly detection of wind turbine based on cascaded and bidirectional deep learning networks. Applied Energy, 305: 117925, 2022.
[65] N. Zhao, X. Wen, and S. Li. A review on gas turbine anomaly detection for implementing health management. Turbo Expo: Power for Land, Sea, and Air, 2016.
[66] Y. Zhao, Z. Nasrullah, and Z. Li. Pyod: A python toolbox for scalable outlier detection. Journal of Machine Learning Research, 20(96):1-7, 2019. URL http://jmmrr.orgpppeer///// 19-011 html
[67] A. Zimek, R. J. Campello, and J. Sander. Ensembles for unsupervised outlier detection: challenges and research questions a position paper. Acm Sigkdd Explorations Newsletter, 15(1): 1 11-22, 2014.
14

---

Supplement
In this supplementary material (I) provide additional theorems and proofs for Section 3 and (2) further describe the experimental results.
A Theoretical Results
Firstly, we provide the proof for Theorem 3.1
Theorem 3.1 (Analysis of EXCEED) Let s be an anomaly score, and tn E [0, 1] the proportion of
training scores S s. For 72 4, there exist 4 6 (n, 7, T') E { 11, l2 (n, 7, T*) E [0, 1] such that
V/ [1, t2] = M,
2e --
Proof. We split this proof into two parts: we show that the reverse inequalities, i.e. that (a) if 4/, S ty. then Ms 2 2. -e- and (b) thn 2 12, then Mr 2 2e- hold and prove the final statement because P(Y- 1[s) is monotonic increasing on s.
(a) The probability P(Ý (s)) (as Eq. D can be seen as the cumulative distribution F of binomial random variable (4g,, n) with at most ny 1 successes out of trials, with 9. = ==1-#a)+1 success probability. By applying Hoeffding 's inequality, we obtain the upper bound
as the
2+n
P(V 1|8) S exp
22
[n11 +1
ny
2 + n
n
that holds for the constraint 1h. S 24m M. 2c-T we search for the values of 1/, such that the upper bound is I e Forcing the upper bound S e- results in
+ 1-27 (1 7). Because PPÝ 1[s) S E -T implies that
n1(1
v)a) +1
2n
T 0,
n n
n
which is satisfied for (
Vn
A
/B, and (I2) A + /B1 t/ S 1, where
A + n(n + 1)(1
B 2n (-37² 2n 7) 47 3) + T( + 2)
n²
2n
However, for T' 2 4, no values of n, 7, and that satisfy the constraint on , also satisfy 12. Moving to 41, we find out that if vnn satisfies Z1, then it also satisfies the constraint th, for any n, 7, and T. Therefore, we we set b (n, 7, T) A vB, /B. As a result,
1 5 = P(Ý = -,
(b) Similarly, TP(Y = 0|s) can be seen the cumulative distribution F of B(ps, n), with n(1 - 7) successes and P. (+) By seeing the binomial sum of Bernoulli random variables, and 2+z
using the property of its cumulative distribution F(n(1 - -),, n. n,Ps) + F(ny n, - p&) 1, we apply the Hoeffding's inequality and compare such upper bound to the e We obtain
1 + thnn - -(1 (1--1) T20
2n
2+n
(1+m)(1-1)-1 The quadratic inequality in th, has solutions n for (I1) 0 < Vn - A₂ VB, and (I2) Ag + VB, S th. < 1, where Ag (2+n) and B, T(++2)2 However, the constraint limits the solutions to Iz. i.e. for the 2 A2 + /BB BB. Thus,
that holds with the constraint vo.
2nd set T, A /B, and conclude that
Sh ž tz P(
1|s) 2 2 M. 2 2e
15

---

Secondly, Theorem relles two important results; given S the anomaly score random variable, (1) if th, was the theoretical cumulative of S, it would have uniform distribution (Theorem[A.) but because in practice (2) t/n is the empirical cumulative of S, its distribution is close to uniform with high probability (Theorem A.2). We prove these results in the following theorems.
Theorem A.I. Let S be the anomaly score random variable, and Fs(() be the cumulative distribution of S applied to S itself. Then v ~ Unif(0, 1).
Proof. We prove that, 2 Uni 1), then (t for any [0. 1]:
(t) = F(eb x P(Fs - P( < F5 (t)) Fs(FF (0) (1))= =t = v ~ Unif(1
Theorem A.2. Let up be in Theorem A.1 and F be its empirical distribution obtained from sample of size n.. For any small > 0 and i [0, 1}, with probability > -
In 2 2n
Fo. (t) E (t
(t)
2n
Proof. For any the DKW inequality implies
P
sup [E[0,1]
FF (1) Po(( >5)
< 2exx (-2ne²)
By setting 8 2ex (-2nE²), i.c. E conclude that
In 2x
and using the complementary probability
In 2
P sup tE|0.1]
Fe, (t) Fo(t) S
1188 8.
2n
B Experiments
Data. Table shows the properties of the 34 datasets used for the experimental compari- son, terms of number of examples, features, and contamination factor y. The datasets can be downloaded in the following link:
Cttasets/Classinn
Q1. REJEX against the baselines. Table f and Table the results (mean + std) aggregated by detectors terms of, respectively, cost per example and ranking position. Results confirm that REJEX obtains an average cost example lower than all the baselines for 9 out of 12 detectors, which is similar the runner-up SS-R SS-REPEN for the remaining 3 detectors. Moreover, REJEX has always the best (lowest) average ranking position.
Q2. Varying the costs Cjps Cfas Cy. Table 6 and Table T the average cost per example and the ranking position (mean + std) aggregated by detectors for three representative cost functions, as discussed the paper. Results are similar in all three cases. For high false positives cost (Cyp 10), REJEX obtains an average cost per example lower than all the baselines for 11 out of 12 detectors and always the best average ranking position. For high false negative cost (cjn = 10) as well for low rejection cost (Cfp 5, Cfn 5. ?), it has the lowest average cost for all detectors and always the best average ranking. Moreover, when rejection is highly valuable (low cost), REJEX's cost has large gap with respect the baselines, which means that it is particularly useful when rejection less expensive.
16

---

Table 3: Properties (number of examples, features, and contamination factor) of the 34 benchmark datasets used for the experiments.
DATASET
#EXAMPLES
#FEATURES
Y
ALOI
20000
27
0.0315
ANNTHYROID
7062
0.0756 6
CAMPAIGN
20000
62
0.1127
CARDIO
1822
0.0960
CARDIOTOCOGRAPPH
2110
0.2204
CENSUS
20000
500
0.0854
DONORS
20000
10
0.2146
FAULT
1941
0.3467 27
FRAUD
20000
0.0021
GLASS
213
7
0.0423
HTTP
20000
3
0.0004
INTERNETADS
1966
1555
0.1872
LANDSAT
6435
0.2071
LETTER
1598
32
0.0626
LYMPHOGRAPHY
148
0.0405 18
MAMMOGRAPHY
7848
6
0.0322
MUSK
3062
166
0.0317
OPTDIGITS
5198
0.0254
PAGEBLOCKS
5393
0.0946 10
PENDIGITS
6870
16
0.0227
PIMA
768
0.3490 8
SATELIIT
6435
0.3164
S ATIMAGE
5801
0.0119
SHUTTLE
20000
0.0725
THYROID
3656
0.0254 6
VERTEBRAL
240
0.1250
VOWELS
1452
0.0317
WAVEFORM
3443
21
0.0290
WBC
223
0.0448 9
WDBC
367
0.0272 30
WILT
4819
0.0533
WINE
129
0.0775
WPBC
198
33
0.2374
YEAST
1453
8
0.3310
Table 4: Cost per example (mean + std) per detector aggregated over the datasets. Results show that REJEX obtains a lower average cost for out of 12 detectors and similar average cost as the runner-up AS-REPEN for the remaining detectors. Moreover, REJEX has the best overall average row).
PER
(MEAN + STD.)
DET.
RoJEx
SS-RIPEN
Mv
ENS
UDR
EM
STABILITY
NORDECT
0.122
0.139
0.124
0.151
0.138
0.148 0.152
CoPOD
0.123 1: 0.138
0.125
1125:1000
0.14
0.135 1 0.142
0.133 1 0.140
0.140
0.144
0.143
0.148
0.145 - 0.147
0.146
1: 0.148
0.135
GMM
0.122
+ 0.135
1.124
0,144
0,141
0.136
0.146
0. 0.145
0.142
0.156
11156+100
0.148
0.151
0.147
0.156
= 0.14
HBOS
0.116 + 0.129
0.123
0:23:000 0.138
0.131
0.132
0.134
0.136
0.135
0.137
0.139
0.141
0,140
0.139
0.142
0.142
IFOR
0.115 1: 0.128
0.123 0.135
0.130
0.136
0.129
0.136
0.134
0.139
0.140
1 0.143
0.139
0.141
0.143
0.144
INNE
0.113
+ 0.129
0.2
0.3
0.145 + 0.134
0.146
0.140
0.145
+: 0.138
0.147
- 0.140
0.146
0.139
0.145 - 0.140
KNN
0.119
1: 0.123
0.125 1 035
040 1 0.131
0.135
L 0.131
0.135
0.130
0.144
0.132
0.141
0.131
0.146
1. 0.133
0.134
0,131
0.1
0.151
LoF
0.126
- 0.131
0.126
0.136
155
140
0.140
039
0. 142
0.138
0.157
0.140
0,151
0.
0.158
0.140
OCsvM
0.120 1 0.131
0.125
0.3
0.138
0.138
0.132
0.140
O.
138
0.140
0.141
0.140
0.137
0.136
0.147
0.143
AvG.
0.121 1: 0.133
125
0.135
131
0.137
0.1
0.140
O. 139
0.140
0.146
1 0.143
0.144
1 0.140
0.140/
0.144
0.144

---

Table 5: Ranking positions (mean + std) per detector aggregated over the datasets. Results show that REJEX obtains always the lowest average rank, despite being close to the runner-up SS-REPER when the detector is LODA.
RANKING POSITION (MEAN STD.)
DET:
RezEx
SS-REPEN
MV
ENS
UDR
EM
STABILITY
NORBJECT
AE
2.63 + 1.63
3.96
+ 2.94
4.78 + 2.10
3.81
+ 2.11
4.98
+:
1 1.88
5.15
1.80
4.92
+: 1.78
5.77
+ 1.84
COpOD
2.49 1 1.65
3.44
1: 2.75
3.97
1 1.92
4.25
1: 2.17
5.24
1: 1.70
5.13
1.67
5.59
1 1.48
5.89
1: 2.13
BCOD
2.43 - 1.44
3.62
+ 2.86
3.73
+ 1.96
4.13 2.29
5.53
1.57
4.75
1.62
5.74
1.39
6.07
1.93
GMM
2.12 = 1.08
3.05
+ 2.49
5.26
= 1.92
3.49
2.00
4.43
+ 1666
6.26
+ 1.24
5.20
+ 1.43
6.20
= 1.45
HBOS
1.57
3.64
+: 2.98
4.54
4.39
4.95
5.04
1.40
1.88
IoR
2.23 1 1.48
3.78
1 2.78
4.12
1 1.90
4.26
1 2.08
5.10
1 1.88
5.27
1.66
5.34
1 1.38
5.91
2.22
INNE
1,73 = 1.14
3.18
+ 2.74
5.86
+ 2.42
5.57
+ 1.40
4.94
+: 1.62
5.57
1.60
5.32
1.37
3.83
1.63
KDE
2.33 1 1.42
3.99
1 2.86
4.74
1 2.06
3.79
1 2.03
5.01
1.0
5.43
1.59
4.87
1.92
5.84
1.80
KNN
2.02 - 1.29
3.58 + 2.87
4.87
+ 1.81
3.94
1.94
4.41
+ 1.83
5.75
1.49
5.22
+ 1.62
6.21
- 1.48
LODA
2.89 - 1.77
3.17
+ 2.30
4.15
2.26
4.36
2.14
4,99
2.00
5.50
2.04
4.98
2.11
5.95
1.73
LoF
2.04 = 1.01
3.16
+ 2.73
5.68
= 1.40
3.32
+ 1.71
3.96
+ 63
6.15 + 1.19
5.47
+ 1.49
6.22
+ 1.31
OCSVM
1.29
4: 2.84
4.89
1.98
3.85
4.86
5.31
5.06
1.66
AVG.
2.29 1 1.40
3.54
2.76
4.72
1: 1.99
4.10
1:
2.01
4.87 1
1.78
5.44 1: 1.63
5.28 1: 1.60 5.77 1: 1.76
Table 6: Cost per example (mean = std) per detector aggregated over the datasets. The table is divided into three parts, where each part has different costs (false positives, false negatives, rejection). Results show that REJEX obtains lower average cost in all cases but one (KDE).
COST PER EXAMPLE FOR THRER COST FUNCTIONS (MEAN + STD)
DET.
REIEX
SS-ROPEN
MV
ENS
UDR
EM
STADILITY
NORDECT
FALSE POSITIVE COST
10, FALSE NEGATIVE COST = 1, REJECTION COST = min min -))
AE
0.504 + 0.626 0,584 0.723
0.697 = 0.763
0.661 = 0.830
0. 703 + 0.829 0.766 + 0,841
0.768 = 0.826
0.825 + 0.873
COPOD
0.491 + 0.637
0,593
0.706
0.686 = 0.746
0.618
0.726
0,707 + 0.788
0.778
0.825
0.785 = 0.801
0.781 + 0.833
ECoD
0.479 + 0.628
0.584 0:44:0000 0.727
0,625
0.705
0.642 0.755
0.711 0.774
0.748
0.800
0.770 0.783
0.771 0.817
GMM
0.568 + 0.713
0,589 = 0.752
0.823 = 0.878
0.715
0.929
0.790
+ 0.925
0.941
2 0.948
0.889 = 0.929
0.950 - 0.967
HBoS
::
0.569 0.758
0.693
0.697 1 0.732
0.709
0.764
0.800
0,771 = 0.770
0.809 0.816
IFRR
0.477 1: 0.602
0.575 1: 0.712
0.665 1 0.718
0.634 1 0.731
0,683 1. 0.786
0.776 1. 0.818
0.763 - 0.788
0.808 1: 0.831
INNE
0.479 + 0.592
0.567 = 0.698
0.752
0.724
0.820 + 0.795
0,815
0.787 0.819
+ 0.793
0.818 = 0.792
0.823 0.799
KDE
0.602 + 0.827
0.589
= 0.704
0,819 = 0,947
0.740 = 0.913
0.793 0.939
0.897
= 0.945
0,774 = 0.906
0.914 = 0.945
KNN
0.498 :: 0.577
U.59 0.726
0.741 - 0.734
0.669 + 0.720
0.669
+ 0.736
0.777
1 0.747
0.734 = 0.735
0.800 + 0.749
LODA
0,518 1. 0.619
0.574
0.709
0.574
0.647
0.689
1 0.729
0.701
0.748
0.762
0.774
0.697
0.682
0.827 0.797
LoF
0.539
: 0.623
0,603
: 0. 742
0.898
- 0.840
0.685
+ 0.773
0.715 + 0.790
0.891
- 0.813
0.831
= 0.821
0.887
+ 0.808
OCSVM
1 0.599
0.589
0.
0.745
0.632 1 0.752
0.782 0.760
0.775
0.695
0.737
0.818
0.806
FALSE POSITIVE COST
1, FALSE NEGATIVE COST
10, REJECTION COST
min
7. 107)
AE
0.730 1: 0.747 0.761 1: 0.909 1 0.882
0.784 1 0.825
0.780 1 0.805
0.819 1 0.843
0.789 :: 0.825 0..79
1: 0.821
CoPOD
:: 0.767
0.765
0.770
0.930
0.888
0.794
4
0.801
0.842
0.802 -
0.827
0.832
EcoD
0.739 + 0.759
0.767 = 0.766
0,900 = 0.858
0.789 + 0.811
0.788 + 0.787
0.840 0,833
0.791 = 0.803
0.821
0.819
GMM
0.670 + 0.676 0.765
= 0.767
0,845 = 0.782
0.754 + 0.755
0.739
0.736
0.785
0.757
0.760 = 0.753
0.766
0.750
HBos
0.687 : 0.684 0.776
0.782
0.824
0.808
0.750 + 0.768
0.744 0.747
0.785
0.787
0.749
0.765
0.753 0.766
IFOR
0.679 + 0.680 0.775
: 0.776
0.847
= 0.824
0.755 + 0.771
0.743 + 0.745
0.761
- 0.772
0.757
= 0.774
0.763 + 0.770
:
0.779
0.695
0.742
0.748
0.722
0.758
0.737
0.716
0.773 0.754
KDE
0.691
1. 0.692
0.791
0.773
0.887
1 0.836
0.754 1 0.760
0.755
0.744
0.785
1 0.807
0.758
0.754
0.759 1 0.760
KNN
0.706 : 0.657
0.767
0.
0.839
0.779
0.791
+ 0.736
769
0.710
0.778
0.736
0.799
0.736
0.803 0.729
LODA
0.750
= 0.714
0.781
= 0.775
0,880
0,850
0.811 = 0.768
0. 806
0.761
0.804
+ 0.783
0.827
0.780
0.838 = 0.784
LoF
0.738
: 0.679
0.764
0.764
0,999
= 0.833
0.826
: 0.757
0.810
:: 0.739
0.871
+ 0.770
0.867
= 7.799
0.846 + 0.747
OCsVM
0.730 1: 0.711
0.780
0.774
0.953
0.878
0.791 1 0.786
0.795 0.773
0.845 0.833 0.787
0.772
0.796
0.783
FALSE POSITIVE COST
5, FALSE NEGATIVE COST
5, REJECTION COST
AB
0.534 + 0.611
0.66
0.741
0.655 + 0.736 0.707 + 0.748
0.705 = 0.740
0.738 0.762
COPOD
0.545 0.619
0.673
0.62
0.716
0.739
ECoD
0.529 1: 0.609
0.625 1.625::0.675
0.629
0.687
0.638
0.702
0.662
0.705
0.701
1 0.736
0.708
= 0.716
0.724
1: 0.727
GMM
0.534 1:
0.626 0.687
0.719
0.709
0.656
0.716
0.720
0.776
0.736
0.746
D.731
0.780
1: 0.743
Hbos
0.499 + 0.572
0.622
0.632
0.661
0.650
0.669
0.641 0.681 0.695
0.706
0.688
= 0.686
0.710 0.709
IFOR
0.497 = 0.569
0.623
0,643 = 0.680
0.620
0.667
0.629
0.696
0.712
0.688
= 0.701
0.714 + 0.719
INNE
0.491 1: 0.569
0.617 0.668
0.622
0.572
0.718
0.691
0.691
0.674
0.709
0.685
0.705 0.675
0.726 0.698
KDE
0.562 + 0.639
1.642=0.667
0.709
= 0.739
0.666
+ 0.711
0.684
0.726 0.748
0.742
0.679 = 0.689
0.761 = 0.742
0.521 :: 0.544
0.677
0.637
0.646
0.634
0.701
0.66
0.693
0.637
0.728 0.664
LODA
0.550 1: 0.595
0.627 1 0.677
0.601
1 0.649
0.670
1 0.668
0
665
0
0.680
0.708
0.698
0.683
- 0.645
0.757
1 0.711
LOF
1: 0.628 0.681
0,809
0.737
0.678
0.682
0.674
0.792
0.703
0.759
0.718
0.788 0.698
OcSVM
0.523
+ 0.582
00.33
0, 0.704
0.728
0.6334444
0.685
0.657
0.695
0. 709
0.660
0.674
0.733 0.716
18

---

Table 7: Rankings (mean + std) per detector aggregated the datasets, where lower positions mean lower costs (better). The table is divided into three parts, where each part has different costs for false positives, false negatives, and rejection. RESEX obtains the lowest (best) average ranking position for all the detectors and all cost functions.
RANKINGS FOR THE THREE COST FUNCTIONS (MEAN + STD)
STABILITY NOREJECT
FALSE POSITIVE COST
10,
FALSE NEGATIVE COST
REJECTION COST
min(10(1 7)
AE
2.35 + 1.37
3.84
2.73
5.87
2.40
3.68
2.05
4.85
+ 1.96
5.33
1.67
4.72
+ 1.68
5.36
1.97
COPOD
2.25 +: 1.45
3.63
2.66
4.79
2.27
3.89
2.27
4,94
1.76
5,46
1.71
5.51
1.45
5.54
2.17
ECOD
2.28 +: 1.30
3.51
2.73
4.63
2.36
3.85
+ 2.21
5.34
1.74
5.11
1.66
5.38
1.39
5.90
2.09
GMM
2.13 0.99
3.10
2.43
2.23 6.36
3.31
1.94
4,21
1.69
6.28
1.27
5.18
1.53
5.44
1.50
HBOS
2.12 1.42
3.46
2.85
5
4.25
2.06
4.78
1.78
5.35
1.66
5.42
1.47
5.20
1.95
[FRR
2.11 + 1.49
3.69
2.61
4.73
#
4.02
2.11
5.07
1.87
5.39
1.61
1.41 5.36
5.63
2.24
4.60
5.32
KDE
2.14 + 1.25
3.82
+ 2.68
5.73
2.36
3.54
1.92
4,75
1.85
5.84 1.58
4,83
= 1.91
5.36
1.75
KNN
1.99 + 1.28
2.74 3.50
5.55
2.21
3.92
2.02
4,37
1.86
5.73
1.46
5.23
1.68
5,71
1.71
LODA
2.36 1: 1.53
3.31
4.29
2.48
4.34
2.14
5.03
1.95
5.42
1.88
4,96
2.04
6.08
1.75
LOF
1.96
1 1.03
3.04
2.46
7.12
1.28
3.14
1.60
3,73
1.31
6.27
1.14
5.59
1 1.66
5.15
1.39
OCSVM
2.15
1.20
3.93
5.92
2.30
2.13
4.70
5.40
5.03
1.89
5
1.67
FALSE POSITIVE COST
FALSE NEGATIVE COST
10, REJECTION COST
min
-1, 10
AE
2.98 +: 1.93
3.82 2.72
7.03
1.95
4.30
2.07
4.49
8.82
4.96
1.83
4.28
1.62
4.14
1.93
ECoD
2.70 +: 1.96
3.88
+ 2.82
2.82
6.87
1.72
4.15
2.02
4.74
1.79
5.01
2.03
4.23 = 1.50
4.42 - 1.90
GMM
2.59 + 1.70
3.99
6.84
2.22
4.04
2.12
4.08
1.77
5.73
1,37
4.62
4.12 - 1.58
HBOS
2.96 +: 2.14
4.32
6.41
2.20
4,49
1.92
4.37
1.82
5.15
1,94
4.48
1.65
3.81 = 1.81
IFRR
2.71 2.06
2.92 4.51
6.80
2.00
4.47
2.09
4.62
1.72
4.33
1.66
4.55
1.47
4,01
1 1.93
INNE
2.64 1: 1.94
4.71
5.06
2.95
5.85
1.52
1.80
4.03
1.64
4.72
1.50
3.94
1.87
KDE
3.00 + 2.01
2.93 4,49
2.27 6.51
4.00
1.84
4,40
1.68
5.01
1.97
4.40
1.78
4.18
1 1.96
LODA
3.44 + 1.96
66
2.71
6.32
2.30
4.22
1.94
4,36
4.47
2.17
4.53
2.09
4.99
1.87
LOF
2.22 + 1.38
3.43
2.67
7.74
0.67
3.47
1.73
3.63
1.40
5.95
1.17
5.35
1.57
4.22
1.38
OCSVM
2.82 1 1.71
2.63 3.83
7.30
1.50
4.23
2.13
4.35
1.78
5.34
1.65
4.32
1.95
3.80
1.72
AE
2.31
+: 1.38
4.05
2.78
5.85
+
2.41
3.66
2.12
4.69
1.86
5.27
1.68
4.84
1.74
5.34
+: 1.92
COPOD
2.24 1 1.49
3.72
2.70
4.62
2.17
3.98
2.34
4.89
1.87
5,26
1.58
5.57
1.50
5.72
1: 2.10
FCOD
2.18 +: 1.31
3.92
2.75
4.22
2.22
3.93
2.33
5,30
1.82
4.91
1.69
5.48
1.38
6.06
1.94
HBOS
1.98 +: 1.37
3.95
2.88
5.30
2.46
4.18
118+200 2.01
4.63
1.83
5.36
1.68
5.41
1.46
5.18
1.93
FOR
2.01 +: 1.46
4.10
2.67
4.71
2.26
2.05
4.98
1.96
5,35
1.60
5.29
5.60
INNE
1.70 +: 1.25
3.75
+ 2.82
4.17
2.42
6.02
1.44
5.57
1.78
4.56
1.36
5.36
1.38
4.87
2.08
KDE
2.22 1: 1.35
4.24
2.73
5.49
2.55
3.62
2.00
4.71
1.95
5.60
1.50
4.79
1.86
5,34
1.87
KNN
1: 1.23
3.88
2.82
5.49
2.39
3.91
1.86
4.29
1.86
5.56
1.71
5.19
1.63
5.69
1.70
LODA
2.58 + 1.60
3.59
+: 2,36
4.34
2.58
4.26
2.17
4.93
1.98
5.33
1,98
5.02
1.98
5.94
1.75
3.26
5.53
OCSVM
2.15 + 1.19
4.18
2.77
5.73
3.62
2.20
4.59
1.88
5.39
1.59
5.05
9.92
5.31
1.67
19


Reviews:
[{"review_id": "yv9RoF2q9v", "reviewer": "Reviewer_6n88", "summary": "This paper proposes an approach to perform learning to reject for anomaly detection in a completely unsupervised manner. The authors make three major contributions: (1) a novel theoretical analysis of a stability metric for anomaly detection, (2) a mechanism for designing an ambiguity rejection mechanism without any labeled data that offers strong guarantees, and (3) an evaluation of the proposed approach on an extensive set of unsupervised detectors and benchmark datasets. The authors show that their method outperforms several adapted baselines based on other unsupervised metrics and that their theoretical results hold in practice.", "questions": "1. Is there any other method to estimate the detector's stability, in addition to EXCEED? If so, how does EXCEED outperform other methods?\n2. In Definition 3.7, the cost function is defined as a simple addition. What if the cost function is of a more complex form?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper proposes a novel approach to perform ambiguity rejection for anomaly detection in a completely unsupervised manner. The authors provide a novel theoretical analysis of a stability metric for anomaly detection and show that it has several previously unknown properties that are of great importance in the context of learning to reject.\n\nQuality: The paper provides a thorough theoretical analysis of the proposed approach and demonstrates its effectiveness through experiments on an extensive set of unsupervised detectors and benchmark datasets. The authors also provide strong guarantees for their proposed method.\n\nClarity: The paper is well-written and easy to follow. The authors provide clear explanations of the proposed approach and the theoretical analysis.\n\nSignificance: The proposed approach addresses the challenge of uncertainty in traditional anomaly detectors and provides a solution through Learning to Reject. The authors show that their method outperforms several adapted baselines based on other unsupervised metrics and that their theoretical results hold in practice. The proposed approach has significant implications for anomaly detection in various domains.", "weaknesses": "The author may provide more intuition on how EXCEED works to estimate the stability.\nThe paper could benefit from a more detailed discussion of the limitations of the proposed approach and potential directions for future research. \nWhile the paper provides a thorough theoretical analysis of the proposed approach, it could benefit from more detailed explanations of the experimental setup and results. Specifically, the paper could provide more information on the hyperparameters used in the experiments and how they were selected, as well as more detailed comparisons with other state-of-the-art methods.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 6n88,\n\nThanks for the **constructive feedback**. We will include a **more thorough overview** of how ExCeeD works in the final version of the paper to improve the readability of the paper. Lines 268 - 273 state that all the **hyperparameters** are set to their **default value** because we are operating in an unsupervised setting, meaning we **do not have labels** to tune them. Finally, here are our responses to your main concerns:\n\n1.  [**Measuring Stability**] Apart from [47] which is included as a baseline in the paper, we are not aware of other methods that quantify a detector’s stability;\n\n2.  [**Cost function**] Setting a proper cost function requires domain knowledge. In the learning to reject literature, most works use an additive cost function (see, e.g., the survey in [25]). Exploring other cost functions is a relevant area and if you are aware of other cost functions used in the literature, please let us know and we will include it in the final version of the paper.\n\n3.  [**State-of-the-art rejection methods**] We would be happy to know what other methods the reviewer is referring to. To the best of our knowledge, there are no other algorithms for setting a rejection threshold without labels.\n"}, {"review_id": "JCifgGk3ZV", "reviewer": "Reviewer_3a9y", "summary": "- The authors proposed a selective predictor (learning to reject) for fully unsupervised setting in anomaly detection problems given an unsupervised anomaly detector.\n- The proposed method is based on the theoretical supports and the threshold can be selected without any labeled data.\n- The experimental results show that the proposed method can significantly reduce the cost of selective prediction.", "questions": "1. EXCEED metric\n- I can understand the brief concepts of the EXCEED metric.\n- However, it would be good to further explain how the training data is perturbed. \n- Also, it would be good to add additional explanations of Equation (1) - like the motivations of this equation.\n\n2. Problem settings\n- So, here, do we assume that we have an access to the contamination ratio (gamma)?\n- If yes, can we extend this method without access to the contamination ratio?\n\n3. With some labels\n- As discussed in Related works, if we have some labels, we can easily optimize the rejection function using two ways that the authors explained.\n- In that case, can we analyze how many samples do we need to have similar performance with the proposed unsupervised method?", "limitations": "Limitations are clearly stated.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed method is grounded on the theoretical supports that could be beneficial on generalization.\n- The experimental sections are extensive and multiple ablation studies show its superiority across various settings.", "weaknesses": "- It seems like the proposed method is only applicable when the anomaly ratio is given. In some cases, anomaly ratio itself is not provided.\n- It would be great if the authors can provide more extensive experiments when we have some labeled data in comparison to the baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 3a9y,\n\nThanks for the **very specific and helpful feedback**. We will address all your comments in the final version of the paper. Here is our response to your questions:\n\n1.  ExCeeD uses a Bayesian formulation that simulates **bootstrapping** the training set as a form of perturbation. Equation 1 computes the confidence for a test score $s$ in two parts. **First**, it computes $\\psi_n$ as the proportion of training scores lower than $s$. **Second**, it quantifies the probability that the model predicts anomaly for $s$ by estimating the proportion of times that $\\psi_n > 1-\\gamma$ (i.e., $s$ is in the top $\\gamma$% of training scores) when simulating the bootstrapping of the training set.\n\n2.  Yes, we assume that the **contamination ratio is given**, as stated in line 98. However, approaches exist to estimate it from a given dataset. This can even be done from a fully unlabeled dataset; see, for example, cite 50 in the paper. \n\n3.  Experiment Q5 (lines 327-333) shows that our approach with a fully labeled training set would **only reduce the test cost by $0.6$%**, on average. We agree that analyzing on a theoretical level how many samples are needed to obtain a performance that is similar to the unsupervised one is interesting. This is certainly a good direction for **future work**, especially for unsupervised settings, because it would shed light on the number of labels needed to **justify the improvement**.\n"}, {"review_id": "ddbqrJIbjM", "reviewer": "Reviewer_R9xH", "summary": "This paper suggests applying the stability metric computed by EXCEED for anomaly detection. The authors present theoretical findings regarding this metric, including the test rejection rate, as well as upper bounds for both the rejection rate and the expected prediction cost. Furthermore, comprehensive experiments are conducted to validate the effectiveness of the proposed method.", "questions": "Please refer to [Weakness].", "limitations": "Please refer to [Weakness].", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The presentation of the paper is clear, and the proposed method is simple but effective.\n2. This paper offers a theoretical analysis of EXCEED, deriving the upper bounds for both the rejection rate and the expected prediction cost.\n3. The effectiveness of the proposed method and the validity of the theoretical results are confirmed through comprehensive experiments.", "weaknesses": "1. The methods compared in Figure 1 appear to be significantly dated. It would be valuable if the paper could include additional results pertaining to recently proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer R9xH,\n\nWe appreciate your **positive review**. Our method is **anomaly detector-agnostic**, which means that it can be applied on top of any anomaly detector. We ran the experiments using $12$ anomaly detectors included in the most recent and largest experimental comparison [23], which include:\n\n-  Classical algorithms, like LOF and IForest, that are often used as baselines because they obtain competitive performance [65, 66, 67];\n\n-  More recent algorithms, like COPOD (2020), ECOD (2022). \n\nNote that cite [23] claims that **“none of the unsupervised methods is statistically better than the others”** and that **“some Deep Learning based unsupervised methods are surprisingly worse than shallow methods”**. \n\nFurthermore, out of $34$ datasets, $15$ datasets have at least one detector with $AUC > 0.90$, and $12$ datasets have at least one detector with $AUC > 0.7$. Thus this seems like a **reasonably extensive benchmark**. \n\nFinally, from the review, it is unclear what other anomaly detection methods the reviewer considers to be state-of-the-art. \n\n----\n\n[65] Qiu Chen, et al. \"Neural transformation learning for deep anomaly detection beyond images.\" International Conference on Machine Learning. PMLR, 2021.\n\n[66] Han, Songqiao, et al. \"Adbench: Anomaly detection benchmark.\" Advances in Neural Information Processing Systems 35 (2022): 32142-32159.\n\n[67] Cai, Jinyu, and Jicong Fan. \"Perturbation learning based anomaly detection.\" Advances in Neural Information Processing Systems 35 (2022).\n"}, {"review_id": "Zhi6dkegJc", "reviewer": "Reviewer_Xnvu", "summary": "This paper presents a rejection scheme for the task of unsupervised anomaly detection.  Learning to reject enables a predictor to withhold from making a prediction; this paradigm is more common in unsupervised learning. Here, the authors extend the rejection idea to the unsupervised anomaly detection task.  The idea is to reject samples based on a stability metric; namely, of the prediction is unstable to small changes in the feature space, the prediction is rejected. This type of stability metric was recently proposed and is termed EXCEED. The authors present a theoretical analysis of the EXCEED metric and derive upper bounds for the test rejection rate and expected prediction cost. The new scheme is evaluated for several anomaly detectors on real datasets and outperforms other rejection schemes.", "questions": "The analysis assumes that $\\gamma$ is known, in practice how can you gain access to this value? Is there a way to overcome this limitation?\nPlease expand on the ECEED metric, equation 1.\nA comma is missing after this equation.\nHow is the cost influenced when changing \\lambda? It is not clear from the text what do you do with this value.\nWhy are you not mentioning the subsampling in the main text? Is it so computationally demanding to evaluate the method on large datasets?\n", "limitations": "Limitations are discussed in the last section, I would however add information on the cases in which rejection increases the cost, for example using statistic across datasets. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, and easy to follow.  Overall, the presentation is scientifically sound. The problem of unsupervised anomaly detection is extremely challenging and important; the paper presents a rejection scheme that could improve trust in commonly used detectors. The idea of using stability and specifically the EXCEED metric, makes sense. The theoretical analysis strengthens the work and offers bounds on the expected values of the presented scheme. The empirical evidence presented in the paper is promising and demonstrates the merits of the method. ", "weaknesses": "Background on the EXCEED method is missing; adding more information on this metric could help the reader. Some recently proposed NN anomaly detectors are missing from the evaluation, for example:\n[1] Qiu, Chen, et al. \"Neural transformation learning for deep anomaly detection beyond images.\" International Conference on Machine Learning. PMLR, 2021.\n[2] Shenkar, T., & Wolf, L. (2021, October). Anomaly detection for tabular data with internal contrastive learning. In International Conference on Learning Representations.\n[3] Lindenbaum, et al. (2021). Probabilistic robust autoencoders for outlier detection. arXiv preprint arXiv:2110.00494.\nThere are many other NN that could be included, I think some NN baselines should be considered. \nThe description of the experiments conducted is too brief; it would be good if the authors could expand on the implementation and evaluation protocol. For example, what is $\\lambda$ in all experiments? Or how is it tuned?\n\nSample size is limited in the evaluation to 20K.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Xnvu,\n\nThanks for your **positive and constructive feedback**. Here are our responses:\n\n1.  [**Experimental setup**] Section 5.1 clarifies our experimental setup, including **how we set hyperparameters**. If you can let us know specific things that are unclear, we will add them. Also, we have submitted and will release all information (code, data repository, …) to replicate the experiments. \n\n2.  [**Setting the decision threshold $\\lambda$**] As stated in lines 71-73, the decision threshold $\\lambda$ is set such that $\\gamma \\times n$ scores are $\\ge \\lambda$, where $\\gamma$ is the dataset’s contamination factor and $n$ is the training set size. Because we are operating in a **fully unsupervised** setting, we do not consider $\\lambda$ as a hyperparameter to tune [59] but we set it the same way as in other papers [see for example cites 23,49,50,51]. Consequently, we do not analyze how the test cost varies when changing $\\lambda$.\n\n3.  [**$\\gamma$ is known**] We assume that the contamination factor $\\gamma$ is given, as stated in line 98. However, approaches exist to **estimate it** from a given dataset. This can even be done from a **fully unlabeled** dataset; see for example cite 50 in the paper.\n\n4.  [**References**] We will discuss the references in the final version of the paper and will do our best to **include as many as possible** in the experimental analysis.\n\n5.  [**ExCeeD**] We will provide further details about exceed in the final version of the paper. Also, see our response to reviewer 3a9y.\n\n6.  [**Computational cost**] Limiting the dataset size to $20K$ by taking a subsample is an experimental detail that has the unique goal of **saving computational effort**. In fact, running all $2040$ experiments with the size limit requires more than a week. Note that, as shown in Q3, our method has **low computational cost**, as opposed to *Stability*, which uses an expensive internal optimization, and *Ens*, which uses an ensemble of models.\n"}, {"review_id": "6OasXC5vEN", "reviewer": "Reviewer_imnX", "summary": "The authors address the topic of rejection of samples in an unsupervised anomaly detection setup. Their approach focuses on determining a constant rejection threshold, which allows the detector to reject examples with high uncertainty. The new proposed method introduces this rejection threshold based on a confidence score given by another existing model (ExCeed). The authors provide theoretical analyses as well as empirical experiments and show that it is possible to set a constant rejection threshold with strong theoretical guarantees. \n", "questions": "None", "limitations": "Difficult write-up.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper provides a good structure but also requires some pre-knowledge in this area to be able to follow the presented thoughts e. g. research questions are later connected according to sections. \n- In-depth theoretical methodology as well as empirical evaluation.\n- Detailed overview of single results in the supplement is given.", "weaknesses": "- It was not always straightforward to follow the paper, especially because a lot of variables are introduced but are defined much later in the paper (e.g. t_1(n, \\gamma, T) (line 131) and  \\gamma = \\mathds{P}(Y = 1) (line 199)). Starting with a more explanatory part would let the reader build an intuition about which factors are important to calculate the rejection threshold. With all the factors in mind, it will get easier to follow the complex theoretical contribution. \n- in line 135 \\epsilon is defined as 1 - 2e^(-T). In the formula between lines 123 and 124, the rejection threshold is defined as \\mathcal{T} = 1 - \\epsilon = 1 - 2e^(-T), which would result in \\epsilon = 2e^(-T).\n\nMinor comments: \n- \"Our approach is called **RejEx** (Rejecting via ExCeed)(line 110)\n- In Theorem 3.8 it is refed to Theorem 3.5 for the definition of g. Theorem 3.5, however, refers to Theorem 3.4; It would be easier to directly refer to Theorem 3.4\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer imnX,\n\nWe appreciate your **positive feedback**, and that you eventually were able to **follow our theoretical contribution**. In the revised version, we will address your points about the notation and try to give some **more intuitions prior to the theoretical sections**.\n\nWe will fix the typos you correctly pointed out: line 135 should have $2e^{-T}$ instead of $1-2e^{-T}$, we missed *RejEx* in line 110, and Theorem 3.8 should refer to Def. 3.4 instead of Theorem 3.5.\n"}]

Author rebuttal:

Meta-review: The authors consider the problem learning a rejector to discard anomalous samples *without* labeled data. The main idea is to apply a threshold to a confidence metric EXCEED proposed by prior work [48]. They offer supporting theory and showcase the efficacy of their approach in experiments.

Overall, the reviewers lean towards accepting the paper. I do however have a couple of important comments about the presentation, which the authors are strongly encouraged to address:
- The efficacy of the proposed method seems to rely on a *strong* modeling assumption that is **not stated** explicitly in the main paper (but mentioned in the prior work [48]). The authors assume a specific dependence between the base scoring function S and the label Y. More concretely, it is assumed that the label $Y|S=t$ follows a Bernoulli distribution with parameter $p_t = P(S \leq t)$. This assumption tying the label $Y$ to the scorer $S$ seems crucial to be able to construct a rejector *without labeled data*. It is important that this assumption is made very clear in the paper and its consequence in designing the rejector be discussed.
- The theoretical analysis appears to be a *finite-sample counterpart* to the asymptotic analysis already provided by the prior work [48]. Having made the above assumption tying the label $Y$ to the scorer $S$, the theoretical results seem to follow from application of *standard concentration inequalities*. Given that the theory is presented as a key contribution, it is important that the authors   highlight the technical difficulties in proving these results.

We urge the authors to address these comments in the camera-ready paper.
Decision: Accept (poster)