Unsupervised Model Selection for Time Series Anomaly Detection
Authors: Mononito Goswami
Cristian Ignacio Challu
Laurent Callot
Lenon Minorics
Andrey Kan
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Time Series
Anomaly Detection
Model Selection
Unsupervised Learning
Rank Aggregation

Abstract: Anomaly detection in time-series has a wide range of practical applications. While numerous anomaly detection methods have been proposed in the literature, a recent survey concluded that no single method is the most accurate across various datasets. To make matters worse, anomaly labels are scarce and rarely available in practice. The practical problem of selecting the most accurate model for a given dataset without labels has received little attention in the literature. This paper answers this question \textit{i.e.} Given an unlabeled dataset and a set of candidate anomaly detectors, how can we select the most accurate model? To this end, we identify three classes of surrogate (unsupervised) metrics, namely, \textit{prediction error}, \textit{model centrality}, and \textit{performance on injected synthetic anomalies}, and show that some metrics are highly correlated with standard supervised anomaly detection performance metrics such as the $F_1$ score, but to varying degrees. We formulate metric combination with multiple imperfect surrogate metrics as a robust rank aggregation problem. We then provide theoretical justification behind the proposed approach. Large-scale experiments on multiple real-world datasets demonstrate that our proposed unsupervised approach is as effective as selecting the most accurate model based on partially labeled data.

Published as a conference paper at ICLR 2023
UNSUPERVISED MODEL SELECTION FOR TIME-SERIES ANOMALY DETECTION
Mononito Goswami & Cristian Challu"
Laurent Callot, Lenon Minories & Andrey Kan Amazon Research
Carnegie Mellon University
(mgoswami, ccha
ccha 1 Lu @cs. cmu edu
(1 (1ca 1 lot, avk an @ama ccom mi no cS$ ama zon de
ABSTRACT
Anomaly detection in time-series has wide range of practical applications. While numerous anomaly detection methods have been proposed in the literature, a re- cent survey concluded that single method is the most accurate across various datasets. To make matters worse, anomaly labels are scarce and rarely available practice. The practical problem of selecting the most accurate model for a given dataset without labels has received little attention in the literature. This paper an- swers this question i.e. Given an unlabeled dataset and set of candidate anomaly detectors, how can we select the most accurate model? To this end, we identify three classes of surrogate (unsupervised) metrics, namely, prediction error, model injected synthetic anomalies, and show that some
centrality, and performance metrics are highly correlated with standard supervised anomaly detection perfor- mance metrics such the Fi score, but to varying degrees. We formulate metric combination with multiple imperfect surrogate metrics as a robust rank aggrega- tion problem. We then provide theoretical justification behind the proposed ap- proach. Large-scale experiments on multiple real-world datasets demonstrate that our proposed unsupervised approach is effective as selecting the most accurate model based on partially labeled data.
INTRODUCTION
Anomaly detection in time-series data has gained considerable attention from the academic and industrial research communities due to the explosion the amount of data produced and the number of automated system requiring some form of monitoring. A large number of anomaly detection methods have been developed to solve this task (Schmidl et al., [022] Blazquez-Garcfa et al.) 2021), ranging from simple algorithms (Keogh et al.
2005 Ramaswamy al.) 2000) to complex deep- learning models (Xu et al., 2018 Challu et al., 2022). These models have sigmificant variance in
performance across datasets (Schmidl et al.J 2022] Paparrizos et al. 20226), and evaluating their actual performance real-world anomaly detection tasks is non-trivial, even when labeled datasets
are available (Wu& & Keogh (021).
Labels are seldom available for many, if not most, anomaly detection tasks. Labels are indications of which time points time-series are anomalous. The definition of an anomaly varies with the use case, but these definitions have in common that anomalies rare events. Hence, accumulating a sizable number of labeled anomalics typically requires reviewing a large portion a dataset by domain expert. This is an expensive, time-consuming, subjective, and thereby error-prone task which a considerable hurdle for labeling even a subset of data. Unsurprisingly, a large number of time-series anomaly detection methods unsupervised semi-supervised i.e. they do not require any anomaly labels during training and inference.
There is no single universally best method (Schmidl al. 2022 Paparrizos al. 2022b). Therefore is important to select the most accurate method for a given dataset without access to anomaly labels. The problem of unsupervised anomaly detection model selection has been overlooked in the literature, even though it is key problem in practical applications. Thus, we offer an answer to the
Work carried when the first authors were interns Amazon AWS AT Labs.

---

Published as a conference paper at ICLR 2023
Metrics on Test TS
M.
M,
Eins
M.
Scale
Anomelly
M,
RRA
M
M.
M
M.
Synchetic Anonaly Injection
Train TS
M,
NNN
Models
Model Centrality
Rankings
The Model Selection Workflow. We identify three classes of surrogate metrics of model quality (Sec.B) 3). and propose novel robust rank aggregation framework to combine multiple rank- ings from metrics (Sec.
Figure 1:
question: Given an unlabeled dataset and set of candidate models, how can we select the most accurate model?
Our approach is based on computing "surrogate" metrics that correlate with model performance yet do not require anomaly labels, followed by aggregating model ranks induced by these metrics (Fig. D. Empirical evaluation on 10 real-world datasets spanning diverse domains such as medicine, sports, etc. shows that our approach can perform unsupervised model selection as efficiently as selection based on labeling subset of data.
In summary, our contributions are as follows:
To the best of our knowledge, propose of the first methods for unsupervised lection of anomaly detection models on time-serics data. To this end, we identify intuitive and effective unsupervised metrics for model performance. Prior work has used few of these unsupervised metrics for problems other than time-series anomaly detection model selection.
We propose novel robust rank aggregation method for combining multiple surrogate met- rics into single model selection criterion. We show that our approach performs on par with selection based labeling subset of data.
We conduct large-scale experiments over 275 diverse time-series. spanning gamut of domains such as medicine, entomology, etc. with 5 popular and widely-used anomaly detection models, each with 1 to 4 hyper-parameter combinations, resulting in over 5,000 trained models. Upon acceptance, we will make our code publicly available.
In the next section, we formalize the model selection problem. We then describe the surrogate metric classes Sec. 3. and present our rank aggregation method in Sec. 4 Our empirical evaluation is
described in Sec. 5 Finally, summarize related work in Sec. and conclude in Sec. 7
PRELIMINARIES & THE MODEL SELECTION PROBLEM
Let (xt, Vo denote multivariate time-series (TS) with observations (#1...., Fr), æ, E Rd and anomaly labels (y1...., yr), ). Yt E {0, 1}. where yt = indicates that the observation I; is an anomaly. The labels are only used for evaluating selection approaches, but not for the model selection procedure itself.
Next, let M (A denote of N candidate anomaly detection models. Each model A, is a tuple (detector, hhpphh-ppppaa r ramet rameters) ers), i.e., a combination of an anomaly detection method (e.g. LSTM-VAE (Park al. 2018) and fully specified hyper-parameter configuration (e.g. for LSTM-VAE, hidden www.iize..... 128, num.layers-2, ...).
Here, only consider models that do require anomaly labels for training. Some models still require unlabeled time-series training data. We therefore, consider train/test split {ær {
2

---

Published as a conference paper at ICLR 2023
{ H? where the former is used if model requires training (without labels). In our notation,
A, denotes a trained model.
We assume that trained model A, when applied to observations { produces anomaly scores {si)t=tes st Rzo. We assume that higher anomaly score indicates that the observation is more likely to be an anomaly. However, we do not assume that the scores correspond to likelihoods of any particular statistical model or that the scores are comparable across models.
Model performance perforrann (((st)=-11 {vr ) ). such as the Area under Precision Recall curve or best F1 score, commonly used in literature. We discuss the choice of the quality metric in the next section.
or, equivalently, quality of the scores can be measured using supervised metric
In general, rather than considering a single semesserie, we will be performing model selection for set of I, time-series with observations indexes time-series. Let Xuain. Keat and Ves denote the train and test portions of observations, and the test portion of labels, respectively. We are now ready to introduce the following problem.
{(ar]
) and labels y = {[ve { where
Problem Unsupervised Time-series Anomaly Detection Model Selection. Given observations Xeea and a set of models M = W trained using Xuain select model that maximizes the anomaly detection quality metric ((Ai(Nest):
The selection procedure cannot use labels.
2.1 MEASURING ANOMALY DETECTION MODEL PERFORMANCE
Anomaly Detection can be viewed a binary classification problem where each time point is classi- fied as an anomaly normal observation. Hence, the performance of model A; can be measured using standard precision and recall metrics. However, these metrics ignore the sequential nature of time-series; thus, time-series anomaly detection is usually evaluated using adjusted versions of precision and recall (Paparrizos et al.] 2022a). We adopt widely used adjusted versions of precision and recall (Xu al.] 2018,] Challu al. 2022 (Shen et al., 2020; Su et al. 2019] Carmona al.) 2021]. These metrics treat time points as independent samples, except when an anomaly lasts for several consecutive time points. In this case, detecting any of these points is treated as if all points inside the anomalous segment were detected.
Adjusted precision and recall can be summarized in metric called adjusted Fi score, which is the harmonic mean of the two. The adjusted P1 score depends on the choice of a decision thresh- old on anomaly scores. In line with several recent studies, we consider threshold selection as a
problem orthogonal to our problem (Schmidl et al. [022] Laptev et al. 2015 Blazquez-Garciaa
al. 2021 Rebjock et al. 202T Paparrizos et al. 2022a b) and therefore, consider metries that summarize model performance across all possible thresholds. Common metrics include area under the precision-recall curve and best Fi (maximum Fi over all possible thresholds). Like Xu et al. 2018), we found strong correlation between the two (App.[A.1]) We also found best Fi to have statistically significant positive correlation with volume under the surface ROC curve, a recently proposed robust evaluation metric (App. AA.10). Thus, in the remainder of the paper, restrict our analysis to identifying models with the highest adjusted best F, score (i.e. Q is adjusted best F)).
3
SURROGATE METRICS OF MODEL PERFORMANCE
The problem of unsupervised model selection is often viewed as finding an unsupervised metric which correlates well with supervised metrics of interest (Ma et al., 2021; Goix 2016 Lin et al. Duan et al. 2019). Each unsupervised metric serves
noisy measure of "model good- ness" and reduces the problem of picking the best performing model according to the metric. We identified three classes of imperfect metries that closely align with expert intuition in predicting the performance of time-series anomaly detection models. Our metrics are unsupervised because they do not require anomaly labels. However, some metrics such as Fi score on synthetic anomalies typically used for supervised evaluation. To avoid confusion we use term surrogate for our metrics. Below we elaborate on each class of surrogate metrics, starting with an intuition behind each class.
2020
If model can forecast reconstruct time-series well it must also be good anomaly detector A large number of anomaly detection methods are based on forecasting or re- construction (Schmidl et al. 2022). and for such models, we can compute forecasting recon-
Prediction Error
3

---

Published as a conference paper at ICLR 2023
struction enror without anomaly labels. We collectively call these prediction error metrics and con- sider a common set of statistics, such as mean absolute error, mean squared error, mean absolute percentage error, symmetric mean absolute percentage eπror, and the likelihood of observations. For multivariate time-series, we average each metric across all the variables. For example, given series of observations {Ir ) and their predictions { mean squared error is defined as MSE - + E'' xt S.) ),)². In the interest of space, we refer the reader to a textbook ge Hynd- man & Athanasopoulos (2018) for definitions of other metrics. Prior work on time-series anomaly detection (Saganowski & Andrysiak] 2020; Laptev et al.] [215]] Kuang et al. (022)) used forecast- ing error to select between some classes of models. Prediction metrics
not perfect for model
selection because the time-series can contain anomalies. Low prediction errors are desirable for all points except anomalies, but we do not know where anomalies are without labels. While prediction metrics can only be computed for anomaly detection methods based on time-series forecasting or reconstruction, the next two classes of metrics apply to any anomaly detection method.
Synthetic Anomaly Injection A good anomaly detection model will perform well on data with syn- thetically injected anomalies. Some studies have previously explored using synthetic anomaly injec- tion to train anomaly detection models (Carmona et al. (02T). Here, we extend this line of research by systematically evaluating model selection capability after injecting different kinds of anomalies. Given an input time-series without anomaly labels, we ran- domly inject an anomaly of a particular type. The location of the injected anomaly is then treated as a sseeudo-ppositive label, while the rest of the time points are treated as (yseudo-Jnegativnn label. We then select a model that achieves the best adjusted Fi score with respect to pseudo-labels. Instead of relying on complex deep generative models [Wen) ett al., 2020) devise simple and efficient yet ef- fective procedures to inject anomalies of previously described types (Schmidl et al.) 2022. Wu & Keogh of anomaly injection approaches to Appendix AA.5 Model selection based on anomaly injection
Splies evemedy
aramely
AAAAANN
WWWAAAN Maw
Acrrage araray
A CUUARAN
www.Mm
Figure 2: Different kinds of synthetic anoma- lies. We inject 9 different types of syn- thetic anomalies randomly, one at time, across multiple copies of the original time- series. The is original time-series be- fore anomalies are injected, is the injected anomaly and the solid is the time-series af- anomaly injection.
2021) shown in Fig. [ We defer the details
might not be perfect because (i) real anomalies might be of different type compared to injected
ones, and (ii) there may already be anomalies for which our pseudo-labels will be negative.
Model Centrality There is only one ground truth, thus models close to ground truth are close to each other. Hence, the most "central" model is the best one. Centrality- metrics have seen recent success in unsupervised model selection for disentangled representation learning (Lin) let al. 2020; Duan et al. 2019) and anomaly detection (Ma et al., 2021). To adapt this approach leverage the scores from the anomaly detection models to define notion of model proximity. Anomaly scores of different models are not directly comparable. However, since anomaly detection is performed by thresholding the scores, we can consider ranking of time points by their anomaly scores. Let ( (i) denote the rank of time point i according to the scores from model k. We define the distance between models A and A as the Kendall's 7 distance, which is the number of pairwise disagreements:
to time-series,
O)) = Σ (())))))))))))))))))))))))))))))
< 0}
(1)
Next, we measure model centrality as the average distance to its K nearest neighbors, where K is parameter. This metric favors models which close to their nearest neighbors. The centrality- based approach is imperfect, because "bad" models might produce similar results and form a cluster.
Each metric, while imperfect, is predictive of anomaly detection performance but to varying extent as we show in Sec. [5] Access to multiple noisy metrics raises a natural question: How can we combine multiple imperfect metrics to improve model selection performance?
4

