summaries: The authors of this paper investigate how generalization is affected by varying the training and testing data splits in deep metric learning (DML). Specifically, they create train/test splits (splitting on classes) which increase in difficulty (meaning that the distributions are more different) and evaluate DML generalization. To measure the gap between train and test distributions, they use FID with ResNet-50. Experimentally, they use popular benchmarks and the Recall@k metric to show that performance decreases as the train/test FID distances become larger. This, and other experiments, show that using a fixed train/test split can lead to misleading conclusions about generalization.

summaries: This paper proposed a new benchmark for deep metric learning under varying degree of distribution shift. First, it introduces a method for creating train/test split with increasing FID --- thereby increasing distribution shift between train and test. Second, various metric learning methods are compared under the benchmarks of varying difficulties.

summaries: The authors present a new benchmark for deep metric learning algorithms, particularly for zero-shot tasks, in order to reflect their generalization under out-of-distribution shifts performance. They propose a novel way of splitting train and test data with increasing difficulty(the gap(distribution shift) between train and test get higher). FID score is chosen to determine the distribution shift between train and test. After an initial split is chosen, the classes are exchanged between the train and test data to obtain a higher FID measure at each time iteratively. The authors suggest to use ROC curve to obtain a one single criteria, while keeping the results for each split in order to observe the performance based on task difficulty. They include experimental analysis on their proposed criteria and show results for some existing methods and architectures. The authors also analyze query-support framework in few-shot learning and its effect on the generalization performance.

summaries: This work proposes a new way to measure OOD performance of metric-learning algorithms. It introduces a proxy-metric for measuring ranking dataset generalization difficulty based on FID score. They construct several train/test splits of increasing difficulty based on this score. They show that splits constructed in such a way are well correlated with performance, thus validating the proposed proxy-metric of OOD generalization difficulty.  Several experiments are performed to assess the performance of modern metric learning methods. An AUC type score over all splits (difficulties) is proposed as an overall score for various methods. Finally, additional experiments that include increasing network capacity, using self-supervised pre-trained models, and fine-tuning with few-shot learning are presented.

abstractText: Deep Metric Learning (DML) aims to find representations suitable for zero-shot transfer to a priori unknown test distributions. However, common evaluation protocols only test a single, fixed data split in which train and test classes are assigned randomly. More realistic evaluations should consider a broad spectrum of distribution shifts with potentially varying degree and difficulty. In this work, we systematically construct train-test splits of increasing difficulty and present the ooDML benchmark to characterize generalization under out-of-distribution shifts in DML. ooDML is designed to probe the generalization performance on much more challenging, diverse train-to-test distribution shifts. Based on our new benchmark, we conduct a thorough empirical analysis of state-of-the-art DML methods. We find that while generalization tends to consistently degrade with difficulty, some methods are better at retaining performance as the distribution shift increases. Finally, we propose few-shot DML as an efficient way to consistently improve generalization in response to unknown test shifts presented in ooDML1.

authors:
Biagio Brattoli
Joseph Tighe
Fedor Zhdanov
Pietro Perona
Krzysztof Chalupka

title: Rethinking zeroshot video classification: End-to-end training for realistic applications

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Tom Brown
Benjamin Mann
Nick Ryder
Melanie Subbiah
Jared D Kaplan
Prafulla Dhariwal
Arvind Neelakantan
Pranav Shyam
Girish Sastry
Amanda Askell
Sandhini Agarwal
Ariel Herbert-Voss
Gretchen Krueger
Tom Henighan
Rewon Child
Aditya Ramesh
Daniel Ziegler
Jeffrey Wu
Clemens Winter
Chris Hesse
Mark Chen
Eric Sigler
Mateusz Litwin
Scott Gray
Benjamin Chess
Jack Clark
Christopher Berner
Sam McCandlish
Alec Radford
Ilya Sutskever
Dario Amodei

title: Language models are few-shot learners

venue: Advances in Neural Information Processing Systems,

authors:
Mathilde Caron
Ishan Misra
Julien Mairal
Priya Goyal
Piotr Bojanowski
Armand Joulin

title: Unsupervised learning of visual features by contrasting cluster assignments

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey Hinton

title: A simple framework for contrastive learning of visual representations

authors:
Weihua Chen
Xiaotang Chen
Jianguo Zhang
Kaiqi Huang

title: Beyond triplet loss: a deep quadruplet network for person re-identification

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Yinbo Chen
Xiaolong Wang
Zhuang Liu
Huijuan Xu
Trevor Darrell

title: A new meta-baseline for few-shot learning

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: ImageNet: A Large-Scale Hierarchical Image Database

venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Jiankang Deng
Jia Guo
Niannan Xue
Stefanos Zafeiriou

title: Arcface: Additive angular margin loss for deep face recognition

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: BERT: Pre-training of deep bidirectional transformers for language understanding

authors:
Alexey Dosovitskiy
Lucas Beyer
Alexander Kolesnikov
Dirk Weissenborn
Xiaohua Zhai
Thomas Unterthiner
Mostafa Dehghani
Matthias Minderer
Georg Heigold
Sylvain Gelly
Jakob Uszkoreit
Neil Houlsby

title: An image is worth 16x16 words: Transformers for image recognition at scale

venue: In International Conference on Learning Representations,

authors:
Yueqi Duan
Wenzhao Zheng
Xudong Lin
Jiwen Lu
Jie Zhou

title: Deep adversarial metric learning

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Logan Engstrom
Brandon Tran
Dimitris Tsipras
Ludwig Schmidt
Aleksander Madry

title: Exploring the landscape of spatial robustness

venue: Proceedings of the 36th International Conference on Machine Learning,

authors:
Istvan Fehervari
Avinash Ravichandran
Srikar Appalaraju

title: Unbiased evaluation of deep metric learning algorithms, 2019

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: Proceedings of the 34th International Conference on Machine Learning,

title: Deep metric learning with hierarchical triplet loss

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Jacob Goldberger
Geoffrey E Hinton
Sam Roweis
Russ R Salakhutdinov

title: Neighbourhood components analysis

authors:
Raia Hadsell
Sumit Chopra
Yann LeCun

title: Dimensionality reduction by learning an invariant mapping

authors:
Ben Harwood
BG Kumar
Gustavo Carneiro
Ian Reid
Tom Drummond

title: Smart mining for deep metric learning

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Kaiming He
Haoqi Fan
Yuxin Wu
Saining Xie
Ross Girshick

title: Momentum contrast for unsupervised visual representation learning

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Dan Hendrycks
Thomas Dietterich

title: Benchmarking neural network robustness to common corruptions and perturbations

authors:
Alexander Hermans
Lucas Beyer
Bastian Leibe

title: In Defense of the Triplet Loss for Person Re- Identification

venue: arXiv e-prints, page arXiv:1703.07737,

authors:
Martin Heusel
Hubert Ramsauer
Thomas Unterthiner
Bernhard Nessler
Sepp Hochreiter

title: Gans trained by a two time-scale update rule converge to a local nash equilibrium, 2017

authors:
Pierre Jacob
David Picard
Aymeric Histace
Edouard Klein

title: Metric learning with horde: High-order regularizer for deep embeddings

venue: In The IEEE Conference on Computer Vision and Pattern Recognition

authors:
Herve Jegou
Matthijs Douze
Cordelia Schmid

title: Product quantization for nearest neighbor search

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Sungyeon Kim
Dongwon Kim
Minsu Cho
Suha Kwak

title: Proxy anchor loss for deep metric learning

authors:
Wonsik Kim
Bhavya Goyal
Kunal Chawla
Jungmin Lee
Keunjoo Kwon

title: Attention-based ensemble for deep metric learning

authors:
Pang Wei Koh
Shiori Sagawa
Henrik Marklund
Sang Michael Xie
Marvin Zhang
Akshay Balsubramani
Weihua Hu
Michihiro Yasunaga
Richard Lanas Phillips
Irena Gao
Tony Lee
Etienne David
Ian Stavness
Wei Guo
Berton A. Earnshaw
Imran S. Haque
Sara Beery
Jure Leskovec
Anshul Kundaje
Emma Pierson
Sergey Levine
Chelsea Finn
Percy Liang

title: Wilds: A benchmark of in-the-wild distribution shifts, 2021

authors:
Alexander Kolesnikov
Lucas Beyer
Xiaohua Zhai
Joan Puigcerver
Jessica Yung
Sylvain Gelly
Neil Houlsby

title: Big transfer (bit): General visual representation learning

venue: Computer Vision – ECCV

authors:
Jonathan Krause
Michael Stark
Jia Deng
Li Fei-Fei

title: 3d object representations for fine-grained categorization

venue: In Proceedings of the IEEE International Conference on Computer Vision Workshops,

authors:
David Krueger
Ethan Caballero
Joern-Henrik Jacobsen
Amy Zhang
Jonathan Binas
Dinghuai Zhang
Remi Le Priol
Aaron Courville

title: Out-of-distribution generalization via risk extrapolation (rex), 2021

authors:
Kwonjoon Lee
Subhransu Maji
Avinash Ravichandran
Stefano Soatto

title: Meta-learning with differentiable convex optimization

authors:
Xudong Lin
Yueqi Duan
Qiyuan Dong
Jiwen Lu
Jie Zhou

title: Deep variational metric learning

venue: In The European Conference on Computer Vision (ECCV),

authors:
Weiyang Liu
Yandong Wen
Zhiding Yu
Ming Li
Bhiksha Raj
Le Song

title: Sphereface: Deep hypersphere embedding for face recognition

venue: IEEE Conference on Computer Vision and Pattern Recognition

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke Zettlemoyer
Veselin Stoyanov

title: Roberta: A robustly optimized bert pretraining approach, 2019

authors:
Timo Milbich
Miguel Bautista
Ekaterina Sutter
Björn Ommer

title: Unsupervised video understanding by reconciliation of posture similarities

venue: In Proceedings of the International Conference on Computer Vision (ICCV),

authors:
Timo Milbich
Omair Ghori
Björn Ommer

title: Unsupervised representation learning by discovering reliable image relations

venue: Pattern Recognition,

authors:
Timo Milbich
Karsten Roth
Homanga Bharadhwaj
Samarth Sinha
Yoshua Bengio
Björn Ommer
Joseph Paul Cohen

title: Diva: Diverse visual feature aggregation for deep metric learning

authors:
Timo Milbich
Karsten Roth
Biagio Brattoli
Björn Ommer

title: Sharing matters for generalization in deep metric learning

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
Ishan Misra
Laurens van der Maaten

title: Self-supervised learning of pretext-invariant representations

authors:
Yair Movshovitz-Attias
Alexander Toshev
Thomas K Leung
Sergey Ioffe
Saurabh Singh

title: No fuss distance metric learning using proxies

authors:
Kevin Musgrave
Serge Belongie
Ser-Nam Lim

title: A metric learning reality

authors:
Hyun Oh Song
Yu Xiang
Stefanie Jegelka
Silvio Savarese

title: Deep metric learning via lifted structured feature embedding

authors:
Michael Opitz
Georg Waltner
Horst Possegger
Horst Bischof

title: Bier-boosting independent embeddings robustly

title: Deep metric learning with bier: Boosting independent embeddings robustly

authors:
Qi Qian
Lei Shang
Baigui Sun
Juhua Hu
Hao Li
Rong Jin

title: Softtriple loss: Deep metric learning without triplet sampling

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV),

authors:
Alec Radford
Jong Wook Kim
Chris Hallacy
Aditya Ramesh
Gabriel Goh
Sandhini Agarwal
Girish Sastry
Amanda Askell
Pamela Mishkin
Jack Clark
Gretchen Krueger
Ilya Sutskever

title: Learning transferable visual models from natural language supervision

authors:
Aniruddh Raghu
Maithra Raghu
Samy Bengio
Oriol Vinyals

title: Rapid learning or feature reuse? towards understanding the effectiveness of maml

authors:
Benjamin Recht
Rebecca Roelofs
Ludwig Schmidt
Vaishaal Shankar

title: Do ImageNet classifiers generalize to ImageNet

authors:
Tal Ridnik
Emanuel Ben Baruch
Asaf Noy
Lihi Zelnik-Manor

title: Imagenet-21k pretraining for the masses

authors:
Karsten Roth
Biagio Brattoli
Bjorn Ommer

title: Mic: Mining interclass characteristics for improved metric learning

authors:
Karsten Roth
Timo Milbich
Bjorn Ommer

title: Pads: Policy-adapted sampling for visual similarity learning

authors:
Karsten Roth
Timo Milbich
Björn Ommer
Joseph Paul Cohen
Marzyeh Ghassemi

title: S2SD: simultaneous similarity-based self-distillation for deep metric learning

authors:
Karsten Roth
Timo Milbich
Samarth Sinha
Prateek Gupta
Bjorn Ommer
Joseph Paul Cohen

title: Revisiting training strategies and generalization performance in deep metric learning

authors:
Karsten Roth
Latha Pemula
Joaquin Zepeda
Bernhard Schölkopf
Thomas Brox
Peter V. Gehler

title: Towards total recall in industrial anomaly detection

authors:
Artsiom Sanakoyeu
Vadim Tschernezki
Uta Buchler
Bjorn Ommer

title: Divide and conquer the embedding space for metric learning

authors:
Florian Schroff
Dmitry Kalenichenko
James Philbin

title: Facenet: A unified embedding for face recognition and clustering

authors:
Jenny Seidenschwarz
Ismail Elezi
Laura Leal-Taixé

title: Learning intra-batch connections for deep metric learning, 2021

authors:
Samarth Sinha
Karsten Roth
Anirudh Goyal
Marzyeh Ghassemi
Hugo Larochelle
Animesh Garg

title: Uniform priors for data-efficient transfer, 2020

authors:
Jake Snell
Kevin Swersky
Richard Zemel

title: Prototypical networks for few-shot learning

title: Improved deep metric learning with multi-class n-pair loss objective

venue: In Advances in Neural Information Processing Systems,

authors:
Juan Luis Suárez
Salvador García
Francisco Herrera

title: A tutorial on distance metric learning: Mathematical foundations, algorithms and experiments, 2018

authors:
Mingxing Tan
Quoc Le

title: EfficientNet: Rethinking model scaling for convolutional neural networks

authors:
Eu Wern Teh
Terrance DeVries
Graham W. Taylor

title: Proxynca++: Revisiting and revitalizing proxy neighborhood component analysis

authors:
Yonglong Tian
Dilip Krishnan
Phillip Isola

title: Contrastive representation distillation

authors:
Yonglong Tian
Yue Wang
Dilip Krishnan
Joshua B. Tenenbaum
Phillip Isola

title: Rethinking few-shot image classification: A good embedding is all you need

authors:
Eleni Triantafillou
Richard Zemel
Raquel Urtasun

title: Few-shot learning through an information retrieval lens

authors:
C. Wah
S. Branson
P. Welinder
P. Perona
S. Belongie

title: The Caltech-UCSD Birds-200-2011 Dataset

venue: Technical Report CNS-TR-2011-001, California Institute of Technology,

authors:
Jian Wang
Feng Zhou
Shilei Wen
Xiao Liu
Yuanqing Lin

title: Deep metric learning with angular loss

authors:
Xun Wang
Xintong Han
Weilin Huang
Dengke Dong
Matthew R. Scott

title: Multi-similarity loss with general pair weighting for deep metric learning

authors:
Chao-Yuan Wu
R Manmatha
Alexander J Smola
Philipp Krahenbuhl

title: Sampling matters in deep embedding learning

authors:
Hong Xuan
Abby Stylianou
Robert Pless

title: Improved embeddings with easy positive triplet mining

venue: In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV),

authors:
Andrew Zhai
Hao-Yu Wu

title: Classification is a strong baseline for deep metric learning, 2018

authors:
Wenzhao Zheng
Zhaodong Chen
Jiwen Lu
Jie Zhou

title: Hardness-aware deep metric learning

heading: 1 Introduction

text:
Image representations that generalize well are the foundation of numerous computer vision tasks, such as image and video retrieval [61, 71, 54, 38, 1], face (re-)identification [57, 34, 8] and image classification [65, 4, 19, 40, 37]. Ideally, these representations should not only capture data within the training distribution, but also transfer to new, out-of-distribution (OOD) data. However, in practice, achieving effective OOD generalization is more challenging than in-distribution [28, 12, 21, 49, 31, 55]. In the case of zero-shot generalization, where train and test classes are completely distinct, Deep Metric Learning (DML) is used to learn metric representation spaces that capture and transfer visual similarity to unseen classes, constituting a priori unknown test distributions with unspecified shift. To approximate such a setting, current DML benchmarks use single, predefined and fixed data splits of disjoint train and test classes, which are assigned arbitrarily [71, 8, 61, 24, 11, 33, 74, 51, 54, 42, 26, 64, 58]. This means that (i) generalization is only evaluated on a fixed problem difficulty, (ii)
1Code available here: https://github.com/CompVis/Characterizing_Generalization_in_DML ∗ Equal contribution, alphabetical order, † equal supervision, x now at University of Tuebingen.
35th Conference on Neural Information Processing Systems (NeurIPS 2021), virtual.
generalization difficulty is only implicitly defined by the arbitrary data split, (iii) the distribution shift is not measured and (iv) cannot be not changed. As a result, proposed models can overfit to these singular evaluation settings, which puts into question the true zero-shot generalization capabilities of proposed DML models.
In this work, we first construct a new benchmark ooDML to characterize generalization under outof-distribution shifts in DML. We systematically build ooDML as a comprehensive benchmark for evaluating OOD generalization in changing zero-shot learning settings which covers a much larger variety of zero-shot transfer learning scenarios potentially encountered in practice. We systematically construct training and testing data splits of increasing difficulty as measured by their Frechet-Inception Distance [23] and extensively evaluate the performance of current DML approaches.
Our experiments reveal that the standard evaluation splits are often close to i.i.d. evaluation settings. In contrast, our novel benchmark continually evaluates models on significantly harder learning problems, providing a more complete perspective into OOD generalization in DML. Second, we perform a large-scale study of representative DML methods on ooDML, and study the actual benefit of underlying regularizations such as self-supervision [38], knowledge distillation [53], adversarial regularization [59] and specialized objective functions [71, 70, 8, 26, 54]. We find that conceptual differences between DML approaches play a more significant role as the distribution shift to the test split becomes harder. Finally, we present a study on few-shot DML as a simple extension to achieve systematic and consistent OOD generalization. As the transfer learning problem becomes harder, even very little in-domain knowledge effectively helps to adjust learned metric representation spaces to novel test distributions. We publish our code and train-test splits on three established benchmark sets, CUB2002011 [68], CARS196 [30] and Stanford Online Products (SOP) [43]. Similarly, we provide training and evaluation episodes for further research into few-shot DML. Overall, our contributions can be summarized as:
• Proposing the ooDML benchmark to create a set of more realistic train-test splits that evaluate DML generalization capabilities under increasingly more difficult zero-shot learning tasks.
• Analyzing the current DML method landscape under ooDML to characterize benefits and drawbacks of different conceptual approaches to DML.
• Introducing and examining few-shot DML as a potential remedy for systematically improved OOD generalization, especially when moving to larger train-test distribution shifts.

heading: 2 Related Work

text:
DML has become essential for many applications, especially in zero-shot image and video retrieval [61, 71, 51, 24, 1, 36]. Proposed approaches most commonly rely on a surrogate ranking task over tuples during training [62], ranging from simple pairs [17] and triplets [57] to higher-order quadruplets [5] and more generic n-tuples [61, 43, 22, 70]. These ranking tasks can also leverage additional context such as geometrical embedding structures [69, 8]. However, due to the exponentially increased complexity of tuple sampling spaces, these methods are usually also combined with tuple sampling objectives, relying on predefined or learned heuristics to avoid training over tuples that are too easy or too hard [57, 72] or reducing tuple redudancy encountered during training [71, 15, 18, 52]. More recent work has tackled sampling complexity through the usage of proxy-representations utilized as sample stand-ins during training, following a NCA [16] objective [41, 26, 64], leveraging softmax-style training through class-proxies [8, 73] or simulating intraclass structures [46].
Unfortunately, the true benefit of these proposed objectives has been put into question recently, with [54] and [42] highlighting high levels of performance saturation of these discriminative DML objectives on default benchmark splits under fair comparison. Instead, orthogonal work extending the standard DML training paradigm through multi-task approaches [56, 51, 39], boosting [44, 45], attention [27], sample generation [11, 33, 74], multi-feature learning [38] or self-distillation [53] have shown more promise with strong relative improvements under fair comparison [54, 38], however still only in single split benchmark settings. It thus remains unclear how well these methods generalize in more realistic settings [28] under potentially much more challenging, different train-to-test distribution shifts, which we investigate in this work.
3 ooDML: Constructing a Benchmark for OOD Generalization in DML
An image representation ϕ(x) learned on samples x ∈ Xtrain drawn from some training distribution generalizes well if can transfer to test data Xtest that are not observed during training. In the particular case of OOD generalization, the learned representation ϕ is supposed to transfer to samples Xtest which are not independently and identically distributed (i.i.d.) to Xtrain. A successful approach to learning such representations is DML, which is evaluated for the special case of zero-shot generalization, i.e. the transfer of ϕ to distributions of unknown classes [57, 71, 24, 8, 54, 42]. DML models aim to learn an embedding ϕ mapping datapoints x into an embedding space Φ, which allows to measure similarity between xi and xj as g(ϕ(xi), ϕ(xj)). Typically, g is a predefined metric, such as the Euclidean or Cosine distance and ϕ is parameterized by a deep neural network.
In realistic zero-shot learning scenarios, test distributions are not specified a priori. Thus, their respective distribution shifts relative to the training, which indicates the difficulty of the transfer learning problem, is unknown as well. To determine the generalization capabilities of ϕ, we would ideally measure its performance on different test distributions covering a large spectrum of distribution shifts, which we will also refer to as “problem difficulties" in this work. Unfortunately, standard evaluation protocols test the generalization of ϕ on a single and fixed train-test data split of predetermined difficulty, hence only allow for limited conclusions about zero-shot generalization.
To thoroughly assess and compare zero-shot generalization of DML models, we aim to build an evaluation protocol that resembles the undetermined nature of the transfer learning problem. In order to achieve this, we need to be able to change, measure and control the difficulty of train-test data splits. To this end, we present an approach to construct multiple train-test splits of measurably increasing difficulty to investigate out-of-distribution generalization in DML, which make up the ooDML benchmark. Our generated train-test splits resort to the established DML benchmark sets, and are subsequently used in Sec. 4 to thoroughly analyze the current state-of-the-art in DML. For future research, this approach is also easily applicable to other datasets and transfer learning problems.