---

Published as a conference paper at ICLR 2023
4 ROBUST RANK AGGREGATION
Many studies have explored the benefits of combining multiple sources of noisy information to reduce error in different areas of machine learning such crowd-sourcing (Dawid & Skene 1979) and programmatic weak supervision (Ratner et al. 2016 Goswami et al. Dey et al. 2022 Gao
et al., 2022; Zhang al. 2022a). Each of our surrogate metries induces a (noisy) model ranking.
Thus two natural questions arise in the context of our work: (1) How do we reliably combine multiple model rankings? (2) Does aggregating multiple rankings help in model selection?
4.1 APPROACHING MODEL SELECTION AS A RANK AGGREGATION PROBLEM
= = ...,,..... denote the universe of elements and SN be the set of permutations [N] For a E SN. let (i) denote the rank element and o (j) denote the element at rank j. Then the rank aggregation problem is follows.
Problem 2. Rank Aggregation. Given a collection of M permutations 01,-.. OM E SN of N items, find a² SN that best summarizes these permulations according to some objective C(a",01,"" ..M)
In our context, the N items correspond to the N candidate anomaly detection models, M corre- sponds to the number of surrogate metrics, a² is the best summary ranking of models, and o o1=1(1) the predicted best model
(1)
The problem of rank aggregation has been extensively studied in social choice, bio-informatics and machine learning literature. Here, we consider Kemeny rank aggregation which involves choosing median ranking (Korba et al. 2017).
distance on the set of rankings and finding a barycentric Specifically, the rank aggregation problem is known as the Kemeny- Young problem if the aggrega- tion objective is defined as C = M E (a", (.)) where d, is the Kendall's 7 distance (Fq.
Kemeny aggregation has been shown satisfy many desirable properties, but it is NP-hard even with as few as 4 rankings (Dwork et al. (2001). To this end, we consider an efficient approximate solution using the Borda method (Borda) 1784) in which each item (model) receives points from each ranking (surrogate metric). For example, if model is ranked r-th by surrogate metric, it receives (N r) points from that metric. The models are then ranked in descending order of total points received from all metrics.
Suppose that we have several surrogate metrics for ranking anomaly detection models. Why would it be beneficial to aggregate the rankings induced by these metrics? The following theorem provides an insight into the benefit of Borda rank aggregation.
Consider two arbitrary models i and with (unknown) ground truth rankings o a"(i) and o "i))- Without the loss of generality, assume a (i) < o (f), i.e., model is better. Next, let's view each surrogate metrie k = ,,...,. MM random variable P4 taking values in permutations SN, such that (1) E [N] denotes the rank of item i. We apply Borda rank aggregation on realizations of these random variables. Theorem states that, under certain assumptions, the probability of Borda ranking making a mistake (i.e., placing model i lower than j) is upper bounded in a way such that increasing M decreases this bound. In appendix 14 empirically show that model selection performance improves as we increase the number of surrogate metrics (rankings).
Theorem 1. Assume that Qs 's are pairwise independent, and that (() < P&())) > for any arbitrary models and j. i.e, each surrogate metric is better than random. Then the probability that
Borda aggregation makes a mistake in ranking items and j is at most 2 exp fixed c.
(-Me Me² ). for some
The proof of the theorem is given in Appendix A.8 We do not assume that Ω4 are identically distributed, but only that 2 's are pairwise independent. We emphasize that the notion of indepen- dence of 2g as random variables is different from rank correlation between realizations of these variables (i.e., permutations). For example, two permutations drawn independently from a Mallow's 'ss distribution can have high Kendall's coefficient (rank correlation). Therefore, our assumption of
We use terms "ranking" and "permutation" as synonyms. The subtle difference is that in a ranking multiple models receive the same rank. Where necessary, we break ties uniformly random.
5

---