heading: 3.1 Measuring the gap between train and test distributions

text:
To create our train-test data splits, we need a way of measuring the distance between image datasets. This is a difficult task due to high dimensionality and natural noise in the images. Recently, Frechet Inception Distance (FID) [23] was proposed to measure the distance between two image distributions by using the neural embeddings of an Inception-v3 network trained for classification on the ImageNet dataset. FID assumes that the embeddings of the penultimate layer follow a Gaussian distribution, with a given mean µX and covariance ΣX for a distribution of images X . The FID between two data distributions X1 and X2 is defined as:
d(X1,X2) ≜ ∥µX1 − µX2∥ 2 2 + Tr(ΣX1 +ΣX2 − 2(ΣX1ΣX2) 1 2 ) , (1)
In this paper, instead of the Inception network, we use the embeddings of a ResNet-50 classifier (Frechet ResNet Distance) for consistency with most DML studies (see e.g. [71, 64, 26, 56, 51, 38, 54, 58]). For simplicity, in the following sections we will still use the abbreviation FID.

heading: 3.2 On the issue with default train-test splits in DML

text:
To motivate the need for more comprehensive OOD evaluation protocols, we look at the split difficulty as measured by FID of typically used train-test splits and compare to i.i.d. sampling of training and test sets from the same benchmark. Empirical results in Tab. 1 show that commonly utilized DML
train-test splits are very close to in-distribution learning problems when compared to more out-ofdistribution splits in CARS196 and SOP (see Fig. 1). This indicates that semantic differences due to disjoint train and test classes, do not necessarily relate to actual significant distribution shifts between the train and test set. This also explains the consistently lower zero-shot retrieval performance on CUB200-2011 as compared to both CARS196 and SOP in literature [71, 70, 24, 54, 42, 38], despite SOP containing significantly more classes with fewer examples per class. In addition to the previously discussed issues of DML evaluation protocols, this further questions conclusions drawn from these protocols about the OOD generalization of representations ϕ.

heading: 3.3 Creating train-test splits of increasing difficulty

text:
Let Xtrain and Xtest denote the original train and test set of a given benchmark dataset D = Xtrain ∪ Xtest. To generate train-test splits of increasing difficulty while retaining the available data D and maintaining balance of their sizes, we exchange samples between them. To ensure and emphasize semantic consistency and unbiased data distributions with respect to image context unrelated to the target object categories, we swap entire classes instead of individual samples. Measuring distribution similarity based on FID, the goal is then to identify classes Ctrain ⊂ Xtrain and Ctest ⊂ Xtest whose exchange yields higher FID d(Xtrain,Xtest). To this end, similar to other works [33, 51, 38], we find resorting to an unimodal approximation of the intraclass distributions sufficient and approximate FID by only considering the class means and neglect the covariance in Eq. 1. We select Ctrain and Ctest as
C∗train = argmax Ctrain∈Xtrain ∥µCtrain − µXtrain∥2 − ∥µCtrain − µXtest∥2 (2)
C∗test = argmax Ctest∈Xtest ∥µCtest − µXtest∥2 − ∥µCtest − µXtrain∥2 (3)
where we measure distance to mean class-representations µXC . By iteratively exchanging classes between data splits, i.e. X t+1train = (X ttrain \ C∗train) ∪ C∗test and vice versa, we obtain a more difficult train-test split (X t+1train ,X t+1 test ) at iteration step t. Hence, we obtain a sequence of train-test splits XD = ((X 0train,X 0test), . . . , (X ttrain,X ttest), . . . , (X Ttrain,X Ttest)), with X 0train ≜ Xtrain and X 0test ≜ Xtest. Fig. 1 (columns 1-3) indeed shows that our FID approximation yields data splits with gradually increasing approximate FID scores with each swap until the scores cannot be further increased by swapping classes.
UMAP visualizations in the supplementary verify that the increase corresponds to larger OOD shifts. For CUB200-2011 and CARS196, we swap two classes per iteration, while for Stanford Online Products we swap 1000 classes due to a significantly higher class count. Moreover, to cover the overall spectrum of distribution shifts and ensure comparability between benchmarks we also reverse the iteration procedure on CUB200-2011 to generate splits minimizing the approximate FID while still maintaining disjunct train and test classes.
To further increase d(X Ttrain,X Ttest) beyond convergence (see Fig. 1) of the swapping procedure, we subsequently also identify and remove classes from both X Ttrain and X Ttest. More specifically, we remove classes Ctrain from X Ttrain that are closest to the mean of X Ttest and vice versa. For k steps, we successively repeat class removal as long as 50% of the original data is still maintained in these
additional train-test splits. Fig. 1 (rightmost) shows how splits generated through class removal progressively increase the approximate FID beyond what was achieved only by swapping. To analyze if the generated data splits are not inherently biased to the used backbone network for FID computation, we also repeat this procedure based on representations from different architectures, pretraining methods and datasets in the supplementary. Note, that comparison of absolute FID values between datasets may not be meaningful and we are mainly interested in distribution shifts within a given dataset distribution. Overall, using class swapping and removal we select splits that cover the broadest FID range possible, while still maintaining sufficient data. Hence, our splits are significantly harder and more diverse than the default splits.

heading: 4 Assessing the State of Generalization in Deep Metric Learning

text:
This section assesses the state of zero-shot generalization in DML via a large experimental study of representative DML methods on our ooDML benchmark, offering a much more complete and thorough perspective on zero-shot generalization in DML as compared to previous DML studies [13, 54, 42, 39].
For our experiments we use the three most widely used benchmarks in DML, CUB200-2011[68], CARS196[30] and Stanford Online Products[43]. For a complete list of implementation and training details see the supplementary if not explicitly stated in the respective sections. Moreover, to measure generalization performance, we resort to the most widely used metric for image retrieval in DML, Recall@k [25]. Additionally, we also evaluate results over mean average precision (mAP@1000) [54, 42], but provide respective tables and visualizations in the supplementary when the interpretation of results is not impacted.
The exact training and test splits ultimately utilized throughout this work are selected based on Fig. 1 to ensure approximately uniform coverage of the spectrum of distribution shifts within intervals ranging from the lowest (near i.i.d. splits) to the highest generated shift achieved with class removal. For experiments on CARS196 and Stanford Online Products, eight total splits were investigated, included the original default benchmark split. For CUB200-2011, we select nine splits to also account for benchmark additions with reduced distributional shifts. The exact FID ranges are provided in the supplementary. Training on CARS196 and CUB200-2011 was done for a maximum of 200 epochs following standard training protocols utilized in [54], while 150 epochs were used for the much larger SOP dataset. Additional training details if not directly stated in the respective sections can be found in the supplementary.

heading: 4.1 Zero-shot generalization under varying distribution shifts

text:
Many different concepts have been proposed in DML to learn embedding functions ϕ that generalize from the training distribution to differently distributed test data. To analyze the zero-shot transfer capabilities of DML models, we consider representative approaches making use of the following concepts: (i) surrogate ranking tasks and tuple mining heuristics (Margin loss with distance-based sampling [71] and Multisimilarity loss [70]), (ii) geometric constraints or class proxies (ArcFace [8], ProxyAnchor [26]), (iii) learning of semantically diverse features (R-Margin [54]) and selfsupervised training (DiVA [38]), adversarial regularization (Uniform Prior [59]) and (iv) knowledge self-distillation (S2SD [53]).
Fig. 2 (top) analyzes these methods for their generalization to distribution shifts the varying degrees represented in ooDML. The top row shows absolute zero-shot retrieval performance measured on Recall@1 (results for mAP@1000 can be found in the supplementary) with respect to the FID between train and test sets. Additionally, Fig. 2 (bottom) examines the relative differences of performance to the performance mean over all methods for each train-test split. Based on these experiments, we make the following main observations:
(i) Performance deteriorates monotonically with the distribution shifts. Independent of dataset, approach or evaluation metric, performance drops steadily as the distribution shift increases.
(ii) Relative performance differences are affected by train-test split difficulty. We see that the overall ranking between approaches oftentimes remains stable on the CARS196 and CUB2002011 datasets. However, we also see that particularly on a large-scale dataset (SOP), established proxy-based approaches ArcFace [8] (which incorporates additional geometric constraints) and ProxyAnchor [26] are surprisingly susceptible to more difficult distribution shifts. Both methods perform poorly compared to the more consistent general trend of the other approaches. Hence, conclusions on the generality of methods solely based on the default benchmarks need to be handled with care, as at least for SOP, performance comparisons reported on single (e.g. the standard) data splits do not translate to more general train-test scenarios.
(iii) Conceptual differences matter at larger distribution shifts While the ranking between most methods is largely consistent on CUB200-2011 and CARS196, their differences in performance becomes more prominent with increasing distribution shifts. The relative changes (deviation from the mean of all methods at the stage) depicted in Fig. 2 (bottom) clearly indicates that particular methods based on machine learning techniques such as self-supervision, feature diversity (DiVA, R-Margin) and self-distillation (S2SD) are among the best at generalizing in DML on more challenging splits while retaining strong performance on more i.i.d. splits as well.
While directly stating performance in dependence to the individual distribution shifts offers a detailed overview, the overall comparison of approaches is typically based on single benchmark scores. To further provide a single metric of comparison, we utilize the well-known Area-under-Curve (AUC) score to condense performance (either based on Recall@1 or mAP@1000) over all available distribution shifts into a single aggregated score indicating general zero-shot capabilities. This Aggregated Generalization Score (AGS) is computed based on the normalized FID scores of our splits to the interval [0, 1]. As Recall@k or mAP@k scores are naturally bounded to [0, 1], AGS is similarly bound to [0, 1] with higher being the better model. Our corresponding results are visualized in Fig. 3. Indeed, we see that AGS reflects our observations from Fig. 2, with self-supervision (DiVA)
and self-distillation (S2SD) generally performing best when facing unknown train-test shifts. Exact scores are provided in the supplementary.
4.2 Consistency of structural representation properties on ooDML
Roth et al. [54] attempts to identify potential drivers of generalization in DML by measuring the following structural properties of a representation ϕ: (i) the mean distance πinter between the centers of the embedded samples of each class, (ii) the mean distance πintra between the embedded samples within a class πintra, (iii) the ‘embedding space density’ measured as the ratio πratio = πintraπinter and (iv) ‘spectral decay’ ρ(Φ) measuring the degree of uniformity of singular values obtained by singular value decomposition on the training sample representations, which indicates the number of significant directions of variance. For a more detailed description, we refer to [54]. These metrics indeed are empirically shown to exhibit a certain correlation to generalization performance on the default benchmark splits. In contrast, we are now interested if these observations hold when measuring generalization performance on the ooDML train-test splits of varying difficulty.
We visualize our results in Fig. 4 for CUB200-2011 and SOP, with CARS196 provided in the supplementary. For better visualization we normalize all measured values obtained for both metrics (i)-(iv) and the recall performances (Recall@1) to the interval [0, 1] for each train-test split. Thus, the relation between structural properties and generalization performance becomes comparable across all train-test splits, allowing us to examine if superior generalization is still correlated to the structural properties of the learned representation ϕ, i.e. if the correlation is independent of the underlying distribution shifts. For a perfectly descriptive metric, one should expect to see heavy correlation between normalized metric and normalized generalization performance jointly across shifts. Unfortunately, our results show only a small indication of any structural metric being consistently correlated with generalization performance over varying distribution shifts. This is also observed when evaluating only against basic, purely discriminative DML objectives as was done in [54] for the default split, as well as when incorporating methods that extend and change the base DML training setup (such as DiVA [38] or adversarial regularization [59]).
This not only demonstrates that experimental conclusions derived from the analysis of only single benchmark split may not hold for overall zero-shot generalization, but also that future research should consider more general learning problems and difficulty to better understand the conceptual impact various regulatory approaches. To this end, our benchmark protocol offers more comprehensive experimental ground for future studies to find potential drivers of zero-shot generalization in DML.

heading: 4.3 Network capacity and pretrained representations

text:
A common way to improve generalization, as also highlighted in [54] and [42], is to select a stronger backbone architecture for feature extraction. In this section, we look at how changes in network capacity can influence OOD generalization across distribution shifts. Moreover, we also analyze the zero-shot performance of a diverse set of state-of-the-art pretraining approaches.
Influence of network capacity. In Fig. 5, we compare different members of the ResNet architecture family [20] with increasing capacity, each of which achieve increasingly higher performance on i.i.d. test benchmarks such as ImageNet [7], going from a small ResNet18 (R18) over ResNet50 (R50) to ResNet101 (R101) variants. As can be seen, while larger network capacity helps to some extent, we observe that performance actually saturates in zero-shot transfer settings, regardless of the DML approach and dataset (in particular also the large scale SOP dataset). Interestingly, we also observe that the performance drops with increasing distribution shifts are consistent across network capacity, suggesting that zero-shot generalization is less driven by network capacity but rather conceptual choices of the learning formulation (compare Fig. 2).
Generic representations versus Deep Metric Learning. Recently, self-supervised representation learning has taken great leaps with ever stronger models trained on huge amounts of image [29, 47] and language data [9, 35, 2]. These approaches are designed to learn expressive, well-transferring features and methods like CLIP [47] even prove surprisingly useful for zero-shot classification. We now evaluate and compare such representations against state-of-the-art DML models to understand if generic representations that are readily available nowadays actually pose an alternative to explicit application of DML. We select state-of-the-art self-supervision models SwAV [3] (ResNet50 backbone), CLIP [47] trained via natural language supervision on a large dataset of 400 million image and sentence pairs (VisionTransformer [10] backbone), BiT(-M) [29], which trains a ResNet50-V2 [29] on both the standard ImageNet [7] (1 million training samples) and the ImageNet-21k dataset [7, 50] with 14 million training samples and over 21 thousand classes, an EfficientNet-B0 [63] trained on ImageNet, and a standard baseline ResNet50 network trained on ImageNet. Note, that none of these representations has been additionally adapted to the benchmark sets, in contrast to the DML approaches which have been trained on the respective train splits.
The results presented in Fig. 6 show large performance differences of the pretrained representations, which are largely dependent on the test dataset. While BiT outperforms the DML state-of-the-art on CUB200-2011 without any finetuning, it significantly trails behind the DML models on the other
two datasets. On CARS196, only CLIP comes close to the DML approaches when the distribution shift is sufficiently large. Finally, on SOP, none of these models comes even close to the adapted DML methods. This shows how although representations learned by extensive pretraining can offer strong zero-shot generalization, their performance heavily depends on the target dataset and specific model. Furthermore, the generalization abilities notably depend on the size of the pretraining dataset (compare e.g. BiT-1k vs BiT-21k or CLIP), which is significantly larger than the number of training images seen by the DML methods. We see that only actual training on these datasets provides sufficiently reliable performance.

heading: 4.4 Few-shot adaption boosts generalization performance in DML

text:
Since distribution shifts can be arbitrarily large, the zero-shot transfer of ϕ can be ill-posed. Features learned on a training set Xtrain will not meaningfully transfer to test samples Xtest once they are sufficiently far from Xtrain, as also already indicated by Fig. 2. As a remedy few-shot learning [60, 67, 14, 48, 32, 6, 66] assumes few samples of the test distribution to to be available during training, i.e. adjusting a previously learned representation. While these approaches are typically explicitly trained for fast adaption to novel classes, we are now interested if similar adaptation of DML representations ϕ helps to bridge increasingly large distribution shifts.
To investigate this hypothesis, we follow the evaluation protocol of few-shot learning and use k representatives (also referred to as shots) of each class from a test set Xtest as a support set for finetuning the penultimate embedding network layer. The remaining test samples then represent the new test set to evaluate retrieval performance, also referred to as query set. For evaluation we perform 10 episodes, i.e. we repeat and average the adaptation of ϕ over 10 different, randomly sampled support and corresponding query sets. Independent of the DML model used for learning the original representation ϕ on Xtrain, adaptation to the support data is conducted using the Marginloss [71] objective with distance-based sampling [71] due to its faster convergence. This also ensures fair comparisons to the adaptation benefit to ϕ and also allows to adapt complex approaches like selfsupervision (DiVA [38]) to the small number of samples in the support sets.
Fig. 7 shows 2 and 5 shot results on CUB200-2011, with CARS196 available in the supplementary. SOP is not considered since each class is already composed of small number of samples. As we see, even very limited in-domain data can significantly improve generalization performance, with the benefit becoming stronger for larger distribution shifts. Moreover, we observe that weaker approaches like ArcFace [8] seem to benefit more than state-of-the-art methods like S2SD [53] or DiVA [38]. We presume this to be caused by their underlying concepts already encouraging learning of more robust and general features. To conclude, few-shot learning provides a substantial and reliable benefit when facing OOD learning settings where the shift is not known a priori.

heading: 5 Conclusion

text:
In this work we analyzed zero-shot transfer of image representations learned by Deep Metric Learning (DML) models. We proposed a systematic construction of train-test data splits of increasing
difficulty, as opposed to standard evaluation protocols that test out-of-distribution generalization only on single data splits of fixed difficulty. Based on this, we presented the novel benchmark ooDML and thoroughly assessed current DML methods. Our study reveals the following main findings: Standard evaluation protocols are insufficient to probe general out-of-distribution transfer: Prevailing train-test splits in DML are often close to i.i.d. evaluation settings. Hence, they only provide limited insights into the impact of train-test distribution shift on generalization performance. Our benchmark ooDML alleviates this issue by evaluating a large, controllable and measurable spectrum of problem difficulty to facilitate future research. Larger distribution shifts show the impact of conceptual differences in DML approaches: Our study reveals that generalization performance degrades consistently with increasing problem difficulty for all DML methods. However, certain concepts underlying the approaches are shown to be more robust to shifts than others, such as semantic feature diversity and knowledge-distillation. Generic, self-supervised representations without finetuning can surpass dedicated data adaptation: When facing large distribution shifts, representations learned only by self-supervision on large amounts of of unlabelled data are competitive to explicit DML training without any finetuning. However, their performance is heavily dependent on the data distribution and the models themselves. Few-shot adaptation consistently improves out-of-distribution generalization in DML: Even very few examples from a target data distribution effectively help to adapt DML representations. The benefit becomes even more prominent with increasing train-test distribution shifts, and encourages further research into few-shot adaptation in DML.
Funding transparency statement This research has been funded by the German Federal Ministry for Economic Affairs and Energy within the project “KI-Absicherung – Safe AI for automated driving” and by the German Research Foundation (DFG) within projects 371923335 and 421703927. Moreover, it was funded in part by a CIFAR AI Chair at the Vector Institute, Microsoft Research, and an NSERC Discovery Grant. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute www.vectorinstitute.ai/#partners.
Acknowledgements We thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting K.R; K.R. acknowledges his membership in the European Laboratory for Learning and Intelligent Systems (ELLIS) PhD program.

title: Characterizing Generalization under Out-Of-Distribution Shifts in Deep Metric Learning


summaries: This paper presents a data-driven approach to model selection for unsupervised outlier detection. The proposed method, METAOD takes a large number of training datasets with outlier labels and a pool of outlier detection models (methods plus their parameters) and uses a matrix factorization method to learn a model performance predictor, which, for given a test dataset, can predict/select a high performing model from the model pool without requiring test time model evaluation.  The performance of METAOD is evaluated with two implementations with the same pool of 300+ models (8 distinct outlier detection methods with different parameter configurations) but two different groups of training datasets.

summaries: The paper proposes a model selection approach called METAOD for outlier detection. METAOD maintains historical performances of various outlier detection models on different datasets, where the performance of a detection model on a new dataset is estimated based on the historical information. The setting is thus similar to meta-learning. METAOD is motivated by Collaborative Filtering, where the compatibility of a user (i.e., a dataset) and an item (i.e., a model) is estimated. A set of meta-features are crafted for charactering a dataset. Experiments show that METAOD benefits outlier detection model selection, compared with no model-selection baselines.

summaries: The paper proposes a method, named MetaOD, which for each input data set selects the most suited outlier detection model together with its relevant hyper-parameter values from a set of given models. The selection is done in a supervised manner. MetaOD works as follows. During the meta-training stage, it considers a set of $m$ models $M = \{M_1, ..., M_m\}$ and a set of $n$ data sets $D = \{D_1, ..., D_n\}$. Each model $M_i$ includes model architecture and model configuration (hyper-parameter values). MetaOD computes performance matrix $P$ where cell $P_{ij}$ is the performance of method $M_j$ on data set $D_i$. Then it learns a data matrix $U \in R^{n \times k}$ and a model matrix $V \in R^{m \times k}$ where $U_i \times V_j^T$ approximates $P_{ij}$. The functions learnt from $U$ and the matrix $V$ are then used during test time to choose the best model (together with its configuration) for each input data set.