Published as a conference paper at ICLR 2023
independence, commonly adopted in theoretical analysis (Ratner et al. 2016), does not contradict our observation of high rank correlation between surrogate metrics.
The Borda method weighs all surrogate metrics equally. However, our experience and theoretical analysis suggest that focusing only on "good" metrics can improve performance after aggregation (see Sec. Jaadd Corollary [ But how do identify "good" ranks without access to anomaly labels?
4.2 EMPIRICAL INFLUENCE AND ROBUST RANK AGGREGATION
Since we do not have access to anomaly labels, we introduce an intuitive unsupervised way to iden- tify "good" or "reliable" rankings based on the notion of empirical influence. Empirical influence functions have been previously used to detect influential cases in regression (Cook & Weisberg, 1980). Given a collection of M rankings S {or,.... ..M ). let Borda(S) denote the aggregate ranking from the Borda method. Then for some or S, empirical influence (I, S) measures the impact of o, the Borda solution.
LAI
El(a;, = ((S) ((S (1))),),, where S(A)
1
Σ d (Borda(AA, o.)
(2)
A
Under the assumption that majority of rankings good, EI is likely to identify bad rankings as ones with high positive EI. This is intuitive since removing bad ranking results in larger decrease in the objective S(S \ {a In appendix A.9 show that under idealized settings, empirical influence can identify bad rankings.
We cluster all rankings based their EI using two-component single-linkage agglomerative clus- tering (Murtagh & Contreras] 2012). discard all rankings from the "bad" cluster, and apply Borda aggregation to the remaining ones. To further improve ranking performance of aggregated rank, especially at the top, we only consider models at the top-k ranks, setting the positions of the rest of the models N (Fagin et al., 2003). See Appendix A.7.1 for details. We collectively refer these variations as Robust Borda rank aggregation.
EVALUATION RESULTS
5.1
DATASETS
We carry out experiments two popular and widely used real-world collections with diverse time- series and anomalies:
UCR Anomaly Archive (UCR) (Wu & Keogh, 2021 Wu and Keogh recently found flaws in many commonly used benchmarks for anomaly detection tasks. They introduced the UCR time-series Anomaly Archive, collection of 250 diverse univariate time-series of varying lengths spanning domains such as medicine, sports, entomology, and space science, with natural as well as realistic synthetic anomalies overcoming the pitfalls of previous benchmarks. Given the heterogeneity of included seriss, we split UCR into subsets by domain, (1) Acceleration, (2) Air Temperature, (3) Arterial Blood Pressure, ABP, (4) Electrical Penetration Graph, EPG, (5) Electrocardiogram, FCG, (6) Gait, (7) NASA, (8) Power Demand, and (9) Respiration, RESP. We will refer to each of these subsets separate dataset.
Server Machine Dataset (SMD) (Su al. 2019) SMD comprises of multivariate time-series with 38 features from 28 server machines collected from large internet company over period of 5 weeks. Each entity includes common metrics such as CPU load, memory and network usage etc. for server machine. Both train and test sets contain around 50,000 timestamps with 5% anomalous cases. While there has been some criticism of this dataset (Wu & Kcogh| (021). we use SMD due to its multivariate nature and the variety it brings that on visually inspecting the SMD, we found most of the anomaly labels to be accurate, much like (Challu al. 2022).
evaluation along with UCR. We emphasize
We refer to SMD as a single dataset, and thus in our evaluation consider datasets (9 from UCR SMD).

---

Published as a conference paper at ICLR 2023
5.2 MODEL SET
There are over a hundred unique time-series anomaly detection algorithms developed using wide variety of approaches. For our experiments, we implemented representative subset of popular methods (Table[[), across two different learning types (unsupervised and semi-superrvsed) and three different method families (forecasting, reconstruction and distance-basee (Schmidl et al. 2022) We defer brief descriptions of models to Appendix A.6
We created a pool of 3 k-NN Ra-
maswamy et al.) 2000). 4 moving average,
DGHL (Challu et al., (002), 4 LSTM- VAE (Park al.] 2018) and 4 RNN (Chang et al. 2017) models by varying hyper- parameters for each model, for total 19 combinations. Finally, to efficiently train our models, we sub-sampled all time-series with T > 2560 by a factor of 10.
Moviing Bowanage
Stristiss
Unugerstent
Perrascing
A--00 Ramasgam st Nox7
Claskcal ML.
Semi Seni-openntal
Distasce
Eilatee
Deep Leaming
Semioupetteal
Fanzacing
Semposgenttt
Receestaction
Table 1: Models set and their properties. Detailed descriptions of model architectures and hyper- parameters can be found in Appendix A.6
5.3 EXPERIMENTAL SETUP
Evaluating model selection performance. We evaluate all model selection strategies based on the adjusted best F1 (Section 2 of the top-1 selected model. While there exist other popular measures to evaluate ranking algorithms such as Normalized Discounted Cumulative Gain (Wang et al.] (013). Mean Reciprocal Rank, etc., our evaluation metric is grounded in practice, since in setting only one model will be selected and used.
be used to select the best model for an individual time-series. Since anomalies are rare, a single time-series may contain only a few anomalies (e.g., one point anomaly in the case of some UCR time-series). This makes the evaluation of a selection strategy very noisy. To combat this issue, we perform model selection at the dataset level, i.e., we select single method for a given dataset.
Our approach
Baselines. As a baseline, we consider an approach in which we label a part of a dataset and select the best method based on these labels. We call this baseline "supervised selection" SS in short. This represents current practice, where a subset of data is labeled, and the best performing model used in the rest of the dataset. Specifically, we randomly partition each dataset into selection (20%) and evaluation (80%) sets. Each time-series in the dataset is assigned to one of these sets. The baseline method selects a model based on anomaly labels the selection set. Our surrogate metrics do not use the selection set. Instead, the surrogate metries are computed over the evaluation set without using the labels. For reference, we also report the expected performance when selecting a model from the model set at random ("random") and the performance of the actual best model ("oracle")).
Adjusted best Fi scores of the selected model (either by the bascline, surrogate metric or rank aggre- gation) are then reported. The entire experiment is repeated 5 times with random selection/evaluation splits.
Model selection strategies. We compare 17 individual surrogate metrics, including prediction error metrics, 9 synthetic anomaly injection metrics, 3 metrics of centrality (average distance to I, 3 and 5 nearest neighbors) (Sectior3); and proposed robust variations of Borda rank aggregation (see (.ppendi(A.7.22
In the preliminary round of evaluations we found of the anomaly injection metrics (scale, noise, cutoff, contextual and speedup) generally outperform other surrogate metrics across all datasets (Appendix (A.3). We apply rank aggregation only to these 5 metrics. While this subset of surrogate metrics was identified using labels, it does not appear to depend on the dataset. Thus, given new dataset without labels, we still propose to use rank aggregation over the same 5 surrogate metrics.
Pairwise-statistical tests. We carry out one-sided paired Wilcoxon signed rank tests at signifi- cance level of a 0.05 to identify significant performance differences between all pairs of model selection strategies and baselines on each dataset.
7

---

Published as a conference paper at ICLR 2023
Emer(VEE) Syntserc
Acdeentton
Syrthouc Kutoff
Enor (VSE)
A38
540
Figure 3: Performance of the top-1 selected model. Box plots of adjusted best F1 of the model selected by each metric or baseline across 5 unique combinations of the selection and evaluation sets. Orange () and blue () vertical lines represent the median and average performance of each metric or baseline, and the minimum influence metric (MTM), respectively. Each box plot is organized into 3 sections: performance of individual metries, Borda and its robust variations, and three baselines.
Experimentation environment. All models and model selection algorithms were trained and built using trrikit-leae 1.1.1 (Pedregosa et al. 2011). PyTorch 1.11.0 Paszke et al. (2019) along with Python 3.9.13. All our experiments were carried out on an AWS g 4x arge EC2 instance with with 16 Intel(R) Xeon(R) CPUs, 122 GiB RAM and 8 GiB GPU.
5.4 RESULTS AND DISCUSSION
subset of our results are shown in Figure and Table Here we provide results for model selec- tion using some of the individual surrogate metrics, as well as three variations of rank aggregation: Borda, robust Borda and special case of robust Borda where we select only one metric, the one that minimizes empirical influence, "minimum influence metric" or MIM (Section 4p. The complete set of results with all ranking metrics can be found in Appendix A.3
No single best surrogate metric. Our results show that there is no surrogate metric which consistently se-
Stanificant Wins ca
Sigulfisnt Lewau Oracle 2s
lects the best model on all datasets. For instance, can
Ranking Methodslloeelies
Randon
Randon
be seen in Figure 3 model selection based on predic- tion error (MSE) performs almost on par with the ora- cle on NASA, respiration (RESP) and server machine dataset (SMD), but worse than random model selection on the electrocardiogram (ECG), Arterial Blood Pres- sure (ABP) and acceleration datasetss
Eyn.
(huizel
Sym
(colocE)
Syn.
(deale)
syn.
(Avasage)
Roaysen Ronds
Boadu
25
Ocacin
5/a
Minimum Influence Metric perform on par with Su- pervised Selection. MIM is never significantly worse than SS and is in fact better on the air temperature (Temperature) dataset. Robust Borda on the other hand, is on par with SS on 8 datasets and significantly worse only on Temperature and SMD.
Table Results of pairwise- statissiat tests. On a total of n = 10 datasets, min- imum influence metric (MIM) and robust Borda have the fewest significant losses to oracle, and are considerably better than random model selection and Borda.
Robust variations of Borda outperform Borda. Aggregating via robust Borda and MIM are sig- nificantly better than Borda aggregation on 4 and 3 datasets, respectively. While MIM is never significantly worse than Borda, Robust Borda is inferior to Borda on SMD.
Robust variations of Borda minimizes losses to Oracle. From Table evident that MIM and Robust borda have fewer significant losses to the oracle in comparison to the 5 surrogate metrics used as their input, and compared to Ss. Thus, in general, robust aggregation is better than any randomly chosen individual surrogate metric. In terms of significant improvements over supervised and random selection, we found MIM to be a better alternative than Robust Borda.
8

---

Published as a conference paper at ICLR 2023
Synthetic anomaly injection metrics outperform other classes of metrics. We found synthetic anomaly injection to perform better than prediction error and centrality metrics (Appendix (A.3). Among the three surrogate classes, centrality metrics performed the worst, most likely due to highly correlated bad rankings.
Prior knowledge of anomalies might help identify good anomaly injection metrics. For in- stance, synthetic metries such as speedup and cutoff perform well on respiration data since these datasets are likely to have such anomalies. The slowing down of respiration rate is a common anomaly and indicative of sleep apnea Similarly, synthetic noise performs well on air temperature dataset, likely because time-series have noise anomalies to simulate the sudden failure of temper- ature sensors. We also hypothesize that the superior performance of synthetic noise might be due to the intrinsic noise and distortion added to 100 of the 250 UCR datasets (Wu & Keogh (021), thereby allowing the metric to choose models which are better suited to handle the noise. prac- tice, domain experts are aware of the type of anomalies that might exist in the data and using our anomaly injection methods; this prior knowledge can be effectively leveraged for model selection.
6 RELATED WORK
Time-series Anomaly Detection. The field has long and rich history with well over hundred pro- posed algorithms, differing in scope (e.g., multivariate vs univariate, unsupervised vs supervised), detection approach (e.g., forecasting, reconstruction. tree-based, etc.), etc. However, recent surveys have found that there is no single universally best method and the choice of the best method depends on the dataset (Schmidl et al. 2022 Blazquez-García et al. 202I).
Meta Learning and Model Selection. These approaches aim to identify the best model for a given dataset based on its characteristies such the number of classes, attributes, instances etc. Recently, Zhao et al.) (2021) explored the use of meta-learning to identify the best outlier detection algorithm on tabular datasets. For time-series datasets, both Ying al. (2020) Zhd/Zhag al.) (2021) also ap- proached model selection as meta-learning problem. All these studies rely on historical performance of models on subset of "meta-train" datasets to essentially learn a mapping from the characteristics of a dataset ("meea-fcattres") to model performance. These methods fail if anomaly labels are un- available for meta-train datasets, or if the meta-train datasets are not representative of test datasets. Both these assumptions are frequently violated in practice, thus limiting the utility of such methods. In our approach, we do not assume access similar datasets with anomaly labels.
Weak Supervision and Rank Aggregation. Our work draws on intuition from a large body of work on learning from weak or noisy labels since predictions of each surrogate metric have inherent noise and biases. We refer the reader to recent surveys on programmatic weak supervision, e.g- (Zhang et al.] 2022a). Since we are interested in ranking anomaly detection methods rather than inferring their exact performance numbers, rank aggregation is much more relevant paradigm for our problem setting.
An extended version of Related Work is provided in Appendix A.l
CONCLUSION
We consider the problem of unsupervised model selection for anomaly detection time-series. Our model selection approach is based on surrogate metrics which correlate with model performance to varying degrees but do not require anomaly labels. We identify three classes of surrogate metrics namely, prediction error, synthetic anomaly injection, and model centrality. We devise effective procedures to inject different kinds of synthetic anomalies and extend the idea of model centrality time-series. Next, we propose combine rankings from different metrics using a robust rank aggregation approach and provide theoretical justification for rank aggregation. Our evaluation using over 5000 trained models and 17 surrogate metrics shows that our proposed approach performs on par with selection based on partial data labeling. Future work might focus on other definitions of model centrality and include more synthetic anomalies types.
SSleep apnea is common and potentially serious health condition in which breathing repeatedly stops and starts (https: //www. nh1bi. nih, gow/hea 1 s appeea

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We provide an open-source implementations of model selection method and anomaly detection models at petetps:/ggttin cttple.ooooooooooeeo
com/
model seeee
All datasets used in this work are available in the public domain. Directions to download the Server Machine Dataset are available at hhtpps: http::///ghhhb whereas the UCR Anomaly Archive can be downloaded from https: wwwp cs ucr edu reamonn/time, Beamons/tiie__seres___dee 2018/
ACKNOWLEDGMENTS
We would like to thank Abishek Sankararaman, Anoop Deoras, Bariş Kurt, Christos Faloutsos, Kelvin Kan, and Peihong Jiang for valuable discussions about the problem statement and methods. We thank the anonymous reviewers and area chairs for helpful suggestions. The first author would also like thank AWS for travel grant attend the conference.
ETHICS STATEMENT
We propose an unsupervised method for model selection of time-series anomaly detection models. In this paper, we restrict ourselves to finding accurate anomaly detection models. The fairness of models chosen via unsupervised model selection is an open problem. While prevailing wisdom suggests a tension between the accuracy and fairness of models, recent work suggests otherwise. In fact. Wick et al. (2019) argue that under reasonable assumptions and certain definitions of fairness, accuracy and fairness are no longer in tension when selection and label bias are accounted for. We believe that an interesting direction of future work is extending our model selection problem and method to account for possibly competing objectives such as accuracy, fairness, inference time etc.
REFERENCES
Nicholas S Abend, Alexis A Topjian, and Sankey Williams. How much does it cost to identify critically ill child experiencing electrographic seizures? Journal of clinical neurophysiology: official publication of the American Elleciroencephalgggphhi Society, 32(3):577, 2015.
Nir Ailon. Aggregation of partial rankings, p-ratings and top-m lists. Algorithmica, 57(2):884-30,, 2010.
Kalousis Alexandros and Hilario Melanie. Model selection via meta-learning: comparative study. International Journal on Artificial Intelligence Tools, 10(04))525-555)) 2001.
Alnur Ali and Marina Meilä. Experiments with kemeny ranking: What works when? Mathematical Social Sciences, 64(1):28 2012.
Ane Bäizuuez-García Angel Conde, Usue Mori, and Jose A Lozano. A review on outlier/anomaly detection time series data. ACM Computing Surveys (CSUR), 54(3):1-33, 2021.
JC de Borda. Mémoire sur les élections au scrutin. Histoire de l'Academie Royale des Sciences pour 1781 (Paris, 1784), 1784.
Chris U Carmona, François-Xavee Xavier Aubet, Valentin Flunkert, and Jan Gasthaus. Neural contextual anomaly detection for time series. arXiv preprint arXiv:2107.07702. 2021.
Cristian I Challu, Peihong Jiang, Ying Nian Wu, and Laurent Callot. Deep generative model with hierarchical latent factors for time series anomaly detection. In International Conference on Artificial Intelligence and Statistics, pp. 1643-1654. PMLR, 2022.
Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Withrock, Mark A Hasegawa-lohnson, and Thomas S Huang. Dilated recurrent neural networks. Advances in neural information processing systems, 30, 2017.
Fabien Collas and Ekhine Irurozki. Concentric mixtures of mallows models for top-k rankings: sampling and identifiability. In International Conference on Machine Learning, pp. 2079-2088 PMLR, 2021.
10

---

Published as a conference paper at ICLR 2023
Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam. Improved bounds for computing kemeny rankings. In AAAI, volume 6, pp. 620-626 2006.
R Dennis Cook and Sanford Weisberg. Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics, 22(4))495-508 1980.
Alexander Philip Dawid and Allan Skene. Maximum likelihood estimation of observer error-rates using the em algorithm. Journal of the Royal Statistical Society: Series C' (Applied Statistics), 28 (1):20-28, 1979.
Arnab Dey, Mononito Goswami, Joo Heung Yoon, Gilles Clermont, Michael Pinsky, Marilyn Hrav- nak, and Artur Dubrawski. Weakly supervised classification of vital sign alerts real artifact. arXiv preprint urXiv:2206.09074 2022.
Sunny Duan, Loic Matthey, Andre Saraiva, Nicholas Watters, Christopher P Burgess, Alexander Lerchner, and Irina Higgins. Unsupervised model selection for variational disentangled represen- tation learning. arXiv preprint arXiv: /905. 12614, 2019.
Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web, pp. 613-622, 2001.
Ronald Fagin, Ravi Kumar, and Dakshinamurthi Sivakumar, Comparing top k lists. SIAM Journal on discrete mathematics, 17(1):134-160 2003.
Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Springenberg, Manuel Blum, and Frank Hutter. Efficient and robust automated machine learning. Advances in neural information pro- cessing systems, 28, 2015.
Michael A Fligner and Joseph S Verducci. Distance based ranking models. Journal of the Royal Statistical Society: Series B (Methodological), 48(3):359-369, 1986.
Michael A Fligner and Joseph S Verducci. Multistage ranking models. Journal of the American Statistical association, 83(403):892 901, 1988.
Chufan Gao, Mononito Goswami, Jieshi Chen, and Artur Dubrawski. Classifying unstructured clinical notes via automatic weak supervision. arXāv preprint arXiv:2206. /0088, 2022.
Pieter Gijsbers, Erin LeDell, Janek Thomas, Sébastien Poirier, Bernd Bischl, and Joaquin Van- schoren. An open source automl benchmark. arXiv preprint arXiv:1907.00909, 2019.
Pieter Gijsbers, Marcos LP Bueno, Stefan Coors, Erin LeDell, Sébastien Poirier, Janek Thomas, Bernd Bischl, and Joaquin Vanschoren. Amlb: an automl benchmark. arXiv preprint 120.:62207.12560, 2022.
Nicolas Goix. How to evaluate the quality of unsupervised anomaly detection algorithms? arXiv preprint arXiv 152, 2016.
Mononito Goswami, Benedikt Boecking, and Artur Dubrawski. Weak supervision for affordable modeling of electrocardiogram data. AMIA Annual Symposium Proceedings, volume 2021, pp. 536. American Medical Informatics Association, 2021.
Sudipto Guha, Nina Mishra, Gouray Roy, and Okke Schrijvers. Robust random cut forest based anomaly detection on streams. In International conference on machine learning, pp. 2712-2721. PMLR, 2016.
Rob Hyndman and George Athanasopoulos Forecasting: principles and practice. OTexts, 2018.
Eamonn Keogh, Jessica Lin, and Ada Fu. Hot sax: Efficiently finding the most unusual time series subsequence. In Fifth IEEE International Conference on Data Mining (ICDM (05), pp. 8-pp. leee, 2005.
Anna Korba, Stephan Clémençon, and Eric Sibony. A learning theory of ranking aggregation. In Artificial Intelligence and Statistics, pp. 1001-1010. PMLR, 2017.

---

Published as a conference paper at ICLR 2023
Miloš Kotlar, Marija Punt, Zaharije Radivojević, Miloš Cvetanovié, and Veljko Milutinović. Novel meta-features for automated machine learning model selection in anomaly detection. IEEE Ac- cess, 9:89675-89687, 2021.
Ye Kuang, Dandan Li, Xiaohong Huang, and Mo Zhou. On the modeling of rtt time series for network anomaly detection. Security and Communication Networks, 2022, 2022.
Nikolay Laptev, Saeed Amizadeh, and lan Flint. Generic and scalable framework for automated time-series anomaly detection. In Proceedings of the 2 21th ACM SIGKDD international confer- ence on knowledge discovery and data mining, pp. 1939-1947, 2015.
Zinan Lin, Kiran Thekumparampil, Giulia Fanti, and Sewoong Oh. Infogan-cr and modelcentrality: Self-supervised model training and selection for disentangling gans. international conference on machine learning, pp- 6127-6139. PMLR, 2020.
Martin Q Ma, Yue Zhao, Xiaorong Zhang, and Leman Akoglu. A large-scale study on unsupervised outlier model selection: Do internal strategies suffice? arXiv preprint a0404:2104.01422, 2021.
Pankaj Malhotra, Lovekesh Vig, Gautam Shroff, Puneet Agarwal, et al. Long short term memory networks for anomaly detection time series. In Proceedings, volume 89, pp. 89-94, 2015.
Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1):86-97, 2012.
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. Advances Neural Information Processing Systems, 13:10328-10337, 2020.
John Paparrizos, Paul Boniol, Themis Palpanas. Ruey Tsay, Aaron Elmore, and Michael Franklin. Volume under the surface: a new accuracy evaluation measure for time-series anomaly detection. Proceedings of the VLDB Endowment, 15(11) (111))::7442111 2022a.
John Paparrizos, Yuhao Kang, Paul Boniol, Ruey S Tsay, Themis Palpanas, and Michael J Franklin. Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection. Proceed- ings of the VLDB Endowment, 15(8): 1691-1711, 2022b.
Dachyung Park, Yuuna Hoshi, and Charles Kemp. multimodal anomaly detector for robot- assisted feeding using an lstm-based variational autoencoder. IEEE Robotics and Automation Letters, 3(3):1544-155 2018
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim. Efficient algorithms for mining outliers from large data sets. Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp. 427-438, 2000.
Alexander Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data programming: Creating large training sets, quickly. Advances in neural information processing systems, 29, 2016.
Quentin Rebjock, Baris Kurt, Tim Januschowski, and Laurent Callot. Online false discovery rate control for anomaly detection in time series. Advances in Neural Information Processing Systems, 34:26487-26498, 2021.
Lukasz Saganowski and Tomasz Andrysiak. Time series forecasting with model selection applied to anomaly detection in network traffic. Logic Journal of the IGPL, 28(4):531-545 2020.
12

---

Published as a conference paper at ICLR 2023
Sebastian Schmidl, Phillip Wenig, and Thorsten Papenbrock. Anomaly detection in time series: comprehensive evaluation. Proceedings of the VLDB Endowment, 15(9):177--1797, 2022.
Lifeng Shen, Zhuocong Li, and James Kwok. Timeseries anomaly detection using temporal hierar- chical one-class network. Advances in Neural Information Processing Systems, 33:13016-13026, 2020.
Ya Su, Youjian Zhao, Chenhao Niu, Rong Liu, Wei Sun, and Dan Pei. Robust anomaly detec- tion for multivariate time series through stochastic recurrent neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, pp. 2828-2837, New York, NY, USA, 2019. Association for Computing Machin- ery. ISBN 9781450362016. doi: 10.1145/3292500.333077 1145/3292500 3330672
CtLhttps: http://oi.oooo orq/10..
Yining Wang, Liwei Wang, Yuanzhi Li, Di He, and Yan Liu. A theoretical analysis of ndeg type ranking measures. In Conference on learning theory, pp. 25-54, PMLR, 2013.
Qingsong Wen, Liang Sun, Fan Yang, Xiaomin Song, Jingkun Gao, Xue Wang. and Huan Xu. Time series data augmentation for deep learning: A survey. arXiv preprint 2244,72002.12478, 2020.
Michael Wick, Jean-
Jean-Baptian Baptiste Tristan, et al. Unlocking fairness: trade-off revisited. Advances in neural information processing systems, 32, 2019.
Renjie Wu and Eamonn Keogh, Current time series anomaly detection benchmarks are flawed and creating the illusion of progress. IEEE Transactions Knowledge and Data Engineering, 2021.
Haowen Xu, Wenxiao Chen, Nengwen Zhao, Zeyan Li, Jiahao Bu, Zhihan Li, Ying Liu, Youjian Zhao, Dan Pei, Yang Feng, et al. Unsupervised anomaly detection via variational auto-encoder for seasonal kpis in web applications. In Proceedings of the 2018 world wide web conference, pp- 187-196, 2018.
Yuanxiang Ying, Juanyong Duan, Chunlei Wang, Yujing Wang, Congrui Huang, and Bixiong Xu. Automated model selection for time-series anomaly detection. arXiv preprint arXiv:2009.044: 2020.
Jieyu Zhang, Cheng- Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner. A survey on program- matic weak supervision. arXiv preprint arXiv:2202.05433 2022a.
Jiuqi Elise Zhang, Di Wu, and Benoit Boulet. Time series anomaly detection via reinforcement learning-based model selection. arXiv preprint arXiv:2205.09888, 2022b.
Peiyi Zhang, Xiaodong Jiang, Ginger M Holt, Nikolay Pavlovich Laptev, Caner Komurlu, Peng Gao, and Yang Yu. Self-supervised learning for fast and scalable time series arXiv preprint 11Xiv:2102.057400 2021.
tuning.
Yue Zhao, Ryan Rossi, and Leman Akoglu. Automatic unsupervised outlier model selection. Ad-
vances in Neural Information P Processing Systems, 34:4489 4502, 2021.
13

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 RELATED WORK
Time-series Anomaly Detection. This field has a long and rich history with well over hundred proposed algorithms (Schmidl et al. (2022): Blázquez-Garvia in their scope (e.g., multivariate vs univariate, unsupervised vs supervised), and in the anomaly detection approach (e.g., forecasting, reconstruction, tree-based, etc.). At high level many of these methods learn model for the "normal" time-series regime, and identify points unlikely under the given model as anomalies. For example, progression of a time-series can be described using a forecasting model, and points deviating from the forecast can be flagged as outliers (Malhotra et al. (2015). ) In another example, for tree-based methods, a data model is an ensemble of decision trees that recursively partition the points (sub-sequences of the time-series), until each sample is isolated. Abnormal points are easier to separate from the rest of the data, and therefore these will tend to have shorter distances from the root (Guha et al. (2016)). we refer the reader to one of the recent surveys on anomaly detection methods and their evaluation (Schmidl al. (2022); Eetzuuez-Garchh et al. (202I); Wu & Keogh (202I)). Importantly, there is no universally best method, and the choice of the best method depends on the data at hand (Schmid!
al. (202I). The methods vary
) For comprehensive overview of the field,
al. (202
Meta Learning and Model Selection. These approaches aim to identify the best model for the given dataset. The use of meta learning for model selection is long-standing idea. For instance, Kalousis and Hilario used boosted decision trees to predict (propose) classifiers for new dataset given data characteristics "meta-features") such as the number of classes, attributes, instances etc (Alexandros & Melanie 2001)). More recently, Zhao et al. 20 explored the use of meta-learning for outlier detection algorithms. Their algorithm relies on a collection of historical outlier detection datasets with ground-truth (anomaly) labels and historical performance of models on these meta- train datasets. The authors leverage meta-features of datasets to build model that "recommends" an anomaly detection method for a dataset. Concurrently, Kotlar et al. (202T) developed a meta- learning algorithm with novel meta-features select anomaly detection algorithms using labeled data in the training phase.
Ying et al. (2020) focused on model selection at the level of time-series. They characterize each time-series based on fixed set of features, and use anomaly-labeled time-series from a knowledge base to train a classifier for model selection and a regressor for hyper-parameter estimation. A similar approach is taken by iyhang et al.] (2021) who extracted time-series features, identified best performed models via exhaustive myper-paramenn tuning, and trained a classifier (or regressor) using the extracted time-series features and information about model performance labels.
In contrast to methods mentioned this sub-section, we are interested in unsupervised model se- lection. In particular, given an unlabeled dataset, we do not assume access to similar dataset with anomaly labels.
Weak Supervision and Rank Aggregation. We consider a number of unsupervised metrics, and these can be viewed weak labels or noisy human labelers. The question is then which metric to use or how to aggregate the metrics. There has been a substantial body of work on reconciling weak labels, mostly in the context of classification, and a lesser extend for regression. Many such methods build joint generative model of unlabeled data and weak labels to infer latent true labels. We refer the interested reader recent survey by Zhang et al. (2022a).
Since we are interested in ranking anomaly detection methods rather than inferring their exact per- formance numbers, rank aggregation more relevant paradigm for our project. Rank aggregation concerns with producing consensus ranking given a number of potentially inconsistent rankings (permutations). One of the dominant approaches in the field involves defining a (pseudo-)distance )distance in the space of permutations and then finding a barycentric ranking. i.e., the one that minimizes distance to other rankings (Korba et al. (2017)) The distance distribution can then be modeled, e.g., using the Mallows model, and rank aggregation reliability can be added by assuming a mixture from Mallows distributions with different dispersion parameters (Collas & Irurozki (202T)). In our work, draw the ideas from this research.
14

---

Published as a conference paper at ICLR 2023
Automatic Machine Learning (AutoML). The success machine learning across gamut of appli- cations has led to an ever-increasing demand of predictive systems that can be used by non-experts. However, current AutoML systems either limited to classification with labeled data (e.g., AutoMI and Combined Algorithm Selection and Hyperparameter Optimization (CASH) problems in (Feurer al. (0135), or sulf-supe regression or forecasting problems (Feurer et al. 2015 Gijsbers et al. 2022 2019).
Using Forecasting Error Select Good Forecasting Models. Some prior work on anomaly detection time-series anomaly detection use the idea of selecting models with low forecasting error to pick the best model for forecasting-base -baned anomaly detection (Saganowski Andrysiak 2020
Laptev et al. 2015 Kuang al. 2022
Semi-supervised anomaly detection model selection. Recently, Zhang et al. (2022b) leveraged reinforcement learning select the best base anomaly detection model given dataset. They too use the idea of model centrality (referred to as Prediction-Consenee method is semi-supervised since relies on actual anomaly labels evaluate the reward function. Moreover, the base models do not include any recent deep bearning-based anomaly detection models. Finally, they evaluate their method on only one dataset (SWaT).
Confidence). However, their
Limitations of Prior Work in the Context of Unsupervised Time-series Anomaly Detection Model Selection. In this section we briefly summarize the limitations of prior work considering the model selection problem in different settings.
Limited, predefined model set .M: Many studies experiment with small number of models for experiments (IM) s 5). Most of these models are not state-of-the-ar for time-series anomaly detection (e.g. (Saganowski & Andrysiak (2020) use Holt-winters and ARFIMA), unrepresentative (only forecasting-basel non-deep learning models), and spe- cialised to certain domains (e.g. network anomaly detection (Saganowski & Andrysiak] 2020 Kuang et al., 2022)). In contrast, our experiments are conducted with 19 models of 5 different types (distance, forecasting and reconstructionn-enn based), which have been shown to perform well for general time-series anomaly detection problems (Schmidl et al. 2022. Paparrizos et al., 2022b). Moreover, our model selection methodology is agnostic to the model set. Note that neither the model centrality and synthetic anomaly injection metrics, nor robust rank aggregation relies on the nature or hypothesis space of the models.
Limited, specialised datasets old benchmarks with known issues: Most studies (Saganowski & Andrysiak] 2020 Kuang et al.)
2022 Laptev et al., 2015) are evaluated limited number of real-world datasets (N
2). of specific domains (e.g. net-
work anomaly detection (Saganowski & Andrysiak 2020 Kuang et al. (022 Most papers either not evaluated on common anomaly detection benchmarks (Saganowski & Andryssaak 2020 Kuang et al. (002)), or evaluated on old benchmarking datasets (e.g. Numenta Anomaly Benchmark) with known issues (Wu Keogh [002I). On the other hand, our methods are evaluated on 275 diverse time-series of different domains such as electrocardiography. air temperature etc.
Supervised model selection: Some prior work, e.g. (Kuang et al. 2022) used super- vised model selection methods such as Bayesian Information Criterion (BIC). However, in our setting methods such as BIC cannot be used because we do not have anomaly labels and measuring model complexity of different model types (deep neural networks, non- parametric models etc.) our case is non-trivial.
No publicly available code: Finally, most papers do have publicly available imple- mentations.
15

---

Published as a conference paper at ICLR 2023
A.2 LIMITATIONS AND FUTURE WORK
Computational Complexity. Our methods are computationally expensive since they rely on pre- dictions from all models in the model set. However, our main baseline is supervised selection which requires manually labeled data. Our premise is that manual labeling is much more expensive than compute time. For example, Amazon Web Services compute time the order cents/hour, where human time cost approximately $10/huu.. In fact, recall that some of our benchmarks involve med- ical datasets where gold standard expert annotations can cost anywhere between $50-200 per hour (bbend et al. 2015).
Assumption: A majority rankings can identify accurate models better than random. Em- pirical influence and robust borda methods provably identify good models only if majority of the rankings can identify good models better than random (see appendices A.8 A.9 An interesting direction of future work is to relax this assumption, make an orthogonal assumption. For exam- ple, there has been work on provably-optmmal model selection of bandit algorithms which assume specific structure of the problem (e.g., linear contextual bandits), and that at least one base model satisfies a regret guarantee with high probability (Pacchiano et al. 2020
Assumption: Partial orderings rather than total ordering. We assume that all metrics impart total ordering of all the models. However, this may not always be true. In our experience, some models may have the same performance as measured by a metric. To this end, future work may focus aggregation techniques of partial rankings (Ailon 2010).
Online model selection. We rely on predictions of models on the test data, however, in practice test data may be unavailable during model selection.
16

---

Published as a conference paper at ICLR 2023
A.3 ADDITIONAL RESULTS
The complete set of results are shown in Fig. and Tab. 3
We compare 17 individual surrogate metries, including 5 prediction error metrics, synthetic anomaly injection metrics, metrics of centrality (average distance to 1, 3 and 5 nearest neigh- bors) (Section3): and 4 proposed robust variations of Borda rank aggregation, namely Partial Borda, Trimmed Borda, Minimum Influence Metric and Robust Borda (see Appendix (.7.2). We also com- pare Borda and its variations with exact Kemeny aggregation Appendix A.7.3
Contrality N)
Contrality Ni-
Accularation
Syntheti (Wander
Syntheic Hppedup))
Synthelc (Sals)
Synthetic (Contechal))
Synthatic
Synthesic (NoGe
Syntheti (Ditem))
Pred. Enar IMAPE
fred. Eror (Lkefhood
Rred.
Partal Burda
Robust Bonda-
MIM
Rancom
Centralny
ABP
ECG
EPG
Powar
contrality No
Synthebic (Spkes)
Synthetic (5pocdup)
Synthebic
Synthetic (Fip)
Synthetic (Contextual)
Synthetic (Average)
Systheicc (Cutoff)
Pred, Emar (SMAPE)
Pred, Enor (MAE
fred. Erar (MSE)
Kemeny
Partol
Tommed Borca
Bonds
0gcil
0.25
05
0.75
0.25
0.5
0.75
0.25
0.5
0.75
0.25
0.5
0.75
0.25
0.5
Figure 4: Performance of the top-l selected model. Box plots of adjusted best Fi of the model
selected by each metric or baseline across 5 unique combinations of the selection and evaluation sets. Orange () and blue () vertical lines represent the median and average performance of each metric or baseline, and the minimum influence metric (MIM), respectively. Each box plot is organized into three sections:
performance of individual metrics, Borda and its robust variations, and three
baselines.
17

---

Published as a conference paper at ICLR 2023
Significant Wins
Significant Losses
Ranking Methods/Busclines
S5
Bandom
Oracle
S5
Random
Random
10
4
Oracle
Borda
0
Robust Borda
Trimmed Borda
Partial Borda
Kemeny
Pred. Error (MSR)
Ecror (Likelihood)
Pred. Error (MAE)
Pred. brror (MAPE]
Fred. Error (SMAPE)
Syntsetic (Cutoff)
Synthetic (Noise)
Synthetic (Average:
Synthetic (Contextual)
Synthetic (Plip)
Synthetic (Scale)
Synthetic (Speedup)
Synthetic (Soikea)
Synthetic (Wander)
Centrality (5 N)
10
3
Centrality
Contrality
Table 3: Results of pairsise-statistical tests.. On a total of = 10 datasets, minimum influence metric (MIM) and robust Borda have the fewest significant losses to oracle, and are much better than random model selection and Borda.
A.4 SYNTHETIC DATA EXPERIMENTS
The Mallows's model FFiigner& & Verducci 1986) popular distance-based distribution model rank data. The probability mass function of Mallows's model with central permutation do and dispersion parameter 0 given by:
p(o) exp(-Od((a, σo))
where d is the Kendall's 7 distance. With increase in 0, there is stronger consensus, thereby making Kemeny aggregation easier.
We aim to empirically answer two research questions:
1. What is the impact noisy permutations on the median rank?
2. Can empirical influence identify outlying permutations?
To this end, we draw permutations from the Mallow's distribution "1, -r MMoo, 0) and N - k permutations at uniformly at random from S,- We compute the median rank using the Borda method. We experiment with {50, 100). (0.05, 0.1, 0.2) and 50 based on the experimental setup used by Ali & Meilä (2012).
18

---

Published as a conference paper at ICLR 2023
100,
0.05
Distance of Median from True Rank
600
500
400
300
100
0.25
0.5
0.5
Percentage Noisy Samples
Percentage Noisy Samples
Percentage Noisy Samples
Figure 5: Impact of Noisy Permutations. With increase noise, the distance of the median permu-
tation (Ø) from the central permutation (oo) increase i.e. noise hurts rank aggregation.
n=50 theta=0.05 noise=0.25
n= theta=0.2 noise=0.25
n=50 theta=0.05 noise=0.5
n=50 theta=0.2
Dalance from Nemddttion
200
650
600
600
550
500
400
500
abo
450
400
250
350
25
theta=0.00
theta=0.2 noise=0,25
nolse=0
0000
2500
2300
2200
2000
2000
1500
2000
1500
1600
1000
1750
1000
1400
1250
500
-10
permutation
permutation
permutation
Figure 6: Empirical Influence can Identify Outlying Permutations. Influence of permutation directly proportional to its distance from the central permutation (at). Under the Mallow's 's model, outlying (or low probability) permutations have a higher distance (ar).
A.5 GENERATING SYNTHETIC ANOMALIES
Natural anomalies not occur randomly, but are determined by the periodic nature of time-series. Therefore, before injecting anomalies determine periodicity of time-series by finding the its auto-correlation, and only inject anomalics (barring spikes which are point-outlerr) at beginming of cycle. We only inject single anomaly in each time-series in repetition, and its length chosen uniformly at random from [1, max length), the latter being a user defined parameter (Fig. 7
Spike Anomaly. To introduce a spike, first draw Bernoulligg and if m inject a spike whose magnitude is governed by a normal distribution & ~ (2,
Flip Anomaly,
We reverse the time-series:
ts_a [i, start:end] ts [i, start:end] [::-1]
Speedup Anomaly. We increase decrease the frequency of time-series using interpolation, where the factor change in frequency (} or 2) a user-defined parameter.
Noise Anomaly. We inject noise drawn from normal distribution A(O0, d²), where is user- defined parameter.
19

---

Published as a conference paper at ICLR 2023
Spikes anomaly
Contextual anomaly
Flip anomaly
10
-15
3.0
Speedup anomaly
Noise anomaly
Cutoff anomaly
55-
Scale anomaly
Wänder anomaly
Average anomaly
20
10-
-55-
282
600
800
1000 1897 1403
2000
400
502
1000
1200
2420
1902
200
2007 1205
1462
Figure 7: Different kinds of synthetic anomalies. We inject 9 different types of synthetic anomalies randomly, at time, across multiple copies of the original time-series. The is original time- series before anomalies are injected, is the injected anomaly and the solid is the time-series after anomaly injection.
Cutoff Anomaly Here, we set time-series to either NN(,,²²) or M(1, where both the choice of location parameter and is user-defined.
Average Anomaly. We run moving average where the length of the window (len window) is determined by the user:
ts_a [i, start:end] moving.average (ts [i, start:end), len-window)
Scale Anomaly. We scale the time-series by user-defined factor (factor):
tsali, start:endi factor*ts start:end
Wander Anomaly. We add a linear trend with the increase in baseline (baseline) defined by users:
tsaali, start:end] np. 1 linspacceceeeee (0, baseline, end-start) ts [i, start:end]
Contextual Anomaly. We convolve a the time-series subsequence linear function aY b, where ~ NN,1 2. and ~ NN
20

---

Published as a conference paper at ICLR 2023
A.6 DESCRIPTION MODELS
There are a hundred unique time-series anomaly detection algorithms developed using wide variety of approaches. For our experiments, we implemented a representative subset of 5 popular methods (Table|]), across two different learning types (unsupervised and semi-supervised) and three different method families (forecasting, reconstruction and distance-based) (Schmidl et al. 2022).
In the context of time-series anomaly detection, "Semi-supervised" means requiring part of time- series known to be anomaly-free. Each time-series in the UCR and SMD collections comprises of a train part with no anomalies and test part with one (UCR) or more anomalies (SMD). We used the train part for training semi -upe-supe models.
We emphasize that our surrogate metrics do not rely on availability of the "clean" train part (and we didn't use the train part for evaluation). Moreover, while semi-supervised models are supposed to be trained on anomaly- part, in practice they can still work (perhaps sub-optimally) after training on time-series that potentially contained anomalies.
The models we implemented can also categorized as forecasting, reconstruction and distance methods. Forecasting methods learn to forecast the next few time steps based on the current context window, whereas reconstruction methods encode observed sub-sequences into a low dimensional latent space and reconstruct them from the latent space. In both cases, the predictions (forecasts or reconstruction) of the models are compared with the observed values. Finally, distance based models used distance metrics (e.g. Euclidean distance) compare sub-sequences, and expect anomalous sub-sequences to have large distances to sub-sequences they are most similar to.
We created pool of 3 k--N (Ramaswamy al. 2000), and 4 moving average, 4 DGHL (Challu et al. 2022), 4 LSTM-VAE (Park et 20118) and 4 RNN (Chang et al., 2017) by varying important hyper-parameters, for total 19 models. Finally, to efficiently train models, sub-sampled all time-series with T > 2560 by factor of 10.
Model
Area
Learning Type
Method Family
Moyii ng Average
Statistics
Unsupervised
Forecasting
N-NN (Ramaswamy al. 2000
Classical
Semi- rumi-suprrvieed
Distunce
Dile aed RKN (C Cann ala 2017
Deep Learning
Semi-supe semi-supervised
Forecasting
IGHT. (Challu et al. 2022
Deep Learning
Semi- supi-vspee
Reconstruction
LS LSTM-18 VME (Park al 2018
Deep Leaming
Semi supervised
Reconstruction
Table 4: Models in the model set and their properties.
Below is brief description of each model.
Moving Average. These models compare observations with the "moving" average of recent obser- vations in sliding window of predefined size. These methods assume that if the current observation differs significantly from moving average, then it must be an anomaly. Specifically, æ; denotes the current observation, h represents the window size and let be an anomaly threshold, then æ, is flagged as an anomaly if:
D1
>T.
Moving average is one of the simplest, efficient yet practical anomaly detection models, frequently used by industry practitioners. Moreover, moving average unsupervised since it does not require any normal training data.
k-Nearest Neighbors (k-NN) (Ramaswamy et al. 2000). These distance-based anomaly detec- tion models compare a window of observations to their k nearest neighbour windows in the training data. If the current window is significantly far its & closest windows on the training set, then must be an outlier. In our implementation, the distance between time-series windows is measured using standard Euclidean distance. Specifically, let wi = { (æt-h,"" *. x denote the current window of size h, "",".. Wo be the l: nearest windows in the train set wi, || ||2 represent the euclidean
21

---

Published as a conference paper at ICLR 2023
norm, and T be anomaly threshold. Then the current window is flagged as anomaly if:
w 1 DT
w;
Dilated RNN (Chang et al. 2017). Dilated Recurrent neural network (RNN) is recently pro- posed improvement over vanilla RNNs, characterized by multi-resolution dilated recurrent skip connections. These skip connections alleviate problems arising from memorizing long term de- pendencies without forgetting short term dependencies, vanishing and exploding gradients, and the sequential nature of forward and back-propagation vanilla RNNs. Given a historical window of time-series, we use a dilated RNN to forecast Tia time steps ahead. Let W = {Et, æT,,, J denote the current window of observations, wØ { &h be the forecasts from the dilated RNN model, and be an anomaly threshold. Then is flagged an anomaly if:
|| --
2022 This model a recent offte-of-theaarr Generative model for time- series anomaly detection. It uses Top-Down Convolution Network (CNN) to map novel hier- archical latent representation to a multivariate time-series windows. The key difference with other generative models as GANs and VAEs is that is trained with the Alternating Back-Propagation al- gorithm. The architecture does not include an encoder, instead, latent vectors are directly sampled from the posterior distribution. Let æ, be the observation and & the reconstruction at timestamp and T be an anomaly threshold. Then 2 is flagged as an anomaly if:
DGHL (Challu
|| x: 112
LSTM-VAE (Pak al., 2018). The LSTM-VAE is reconstruction based model that uses Variational Autoencoder with LSTM components to model the probability of observing the target time-series. The model also uses the latent representation to dynamically adapt the threshold to flag anomalies based on the normal variability of the data. The anomaly scores corresponds to the negative likeliiiooo of an observation, Tt, based on the output distribution of the model, and is flagged as an anomaly if the score is larger than threshold T:
- plx:)())) >
22

---

Published as a conference paper at ICLR 2023
A.7 BORDA RANK AGGREGATION
Borda is positional ranking system and is an unbiased estimator of the Kemeny ranking of a sample distributed according to the Mallows Model (Fligner Verducei 1988). Consider N models and a collection of M surrogate metrics S = {01, ... JM J. We use o% to both refer to the surrogate metric and the ranking it induces. Then under the Borda scheme, for any given metric os the 7th model receives - (i) points. Thus, the ith model accrues a total of اi (N - ox(1)) points. Finally, all the models are ranked in decreasing order of their total points and ties are broken uniformly at random. Borda can be computed in quasi-linear (O(M + N log N)) time.
A.7.1 IMPROVING RANKING PERFORMANCE THE TOP
In model selection, we only care about top-ranked models. Thus, to improve model selection perfor- mance at the top-ranks, we only consider models at the top-k ranks, setting the positions of the rest of the models to N (Fagin et al., 2003). Here, i is a user-specified hyper-parameter. Specifically, under the top-k Borda scheme, the hth model accrues a total of Add Io (t) I k] om (i)) points. Intuitively, this increases the probability of models which have top-k ranks consistently across surrogate metrics, to have top ranks upon aggregation.
A.7.2 ROBUST VARIATIONS OF BORDA
We consider multiple variations of Borda, namely Partial Borda, Trimmed Borda, Minimum Influ- ence Metric (MIM) and Robust Borda. We collectively refer to these as robust variations of Borda rank aggregation.
Partial Borda improves model selection performance, especially the top ranks by only consider- ing models at the top-k ranks, as described Appendix [A.7.T]
Trimmed Borda another robust variation of Borda, which only aggregates reliable ("good") per- mutations. Trimmed Borda identifies outlying or "bad" permutations as ones having high positive empirical influence.
Minimum Influence Metric (MIM) for dataset is the surrogate metric with minimum influence. Recall that while high positive influence is indicative of "bad" permutations, low values of influence are indicative of "good" permutations.
Robust Borda performs rank aggregation only based on the top-k ranks while truncating permuta- tions with high positive influence. Hence, Partial Borda, Trimmed Borda and Minimum Influence Metric can be viewed as special cases of Robust Borda.
A.7.3 EXACT KEMENY RANK AGGREGATION
The Kemeny rank aggregation problem be viewed minimization problem weighted directed graph (Conitzer et al. 2006). Let G = (V. E) denote a weighted directed graph with the models as vertices. For every pair of models,
define edge (i j) E and set its weight as Wij = E> Lipus Dkm Lozul Here the indicator lii = denotes that metric prefers model i over model and hence Wij denotes the number of metries which prefer model i over j.
Then we can formulate the rank aggregation problem as a binary linear program:
minimize
WaZee
subject to
Vi # jj V, + +.zz (Anti-symmetry and totality constraints)
Vi + j & k E V + Tzk + -bi 2 1 (Transitivity constraints)
Vi Vi J {0. 13
(Binary constraint)
Intuitively, we incur cost for every metric's 's pairwise comparison that we do not honor.
23

---

Published as a conference paper at ICLR 2023
A.8 THEORETICAL JUSTIFICATION FOR BORDA RANK AGGREGATION
Suppose that we have several surrogate metrics for ranking our anomaly detection models. Also suppose that each of these metries is better than random ranking. Why would it be beneficial to aggregate the rankings induced by these metrics? Theorem [ provides an insight into the benefit of Borda rank aggregation.
Suppose that we have N anomaly detection models to rank. Consider two arbitrary models i and j with (unknown) ground truth rankings di) and dj)).. Without the loss of generality, assume o" (1) < <0((j), i.e., model i is better.
Next, let's view each surrogate metric 1,... M as a random variable S2 taking values in permutations Sv (a set of possible permutations over N items), such that (1) E [N] denotes the rank of item i. We are interested in properties of Borda rank aggregation applied on realizations of these random variables. Theorem T states that, under certain assumptions, the probability of Borda ranking making a mistake (i.e., placing model lower than j) is upper bounded in a way such that increasing M decreases this bound.
Theorem. Assume that Q 's are pairwise independent, and that (i) < O2x())) > 0.5 for any arbitrary models and j, i.e. each surrogate metric better than random. Then the probability that
Borda aggregation makes mistake in ranking models and is most 2 exp (- Mr² fixed c.
(-22) for some
P4( Thus Xx if (1)() < (2)(j) and X = -1, otherwise. Denote the expectation of these random variables as ER 2 [[].]. We assume that Es > e, vk E [M] for some small e > 0, i.e. that each surrogate metric is better than random.
Proof. We begin by defining random variables X3 (1)
k= Xx. EM EMM Eg. Note that if SM > 0 then Borda aggregation will Next, define SM ΣM correctly rank higher than j.
If 94 are pairwise independent, then X₁ are pairwise independent, and we can apply Hoeffding's inequality for all > 0:
21
PP(SMM - Easl 2 2 exxp
4M
P(EM - SM 2 < 2 expp
2M
(FAr) )²
PPSM 50 < 2exp(
setting = -EM
2MM
Me²
P(SM S 50 < cexp
because < Eg,, Vk.
2
Recall, that Sa < 0 results in an incorrect ranking (ranking j higher than i), and Su = 0 results in tie (that break uniformly at random). Therefore, the probability that Borda aggregation makes a mistake in ranking items and j is upper bounded as per the above statement.
We do not assume that Ω4 are identically distributed, but we assume that Ω2 's are pairwise inde- pendent. We emphasize that the notion of independence of Sg random variables is different from rank correlation between realizations of these variables (i.c., permutations). For example, two per- mutations drawn independently from Mallow's distribution can have high Kendall's coefficient (rank correlation). Therefore, our assumption of independence, commonly adopted theoretical analysis (Ratner al., 2016), does not contradict observation of high rank correlation between surrogate metrics.
Corollary 1. Under the same assumptions as Theorem if Borda aggregation makes a mistake in ranking models i and with probability most å > 0, then min ((Qx I&(i) where & [M] and i [N] are any two arbitrary models.
log
24

---

Published as a conference paper at ICLR 2023
Proof. The proof follows from upper bounding the probability that Borda makes a mistake in rank- ing models i and by 8:
M
2 2log 3
PSSM & 00 < exp( 5 c2 V
(3)
Consider the following relationship between e and min (12 < (2x(1))) for l E [M]:
S min F min 21P(S4 (1) < 9x())) - = 2(min P())(()) < Rx()))) -1
(4)
From Equations
and
conclude that:
log 1 +
min (i) S2(i)) 2
2M
2
To reduce chances of error, follows from Corollary [ that we can either increase the number of surrogate metrics, collect smaller number of highly accurate metries. As example, set 5 = 0.05 and consider M 20 metrics. Then for the Borda to err at most 5% of times, each surrogate metric must prefer A, over Aj with probability at least 0.7. This also highlights the importance of empirical influence in identifying and removing bad permutations from the Borda aggregation.
A.9 THEORETICAL JUSTIFICATION FOR EMPIRICAL INFLUENCE
In this section provide two arguments in support of Empirical Influence (EI). First, note that in an idcalized case, where all but one metrics are perfect, EI helps identify the imperfect metric.
Lemma 2. Consider a set of M surrogate metrics that consists of (M 1) perfect metrics and one imperfect metric. The perfect metrics induce permutations 01 the ground truth permutation, while the imperfect metric induces permutation aM # a². Then
σM-1 = a², where o²
El(aM) 2 El(o,) for any 1 2 i M 1.
Proof. Let = (0 . ,MM). = 1
E!A d. (Borda(AA), and 2 212 M
Then
Bl(oy) - El(a;) = f(S) ((S) f(S (f(S)o,)) f(S σM)
Since, σi =... OM-1 o0 we have Borda \ aM) = o² and S(S aM) = 0. Kendall tau distance d, is non-negative, hence f(S o.) 2 0.
We have that (l( 2 Bl():).
Next, recall that Borda (AA) is unbiased estimator of the central permutation the Kemeny- problem. Given set of permutations A. the central permutation is defined as
AA
1
e(A) arg min
dx.
(5)
A
GEA
where the minimization is over all possible permutations X of N items.
We now consider a modified notion of Empirical Influence that uses the central permutation instead of Borda approximation.
BI(()) = f'8)) ('S a),
25

---

Published as a conference paper at ICLR 2023
where f'(A)= TAi E!A d=(c(A).o...
Using this modified definition, we show how El capable of distinguishing between permutations close and far from the central permutation. Recall that good permutations are those that are close to the central permutation.
Lemma 3. Consider a set of permutations S = 10,...., 02- Jok, Tbadh where ook and abad represent good and bad permutations, respectively.
Let o² be the unknown ground truth permutation.
Next, for some O, assume that d=(a", (oak) < and do" (bbad) > 3r.
We also assume that overall, our set S is of reasonable quality in the sense that de (c(( x0) for any E S.
Then, we have that Ef' (ahad) > ET (o.)).
Proof. Consider the difference
El' (Abed) - (ookk)))) ((()) 0 f(a) (' ooo)
= f' aok) - (8 (Tbaa)
Σ (Cbes,
Σ
d (Cou,
Here, Cok = =(S \ obad) and Qoad = c(S ooo))
We have that
Σ oESioa
d, (Crad, σ)
Σ
dr (Coks ④))
DESi
Σ
dr dr
Σ
d, (Cok: o) + (Cbadd Tead) - dr (Cbad, Tok)
Under our assumptions, di (Cbad, σ*) T, dr (obad, 0³) 3r and d, (ook <r. Therefore EI' (abad) > (aak).
A.10 CORRELATION BETWEEN ADJUSTED BEST F; AND VUS-ROC
Motivation. Paparrizos et al. 2022a) in a recent study found the volume under the surface of the ROC curve (VUS-ROC) to be more robust than other compared evaluation metries. Their study did not compare VUS-ROC against adjusted best F1, used in this paper. The VUS-ROC metric is defined for univariate time-series, whereas one of the datasets we use, the Server Machine dataset (SMD), has multivariate time-series. Hence, our main results are still with respect to adjusted best Fr. However, we carry out an experiment to evaluate the correlation between VUS-ROC correlates with adjusted best Fi.
Experimental setup. For every time-series, we computed the spearman-r and kendall-7 correla- tion between the performance of models measured by VUS-ROC and adjusted best F, We carried out this experiment on 250 time-series from the UCR anomaly archive (Wu & Keogh (02T). We measured the dispersion of evaluation measure (VUS-ROC or adjusted best Fi) time-series as the interquartile range of performance values of all models in that time-series. The sliding window parameter that VUS-ROC relies on, automatically set to the auto-correlation of time-series.
Results. Out of 250 time-series, only 23 time-series did not have statistically significant positive kendall-7 and spearman-r correlation. All these time-series had low dispersion of the evaluation measures i.e. the difference in performance of most models trained on the time-series, measured in terms of VUS-ROC or adjusted best Fi, was less than 10%.
26

---

Published as a conference paper at ICLR 2023
A.11 CORRELATION BETWEEN ADJUSTED BEST F1 AND ADJUSTED PR-AUC
On our datasets, performance of models measured using PR-AUC and adjusted best Fi had statisti- cally significant highly positive correlation (see Figure
fs = 0.94 (0.0), t 0.81 (0.0)
Adjusted PR-AUC
0.6
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0
Adjusted best F3
Figure 8: Correlation between adjusted best and adjusted PR-AUC. rs and denote the spear- man and kendall correlation, respectively. p-values of two-sided tests are reported in parenthesis.
A.12 DOES EMPIRICAL INFLUENCE IDENTIFY BAD METRICS?
To measure the correlation between empirical influence and quality of metric, we provide (1) experiments real-world datasets, and (2) analysis on synthetic data in Appendix A.4 where we see that empirical influence can almost perfectly identify bad metrics.
Experimental setup. We define the quality of metric using two quantities: (Q1) adjusted best Fj of top-5 models ranked by a metric a, (Q2) difference in the adjusted best F1 of top-5 and bottom-5 models ranked by metric This quality metric inspired by the separation analysis in Paparrizos et al. (2022a).
Results. out of 9 datasets had negative kendall-r correlation between the quality of a metric and its empirical influence, when quality is measured using Q1. Of these 6 datasets, 4 datasets had statistically significant negative correlation. Recall that bad metries have high positive empirical influence (Section 4.2). Even when quality is measured using Q2, 6 out of 9 datasets had negative kendall-r correlation between the quality of a metric and its empirical influence. these 6 datasets, 2 datasets had statistically significant negative correlation.
27

---

Published as a conference paper at ICLR 2023
A.13 RESULTS WHEN AGGREGATING OVER ALL METRICS
When we perform robust rank aggregation over all the metrics, instead of only anomaly injection metrics (scale, noise, cutoff, contextual and speedup), observed a degradation the performance of both minimum influence metric (MIM) and robust Borda. MIM has more significant wins and fewer significant losses when only the 5 best performing metrics are aggregated. This degradation in performance can be explained by the fact that some metrics have ranking performance worse than random model selection, for example model centrality metrics and prediction likelihood.
Significant Wins
Significant Losses
Ranking Metlods/Baselines
SS
Random
Oracle
SS
Random
MIM
0
1
3
Robust Borda
0
2
2
Table 5: Results of pairwise-statisticd tests, when aggregation performed using all metrics on datasets.
Significant Wins
Significant Losses
Ranking Methods/Baselines
SS
Random
Oracle
SS
Random
MTM
2
3
5
0
0
Robust Borda
2
4
2
Table 6: Results of pairwise-statisee tests, when aggregation performed using only best per-
forming 5 metrics
6 datasets.
A.14 DOES THEOREM I HOLD PRACTICE?
In this short experiment we provide empirical support for Theorem 1.
Experimental setup. Theorem considers error bounds when ranking two models. Thus, for each time series identify the best- and worst-performing models and empirically test whether aggregation over more rankings helps reduce this error. We varied the number of surrogate metrics from 2 to 17, and perform borda rank aggregation find the best model. The performance of the aggregated borda rank is measured as the adjusted best Fi of the top ranked model. For each combination of m metrics, we report the performance averaged over all (1?) unique combinations of the metrics.
First, we present the performance of the best model identified by borda aggregation of a combination of metrics, averaged across all the time-series. Overall, we see a clear trend where the performance of the selected best model increases with the number of surrogate metrics (rankings).
Results.
Average performance when using mn metrics
Adjusted best
metrics
0.588
m = metrics
0.795
8 metries
0.784
m metrics
0,829
14 metrics
0.821
m metrics
0.838
Table Adjusted best Fi of the best model as identified by borda aggregation of all possible combi- nations of metrics, averaged across all time-series datasets. Increasing the number of surrogate metrics improves model selection performance.
In only 27 out of 181 time-series, we did not observe monotonic improvement as the number of metrics increased. However, we notice that in all such cases, the performance detection models
anomaly low and similar to each other. Under such circumstances, not only do surrogate metrics tend to be noisy, violating the assumptions of the theorem, but also, model selection does matter much.
28

---

Published as a conference paper at ICLR 2023
Below, example, also report the results of two individual time-series where theorem at play, and another time-series where our theorem does not hold:
Average performance when using metrics
Adjusted best Fj
m metrics
0.507
m 5 metrics
0.701
m metrics
0.584
11 metrics
0.742
m metrics
0.629
= 17 metrics
0.984
Table 8: Adjusted best F1 of the best model as identified by borda aggregation of all possible com- binations of m metrics, on machine-3-6 time-series of the Server Machine dataset. Increasing the number of surrogate metrics improves model selection performance.
Average performance when using metries
Adjusted best Fi
m metrics
0.566
m metries
0.742
m = metrics
0.645
11 metrics
0.780
m 14 metrics
0.677
17 metrics
0.999
Table Adjusted best Fi of the best model as identified by borda aggregation of all possible combi- nations of m metrics, InternalBleeding17 time-series of the UCR Anomaly Archive. Increasing the number of surrogate metrics improves model selection performance.
Average performance when using m metrics
Adjusted best Fj
metrics
0.324
m = metrics
0.396
8 metries
0.272
m metrics
0.268
14 metrics
0.240
m metrics
0.240
Table 10: Adjusted best F1 of the best model as identified by borda aggregation of all possible time-series of the UCR Anomaly
combinations of m metrics, DISTORTEDineemalBleeee Archive. In this time-series, increasing the number of surrogate metrics hurts model selection per- formance.
29


Reviews:
[{"review_id": "rKJN59g_G0", "reviewer": "Reviewer_Qvoy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on anomaly detection model selection metrics in the unsupervised setting where a user does not have access to labeled anomalies in order to select the best model. They identify three classes of these surrogate metrics (prediction error, synthetic anomaly injection, and model centrality) and also propose a way to combine rankings from multiple surrogate metrics with some theoretical guarantees. They show experiments comparing surrogate metrics from the three classes with their combined rankings method against an oracle, random baseline, and partially labeled baseline. ", "summary_of_the_review": "This paper is presented well, proposes an interesting novel concept, and has strong justifications. The only weakness is that empirical results seem somewhat mixed in supporting their claims. ", "strength_and_weaknesses": "Strengths:\n- Very interesting concept, does not seem well studied prior in the literature\n- The proposed Borda rank aggregation has theoretical justifications\n- Overall well presented paper\n\nWeaknesses:\n- Is minimizing empirical influence, essentially throwing out \"bad\" surrogate metrics as \\sigma_i are the rankings of surrogate metric i ? If so, in the empirical results it would be interesting to see if the surrogate metrics that are \"bad\" for a dataset, align with that metrics performance on the dataset. I believe the surrogate metrics being aggregated are the same ones used individually?\n\n- Under the assumptions of Theorem 1 the probability that Borda aggregation makes a mistake in ranking is an exponentially decaying in the number of surrogate metrics M. The experimental results never seem to empirically support this though. While it would be potentially computationally expensive to show it asymptotically, it would be good to see a plot of the performance of Borda aggregation increasing as the number of surrogate metrics increase, even if it is just from 2 to 17.\n\n- None of the methods are able to have significant wins against random on all 10 datasets? Additionally Pred. Error MSE has significant losses against Random in 4 datasets; but it is used as one of the surrogate metrics in Borda? For those 4 datasets, wouldn't that metric basically violate the assumptions of Theorem 1 that Borda is aggregating surrogate metrics that are better than random?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NuKBOZgVkj", "reviewer": "Reviewer_E7ki", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a solution for selecting models for time-series anomaly detection. Starting from the assumption that no single model performs best across all datasets, the paper argues for the importance of AutoML solutions in that area. As a result, the paper first studies surrogate measures that correlate with the accuracy of anomaly detection methods. Then, it combines these measures using a rank aggregation technique. In the end, the paper demonstrates the effectiveness of the proposed solution.", "summary_of_the_review": "See above. The missed AutoML baselines is a major flaw of this work. In addition, many recent advances in the time-series anomaly detection literature are not mentioned/ignored, which may change the outcome of this work.", "strength_and_weaknesses": "Strengths\n\n1. Time-series anomaly detection is a well-studied, timely, and important problem\n2. Well-written and easy to follow\n3. AutoML for anomaly detection for time series is not sufficiently studied and hence this study fills a gap\n\nWeaknesses\n\n1. Missing baselines from the AutoML area in general\n2. Missing baselines from the AutoML area for time series\n3. Omitted new benchmarks and evaluation strategies\n\nComments:\n\n- AutoML is a very well-studied area. The paper claims it's the first work regarding time-series anomaly detection, which is also not true. A simple query reveals multiple solutions in that area that are unfortunately not mentioned and not compared against. It's very difficult to assess the importance of this work and if it advances state of the art without covering and comparing the relevant work appropriately\n\nhttps://scholar.google.com/scholar?hl=en&as_sdt=0%2C36&q=model+selection+time-series+anomaly+detection&btnG=\n\nExisting AutoML solutions for non-time-series data can very well be adopted for this problem and needs to be compared. Time-series specific AutoML solution for anomaly detection or other ML tasks should also be used in comparison.\n\n- The work relies on specific recent papers to justify reasoning/choices (e.g., Schmidl et al.) while ignoring works appearing at the same time/conference, with different findings. Schmidl et al limited the time a method could run during their evaluation and used methods \"as is\" (i.e., not reimplemented), which resulted in model failures, which were not taken into consideration but instead decreased the overall performance of specific methods. This is truly problematic as their findings differ from other studies in this area, e.g., Paparrizos et al., which focused on significantly more data (12000+ time series) but less methods and identified several methods significantly outperforming current SOTA. Even though the claim that no method performs well across every single dataset still holds, several of the choices in the current papers are problematic (use of baselines, use of datasets, use of evaluation measures). Recent developments suggest using different evaluation measures in the first place, proving that the F measure is flawed.\n\n\"Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection.\" Proceedings of the VLDB Endowment 15.8 (2022): 1697-1711.\n\n\"Volume under the surface: a new accuracy evaluation measure for time-series anomaly detection.\" Proceedings of the VLDB Endowment 15.11 (2022): 2774-2787.\n\n\n\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6mrpaWFqxp", "reviewer": "Reviewer_VFqz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This manuscript tried to answer the question in the community of time series anomaly detection: given an unlabeled dataset and a set of candidate anomaly models, how can we select the most accurate model? Therefore, this paper proposed a robust rank aggregation method with theoretical justifications. This unsupervised model selection method has been verified on multiple real-world datasets.", "summary_of_the_review": "Overall the idea of using rank aggregation for model selection for time series anomaly detection offers new insights, and the evaluation is solid.", "strength_and_weaknesses": "Pros:\n1. The proposed model selection criterion is simple and flexible to implement.\n2. Extensive experiments using various anomaly detection criteria have been performed.\n\nCons:\n1. In the numerical experiments, the proposed rank aggregation strategy is only applied to five pre-selected anomaly injection metrics. It is suggested to run the rank aggregation strategy on all the studied surrogate metric in order to fully showcase the capability of the proposed anomaly detection model selection criterion.\n2. The superiority of the proposed method in comparison to other metrics is not that significant.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0djXzsgrLzC", "reviewer": "Reviewer_kY2N", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an approach of combining unsupervised metrics to realize an effective selection of anomaly detection models for time-series data. The unsupervised are highly correlated with standard supervised anomaly detection performance metrics. Therefore, the proposed approach can detect anomalies in an unsupervised manner. Using datasets of various domains, the paper performed experiments to show the effectiveness of the proposed approach.", "summary_of_the_review": "More theoretical analyses are required for the proposed approach. \nThe computational time of each approach should be shown in the paper. \nThe superiority of the proposed approach in terms of accuracy is not so high to accept the paper.", "strength_and_weaknesses": "Strength:\n- Simple model to be easily implemented.\n- General approach to accommodate various anomaly detection approaches.\n- Extensive experiments are performed in the paper. \n\nWeakness:\n- The proposed approach is a combination of existing methods. \n- Technical depth of the proposed approach is not so deep.\n- The advantage of the proposed approach is not so significant compared to other approaches.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%