summaries: This paper proposes a data-driven method, METAOD to unsupervised outlier model selection problem based on meta-learning. METAOD makes use of many detection models on historical outlier detection benchmark datasets and selects an effective model to be employed on a new dataset without. Authors introduce meta-features that quantify the outlying characteristics of a dataset. Experiments have shown the promise of METAOD. The authors have implemented an open-source tool METAOD and our meta-learning database for practical use.

abstractText: Given an unsupervised outlier detection task on a new dataset, how can we automatically select a good outlier detection algorithm and its hyperparameter(s) (collectively called a model)? In this work, we tackle the unsupervised outlier model selection (UOMS) problem, and propose METAOD, a principled, data-driven approach to UOMS based on meta-learning. The UOMS problem is notoriously challenging, as compared to model selection for classification and clustering, since (i) model evaluation is infeasible due to the lack of hold-out data with labels, and (ii) model comparison is infeasible due to the lack of a universal objective function. METAOD capitalizes on the performances of a large body of detection models on historical outlier detection benchmark datasets, and carries over this prior experience to automatically select an effective model to be employed on a new dataset without any labels, model evaluations or model comparisons. To capture task similarity within our meta-learning framework, we introduce specialized metafeatures that quantify outlying characteristics of a dataset. Extensive experiments show that selecting a model by METAOD significantly outperforms no model selection (e.g. always using the same popular model or the ensemble of many) as well as other meta-learning techniques that we tailored for UOMS. Moreover upon (meta-)training, METAOD is extremely efficient at test time; selecting from a large pool of 300+ models takes less than 1 second for a new task. We open-source1 METAOD and our meta-learning database for practical use and to foster further research on the UOMS problem.

authors:
S.M. Abdulrahman
P. Brazdil
J.N. van Rijn
J. Vanschoren

title: Speeding up algorithm selection using average ranking and active testing by introducing runtime

venue: Mach. Learn.,

title: Outlier Analysis

venue: Springer,

authors:
J. Bergstra
Y. Bengio

title: Random search for hyper-parameter optimization

title: Meta-learning for user cold-start recommendation

venue: IJCNN, pages 1–8. IEEE,

authors:
B. Bilalli
A. Abelló Gamazo
T. Aluja Banet

title: On the predictive power of meta-features in OpenML

venue: International Journal of Applied Mathematics and Computer Science, 27(4):697–712,

authors:
M.M. Breunig
H.-P. Kriegel
R.T. Ng
J. Sander

title: LOF: Identifying density-based local outliers

venue: SIGMOD Conference, pages 93–104. ACM, 2000. SIGMOD Record 29(2), June

authors:
E. Burnaev
P. Erofeev
D. Smolyakov

title: Model selection for anomaly detection

venue: ICMV, volume 9875 of SPIE Proceedings, page 987525. SPIE,

authors:
G.O. Campos
A. Zimek
J. Sander
R.J.G.B. Campello
B. Micenková
E. Schubert
I. Assent
M.E. Houle

title: On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study

venue: Data Min. Knowl. Discov., 30(4):891–927,

authors:
J. Chen
S. Sathe
C.C. Aggarwal
D.S. Turaga

title: Outlier detection with autoencoder ensembles

venue: SDM, pages 90–98. SIAM,

authors:
I. Davidson
S.S. Ravi

title: A framework for determining the fairness of outlier detection

venue: G. D. Giacomo, A. Catalá, B. Dilkina, M. Milano, S. Barro, A. Bugarín, and J. Lang, editors, ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, pages 2465–2472. IOS Press,

authors:
A. Emmott
S. Das
T.G. Dietterich
A. Fern
W.-K. Wong

title: Anomaly detection meta-analysis

authors:
X. Fan
Y. Yue
P. Sarkar
Y.X.R. Wang

title: A unified framework for tuning hyperparameters in clustering problems

authors:
M. Feurer
B. Letham
E. Bakshy

title: Scalable meta-learning for bayesian optimization

authors:
M. Feurer
J.T. Springenberg
F. Hutter

title: Initializing bayesian hyperparameter optimization via meta-learning

venue: AAAI, pages 1128–1135. AAAI Press,

authors:
L. Franceschi
M. Donini
P. Frasconi
M. Pontil

title: Forward and reverse gradient-based hyperparameter optimization

venue: ICML, volume 70 of Proceedings of Machine Learning Research, pages 1165–1173. PMLR,

authors:
J. Fréry
A. Habrard
M. Sebban
O. Caelen
L. He-Guelton

title: Efficient top rank optimization with gradient boosting for supervised anomaly detection

venue: ECML/PKDD, volume 10534, pages 20–35,

authors:
M. Goldstein
A. Dengel

title: Histogram-based outlier score (hbos): A fast unsupervised anomaly detection algorithm

venue: KI-2012: Poster and Demo Track, pages 59–63,

authors:
X. He
K. Zhao
X. Chu

title: Automl: A survey of the state-of-the-art

venue: Knowl. Based Syst., 212:106622,

authors:
F. Hutter
H.H. Hoos
K. Leyton-Brown

title: Sequential model-based optimization for general algorithm configuration

venue: C. A. C. Coello, editor, LION, volume 6683 of Lecture Notes in Computer Science, pages 507–523. Springer,

authors:
T. Idé
H. Kashima

title: Eigenspace-based anomaly detection in computer systems

venue: W. Kim, R. Kohavi, J. Gehrke, and W. DuMouchel, editors, KDD, pages 440–449. ACM,

authors:
K. Järvelin
J. Kekäläinen

title: Cumulated gain-based evaluation of IR techniques

venue: ACM Transactions on Information Systems (TOIS), 20(4):422–446,

authors:
D.R. Jones
M. Schonlau
W.J. Welch

title: Efficient global optimization of expensive black-box functions

venue: J. Global Optimization, 13(4):455–492,

authors:
S. Kadioglu
Y. Malitsky
M. Sellmann
K. Tierney

title: Isac - instance-specific algorithm configuration

venue: ECAI, volume 215 of Frontiers in Artificial Intelligence and Applications, pages 751–756. IOS Press,

authors:
H.-P. Kriegel
M. Schubert
A. Zimek

title: Angle-based outlier detection in high-dimensional data

venue: Y. Li, B. Liu, and S. Sarawagi, editors, KDD, pages 444–452. ACM,

authors:
K. Lai
D. Zha
G. Wang
J. Xu
Y. Zhao
D. Kumar
Y. Chen
P. Zumkhawaka
M. Wan
D. Martinez
X. Hu

title: TODS: an automated time series outlier detection system

venue: Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 16060–16062. AAAI Press,

authors:
H. Lee
J. Im
S. Jang
H. Cho
S. Chung

title: MeLU: Meta-learned user preference estimator for cold-start recommendation

venue: KDD, pages 1073–1082. ACM,

authors:
L. Li
K.G. Jamieson
G. DeSalvo
A. Rostamizadeh
A. Talwalkar

title: Hyperband: A novel bandit-based approach to hyperparameter optimization

authors:
L. Li
M.L. Littman
T.J. Walsh
A.L. Strehl

title: Knows what it knows: a framework for self-aware learning

authors:
Y. Li
Z. Chen
D. Zha
K. Zhou
H. Jin
H. Chen
X. Hu

title: Autood: Neural architecture search for outlier detection

venue: 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19-22, 2021, pages 2117–2122. IEEE,

authors:
Y. Li
D. Zha
P.K. Venugopal
N. Zou
X. Hu

title: Pyodds: An end-to-end outlier detection system with automated machine learning

venue: A. E. F. Seghrouchni, G. Sukthankar, T. Liu, and M. van Steen, editors, Companion of The 2020 Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, pages 153–157. ACM / IW3C2,

authors:
F.T. Liu
K.M. Ting
Z.-H. Zhou

title: Isolation forest

venue: ICDM, pages 413–422. IEEE Computer Society,

authors:
M. Misir
M. Sebag

title: Alors: An algorithm recommender system

authors:
M. Nikolic
F. Maric
P. Janicic

title: Simple algorithm portfolio for sat

title: Loda: Lightweight on-line detector of anomalies

authors:
S. Ramaswamy
R. Rastogi
K. Shim

title: Efficient algorithms for mining outliers from large data sets

venue: W. Chen, J. F. Naughton, and P. A. Bernstein, editors, SIGMOD Conference, pages 427–438. ACM, 2000. SIGMOD Record 29(2), June

authors:
S. Rayana
L. Akoglu

title: Less is more: Building selective anomaly ensembles

venue: ACM Trans. Knowl. Discov. Data, 10(4):42:1–42:33,

authors:
B. Schölkopf
J.C. Platt
J. Shawe-Taylor
A.J. Smola
R.C. Williamson

title: Estimating the support of a high-dimensional distribution

venue: Neural Computation, 13(7):1443–1471, July

authors:
B. Schölkopf
R.C. Williamson
A.J. Smola
J. Shawe-Taylor
J.C. Platt

title: Support vector method for novelty detection

venue: NIPS, pages 582–588. The MIT Press,

authors:
G. Shafer
V. Vovk

title: A tutorial on conformal prediction

venue: J. Mach. Learn. Res., 9:371–421,

authors:
B. Shahriari
K. Swersky
Z. Wang
R.P. Adams
N. de Freitas

title: Taking the human out of the loop: A review of bayesian optimization

venue: Proc. IEEE,

authors:
R.E. Shawi
M. Maher
S. Sakr

title: Automated machine learning: State-of-the-art and open challenges

authors:
S. Shekhar
N. Shah
L. Akoglu

title: Fairod: Fairness-aware outlier detection

venue: M. Fourcade, B. Kuipers, S. Lazar, and D. K. Mulligan, editors, AIES ’21: AAAI/ACM Conference on AI, Ethics, and Society, Virtual Event, USA, May 19-21, 2021, pages 210–220. ACM,

title: Cyclical learning rates for training neural networks

venue: WACV, pages 464–472. IEEE Computer Society,

authors:
D.H. Stern
H. Samulowitz
R. Herbrich
T. Graepel
L. Pulina
A. Tacchella

title: Collaborative expert portfolio management

venue: AAAI. AAAI Press,

authors:
J. Tang
Z. Chen
A.W. Fu
D.W. Cheung

title: Enhancing effectiveness of outlier detections for low density patterns

venue: PAKDD, volume 2336 of Lecture Notes in Computer Science, pages 535–548,

authors:
D.M.J. Tax
R.P.W. Duin

title: Support vector data description

authors:
S. Vaithyanathan
B. Dom

title: Generalized model selection for unsupervised learning in high dimensions

venue: NIPS, pages 970–976. The MIT Press,

authors:
L. van der Maaten
G. Hinton

title: Visualizing high-dimensional data using t-sne

venue: J. of Mach. Lear. Res.,

title: Meta-learning

venue: Automated Machine Learning, pages 35–61. Springer,

authors:
M. Vartak
A. Thiagarajan
C. Miranda
J. Bratman
H. Larochelle

title: A meta-learning perspective on cold-start recommendations for items

venue: NeurIPS, pages 6904–6914,

authors:
M. Wistuba
N. Schilling
L. Schmidt-Thieme

title: Learning hyperparameter optimization initializations

venue: DSAA, pages 1–10. IEEE,

title: Scalable gaussian process-based transfer surrogates for hyperparameter optimization

authors:
D.H. Wolpert
W.G. Macready

title: No free lunch theorems for optimization

venue: IEEE Trans. Evolutionary Computation, 1(1):67–82,

authors:
Y. Xiao
H. Wang
L. Zhang
W. Xu

title: Two methods of selecting gaussian kernel parameters for one-class SVM and their application to fault detection

venue: Knowl. Based Syst., 59:75–84,

authors:
L. Xu
F. Hutter
J. Shen
H.H. Hoos
K. Leyton-Brown

title: Satzilla2012: Improved algorithm selection based on cost-sensitive classification models

venue: Proceedings of SAT Challenge, pages 57–58,

authors:
C. Yang
Y. Akimoto
D.W. Kim
M. Udell

title: OBOE: collaborative filtering for AutoML model selection

venue: KDD, pages 1173–1183. ACM,

authors:
L. Yang
A. Shami

title: On hyperparameter optimization of machine learning algorithms: Theory and practice

venue: Neurocomputing, 415:295–316,

authors:
Q. Yao
M. Wang
H.J. Escalante
I. Guyon
Y. Hu
Y. Li
W. Tu
Q. Yang
Y. Yu

title: Taking human out of learning applications: A survey on automated machine learning

authors:
T. Yu
H. Zhu

title: Hyper-parameter optimization: A review of algorithms and applications

authors:
Y. Zhao
X. Hu
C. Cheng
C. Wang
C. Wan
W. Wang
J. Yang
H. Bai
Z. Li
C. Xiao
Y. Wang
Z. Qiao
J. Sun
L. Akoglu

title: SUOD: Accelerating large-scale unsupervised heterogeneous outlier detection

venue: Proceedings of Machine Learning and Systems,

authors:
Y. Zhao
Z. Nasrullah
Z. Li

title: PyOD: A python toolbox for scalable outlier detection

authors:
Z. Zheng
J. Yang
Y. Zhu

title: Initialization enhancer for non-negative matrix factorization

venue: Eng. Appl. Artif. Intell., 20(1):101–110,

authors:
C. Zhou
R.C. Paffenroth

title: Anomaly detection with robust deep autoencoders

venue: KDD, pages 665–674. ACM,

heading: 1 Introduction

text:
The lack of a universal learning model that performs well on all problem instances is well recognized [53]. Therefore, effort has been directed toward building a toolbox of various models and algorithms, which has given rise to the problem of algorithm selection and hyperparameter tuning (i.e., model selection). The same problem applies to outlier detection (OD); a long list of detectors has been developed in the last decades [2], with no universal “winners” [8].
In supervised learning, model selection can be done via performance evaluation of each trained model on labeled hold-out data. In contrast, unsupervised OD does not have access to any labels, nor is there a universal objective function that could guide model selection (cf. clustering where a loss function enables model comparison). Unsupervised model selection for OD is challenging exactly because both model evaluation and comparison are not feasible—which renders any trial-and-error techniques like grid search or iterative strategies like Bayesian hyperparameter optimization [57] inapplicable. Consequently, there has been no principled work on unsupervised outlier model selection—rather, the choice of a model for a new task (or dataset) remains “a black art”. A typical approach is to use popular OD algorithms, like LOF [6] and iForest [31] (often with default hyperparameters) which are shown to be competitive on average on many benchmark datasets. However, as noted earlier, none of
1Code available at URL: https://github.com/yzhao062/UOMS
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
these methods can universally outperform others on all tasks [8]. We argue that model selection is exactly how one can “break the performance ceiling” for OD.
In this work, we tackle the unsupervised outlier model selection (UOMS) problem systematically. To that end, we introduce (to the best of our knowledge) the first UOMS approach that selects an effective model to be employed on a new detection task without any model evaluation (using labels) or model comparison (via loss criteria). Our proposed method, called METAOD, is based on meta-learning, and stands on the prior performances of a large collection of existing detection models on an extensive corpora of historical outlier detection benchmark datasets. In a nutshell, the idea is to estimate a candidate model’s performance on the new task (with no labels) based on its prior performance on similar historical tasks. We remark that METAOD is strictly a model selection technique – that picks one model (a detector and its associated hyperparameter(s)) from a pool of (existing) candidate models – and not yet-another outlier detection algorithm itself.
In leveraging meta-learning, we establish a connection between the UOMS problem and the cold-start problem in collaborative filtering (CF), where the new task in UOMS is akin to a new user in CF (with no available evaluations, hence cold-start) and the model space is analogous to the item-set. Differently, OD necessitates the identification of a single best model (i.e., top-1 rank), whereas CF typically operates in a top-k setting. In CF, future recommendations can be improved based on user feedback which is not applicable to OD. Moreover, METAOD requires the effective learning of task similarities based on characteristic dataset features (namely, meta-features) that capture the outlying properties within a dataset, whereas user features (location, age, etc.) in CF may be readily available.
In summary, the key contributions of this work include the following:
• First Approach to Unsupervised Outlier Model Selection: We propose METAOD, (to our knowledge) the first effort on unsupervised model selection for OD tasks. Notably, given a new dataset (i.e., at test time), it does not rely on any ground-truth labels for model evaluation or any loss or heuristic criterion for model comparison. METAOD stands on meta-learning in principle, and historical collections of outlier models and benchmark datasets in practice.
• Problem Formulation: We establish a correspondence between UOMS and CF under cold-start, where the new task “better likes” a model that performs better on similar historical tasks.
• Specialized Meta-features: We design novel meta-features to capture the outlying characteristics in a dataset toward effectively quantifying task similarity specifically among OD tasks.
• Effectiveness and Efficiency: Through extensive experiments on two benchmark testbeds that we have constructed, we show that selecting a model by METAOD for each given task significantly outperforms always using a popular model like iForest, as well as other possible meta-learning approaches that we tailored for UOMS. Moreover, METAOD incurs negligible run-time overhead (<1 second) at test time. • Open-source Platform: We open-source1 METAOD and our meta-learning database for the community to use it for UOMS in practice, and to extend it with new datasets and models. We expect the growth of the database would make meta-learning based approaches, like METAOD, more powerful and also help foster further research on this new direction to an important problem.

heading: 2 Related Work

heading: 2.1 Model Selection for Outlier Detection (OD)

text:
Most outlier mining work have focused on developing new, better methods for detection on different types of data [2]. In comparison, there are only a few work on the outlier model selection problem –which detector and hyperparameter(s) to use on a new task– all of which require some labeled data. Recent work include AutoOD [29] that focuses on automatic neural architecture search, however, it is limited to deep autoencoder based detection, and more importantly it relies on hold-out labeled data for evaluation. Similarly, PyODDS [30] and TODS [25] both require ground truth labels.
To our knowledge, there is no existing work on the general unsupervised outlier model selection (UOMS) problem, which is considerably more challenging, as (1) model evaluation is infeasible due to the lack of any ground truth labels, and (2) model comparison of different heterogeneous detectors is infeasible due to the lack of a universal OD loss function.
We note that some OD methods do have a loss function; e.g. auto-encoders [9, 63] aim to minimize reconstruction error for modeling the inliers, and one-class classification (OCSVM [38], SVDD [46], etc.) aims to maximize margin to the origin or minimize the radius of a data-enclosing hyperball. There is also work on model selection for one-class models [7, 54], however, those are limited to this specific family of methods and do not apply in the general case. Our proposed METAOD is not limited to one specific model family, but can select among any (heterogeneous) set of detectors.

heading: 2.2 Model Selection in ML, AutoML, Meta-Learning

text:
Model selection refers to the process of algorithm selection and/or hyperparameter optimization (HO). With the advent of complex (e.g. deep) models, HO in high dimensions has become impractical to be human-powered [59]. As such, automating ML pipelines has seen a surge of attention [18]. Meta-learning has been a key contributor to the AutoML effort [41, 49, 58].
Supervised Model Selection: Most existing work focus on the supervised setting, and use hold-out data with labels. Randomized [3], bandit-based [27], and Bayesian optimization (BO) techniques [40] are various state-of-the-art (SOTA) approaches to HO. Specifically sequential model-based BO [19, 22] evaluates hold-out performance at various initial hyperparameter configurations (HC), where a (smooth) surrogate function is fit to the resulting 〈HC, performance〉 pairs, which is then used to strategically query other HCs, e.g., via hyper-gradient based search [15]. Meta-learning has also been employed [13, 52], e.g., to find promising initialization for (i.e. warm-starting) BO [14, 51].
Note that all of these approaches rely on multiple model evaluations (i.e., performance queries) for various HCs, and hence cannot be applied to the unsupervised outlier model selection problem.
Unsupervised Model Selection: Unsupervised ML tasks (e.g., clustering) poses additional challenges for model selection [12, 47]. Nonetheless, those exhibit established objective criteria that enable model comparison, unlike OD. For example, BO methods still apply where the surrogate can be trained on 〈HC, objective value〉 pairs, for which meta-learning can provide favorable priors. Task-independent meta-learning [1], that simply identifies the globally best model on historical tasks, applies to the unsupervised setting and hence OD. This can be refined by identifying the best model on not all, but similar tasks, where task similarity is measured in the meta-feature space via clustering [23] or nearest neighbors [33]. This type of similarity-based recommendations points to a connection between algorithm selection and collaborative filtering (CF), first recognized by Stern et al. [44]. The most related to UOMS is CF under cold start, where evaluations are not-available (in our case, infeasible) for a new user (in our case, task). There have been a number of work using meta-learning for the cold-start recommendation problem [4, 26, 50], and vice versa, using CF solutions for ML algorithm selection [32, 56]. We tailor these to UOMS and compare to METAOD in the experiments.

heading: 3 Unsupervised Outlier Model Selection via Meta-learning

heading: 3.1 Problem Statement

text:
We consider the model selection problem for unsupervised outlier detection, which we refer to as UOMS (unsupervised outlier model selection) hereafter. Given a new dataset, without any labels, the problem is to select both (i) a detector/algorithm and (ii) its associated hyperparameter(s) (HP). The former is a discrete choice, given the finite set of existing detection algorithms. The latter is continuous, and hence induces infinitely many candidate models.
Under certain assumptions, such as performance changing smoothly in the HP space, a HP configuration can be selected iteratively based on evaluations on several other carefully-chosen configurations. Importantly however, OD is not amenable for such iterative search over models—evaluations are not possible due to the lack of labels and absence of a universal objective criterion. The selection of a model, therefore, is to be done without building or evaluating any model on the new dataset. Given this constraint, we discretize the HP space for each candidate detector to make the search space tractable, which induces a finite pool of models denoted M = {M1, . . . ,Mm}. Each model M ∈M can be seen as a {detector, configuration} pair, where the configuration depicts a specific set of values for the detector’s HP(s). (See Appendix A for details.) Then, the UOMS problem is stated as follows:
Problem 1 (Unsupervised Outlier Model Selection (UOMS)) Given a new input dataset (i.e., detection task) Dtest = (Xtest) without any labels, Select a model M ∈M to employ on Xtest.
3.2 Proposed METAOD
In this work we consider the UOMS problem and propose a meta-learning based solution, leveraging past experience on historical detection tasks. As such, our METAOD relies on
• a collection of historical outlier detection datasets Dtrain = {D1, . . . ,Dn}, namely, a meta-train database with ground truth labels, i.e., {Di = (Xi,yi)}ni=1, and • the historical performances of the pool of candidate models, M, on the meta-train datasets. We denote by P ∈ Rn×m the performance matrix, where Pij corresponds to the j-th model Mj’s performance2 on the i-th meta-train dataset Di.
Note that model performance can be evaluated on the historical meta-train datasets as they contain ground truth labels, which however is not the case for any newcoming task at test time.
Our METAOD consists of two-phases: offline (meta-)training of the meta-learner on Dtrain, and online prediction that enables unsupervised model selection at test time for Dtest. Arguably, the running time of the offline phase is not critical. In contrast, model selection for a newcoming task should incur small run-time overhead, as it precedes the actual building of the selected OD model. Fig. 1 summarizes the process and the major components of METAOD, where we highlight the components transferred from offline (meta-learning) to online stage (model selection) in blue. We also provide the detailed steps of METAOD in pseudo-code, for both meta-training (offline) and model selection (online), in Appendix D Algo. 1.

heading: 3.2.1 (Meta-)Training (Offline)

text:
In principle, meta-learning carries over prior experience on a set of historical tasks to “do better” on a new task. Such improvement can be unlocked only if the new task resembles and thus can build on at least some of the historical tasks (such as learning ice-skating given prior experience with roller-blading), rather than representing completely unrelated phenomena. This entails defining an effective way to capture task similarity between an input task and the historical tasks at hand.
In machine learning, similarity between meta-train and test datasets are quantified through characteristic features of a dataset, also known as meta-features. Those typically capture statistical properties of the data distributions. (See survey [49] for various types of meta-features.)
To capture prior experience, METAOD first constructs the performance matrix P by running/building and evaluating all the m models in our defined model space M on all the n meta-train datasets Dtrain.3 To capture task similarity, it then extracts a set of d meta-features from each meta-train dataset, denoted by M = ψ({X1, . . . ,Xn}) ∈ Rn×d where ψ(·) depicts the feature extraction module. We defer the details on the meta-feature specifics to §3.3.
At this stage, it is easy to recognize the connection between the UOMS and the collaborative filtering (CF) under cold start problems. Simply put, meta-train datasets are akin to existing users in CF that have prior evaluations on a set of models that are akin to the item-set in CF. The test task is akin to a newcoming user with no prior evaluations (and in our case, no possible future evaluation either), which however exhibits some pre-defined features.
Capitalizing on this connection, we take a matrix factorization based approach where P is approximated by the dot product of what-we-call dataset matrix U ∈ Rn×k and model matrix V ∈ Rm×k. The intent is to capture the inherent dataset-to-model affinity via the dot product similarity in the k-dimensional latent space, such that Pij ≈ UiVjT where matrix subscript denotes the row. What loss criterion is suitable for the factorization? In CF the typical goal is top-k item recommendation. In METAOD, we aim to select the model with the best performance on a task which demands top-1 optimization. Therefore, we discard least squares and instead optimize the rank-based (row- or
2Area under the precision-recall curve (Average Precision or AP); can be substituted with any other measure. 3Note that this step takes considerable compute-time, which however amortizes to “do better” for future
tasks. To this effect, we open-source our trained meta-learner to be readily deployed.
dataset-wise) discounted cumulative gain (DCG) [21],
max U,V n∑ i=1 DCGi(Pi,UiVT ) . (1)
The factorization is solved via alternating optimization, where initialization plays an important role for such non-convex problems. We find that initializing U, denoted U(0), based on meta-features facilitates stable training, potentially by hinting at inherent similarities among datasets as compared to random initialization. Specifically, an embedding function φ(·) is used to set U(0) := φ(M) for φ : Rd 7→ Rk, k < d. Details on objective criteria and optimization are deferred to §3.4. By construction, matrix factorization is transductive. On the other hand, we would need Utest to be able to estimate performances of the model set M on a new dataset Xtest. To this end, one can learn an (inductive) multi-output regression model that maps the meta-features onto the latent features. We simplify by learning a regression function f : Rk 7→ Rk that maps the (lower dimensional) embedding features φ(M) (which are also used to initialize U) onto the final optimized U. Note that this requires an inductive embedding function φ(·) to be applicable to newcoming datasets. In implementation, we use PCA for φ(·) and a random forest regressor for f(·) although METAOD is flexible to accommodate any others provided they are inductive.
Remark: METAOD improves over the existing methods that use CF in machine learning model selection (see §2.2) in two aspects. First, METAOD builds specialized landmarker features tailored for capturing outlying characteristics of a dataset, while the existing ML model selection mainly uses generic statistical features (see §3.3). Second, METAOD uses a customized (backpropagatable/smooth) rank-based loss in CF for more effective top-1 optimization (see §3.4), while existing approaches mainly leverage mean squared loss (MSE).

heading: 3.2.2 Prediction for Unsupervised Model Selection (Online)

text:
Meta-training stage yields the estimated functions ψ(·), φ(·), and f(·) as well as the model matrix V ∈ Rm×k, which we save for test time (See Fig. 1). Given a new dataset Xtest for OD, METAOD first computes the corresponding meta-features as Mtest := ψ(Xtest) ∈ Rd. Those are then embedded via φ(Mtest) ∈ Rk, which are regressed to obtain the latent features, i.e., Utest := f(φ(Mtest)) ∈ Rk. Model set performances are predicted as Ptest := UtestVT ∈ Rm. Finally, the model with the largest predicted performance is outputted as the selected model, that is,
argmax j 〈 f(φ(ψ(Xtest))),Vj 〉 . (2)
Remark: Notice that model selection by Eq. (2) for a newcoming dataset is solely based on its meta-features and other pre-trained components from meta-learning. It does not rely on ground-truth labels or any OD model evaluations, therefore, METAOD provides unsupervised outlier model selection. Further, it does not require choosing or tuning any values at test time, and hence is fully automatic. In terms of computation, test-time embedding by φ (PCA) and regression by f (regression trees) take near-constant time given the small number of meta-features, embedding dimensions, and trees of fixed depth. Moreover, we use meta-features with computational complexity linear in the dataset size as we describe next.

heading: 3.3 Meta-Features for Outlier Detection

text:
A key part of METAOD is the extraction of meta-features that capture the important characteristics of an arbitrary dataset. Existing outlier detection models have different methodological designs (e.g., density, distance, angle, etc. based) and different assumptions around the topology of outliers (e.g., global, local, clustered). As a result, we expect different models to perform differently depending on the input dataset and the nature of outliers it exhibits—hence no “winner”. In our meta-learning approach, the goal is to identify the datasets in the meta-train database that exhibit similar characteristics to a given test dataset, and focus on models that do well on those similar datasets. This is akin to recommending to a new user those items liked by similar users.
To this end, we extract meta-features that can be organized into two categories: (1) statistical features, and (2) landmarker features. Broadly speaking, the former captures statistical properties of the underlying data distributions; e.g., min, max, variance, skewness, covariance, etc. of the features and
feature combinations. (See Appendix B Table 3 for the complete list.) These kinds of meta-features have been commonly used in the AutoML literature [5].
The optimal set of meta-features has been shown to be application-dependent [49]. Therefore, perhaps more important are the landmarker features, which are problem-specific, and aim to capture the outlying characteristics of a dataset. The idea is to apply a few of the fast, easy-to-construct OD models on a dataset and extract features from (i) the structure of the estimated OD model, and (ii) its output outlier scores. For the OD-specific landmarkers, we use four OD algorithms: iForest [31], HBOS [17], LODA [34], and PCA [20] (reconstruction error as outlier score). We choose the four OD algorithms due to their efficiency and diversity (as a group). First, they are all fast algorithms and able to handle large, high-dimensional datasets [2]. This makes the meta-feature generation efficient and practical in the real world. Second, these four OD algorithms as a group show decent diversity (i.e., internal detection mechanism) to capture rich outlying characteristics. Consider iForest as an example. It creates a set of what-is-called extremely randomized trees that define the model structure, from which we extract structural features such as average horizontal and vertical tree imbalance. As another example, LODA builds on random-projection histograms from which we extract features such as entropy. In addition, based on the list of outlier scores from these models, we compute features such as dispersion, max consecutive gap in the sorted order, etc. We elaborate on the details of the landmarker features in Appendix B.2.

heading: 3.4 Meta-Learning Objective and Training

heading: 3.4.1 Rank-based Criterion

text:
A typical loss criterion for matrix factorization is the mean squared error (MSE), a.k.a. the Frobenius norm of the error matrix P−UVT . While having nice properties from an optimization perspective, MSE does not (at least directly) concern with the ranking quality. In contrast, our goal is to rank the models for each dataset row-wise, as model selection concerns with picking the best possible model to employ. Therefore, we use a rank-based criterion called DCG from the information retrieval literature [21]. For a given ranking, DCG is given as
DCG = ∑ r brel_r − 1 log2(r + 1)
(3)
where rel_r depicts the true relevance of the item ranked at the r-th position and b is a scalar (typically set to 2). In our setting, we use the performance of a model to reflect its true relevance to a dataset. As such, DCG for dataset i is re-written as
DCGi = m∑ j=1 bPij − 1 log2(1 + ∑m k=1 1[P̂ij ≤ P̂ik])
(4)
where P̂ij = 〈Ui,Vj〉 is the predicted performance that dictates the ranking order. Intuitively, ranking high-performing models at the top leads to higher DCG, and a larger b increases the emphasis on the quality of models at the higher rank positions.
A challenge with DCG is that it is not differentiable, unlike MSE, as it involves ranking/sorting. Specifically, the sum term in the denominator of Eq. (4) uses the (nonsmooth) indicator function to obtain the position of model j as ranked by the estimated performances. We circumvent this challenge by replacing the indicator function by the (smooth) sigmoid approximation [16] as follows.
DCGi ≈ sDCGi = m∑ j=1 bPij − 1 log2(1 + ∑m k=1 σ(P̂ik − P̂ij))
(5)

heading: 3.4.2 Initialization & Alternating Optimization

text:
Overall we optimize the smoothed criterion, sDCG, over all meta-train datasets Dtrain = {Di}ni=1 as
min U,V L = − n∑ i=1 sDCGi(Pi,UiVT ) , (6)
by alternatingly solving for U as we fix V (and vice versa) by gradient descent. We initialize U by leveraging the meta-features, which are embedded to a space with the same size as U. By capturing the latent similarities among the datasets, such an initialization not only accelerates convergence [62] but also facilitates convergence to a better local optimum. V is initialized from a unit Normal.
As we aim to maximize the total dataset-wise DCG, we make a pass over meta-train datasets one by one at each epoch. For brevity, we give the gradients for Ui and Vj in Eq.s (7) and (8), respectively.
∂L
∂Ui = ln (2) m∑ j=1  bPij − 1 βij ln 2 (βij) ∑ k 6=j σ(wijk)(1− σ(wijk))(Vk −Vj)  (7) ∂L
∂Vj = − ln (2) m∑ j=1  bPij − 1 βij ln 2 (βij) ∑ k 6=j σ(wijk)(1− σ(wijk))Ui  (8) where wijk = 〈Ui, (Vk −Vj)〉 and βij = 32 + ∑ k 6=j σ(w i jk); see derivations in Appendix C.

heading: 4 Experiments

heading: 4.1 Experiment Setting

text:
Model Set and Evaluation. We pair 8 SOTA OD algorithms and their corresponding hyperparameters to compose a model set M with 302 unique models. (See Appendix A Table 2 for the complete list.) We evaluate METAOD and the baselines on 2 testbeds introduced below, resp. with 100 and 62 datasets, via cross-validation where datasets are split into meta-train/test in each fold. For each testbed, we first generate the performance matrix P, by evaluating the models from M against the benchmark datasets in the testbed. For randomized detectors (random-split trees/random projections/etc.), we run five independent trials and record the average performance. For consistency, all models are built using the PyOD library [61] on an Intel i7-9700 @3.00 GHz, 64GB RAM, 8-core workstation. We compare two methods statistically, using the pairwise Wilcoxon signed rank test on performances across datasets (significance level p < 0.05).
Testbed Setup. Meta-learning works well if a new task can leverage prior knowledge; e.g., mastering motorcycle can benefit from bike riding experience. As such, METAOD relies on the assumption that a newcoming test dataset shares similarity with some meta-train datasets. We create two testbeds with different train/test dataset similarity, to systematically study the effect of task similarity.
1. Proof-of-Concept (POC) testbed contains 100 datasets that form clusters of similar datasets, where 5 different detection tasks (“siblings”) are created from each one of 20 “mothersets”. 2. Stress Testing (ST) testbed consists of 62 independent datasets from 3 different public-domain OD dataset repositories , which exhibit relatively lower similarity to one another.
We refer to Appendix E for the complete list of datasets and details on testbed generation. Fig. 2 illustrates the differences between POC and ST testbeds, where the meta-features of their constituting
datasets are embedded to 2-D by t-SNE [48]. By construction, POC consists of clusters and hence exhibits higher task/dataset similarity as compared to ST.
Baselines. Being the first work for UOMS, METAOD does not have immediate competing baselines. Therefore we employ simple ideas and tailor some existing methods for comparison. We also create 2 variations of METAOD (marked with †) for ablation analysis. In Appendix F we give detailed descriptions of all 10 baselines. Briefly, they are organized as follows: (i) no model selection always employs the same popular model, namely (1) LOF [6] or (2) iForest [31], or the ensemble of all the models called (3) Mega Ensemble (ME); (ii) simple metalearners include (4) Global Best (GB) that selects the model with the largest avg. performance across meta-train datasets, (5) ISAC [23] and (6) ARGOSMART (AS) [33]; and (iii) optimization-based meta-learners include (7) Supervised Surrogates (SS) [55] and (8) ALORS [32].
Variants of METAOD are (9) †METAOD_C where performance and meta-feature matrices are concatenated as C = [P,M] ∈ Rn×(m+d), before factorization, C ≈ UVT . Given a test dataset, zeroconcatenated meta-features are projected and reconstructed as [P̂test; M̂test] := [0 . . . 0;Mnew]VVT ; and (10) †METAOD_F where U is fixed at φ(M) after the embedding step and only V is optimized. Additionally, we report Empirical Upper Bound (EUB) (only) for POC, as the performance of the best model on a dataset’s 4 “siblings”; this (valuable) information is not available in practice–hence “upper bound”. For ST with lower task similarity, we include Random Selection (RS) as baseline.

heading: 4.2 POC Testbed Results

text:
Testbed Setting. POC testbed is built to simulate the scenario where there are similar meta-train tasks to a given test task. We use the benchmark datasets4 by Emmott et al. [11], who created “childsets” from 20 independent “mothersets” by sampling. Consequently, the childsets generated from the same motherset using the same generation properties (e.g., the frequency of anomalies) can be deemed as “siblings” with large similarity. We build the POC testbed by using 5 siblings from each motherset, resulting in 100 datasets. We split them into 5 folds for cross-validation, each test fold containing 20 independent childsets without siblings.
Results. In Fig. 3, we observe that METAOD is superior to all baseline methods w.r.t. the average rank and mean average precision (MAP), and performs comparably to the Empirical Upper Bound (EUB). Table 1 (left) shows that METAOD is the only meta-learner that is not significantly different from both EUB (MAP=0.2051) and the 4-th best model (0.2185). Moreover, METAOD is significantly better than the baselines that do not employ any model selection (LOF (0.1282), iForest (0.1536), and ME (0.1382)), as well as all the other meta-learners including GB (0.1524), ISAC (0.1658) and ALORS (0.1728). For the full POC evaluation, see Appendix G.1.
Averaging all models (ME) does not lead to good performance as one may expect. As shown in Fig. 3, ME is the worst baseline by average rank in the POC testbed. Using a single detector, e.g.,
4https://ir.library.oregonstate.edu/concern/datasets/47429f155
iForest, is significantly better. This is mainly because some models perform poorly on any given dataset, and ensembling all the models indiscriminately draws overall performance down. Using selective ensembles [36] could be beneficial, however, ensembles of many models are expensive to build in practice. In contrast, METAOD is fast at test time and selects without building any models.
Meta-learners perform significantly better than methods without model selection. In particular, four meta-learners (METAOD, SS, METAOD_C, METAOD_F) significantly outperform single outlier detection methods (LOF and iForest) as well as the Mega Ensemble (ME) that averages all the models. METAOD respectively has 58.74%, 32.48%, and 47.25% higher MAP over LOF, iForest, and ME. These results signify the benefits of model selection.
Optimization-based meta learners generally perform better than simple meta learners. Top-3 meta learners by average rank (METAOD, SS, and METAOD_C) are all optimization-based and significantly outperform simple meta-learners like ISAC as shown in Fig. 3. Simple meta-learners weigh meta-features equally for task similarity, whereas others learn which meta-features matter (e.g., regression on meta-features), leading to better results. We find that METAOD respectively achieves 33.53%, 22.74%, and 4.73% higher MAP than simple meta-learners including GB, ISAC, and AS.

heading: 4.3 ST Testbed Results

text:
Testbed Setting. When meta-train datasets lack similarity to the test dataset, it is hard to capitalize on prior experience. In the extreme case, meta-learning may not perform better than no-model-selection baselines, e.g., a single detector. To investigate the impact of the train/test similarity on meta-learning performance, we build the ST testbed that consists of 62 public-domain datasets from 3 different repositories (See Appendix E Table 4) with relatively low similarity as shown in Fig. 2. For evaluation on ST, we use leave-one-out cross validation; each time using 61 datasets as meta-train.
Results. For the ST testbed, METAOD still outperforms all baseline methods w.r.t. average rank and MAP as shown in Fig. 4. Table 1 (right) shows that METAOD (0.3382) could select, from a pool of 302, the model that is as good as the 58-th best model (top 20%) per dataset (0.3513) in this challenging testbed. The comparable model changes from the 4-th best per dataset in POC to 58-th best in ST, which is expected due to the lower task similarity to leverage in ST. Notably, all other baselines are worse than the 80-th best model with statistical significance. Moreover, METAOD is significantly better than all baselines except iForest. Note that METAOD also significantly outperforms RS, showing that it is able to exploit the meta-train database despite limited task similarity and not simply resorting to random picking. These results suggest that METAOD is a good choice under various extent of similarity among train/test datasets. We refer to Appendix G.2 for detailed ST results on individual ST datasets.
Training stability affects performance for optimization-based methods. Notably, several optimization-based meta-learners, such as ALORS and METAOD_C, do not perform well for ST. We find that the training process of matrix factorization is not stable when latent similarities are
weak. In METAOD, we employ two strategies that help stabilize the training. First, we leverage meta-feature based (rather than random) initialization. Second, we use cyclical learning rates that help escape saddle points for better local optima [43]. Consequently, METAOD (0.3382) significantly outperforms ALORS (0.2981) and METAOD_C (0.1946) with 13.45% and 73.79% higher MAP.
Global methods outperform local methods under limited task similarity. In ST, datasets are less similar and simple meta-learners that leverage task similarity locally often perform poorly. For example, AS selects the model based on the 1-NN, and is likely to fail if the most similar meta-train task is still quite dissimilar to the current task. Notably, the global meta-learner GB outperforms AS and ISAC. Note the opposite ordering among these methods in POC as shown in Fig. 3. In short, effectiveness of simple meta-learners tends to be sensitive to the train/test dataset similarity, which makes them hard to use in general. In contrast, METAOD performs well in both settings.

heading: 4.4 Runtime Analysis

text:
Empowered by meta-training, METAOD (meta-feature generation and model selection) takes less than 1 second on most test datasets, as shown in Fig. 5, where it incurs negligible overhead relative to building/training the selected outlier model (≈10% on avg.). Fig. 6 corroborates the statement by showing the comparison on the 10 largest datasets in POC.
Notably, meta-feature extraction may be trivially parallelized whereas the model selection is even faster, e.g., using SUOD [60], effectively taking constant time (See §3.2.2).

heading: 5 Conclusion

text:
We addressed the unsupervised outlier model selection (UOMS) problem without relying on any labels, model evaluations or comparisons for the first time. Our proposed METAOD is a meta-learner, and builds on an extensive pool of historical outlier detection datasets and models. Given a new task, it selects a model based on the past performances of models on similar historical tasks. To effectively capture task similarity, we designed novel problem-specific meta-features. Importantly, METAOD is (i) fully automatic, requiring no supervision at test time, and (ii) lightweight, incurring relatively small selection time overhead prior to outlier model building. Extensive experiments on two large testbeds showed that METAOD significantly improves detection performance over always using some of the most popular outlier models as well as several other meta-learners tailored for UOMS.
We open-source1 METAOD and our meta-learning database for use in practice. We expect metalearning to become more powerful as the meta-train database grows. Therefore, we also share all our code and testbeds with the community to stimulate further advances in automating UOMS. Future work can address UOMS in the continuous hyperparameter space, leverage self-aware learning [28] and conformal prediction [39] to estimate the confidence in selection, and explore the potential bias and fairness issues in OD model selection [10, 42].

title: Automatic Unsupervised Outlier Model Selection