Robust Subspace Recovery Layer for Unsupervised Anomaly Detection
Authors: Chieh-Hsin Lai
Dongmian Zou
Gilad Lerman
Venue:  (2020)
Keywords: robust subspace recovery
unsupervised anomaly detection
outliers
latent space
autoencoder

Abstract: We propose a neural network for unsupervised anomaly detection with a novel robust subspace recovery layer (RSR layer). This layer seeks to extract the underlying subspace from a latent representation of the given data and removes outliers that lie away from this subspace. It is used within an autoencoder. The encoder maps the data into a latent space, from which the RSR layer extracts the subspace. The decoder then smoothly maps back the underlying subspace to a ``manifold" close to the original inliers. Inliers and outliers are distinguished according to the distances between the original and mapped positions (small for inliers and large for outliers). Extensive numerical experiments with both image and document datasets demonstrate state-of-the-art precision and recall. 

Published as a conference paper at ICLR 2020
ROBUST SUBSPACE RECOVERY LAYER FOR UNSUPERVISED ANOMALY DETECTION
Chieh-Hsin Lai; Dongmian Zou"& & Gilad Lerman
School Mathematics University of Minnesota Minneapolis, MN 55455 (laixx313, dzou, 1erman]eumn. edu
ABSTRACT
We propose neural network for unsupervised anomaly detection with a novel robust subspace recovery layer (RSR layer). This layer seeks extract the under- lying subspace from a latent representation of the given data and removes outliers that lie away from this subspace. maps the data into a latent space, from which the RSR layer extracts the subspace. The decoder then smoothly maps back the underlying subspace "manifold" close to the original inliers. Inliers and outliers are distinguished according to the distances between the original and mapped positions (small for inliers and large for outliers). Extensive numerical experiments with both image and document datasets demonstrate state-of-the-ar precision and recall.
used within an autoencoder. The encoder
INTRODUCTION
Finding and utilizing patterns in data is a common task for modern machine learning systems. How- ever, there is often some anomalous information that does not follow common pattern and has to be recognized. For this purpose, anomaly detection aims to identify data points that "do not con- form to expected behavior" (Chandola et al.] 2009). We refer to such points as either anomalous outliers. In many applications, there is ground truth available to distinguish anomalous from normal points, and they need to be detected in an unsupervised fashion. For example, one may need to remove anomalous images from set of images obtained by search engine without any prior knowledge about how a normal image should look (Xia et al. 2015). Similarly, one may need to distinguish unusual news items from large collection of news documents without any information whether news item is usual or not (Kannan er al.) 2017). In these examples, the only assumptions are that normal data points appear more often than anomalous ones and have a simple underlying structure which is unknown to the user.
Some early methods for anomaly detection relied on Principal Component Analysis (PCA) (Shyu et al. 2003 Here one assumes that the underlying unknown structure of the normal samples is linear. However, PCA is sensitive to outliers and will often not succeed in recovering the linear structure or identifying the outliers (Lerman & Maunu, 2018 Vaswani & Narayanamurthy 2018).
More recent ideas of Robust PCA (RPCA) (Wright et al. 2009 Vaswani Narayanamurthy 2018) have been considered for some specific problems of anomaly detection removal (Zhou & Paffen- roth 2017: Paffenroth et al. 2018). RPCA assumes sparse corruption, that is, few elements of the data matrix corrupted. This assumption is natural for some special problems in computer vision, in particular, background subtraction (De La Torre & Black 2003] Wright et al.) 2009 Vaswani & Narayanamurthy/ 2018). However, natural setting of anomaly detection with hidden linear struc- ture may assume instead that a large portion of the data points are fully corrupted. The mathematical framework that addresses this setting is referred
robust subspace recovery (RSR) (Lerman &
Maunu 2018).
While Robust PCA and RSR try to extract linear structure or identify outliers lying away from such structure, the underlying geometric structure of many real datasets is nonlinear. Therefore, one
"Equal contribution.

---

Published as a conference paper at ICLR 2020
needs to extract crucial features of the nonlinear structure of the data while being robust to outliers. In order to achieve this goal, we propose to use an autoencoder (composed of an encoder and a decoder) with an RSR layer. We refer to it RSRAE (RSR autoencoder). It aims to robustly and nonlinearly reduce the dimension of the data in the following way. The encoder maps the data into a high-dimensional space. The RSR layer linearly maps the embedded points into low-dimensional subspace that aims to learn the hidden linear structure of the embedded normal points. The decoder maps the points from this subspace the original space. It aims map the normal points near their original locations, and the anomalous points far from their original locations.
Ideally, the encoder maps the normal data to a linear space and any anomalies lie away from this subspace. In this ideal scenario, anomalies can be removed by an RSR method directly applied to the data embedded by the encoder. Since the linear model for the normal data embedded by the encoder is only approximate, we do not directly apply RSR to the embedded data. Instead, we minimize sum of the reconstruction error of the autoencoder and the RSR error for the data embedded by the encoder. We advocate for alternating procedure, so that the parameters of the autoencoder and the RSR layer are optimized in turn.
1.1 STRUCTURE OF THE REST OF THE PAPER
Section 2 reviews works that are directly related to the proposed RSRAE and highlights the original contributions of this paper. Section B explains the proposed RSRAE, and in particular, its RSR layer and total energy function. Section includes extensive experimental evidence demonstrating effectiveness of RSRAE with both image and document data. Section 5 discusses theory for the relationship of the RSR penalty with the WGAN penalty. Section 6 summarizes this work and mentions future directions.
2 RELATED WORKS AND CONTRIBUTION
We review related works in Section 2.1 and highlight our contribution in Section 2.2
2.1 RELATED WORKS
Several recent works have used autoencoders for anomaly detection. Xia al. (2015) proposed the earliest work on anomaly detection via an autoencoder, while utilizing large reconstruction error of outliers. They apply an iterative and cyclic scheme, where in each iteration, they determine the inliers and use them for updating the parameters of the autoencoder. AAytkin et al. (2018) apply & normalization for the latent code of the autoencoder and also consider the case of multiple modes for the normal samples. Instead of using the reconstruction error, they apply k-means clustering for the latent code, and identify outliers as points whose latent representations are far from all the cluster centers. Zong al. (2018) also use autoencoder with clustered latent code, but they fit a Gaussian Mixture Model using an additional neural network. Restricted Boltzmann Machines (RBMs) are similar autoencoders. /Zhi et al. (2016) define "energy functions" for RBMs that similar to the reconstruction losses for autoencoders. They identify anomalous samples according to large energy values. Chalapathyy et al. (2017) propose using ideas of RPCA within an autoencoder, where they alternatively optimize the parameters of the autoencoder and a sparse residual matrix.
The above works are designed for datasets with small fraction of outliers. However, when this fraction increases, outliers are often not distinguished by high reconstruction errors or low similarity scores. In order to identify them, additional assumptions on the structure of the normal data need to be incorporated. For example, Zhou & Paffenroth| (2017) decompose the input data into two parts: low-rank and sparse (or column-sparse). The low-rank part is fed into an autoencoder and the sparse part is imposed as a penalty term with the f--norm (or f2 -norm for column- -aaasstspaaastty........
In this work, we use a term analogous to the -nrmm, which can be interpreted as the sum of absolute deviations from latent subspace. However, we do not decompose the data priori, but minimize an energy combining this term and the reconstruction error. Minimization of the former
term is known as least absolute deviations in RSR (Lerman & Maunu 2018). ) It was first suggested for RSR and related problems in Watsso (200T): Ding et al. (2006); Zhang et al. (2009). The robust- ness to outliers of this energy, or of relaxed versions of was studied in McCoy & Tropp (201 Xu
2

---

Published as a conference paper at ICLR 2020
et al. (2012); Lerman & Zhang (2014); Zhang & Lerman (2014); Lerman al. (0115 Lerman & Maunu (2017 7) ); Maunu et al. (2017). In particular, Maunu et al. (2017) 1 established its well-behaver
landscape under special, though natural, deterministic conditions. Under similar conditions, they guaranteed fast subspace recovery by a simple algorithm that aims to minimize this energy.
Another directly related idea for extracting useful latent features is an addition of linear self- expressive layer to an autoencoder (Ji et al. 2017). It is used in the different setting of unsupervised subspace clustering. By imposing the self- exeessspresssssssss, the autoencoder robust an increasing number of clusters. Although self-expressiveness also improves robustness to noise and outliers, Ji et al. (2017) aims at clustering and thus its goal is different than ours. Furthermore, their self- expressive energy does not explicitly consider robustness, while ours does. [ezama et al.] (2018) consider a somewhat parallel idea of imposing a loss function to increase the robustness of represen- tation. However, their goal is to increase the margin between classes and their method only applies to supervised setting in anomaly detection, where the normal data is multi-modal.
2.2 CONTRIBUTION OF THIS WORK
This work introduces an RSR layer within autoencoder. It incorporates special regularizer that enforces an outliers-robust linear structure in the emhedding obtained by the encoder. We clarify that the method does not alternate between application of the autoencoder and the RSR layer, but fully integrates these two components. Our experiments demonstrate that a simple incorporation of "robust loss" within regular autoencoder does not work well for anomaly detection. We try to explain this and also the improvement obtained by incorporating an additional RSR layer.
Our proposed architecture simple implement. Furthermore, the RSR layer is limited specific design of RSRAE but can be put into any well-designed autoencoder structure. The epoch time of the proposed algorithm is comparable those of other common autoencoders. Furthermore, our experiments show that RSRAE competitively performs in unsupervised anomaly detection tasks.
RSRAE addresses the unsupervised setting, but is not designed to highly competitive in the semi- supervised or supervised settings, where one has access to training data from the normal class or from both classes, respectively. In these settings, RSRAE functions like a regular autoencoder with- out taking an advantage of its RSR layer, unless the training data for the normal class is corrupted with outliers.
The use of RSR is not restricted to autoencoders. We establish some preliminary analysis for RSR within a generative adversarial network (GAN) (Goodfellow et al. 2014 Arjovsky et al. 2017) in Section 5 More precisely, we show that a linear WGAN intrinsically incorporates RSR in some special settings, although it is unclear how to impose an RSR layer.
RSR LAYER FOR OUTLIER REMOVAL
We assume input data (x in R.M. and denote by X its corresponding data matrix, whose t-th column is x The encoder of RSRAE, 6, a neural network that maps each data point, x(t), its latent code (4) & (x(()) RD The RSR layer a linear transformation A gdxD that reduces the dimension to d. That is, { (z Rd. The decoder 9 is neural network that maps z(()
to (1) in the original ambient space RMM
We can write the forward maps in a compact form using the corresponding data matrices as follows:
Z 6(X), Ż = AZ, X = (().
Ideally, we would like to optimize RSRAF so only maintains the underlying structure of the normal data. We assume that the original normal data lies on d-dimensional "manifold" in DR and thus the RSR layer embeds its latent code into Rd. In this ideal optimization setting, the similarity between the input and the output of RSRAE is large whenever the input is normal and small whenever the input is anomalous. Therefore, by thresholding a similarity measure, one may distinguish between normal and anomalous data points.
In practice, the matrix A and the parameters of & and D are obtained by minimizing a loss function, which is sum of two parts: the reconstruction loss from the autoencoder and the loss from the RSR
3

---

Published as a conference paper at ICLR 2020
layer. For O, & reconstruction loss for the autoencoder is
( Σ x x(0)
In order to motivate our choice of RSR loss, we review common formulation for the original RSR problem. this problem one needs to recover a linear subspace, or equivalently an orthogonal projection P onto this subspace. Assume a dataset {y [y(") and let I denote the identity matrix in the ambient space of the dataset. The goal is to find an orthogonal projector P of dimension d whose subspace robustly approximates this dataset. The least q-th power deviations formulation for q > or least absolute deviations when q (Lerman & Maunu 2018), seeks P that minimizes
Tr=1
L(P)
Σ
[I P y)
(3)
The solution of this problem is robust to some outliers when & (Lerman & Zhang] 2014
Lerman & Maunu 2017); furthermore, g 1 can result in a wealth of local minima and thus preferable (Lerman & Zhang 2014 Lerman Maunu 2017
similar loss function to
3 for RSRAE is
L (A)
LRSR, (A) + A2 (A)
(4)
A
(1
(4)
A2 AAT
Lall
20
where A denotes the transpose of A, Ia denotes the d x d identity matrix and ||-1|p denotes the Frobenius norm. Here A1 A2 are predetermined hyperparameters, though we later show that one may solve the underlying problem without using them. We note that the first term in the weighted sum of (4) is close to (3) as long as A A close to an orthogonal projector. To enforce this requirement introduced the second term in the weighted sum of (4). In Appendix C we discuss further properties of the RSR energy and its minimization.
To emphasize the effect of outlier removal, take p 1 in 2 and the 12,1 norm, or the formulation of least absolute deviations, for both reconstruction and RSR. The loss function of RSRAE is the sum of the two loss terms in (2) and (4), that is,
in (4. That is,
LRSRAF (E, ②) L A, 2)
(5)
We remark that the sole minimization of LA p: without L is not effective for anomaly detection.
We numerically demonstrate this in Section 4.3 and also try explain in Section 5.1
Our proposed algorithm for optimizing (). which we refer to as the RSRAE algorithm, uses alternat- ing minimization. It iteratively backpropagates the three terms LA LRSR, LRSR, and accordingly updates the parameters of the RSR autoencoder. For clarity, we describe this basic procedure in Al- gorithm of Appendix A It independent of the values of the parameters \ and Ag. Note that the additional gradient step with respect to the RSR loss just updates the parameters in A. Therefore does not significantly increase the epoch time of standard autoencoder for anomaly detection. Another possible method, which we refer to as RSRAF+, is direct minimization of LRSRAE, with predetermined X₁ and A2 auto-differentiation (see Algorithm of Appendix AA. Section 4.3 and Appendix 1.2 demonstrate that in general, RSRAE performs better than RSRAE+. though it is pos- sible that similar performance can be achieved by carefully tuning the parameters '₁ and X2 when implementing RSRAE+.
We remark that a standard autoencoder obtained by minimizing only L without the RSR loss. One might hope that minimizing L AE may introduce the needed robustness. However, Section 4.3 and Appendix 1.2 demonstrate that results obtained by minimizing L or 2 are comparable, and worse than those of RSRAF and RSRAF+.
4

---

Published as a conference paper at ICLR 2020
4 EXPERIMENTAL RESULTS
We test our method on five datasets: Caltech 101 (Fei-Fei et al. 2007). Fashion-MNIST (Xiao
et al. 2017). Tiny Imagenet (a small subset of Imagenet (Russakovsky et al. 2013). Reuters-21578
Lewis 1997) and 20 Newsgroups (Lang 1995).
Caltech 101 contains 9, 9,146 RGB images labeled according to 101 distinct object categories. We take the 11 categories that contain at least 100 images and randomly choose 100 images per category.
We preprocess all 1100 images to have size 32 x 32 x and pixel values normalized between -1 and 1. In each experiment, the inliers are the 100 images from certain category and we sample x 100 outliers from the rest of 1000 images of other categories, where e E {0.1, 0.3, 0.5, 0.7, 0.9).
Fashion-MNIST contains 28 28 grayscale images of clothing and accessories, which are catego- rized into 10 classes. We use the test set which contains 10,000 images and normalize pixel values to lie in [-1, 1]. In each experiment, we fix class and the inliers the test images in this class. We randomly sample x 1,000 outliers from the rest of classes (here and below e as above). Since there are around 1000 test images in each class, the outlier ratio is approximately c.
Tiny Imagenet contains 200 classes of RGB images from distinct subset of Imagenet. We select 10 classes with 500 training images per class. We preprocess the images to have size 32 x 32 and pixel values in [-1, 1]. We further represent the images by deep features obtained by a ResNet (He et al. 2016) with dimension 256 (Appendix I.I provides results for the raw images). In each experiment, 500 inliers are from fixed class and x 500 outliers are from the rest of classes.
Reuters-21578 contains 90 text categories with multi-labels. We consider the five largest classes with single labels and randomly sample from them 360 documents per class. The documents are preprocessed into vectors of size 26,145 147 by sequentially applying the TFIDF transformer and Hash- ing vectorizer (Rajaraman & Ullman| [011). In each experiment, the inliers are the documents of fixed class and e X 360 outliers are randomly sampled from the other classes.
20 Newsgroups contains newsgroup documents with 20 different labels. We sample 360 documents per class and preprocess them as above into vectors of size 10,000. In each experiment, the inliers are the documents from fixed class and x 360 outliers are sampled from the other classes.
4.1 BENCHMARKS AND SETTING
We compare RSRAE with the following benchmarks: Local Outlier Factor (LOF) (Breunig et al.
2000). One-Class SVM (OCSVM) (Schölkopf et al. 2000 Amer et al. 2013). Isolation Forest (IF) (Liu et al. 2012), Deep Structured Energy Based Models (DSEBMs) (Zhai et al. 2016), Geomet- Tic Transformations (GT) (Golan & Yaniv 2018), and Deep Autoencoding Gaussian Mixture Model (DAGMM) (Zong et al. 2018). Of those benchmarks, LOF, OCSVM and IF are traditional, while powerful methods, for unsupervised anomaly detection and do not involve neural networks. DSEBMs, DAGMM and GT are more recent and all involve neural networks. DSEBMs built for unsupervised anomaly detection. DAGMM and GT are designed for semi-supervised anomaly detection, but allow corruption. We use them to learn a model for the inliers and assign anomaly scores using the combined set of both inliers and outliers. GT only applies image data. We briefly describe these methods in Appendix E
We implemented DSEBMs, DAGMM and GT using the codes from Golan & El- Yaniv 2211 8) with minimal modification so that they adapt to the data described above and the available GPUs in our machine. The LOF, OCSVM and IF methods are adapted from the scikit-learn packages.
We describe the structure of the RSRAE as follows. For the image datasets without deep features, the encoder consists of three convolutional layers: 5 5 kernels with 32 output channels, strides 2; 5 x 5 kernels with 64 output channels, strides 2; and 3 x 3 kernels with 128 output channels, strides 2. The output of the encoder is flattened and the RSR layer transforms it into 10-dimensional vector. That is, we fix d = 10 in all experiments. The decoder consists of dense layer that maps the output of the RSR layer into a vector of the same shape as the output of the encoder, and three deconvolutional layers: 3 x 3 kernels with 64 output channels, strides 2; 5 x 5 kernels with 32
'Our implementation is available at httpp://gihuu..com///o/o/////// https///gtthulcccmm///o//ooooooo hat.r//ommmoo.cccccccoommsoooooo Trasformations
5

---

Published as a conference paper at ICLR 2020
output channels, strides 2: 5 x 5 kernels with (grayscale) or 3 (RGB) output channels, strides 2. For the preprocessed document datasets or the deep features of Tiny Imagenet, the encoder is a fully connected network with size (32, 64, 128). the RSR layer linearly maps the output of the encoder to dimension 10, and the decoder is a fully connected network with size (128, 64, 32, D) where D the dimension of the input. Batch normalization is applied to each layer of the encoders and the decoders. The output of the RSR layer is fz-normalized before applying the decoder. For DSEBMs and DAGMM we use the same number of layers and the same dimensions in each layer for the autoencoder as in RSRAE. For each experiment, the RSRAE model is optimized with Adam using a learning rate of 0.00025 and 200 epochs. The batch size is 128 for each gradient step. The setting of training is consistent for all the neural network based methods.
The two main hyperparameters of RSRAE are the intrinsic dimension d and learning rate. Their values were fixed above. Appendix G demonstrates stability to changes in these values.
All experiments were executed on a Linux machine with 64GB RAM and four For all experiments with neural networks, we used TensorFlow and Keras. We report runtimes in Appendix H
GPUs.
4.2 RESULTS
We summarize the precision and recall of our experiments by the AUC (area under curve) and AP (average precision) scores. For completeness, we include the definitions of these common scores in Appendix F. We compute them by considering the outliers as "positive". We remark that we did not record the precision-recall-P scores, as in Xiaa et al. (2015); Zong al. (018)), since in practice requires knowledge of the outlier ratio.
Figs. land 2 present the AUC and AP scores of RSRAE and the methods described in Section 4.1 for the datasets described above, where GT is only applied to image data without deep features. For each constant e (the outlier ratio) and each method, we average the AUC and AP scores over runs with different random initializations and also compute the standard deviations. For brevity of presentation, we report the averaged scores among all classes and designate the averaged standard deviations by bars.
The results indicates that RSRAE clearly outperforms other methods most cases, especially when is large. Indeed, the RSR layer was designed to handle large outlier ratios. For Fashion MNIST and Tiny Imagenet with deep features, IF performs similarly to RSRAE, but IF performs poorly on the document datasets. OCSVM is the closest to RSRAE for the document datasets but it is generally not so competitive for the image datasets.
4.3 COMPARISON WITH VARIATIONS OF RSRAE
We use one image dataset (Caltech 101) and one document dataset (Reuters-21578) and compare between RSRAE and three variations of it. The first one is RSRAE+ (see Section B) with λ A = 0.1 in (4) (these parameters were optimized on 20 Newsgroup, though results with other choices of parameters are later demonstrated in Section G.3) The next two are simpler autoencoders without RSR layers: AE-1 minimizes AE, the f2,1 reconstruction loss; and AE minimizes L the f2 reconstruction loss (it a regular autoencoder for anomaly detection). We maintain the same architecture as that of RSRAE, including the matrix A, but use different loss functions.
Fig. 3 reports the AUC and AP scores. We see that for the two datasets RSRAE+ with the prespec- ified A1 and A does not perform as well as RSRAF, but its performance is still better than AE and AE-I. This is expected since we chose a₁ and 22 after few trials with a different dataset, whereas RSRAE is independent of these parameters. The performance of AE and AE-1 is clearly worse, and they are also not as good as some methods compared with in Section 4.2 At last, AE is generally comparable with AE-1. Similar results are noticed for the other datasets in Appendix [.2
RELATED THEORY FOR THE RSR PENALTY
We explain here why we find it natural to incorporate RSR within a neural network. In Section 5.1 we first review the mathematical idea of autoencoder and discuss the robustness of linear

---

Published as a conference paper at ICLR 2020
autoencoder with f, loss (i.e., RSR loss). We then explain why general autoencoder with 22.1 loss is not expected to robust to outliers and why an RSR layer can improve its robustness. Section 5.2 is first step of extending this view generative network. It establishes some robust- ness of WGAN with a linear generator, but the extension of an RSR layer to WGAN is left as an open problem.
5.1 ROBUSTNESS AND RELATED PROPERTIES OF AUTOENCODERS
Mathematically, an autoencoder for a dataset {x(0) C RDD and a latent dimension < D is ft=l
composed of encoder & IRD Rd and decoder 9 Rd + R that minimize the following energy function with 2:
Σ
where o denotes function decomposition. It natural nonlinear generalization of PCA (Goodfel- low et al. 2016). Indeed, the case of a linear autoencoder, and are linear maps represented by matrices E RdxD and D E Dxd, respectively, that need to minimize (among such matrices) the following loss function with p = 2
1 -DD--DEXX Σ
(0)
We explain in Appendix D.I that if (D*, E²) is minimizer of 7 with 2 (among E E RdxD and Dxd), then D is the orthoprojector on the d-dimensional PCA subspace. This means, that the latent code (E*x(") parametrizes the PCA subspace and an additional application of D' to [E'x(") 1= results in the projections of the data points (x(1))
Tt=1 onto the PCA subspace. The recovery етror for data points on this subspace is zero (as D'E is the identity on this subspace),
J
and in general, this eтror is the Euclidean distance to the PCA subspace, ||x(*) -D"E'x(*) I12
Intuitively, the idea of a general autoencoder is the same. It aims fit nice structure, such manifold, to the data, where ideally 2 o & is a projection onto this nice structure. This idea can only be made rigorous for data approximated by simple geometric structure, e.g., by a graph of sufficiently smooth function.
1.0
0.8
0.8
AUC score
score
Caltech 101
RSR AF
BSRAF LOF DCSVV
LOE
0.4
0.2
0.2
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
The constant
The constunt
1.0
Fashion MNIST
0.8
AUC soore
scaee
ISSAAE
ISIAAE
LOF
0.4
0.4
0.2
DNEBMM DAGNNM
0.2
DWGNM
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The
Figure 1: AUC and AP scores for RSRAE using Caltech 101 and Fashion MNIST.

---

Published as a conference paper at ICLR 2020
0.8
0.8
Tiny Imagenet
AP scoro
0.6
0.6
AUC
0.4
0.4
LOF
OCSVM
DCSVM
0.2
DSTIIM DAGMM
0.2
DN6MMM
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant
The consiant e
1.0
0.8
0.8
Reuters-21 21578
AUC score
AP score
0.6
0.6
0.4
0.4
LGF
OCSVM
DCSVM
0.2
D40RM DAGGSM
0.2
DSTBMN
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant
The constant c
1.0
1.0
0.8
0.8
20 Newsgroups
AP score
AUC
0.6
0.6
RSRAF
0.4
10F
0.4
LOF
OCSVM
DCSVM
1
DSEBMc DAGMM
0.2
DSEBA6
DWGMM
0.1
0.3
0.7
0.9
0.1
0.3
0.5
0.7
The constant
The constant
Figure 2: AUC and AP scores for RSRAE using Tiny Imagenet with deep features, Reuters- -1578 and 20 Newsgroups.
In order to extend these methods to anomaly detection, one needs to incorporate robust strategies, so that the methods can still recover the underlying structure the inliers, and consequently assign lower recovery errors for the inliers and higher recovery errors for the outliers. For example, in the linear case, one may assume a set inliers lying on and around a subspace and an arbitrary set of outliers (with some restriction
their fraction). PCA, and equivalently, the linear autoencoder that minimizes 7 with p = 2, is not robust to general outliers. Thus it is not expected to distinguish well between inliers and outliers in this setting. As explained in Appendix D.. minimizing (7) with p gives rise to the least absolute deviations subspace. This subspace can be robust to outliers under some conditions, but these conditions are restrictive (see examples in Lerman & Zhang (2014). In order to deal with more adversarial outliers, it is advised to first normalize the data to the sphere (after appropriate centering) and then estimate the least absolute deviations subspace. This procedure was theoretically justified for general setting of adversarial outliers in Maunu & Lerman (2019).
As in the linear case, an autoencoder that uses the loss function in 6 with p may not be robust to adversarial outliers. Unlike the linear case, there no simple normalizations for this case. Indeed, the normalization to the sphere can completely distort the structure an underlying manifold and is also hard to center in this case. Furthermore, there are some obstacles of establishing robustness for the nonlinear case even under special assumptions.
Our basic idea for robust autoencoder is to search for latent low-dimensional code for the in- liers within a larger embedding space. The additional RSR loss focuses on parametrizing the low- dimensional subspace of the encoded inliers, while being robust to outliers. Following the above discussion, we enhance such robustness by applying a normalization similar to the one discussed above, but adapted better the structure of the network (see Section The emphasis of the RSR
8

---

Published as a conference paper at ICLR 2020
0.8
0.8
AUC AUC score
AP score
0.6
0.6
Caltech 101
0.4
0.4
BSRAT ISSAEE
RSRAE
0.2
AE1
0.2
ESHAAY
AE-
AB
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant
The constant
1.0
1.0
0.8
0.8
Reuters- Reuters-21572 21.78
AUC AUCssoom score
AP score
0.6
0.6
0.4
RSRAE ISELAD!
KSRAE ISHAEY
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant
The constant
Figure 3: AUC and AP scores for RSRAE and alternative formulations using Caltech 101 and Reuters-21578.
layer is on appropriately encoding the inliers, where the encoding of the outliers does matter. is okay for the encoded outliers to lie within the subspace of the encoded inliers, as this will result large recovery errors for outliers. However, general, most encoded outliers lie away from this subspace, and this is why such mechanism is needed (otherwise, regular autoencoder may obtain a good embedding).
5.2 RELATIONSHIP OF THE RSR LOSS WITH LINEARLY GENERATED WGAN
An open problem is whether RSR be used within other neural network structures for unsuper- vised learning, such as variational autoencoders (VAEs) (Kingma & Welling 2013) and generative adversarial networks (GANs) (Goodfellow al., 2014). The latter two models used in anomaly
detection with score function similar to the reconstruction error (An & Cho 2015 Vasilev et al.
2018 Zenati al. 2018 Kliger & Fleishman 2018
While we do not solve this problem, we establish natural relationship between RSR and Wasserstein-GAN (WGAN) (Arjovsky et al. 2017 Guirajani al. (017)) with linear generator, which is analogous to the example of a linear autoencoder mentioned above.
Let W, denote the p- Wasserstein distance in E (p 1). That is, for two probability distributions μ, on RDD
1/P
Wo(n, v) = inf (xx)) |x - -11 (FElI().))
where IT(,,, v) the set of joint distributions with μ., v as marginals. We formulate the following proposition (while prove it later in Appendix[D.2. and then interpret it.
Proposition 5.1. Let p 2 and μ be a Gaussian distribution on RDD with mean mx RDD and full-rank covariance matrix Ex E DxD (that is, p is N (mmx. Ex)). Then
min is (y)
Wp(unv)
my RRD
(9)
rank Ey) =
is achieved when my mx and Ey = P ExP where for X ~
argmin
X P P XI6
(10)
dim_L=d

---

Published as a conference paper at ICLR 2020
The setting of this proposition implicitly assumes a linear generator of WGAN. Indeed, the linear mapping. which can be represented by a x D matrix, maps distribution in N (mxx Σx) into distribution in N (my, Ey) and reduces the rank of the covariance matrix from D to d. The proposition states that in this setting the underlying minimization is closely related to minimizing the loss function (3). Note that here p 1, however, if one further corrupts the sample, then is the suitable choice (Lerman & Maunu 2018). This choice is also more appropriate for WGAN, since there is no p-WGAN for p +
Nevertheless, training WGAN is not exactly the same as minimizing the Wi distance (Gulrajani et 2017), since it is difficult impose the Lipschitz constraint for neural network. Furthermore, in practice, the WGAN generator, which is neural network, is nonlinear, and thus its output is typically non-Gaussian. The robustness of WGAN with a linear autoencoder, which we established here, does not extend to general WGAN (this is similar to our earlier observation that the robustness of linear autoencoder with an RSR loss does not generalize to a nonlinear autoencoder). We believe that similar structure like the RSR layer has to be imposed for enhancing the robustness of WGAN, and possibly also other generative networks, but we leave its effective implementation as an open problem.
CONCLUSION AND FUTURE WORK
We constructed a simple but effective RSR layer within the autoencoder structure for anomaly detec- tion. It is easy to use and adapt. We have demonstrated competitive results for image and document data and believe that it can be useful in many other applications.
There are several directions for further exploration of the RSR loss in unsupervised deep learning models for anomaly detection. First, we are interested in theoretical guarantees for RSRAE. A more direct subproblem is understanding the geometric structure of the "manifold" learned by RSRAB. Second, it is possible that there are better geometric methods to robustly embed the manifold of inliers. For example, one may consider multiscale incorporation of RSR layers, which we expand on in Appendix D.3 Third, one may try to incorporate an RSR layer in other neural networks for anomaly detection that use nonlinear dimension reduction. We hope that some of these methods may be easier to directly analyze than our proposed method. For example, we are curious about successful incorporation
robust metrics for GANs or WGANs, In particular, we wonder about extensions of the theory proposed here for WGAN when considering more general setting.
ACKNOWLEDGMENT
This research has been supported by NSF award DMS 1ANS188-30 1--3018-3. Part of this work was pursued when Dongmian Zou was a postdoctoral associate at the Institute for Mathematics and its Applications at the University of Minnesota. We thank Teng Zhang for his help with proving Proposition |. (we discussed related but different proposition with similar ideas of proofs). We thank Madeline Handschy for commenting on an earlier version of this paper.
REFERENCES
Mennatallah Amer, Markus Goldstein, and Slim Abdennadher. Enhancing one-class support vector machines for unsupervised anomaly detection. In Proceedings of the ACM SIGKDD Workshop on Outlier Detection and Description, pp. 8-15. ACM, 2013.
Jinwon An and Sungzoon Cho. Variational autoencoder based anomaly detection using reconstruc- tion probability. Special Lecture on IE, 2(1), 2015.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning. volume 70 of Pro- ceedings of Machine Learning Research, pp. 223, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL httpa//ccnnnss.mmmsssss///////// 17.hhml
Caglar Aytekin, Xingyang Ni, Francesco Cricri, and Emre Aksu. Clustering and unsupervised anomaly detection with la normalized deep auto-encoder representations. In 20/8 International
10

---

Published as a conference paper at ICLR 2020
Joint Conference Neural Networks (IJCNN), pp. 1-6, July 2018. doi: 10.1109/IICN.2001. 8489068.
Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng. and Jörg Sander. LOF: identifying density- based local outliers. In ACM sigmod record, volume 29, 2, pp. 93-104, ACM, 2000.
Raghavendra Chalapathy, Aditya Krishna Menon, and Sanjay Chawla. Robust, deep and inductive anomaly detection. In Joint European Conference on Machine Learning and Knowledge Discov- ery in Databases, pp. 36-51. Springer, 2017.
Varun Chandola, ArindaFm Banerjee, and Vipin Kumar. Anomaly detection: survey, ACM computing surveys (CSUR), 41))111, 2009.
Jesse Davis and Mark Goadrich. The relationship between precision-recall and curves. In Proceedings of the 23rd International Conference on Machine Learning. ICML '06, pp. 233- 240, New York, NY, USA, 2006. ACM. ISBN 1-59593-383-2.. doi: 10.1145/1 143844. 1143874. URL http://doi..cm.orgg//i httgg/....///14.5200 14511444444444414433777
Fernando De La Torre and Michael J Black. A framework for robust subspace learning. International Journal of Computer Vision, 54(1-3): 111-333:111112:3 17-142, 2003.
Chris Ding, Ding Zhou, Xiaofeng He, and Hongyuan Zha. R1-PCA: rotational invariant 1 -norm principal component analysis for robust subspace factorization. Proceedings of the 23rd inter- national conference Machine learning, pp. 281-288 ACM, 2006.
Li Fei-Fei, Rob Fergus, and Pietro Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. Computer vision and Image understanding, 106(1):59-70, 2007.
Izhak Golan and Ran El- Yaniv. Deep anomaly detection using geometric transformations. In Ad- vances Neural Information Processing Systems, pp. 9781-9791, 2018.
Markus Goldstein and Seiichi Uchida. A comparative evaluatton of unsupervised anomaly detection algorithms for multivariate data. PloS one, 114)::0055) 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Im- proved training of Wasserstein GANs. In Advances in Neural Information Processing Systems, pp. 5767-5777, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630-645. Springer, 2016.
Pan Ji. Tong Zhang, Hongdong Li, Mathicu Salzmann, and Ian Reid. Deep subspace clustering networks. In Advances in Neural Information Processing Systems, pp. 24-33, 2017.
Peter W Jones. Rectifiable sets and the traveling salesman problem. Invent Math, 102(():1-15, 1990.
Ramakrishnan Kannan, Hyenkyun Woo, Charu Aggarwal, and Haesun Park. Outlier detection for text data. In Proceedings of the 2017 SIAM International Conference on Data Mining, pp- 489-497, 2017. URL, http:///epuusssaaaoooo//////////
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference for Learning Representations. arXiv:1412.6980. 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational Bayes. 2nd International Conference for Learning Representations. arXiv: 1312.1111 2013.

---

Published as a conference paper at ICLR 2020
Mark Kliger and Shachar Fleishman. Novelty detection with GAN, 2018. URL https://openreviee. Seetforummdd--yyEPhhho0
Ken Lang. Newsweeder: Learning to filter netnews. In Proceedings of the Twelfth International Conference on Machine Learning, pp. 331-339, 1995.
Gilad Lerman and Tyler Maunu, Fast, robust and non-convex subspace recovery. Information and Inference: A Journal of the IMA, 7(2):277-336, 2017.
Gilad Lerman and Tyler Maunu. An overview of robust subspace recovery. Proceedings of the IEEE, 106(8):1300-1400 2018.
Gilad Lerman and Teng Zhang. recreryvyyy of the most significant subspace among multiple sub- spaces with outliers. Constructive Approximation. 40(3):329- -352299--5-0 2014.
Gilad Lerman, Michael McCoy, Joel A Tropp, and Teng Zhang. Robust computation of linear models by convex relaxation. Foundations of Computational Mathematics, 15(2):663-410 2015.
David Lewis. Reuters-21578 text categorization test collection. Distribution 1.0, AT&T Labs- Research, 1997.
José Lezama, Qiang Qiu, Pablo Musé, and Guillermo Sapiro. OLÉ: Orthogonal low-rank embedding-a plug and play geometric loss for deep learning. In Proceedings of the IEEE Confer- ence on Computer Vision and Pattern Recognition, pp. $109-8118, 2018.
Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation- based anomaly detection. ACM Trans- actions on Knowledge Discovery from Data (TKDD), 6(1):3, 2012.
Tyler Maunu and Gilad Lerman. Robust subspace recovery with advensarial outliers. CoRR, 0bbs/1904.03275. 2019. URL http:pp/aarii.ooo////////440030
Tyler Maunu, Teng Zhang, and Gilad Lerman. A tell-tempered landscape for non-convex robust subspace recovery. arXiv preprint vrXiv:/706.038%0 2017.
Michael McCoy and Joel A Tropp. Two proposals for robust PCA using semidefinite programming. Electronic Journal of Statistics, 5:1 5:1123 5:1123-11600 1160, 2011.
Randy Paffenroth, Kathleen Kay, and Les Servi. Robust PCA for anomaly detection in cyber net- works. arXiv preprint arXiv: (801:080000117/11 2018.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake VanderPlas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duch- esnay. Scikit-leamn: Machine learning in Python. Journal of Machine Learning Research, 12: 2830, 2011.
Anand Rajaraman and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2011.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 11533)221-252, 2015.
Bernhard Schölkopf, Robert C Williamson, Alex Smola, John Shawe-Taylor, and John Platt. Support vector method for novelty detection. In Advances in neural information processing sys- tems, pp. 582-588, 2000.
Mei-Ling Shyu, Shu-Ching Chen, Kanoksri Sarinnapakom, and LiWu Chang, A novel anomaly detection scheme based on principal component classifier. In Proc. ICDM Foundation and New Direction of Data Mining workshop, 2003, pp. 172-179, 2003.
Aleksei Vasilev, Vladimir Golkov, Iona Lipp. Eleonora Sgarlata, Valentina Tomassini, Derek K Jones, and Daniel Cremers. q-space novelty detection with variational autoencoders. arXiv preprint arviv 1806 02997, 2018
12

---

Published as a conference paper at ICLR 2020
Namrata Vaswani and Praneeth Narayanamurthy. Static and dynamic robust PCA and matrix com- pletion: A review. Proceedings of the IEEE, 106(8):1359 1379, 2018.
G. Alistair Watson. Some Problems in Orthogonal Distance and Non-Orthogondl Distance Re- gression. Defense Technical Information Center, 2001. URL
WKKKGWAACAAJ
John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Advances in neural information processing systems, pp. 2080-2088, 2009,
Yan Xia, Xudong Cao, Fang Wen, Gang Hua, and Jian Sun. Learning discriminative reconstruc- tions for unsupervised outlier removal. Proceedings of the IEEE International Conference on Computer Vision, pp. 1511-1519, 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for bench- marking machine learning algorithms. arXiv preprint UrXiv:1708.0774/ 2017.
Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust PCA via outlier pursuit. IEEE Truns. Information Theory, 58(5)3304733064, 2012. doi: 10.1109/TT1:201122111
Houssam Zenati, Chuan Sheng Foo, Bruno Lecouat, Gaurav Manek, and Vijay Ramaseshan Chan- drasekhar. Efficient GAN-based anomaly detection, 2018. URL http:://oeemrvvie..cc///ummm
id= AMM.JDD
Shuangfei Zhai, Yu Cheng, Weining Lu, and Zhongfei Zhang. Deep structured energy based models for anomaly detection. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, pp. 1100-1109, 20166
Teng Zhang and Gilad Lerman. A novel M-estimator for robust PCA. Journal of Machine Learning Research, (5()):79--808 2014.
Teng Zhang, Arthur Szlam, and Gilad Lerman. Median K-flats for hybrid linear modeling with many outliers. In Computer Vision Workshops (ICCV Workshops), 2009 IEEE 12th International Conference on, pp. 234-241. IEEE, 2009.
Chong Zhou and Randy C Paffenroth. Anomaly detection with robust deep autoencoders. In Pro- ceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 665-674, ACM, 2017.
Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng. Cristian Lumezanu, Dacki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In Inter- national Conference Learning Representations, 2018. URL https///ppenerieewwe/ffommddd BJJL
13

---

Published as a conference paper at ICLR 2020
A DETAILS OF RSRAE AND RSRAE+
The implementations of both RSRAE and RSRAE+ are simple. For completeness we provide here their details algorithm boxes. The codes will be later posted in a supplementary webpage. Algo- rithm describes RSRAE, which minimizes (5) by alternating minimization. It denotes the vectors of parameters of the encoder and decoder by and yp, respectively.
Algorithm RRRRAE
Input: Data {x(")) thresholds CAE, <RSR, CRSRs er; architecture and initial parameters of 6, 2, A (including number of columns of A); number of epochs & batches; learning rate for backpropagation; similarity measure
Output: Labels of data points normal anomalous
1: for each epoch do
2: Divide imput data into batches
3: for each batch do
4: if (O, A,) CAE then
5:
Backpropagate L L (0, A, w.r.t. 0, A, vp & update 9, A,
6: end if
7: if LAsn, (A) eSR, then
Backpropagate TRRR, (A) w.r.t. A & update A 9: end if
8:
if LARR (A) > ERSR, then
Backpropagate LRSR, (A) w.r.t A update A
12: end if
end for
14:
end for
15:
for t = I,..,, .N. do
16:
Calculate similarity between (9) and (())
17:
if similarity 2 er then
x()) normal
19: else
20: (!)) is anomalous
21: end if
22:
end for
23:
return Normality labels for 1,...,N
We clarify some guidelines for choosing default parameters, which follow in all reported exper- iments. We set сAE, ERSR, and ERSR, to be zero. In general, we use networks with dense layers but for image data use convolutional layers. We prefer using tanh as the activation function due to its smoothness. However, for dataset that does not in the unit cube, we use either ReLU function if all of its coordinates and the elements A are initialized to be i...d. standard normal. In all numerical experiments, we the number of columns of A be 10, that is, d = 10. The learning rate chosen so that there is a sufficient improvement of the loss values after each epoch. Instead of fixing éT, we report the AUC and AP scores for different values of éT.
positive,
leaky ReLU function otherwise. The network parameters
Algorithm describes RSRAE+, which minimizes
5 with fixed A and Xg by auto-differentiatiin..
14

---

Published as a conference paper at ICLR 2020
Algorithm 2 RSRAA+
Input: Data (x(*) 1N
ft=1i thresholds EœE, eT; architecture and initial parameters of 6, 2, A (includ- ing number of columns of A); parameters of the the energy function λ1, A2; number of epochs & batches; learning rate for backpropagation; similarity measure
Output: Labels of data points normal anomalous
1: for each epoch do
2: Divide input data into batches
3: for each batch do
4: if A (0, (p) CAE then
5:
Backpropagate L ( A) + LSRR (A) + X2L (A) w.r. 0, A, & update
0, A. 4 6: end if
7: end for
8: end for
9: for I,..., do
10: Calculate similarity between x(9) and ((()
11:
if similarity 2 er then
12:
(*)) is normal
13: else
14: (*)) is anomalous
15: end if
16: end for
return Normality labels for l I,...,N
B DEMONSTRATION OF RSRAE FOR ARTIFICIAL DATA
For illustrating the performance of RSRAE, in comparison with a regular autoencoder, we consider simple artificial geometric example. We assume corrupted data whose normal part is embedded in "Swiss roll manifold which is -vo-dimensional manifold in R3, More precisely, the normal part is obtained by mapping 1,000 points uniformly sampled from the rectangle [3TT/2 9 x [0, 21] into R by the function
(s, 6) + (1 cos(()), s, sin(t)).
(11)
The anomalous part is obtained by i..dd sampling of 500 points from an isotropic Gaussian distri- bution in R with zero mean and standard deviation 2 in any direction. Fig. 4a illustrates such sample, where the inliers are in black and the outliers are in blue. We remark that Salis identical.
We construct the RSRAE with the following structure. The encoder is composed of fully-connected layers of sizes (32, 64, 128). The decoder is composed of fully connected layers of sizes (128, 64, 32, 3). Each fully connected layer is activated by the leaky ReLU function with a = 0.2. The intrinsic dimension for the RSR layer, that, is the number of columns of A, is 2
For comparison, we construct the regular autoencoder AE (see Section 4.3) Recall that both of them have the same architecture (including the linear map A), but AE minimizes the &g loss function in (6) (with = 2) without an additional RSR loss. We optimize both models with 10,000 epochs and batch gradient descent using Adam Kingma & Ba 2014) with learning rate of 0.01.
The reconstructed data (X) using RSRAE and AE are plotted in Figs. 4d and 5d respectively. We further demonstrate the output obtained by the encoder and the RSR layer. The output of the encoder, project it onto R3 as follows. We first find two vectors that span the image of and we add to it the "principal direction" of Z orthogonal to the span of A. We project onto the span of these vectors. Figs.44b)a 44) show these projections for RSRAE and AE, respectively. Figs. 4c and 5c demonstrate the respective mappings of Z by A during the RSR layer.
Z & ((X), lies in R 128 For visualization purposes
Figs. and 5d imply that the set of reconstructed normal points in RSRAE seem to lie on the original manifold, whereas the reconstructed normal points by AE seem only lie near, but often
www.:n/gwhi..iiaaiiimmmmiiiiiinn swiss roll.hmml
15

---

Published as a conference paper at ICLR 2020
not the Swiss roll manifold. More importantly, the anomalous points reconstructed by RSRAE seem to be sufficiently far from the set of original anomalous points, unlike the reconstructed points by AE. Therefore, RSRAE can better distinguish anomalies using the distance between the original and reconstructed points, where small values are obtained for normal points and large ones for anomalous
Fig. b demonstrates this claim. They plot the histograms of the distance between the original and reconstructed points when applying RSRAE and AE, where distances for normal and anomalous points are distinguished by color. Clearly, RSRAE distinguishes normal and anomalous data better than AE
Encoder
6:R3 >R
(a) Input data X
(b) ((X) projected onto 3D
RSR
Decoder
linear mapping A:R +R2
9RR2_R3
(d) Output of RSRAE
(c) Z AZ
X (2)
Figure 4: Demonstration of the output of the encoder, RSR layer and decoder of RSRAE on corrupted Swiss roll dataset.
Encoder 833 125
12
(a) Input data X
(b) Z 6 (X) projected onto 3D
linear mapping
Decoder
A:R 128 2
R. R
(d) Output of AE (Z)
(c) Z AZ
Figure 5: Demonstration of the output of the encoder, mapping by A, and decoder of AE on corrupted Swiss roll dataset.
16

---

Published as a conference paper at ICLR 2020
ditribation
AF cmn dieniiariin
460
407
acctd malle
242
352
:60
307-
250
220
260
200
0.
15.0
302
(a) Error distribution for RSRAE.
(b) Error distribution for AE.
Figure 6: Demonstration of the reconstruction enror distribution for RSRAE and AE.
C FURTHER DISCUSSION OF THE RSR TERM
The RSR energy in (4 includes two different terms. The proposition below indicates that the second term of (4) is zero when plugging into it the solution of the minimization of the first term of (4) with the additional requirement that has full rank. That is, in theory, one may only minimize the first term of (4) over the set of matrices A E RRdDD with full rank. We then discuss computational issues of this different minimization.
Proposition C.1. Assume that {z LN Mi=l C. R. spans RR,, d & D and let
N Σ
A = argmin AERAXD rank(A)=d
|2:00
AT
(12)
Then A A T Ia.
Proof. Let A be optimizer of 12 and P denote the orthogonal projection onto the range of A A*. Note that P* can be written as A where À is a d D matrix composed of an orthonormal basis of the range of P Therefore, being an optimum of (12). A* satisfies
(0)) (0 N (1) A T A'
t 1, 1...,,N N
(13)
On the other hand, the definition orthogonal projection implies that
(0) (1)
(1)
... 14 This equality and the fact that P* is projection on
T
(14)
That is, equality is obtained in 13 and the range of A #1' A imply that
(0)
A
+T A
1=1,..,,
(15)
Since ( 1iml spans R 15 results
P A A A
(16)
which further implies that
A A A'P"
(17)
Combining this observation (A A A conclude that AT La.
* A*) with the constraint that A has full rank, we
The minimization in (2) is nonconvex and intractable. Nevertheless, Lerman & Maunu (0017) propose heuristic to solve it with some weak guarantees and Maunu et al. (2017) propose an algorithm with guarantees under some conditions. However, such a minimization is even more difficult when applied to the combined energy in (5). instead of (4). Therefore, find it necessary to include the second term in (4) that imposes the nearness of A AA to an orthogonal projection (equivalently, of AAT to the identity).
17

---

Published as a conference paper at ICLR 2020
D MORE ON RELATED THEORY FOR THE RSR PENALTY
In Section D.I we characterize the solution ( via a subspace problem. Special case solutions to this problem include both the PCA subspace and the least absolute deviations subspace. In Sec- tion [.2 we prove Proposition 5.1 In Section D.3 we review some pure mathematical work that we find relevant this discussion.
D.1 PROPERTY OF LINEAR AUTOENCODERS
The following proposition expresses the solution of ( in terms of another minimization problem. After proving it, we clarify that the other minimization problem is related to both PCA and RSR.
Proposition D.1. Let > 1, d < D, and (x (D', E*) 1 IR Dxd x RdxD is a minimizer of 77. then
Jt= C IR be dataset with rank at least d. If
D'E = P
(18)
where P E DDD is a minimizer of
N
Σ
x
(x) 1P
(19)
2
among all orthoprojectors P (that is, P p and p P) of rank d.
Proof. Let pe be minimizer of 19 and (D* E*) be minimizer of 77. Since pe is an orthopro- jector of rank d it can be written as P U where U E ERDxd and thus
Σ x (DEE'(0
I
Σ
x U ((t)
Σ ||x0 p
(20)
Let L denote the column space of D*E*
Then by the property of orthoprojection
|x0 D'E'x(1)
2 (() P
p
for SISN N
(21)
and consequently
N x(1) P
N
Σ x(0 - (D
(t)
1
x(1) - pSx(10|(
(22)
t=l
The combination of 20 and
22
yields the following two equalities
(1)
P
P
(()
p2x((t]
(23)
2
N
x D'Exx Σ
(
P
Σ
(1) - P (t)
(24)
1=1
We note that (3 implies that Per is minimizer of (19) (among all rank d orthoprojectors) We
further note that 21 and (24) yield that for all 1
x ('E''(0
|| = =1xx00 P
(2)
(25)
1
Since (1) E L and Py an orthoprojector we conclude from 25 that
D D'E'x(0 (x) for N.
(26)
We note that the definition of (D", E*) implies that L (which is the column space of D*E*) is
contained in the span of (x 1= We also recall that the dimension of the span of (x(") ff=1
at least the dimension of L. that is, d. Combining the latter facts with (26) we obtain that
D'E" Pve This and the fact that y is minimizer of (19 (which derived from concludes (18).
18

---

Published as a conference paper at ICLR 2020
Note that when p 2, the energy function in 19 corresponds to PCA. More precisely, minimizer P* of (99) (among rank orthoprojectors) is an orthoprojector on a d-dimensional PCA subspace, equivalently, subspace spanned by top d cigenvectors of the sample covariance (we assume for simplicity linear, and not affine, autoencoder, so the PCA subspace is linear and thus when p = the data centered the origin). This minimizer is unique if and only if the d-th eigenvalue of the sample covariance is larger than the (d+ 1)-st cigenvalue. These elementary facts are reviewed in Section II-A of Lerman & Maunu (2018).
When p - 1, the minimizer P of (99 (among rank d orthoprojectors) is an orthoprojector on the d-dimensional least absolute deviations subspace. This subspace is reviewed Section II-D of Lerman & Maunu (2018) as common approach for RSR. The minimizer is often not unique. where sufficient and necessary conditions for local minima of (19) are studied in Lerman & Zhang 2014).
D.2 PROOF OF PROPOSITION
Proof. We denote the subspace L in the left hand side of (10 by L in order to distinguish it from the generic notation L for subspaces. Consider the random variable X ~ 14, Where μ is (mx Ex). Fix E M(1, v). We note that
Bxx,y)= ||X YIB
||x y12 π (x, dy
R JRD
dist (x, L)/ / J&p
min
=(x: dx
(27)
dim
min
dist(x, L) p(x) dx
dim
JgD
min E| dim
The inequality in 27 holds since X is fixed and Y satisfies (X, π. the distribution of is A Mmmy, Ey) Therefore, almost surely, takes values in the d-dimensional affine subspace {y RD y my range(Ex)) [y.]. Furthermore, note that equality in (27 is achieved when Y X.
We conclude the proof by showing that
m E Lt.
(28)
Indeed, 28 implies that the orthogonal projection of X ~ N(mx, Ex) onto Ix results a random vanable with distribution which is NMmx,, P. about the optimality Y Py.X, the density of this distribution is the optimal solution of (9).
Exp-xxP By the above observation
To prove 28 assume without loss of generality that mx 0. Denote the orthogonal projection of the origin onto the affine subspace L by m and let Lo = L m We need to show that _x = Lo equivalently. m O. We note Lo is linear subspace, m is orthogonal to Lo and thus there exists a rotation matrix O such that
O. = {(0,-. ... 0, --1, ..
ED 20-d+1. . ;DD: ,
.... En E R).
(29)
and
Om = (m,, ... mD
.0)
(30)
For any E R we note that p(x) p(-x) since μ is Gaussian. Using this observation, other basic observations and the notation Ox (I), ... , aDD) we obtain that
dist ((())(()) + clist(-xx, X (p())p((xx
(dist(x, LI'P dist(-x,-5 Lx*) { )P) (xx)
(dist((xx, O.L + dist( Oxx O.L()P))))) μ1(x)
D-d
1/2
D-d
D/2
Σ
(2t -mmmm))
+
Σ
(-2 -mi?²
m(x)
1=1
19

---

Published as a conference paper at ICLR 2020
D-d
1/2
D
)
2/2
Σ (2) - mm;)²
+
Σ 1m1
(a) + m3)²
m(x))
D-d d
p/2
2 2
Σ
1x()
(31)
==1
2 dist Ox, 0, ((()
2 dist(x, Lo) ((x)
= (dist(x, L0) + dist( -x, 20) m(x) 26)
dist( (xatt(xx-a0 Lb) ((-x)-
The inequality in (31) follows from the fact that for 2 1, the function 11-12 is convex as it is composition of the convex function |.1| : IRd - R4 and the increasing convex function (.) :
R+ R.. Equality is achieved in (31) my for i 1..... ,D d. that is, L' = Lo.
Integrating the left and right hand sides of (1 over RD results in
/
dist(x, (*)P,(()sss > dist(x,
(32)
RDD
Since -- is minimizer among all affine subspaces of rank d of fRo dist(x, L)) dx E X P P equality obtained in (32). Consequently, equality is obtained, almost every- where, in 31 Therefore, J = Lo and the claim is proved.
D.3 RELEVANT MATHEMATICAL. THEORY
We note that complex network can represent a large class of functions. Consequently, for a suf- ficiently complex network, minimizing the loss function in (6) results in minimum value zero. In this case the minimizing "manifold" contains the original data, including the outliers. On the other hand, the RSR loss term imposes fitting a subspace that robustly fits only part of the data and thus cannot result minimum value zero. Nevertheless, imposing subspace constraint might be too restrictive, even in the latent space. A seminal work by Jones (1990) studies optimal types of curves that contain general sets. This work relates the construction and optimal properties of these curves with multiscale approximation of the underlying set by lines. It generalized to higher dimen- sions in (?) and to a setting relevant to outliers (?). These works suggest loss functions that incorporate several linear RSR layers from different scales. Nevertheless, their pure setting does not directly apply to our setting. We have also noticed various technical difficulties when trying to directly implement these ideas to our setting.
E BRIEF DESCRIPTION OF THE BASELINES AND METRICS
We first clarify the methods used as baselines in Section
Local Outlier Factor (LOF) measures the local deviation of a given data point with respect to its neighbors. If the LOF of data point is too large then the point is determined to be an outlier.
One-Class SVM (OCSVM) learns a margin for a class of data. Since outliers contribute less than the normal class, it also applies to the unsupervised setting (Goldstein & Uchida 2016). It is usually applied with a non-linear kernel.
Isolation Forest (IF) determines outliers by looking at the number of splittings needed for isolating a sample. constructs random decision trees. A short path length for separating a data point implics higher probability that the point is an outlier.
Geometric Transformations (GT) applies a variety of geometric transforms to input images and consequently creates self-labeled dataset, where the labels the types of transformations. Its anomaly detection is based on Dirichlet Normality score according to the softmax output from a classification network for the labels.
20

---

Published as a conference paper at ICLR 2020
Deep Structured Energy-Based Models (DSEBMs) outputs an energy function which is the nega- tive log probability that a sample follows the data distribution. The energy based model connected to an autoencoder to avoid the need of complex sampling methods.
Deep Autoencoding Gaussian Mixture Model (DAGMM) is also a deep autoencoder model. optimizes end-to-end structure that contains both autoencoder and estimator for Gaussian Mixture Model. The anomaly detection is done after modeling the density function of the Gaussian Mixture Model.
Next, we review the definitions of the two metrics that we used: the AUC and AP scores (Davis & Goadrich 2006). In computing these metrics we identify the outliers as "positive".
AUC (area-under-curve) is the area under the Receiver Operating Characteristic (ROC) curve. Recall that the True Positive Rate (TPR), or Recall, is the number of samples correctly labeled as positive divided by the total number of actual positive samples. The False Positive Rate (FPR), on the other hand, the number of negative samples incorrectly labeled as positive divided by the total number of actual negative samples. The ROC curve is graph of TPR as function of FPR. It is drawn by recording values of FPR and TPR for different choices of eT in Algorithm [
AP (average-precision) is the area under the Precision-Recall Curve. While Recall is the TPR, Precision is the number of samples correctly labeled as positive divided by the total number of predicted positives. The Precision-Red Recall curve is the graph of Precision as function of Recall. It is drawn by recording values of Precision and Recall for different choices of eT in Algorithm |
Both AUC and AP can be computed using the corresponding functions in the scikit-learn package (Pedregosa et al. 2011).
F COMPARISON WITH RSR AND RCAE
We demonstrate basic properties of our framework by comparing to two different frameworks. The first framework is direct RSR, which tries model the inliers by a low-dimensional subspace, as opposed to the nonlinear model discussed in here. Based on careful comparison of RSR methods Lermmn & Maunu (2018), use the Fast Median Subspace (FMS) algorithm (Lerman & Maunu 2017) and its normalized version, the Spherical FMS (SFMS). The other framework can be viewed nonlinear version of RPCA, instead of RSR. It assumes sparse elementwise corruption of the data matrix, instead of corruption of whole data points, or equivalently, of some columns of the data matrix. For this purpose we use the Robust Convolutional Autoencoder (RCAE) algorithm of Chalapathy et al. (2017). who advocate it as "extension of robust PCA to allow for nonlinear manifold that explains most of the data". We adopt the same network structures as in Section 4.1
Fig. 7 reports comparisons of RSRAE, FMS, SFMS and RCAE on the datasets used in Section We first note that both FMS and SFMS are not effective for the datasets we have been using. That is, the inliers in these datasets are not well-approximated by linear model. It is also interesting to notice that without normalization to the sphere, FMS can be much worse than SFMS. That is, SFMS is often way more robust to outliers than FMS. This observation and the fact that there are no obvious normalization procedures a general autoencoder (see Section 5 clarifies why the mere use of the LA loss for autoencoder is not expected to be robust enough to outliers.
Comparing with RSRAE, we note that RCAE is not a competitive method for these datasets. This is not surprising since the model of RCAE, which assumes sparse elementwise corruption, does not fit well to the problem of anomaly detection, but to other problems, such as background detection.
21

---

Published as a conference paper at ICLR 2020
0.8
AUC AUC score
AP soore
0.6
0.6
Caltech 101
0.4
0.4
ISSAA
ISRAT
FMS
PMS
SEMS
0.0
0.1
0.5
The constant c
The constant
1.0
Fashion MNIST
AUC AUC score
AP score
0.6
0.6
0.4
0.4
RSRAE
RSRAE
1345
SEMS
0.2
SEMS
1MS
RCAE
0.9
0.1
0.3
0.5
The constant c
The constant
1.0
1.0
0.8
0.8
Tiny Imagenct
AP score
0.6
AUC
0.4
0.4
0.2
SINSS
EMS
0.2
SEMS
1N8
RCAB
REAB
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant
The constunt
1.0
1.0
0.8
0.8
Reuters- 21578
AUC score
AP so0re
0.6
0.4
0.2
0.2
RCAE
RCAB
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
constant e
The constant
1.0
1.0
0.8
0.8
20 Newsgroups
AP score
0.6
0.6
AUC
RSRAE
0.2
0.2
RCAL
REAE
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5 constunt
0.7
0.9
The constant
Figure 7: AUC and AP for RSRAE, FMS, SFMS and RCAE. From top to bottom the results using Caltech 101, Fashion MNIST, Tiny Imagenet with deep features, Reuters-21578 and 20 Newsgroups.
22

---

Published as a conference paper at ICLR 2020
G SENSITIVITY TO HYPERPARAMETERS
We examine the sensitivity some of the reported results to changes in the hyperparameters. Sec- tion tests the sensitivity of RSRAE changes in the intrinsic dimension d. Section G.2 tests the sensitivity of RSRAE to changes in the learning rate, Section G.3 tests the sensitivity of RSRAE+ changes in A and Xz.
G.1 SENSITIVITY TO THE INTRINSIC DIMENSION
In the experiments reported in Section we fixed d 10. Here check the sensitivity of the reported results to changes in We use the same datasets of Section 4.2 with an outlier ratio of 0.5 and test the following values of d: 1, 5,88 10, 12, 15, 20, 30, 40, 50. Fig. 8 reports the AUC and AP scores for these choice of d and for these datasets with c = 0.5. We note that, in general, results not sensitive choices of 30.
We believe that the structure these datasets is complex, and not represented by a smooth man- ifold of fixed dimension. Therefore, low-dimensional encoding of the inliers is beneficial with various choices of low dimensions.
When d gets closer D the performance deteriorates. Such a decrease in accuracy is noticeable for Reuters-21578 and 20 Newsgroups, where for both datasets D = 128. For the image data sets (without deep features) D 1152 and thus only relatively small values of were tested. As an example of large d for an image dataset, we consider the case of d = D = 1152 in Caltech101 with e 0.5. In this case, AUC 0.619 and AP 0.512, which are very low scores.
We conclude that in our experiments (with 0.5), RSRAE was stable in d around our choice of 10.
1.0
1.0
Fashion MNIST
AUC: XP score
0.9
AUC: AP spore
0.9
Caltech 101
0.8
0.8
0.7
0.7
4P
0.6
0.6
30
Intrinsic dimension d
Intrinsic dimension
1.0
Tiny Imagenet
Reuters- 21578
AUC! AP soore
AUC// AP score
ABC sare
810
15
20
30
10
50
5
810
15
20
30
40
50
Intrinsic dimension
Intrinsic dimension
1.0
20 Newsgroups
0.9
AUC/ AB
0.8
0.7
APoeer
0.6
20
Intrinsic dimemsion
Figure 8: AUC and AP scores for different choices of d. The datasets are the same those in
Section 4.2 where the outlier ratio is = 0.5.
23

---

Published as a conference paper at ICLR 2020
G.2 SENSITIVITY THE LEARNING RATE
In the experiments reported in Section we fixed the learning rate for RSRAE to be 0.00025. Here check the sensitivity of the reported results changes the learning rate. We the same datasets of Section 4.2 with an outlier ratio of = 0.5 and test the following values of the learning rate: 0.0001, 0.00025, 0.0005, 0.001, 0.0025, 0.005, 0.01, 0.025, 0.05, 0.1. Fig. reports the AUC and AP scores for these values and for these datasets (with 0.5). We note that the performance stable for learning rates not exceeding 0.01.
1.0
0.9
0.9
AUC AP sooe
Fashion MNIST
AUC:AP scor
0.7
0.7
Caltech 101
0.5
0.5
ML umm
AP scort
0.3
0.0001
0,00025
01885
0.001
01823
0,005
e:11
0,025
0.65
0.1
0.3
0.00011
0.00225
0,0005
0,001
0,825
0.009
0.01
0,025
0.65
0.1
Leaming File
Leanning ri
1.0
1.0
AUCT AP sore
0.8
AUC/A AP score
0.8
Tiny Imagenct
Reuters-21577
0.6
0.6
04
0.4
0.3
0,0811
0.00055
0.0885
0,001
0,0025
0,885
0.0
0.025
0.05
0.3
0.0011
0.08255
0.085
0,001
0,0255
0.005
0,11
0,025
0.1
Learning
Leaming me
1.0
0.9
0.8
20 Newsgroups
AUC AP
0.7
0.5
0.4
AlT Abwor
0.3
00001
00R05
0.0gg
0.001
0,825
0.0g
0,01
0,255
das
0.1
Leaming
Figure 9: AUC and AP scores for various learning rates. The datasets are the same those in Section where the outlier ratio is c 0.5.
G.3 SENSITIVITY OF RSRAE+ TO d AND A
We study the sensitivity of RSRAE+ to different choices of x and Λ2. We recall that RSRAE does require these parameters.
still interesting check such sensitivity and find out whether careful tuning of these parameters in RSRAE+ can yield better scores than those of RSRAE. We use the same datasets of Section 4.2 with an outlier ratio of 0.5 and simultancously test the following values of either À or A2 0.01, 0.02, 0.05, 0.1, 0.5, 1.0, 2.0. Figs. 10 and 11 report the AUC and AP scores for these values and datasets (with e = 0.5). For each subtigure, the above values of A₁ and A2 recorded the and axes, respectively. The darker colors of the heat map correspond to larger scores. For comparison, the corresponding AUC or AP score of RSRAE indicated in the title of each subfigure.
We note that RSRAE+ is more sensitive to X₃ than X2. Furthermore, as A increases the scores often more stable to changes in Å1. That is, the magnitudes of the derivatives of the scores with respect to A seem to generally decrease with X In Section 4.3 we used X = X₂ = 0.1 as this choice seemed optimal for the independent of 20 Newsgroup. We note though that optimal
24

---

Published as a conference paper at ICLR 2020
hyperparameters depend on the dataset and it is thus not good idea to optimize them using different datasets. They also depend on the choice of c, but for brevity we only test them with = 0.5.
At last we note that the AUC and AP scores of RSRAE are comparable to the fine-tuned ones of RSRAE+ (where с = 0.5). We thus advocate using the alternating minimization of RSRAE, which independent of Å1 and X2-
AUC scores (RSRAE: 0.772) -0.574 0,575
(RSRAE: 0.657)
0.01
0,591 0.612 0.629 0:53 6694
759
0.76
041
4.479
0.483
0.494
0.513
0.525 0.545
1,55
0.65
0.02 0.573 0.573 0.591 0.009 0.634 0.645
0.72
0.76
0,22
0.482
0.482
0.491 0.509 0.528 0.537
0.62
0.72
0.55
0.57
0.573
0.593
0.621
0.15
0.474
0.513
0.60
0.1
0.575 0,575 0.59 0.611 0.63
0.654
0.714
0.756
0.68
0.1
0.483 0.48
0.492
0,513
0.514
0.537
8.61800645
0.645
-05722 0,573
039
0,56
Caltech 101
0.64
85 00.71 0,574 0.586
0.618
0.024
0.654
0.7
0.761
0.479 0.A8
0.493
0.519
0.512
0.549
0.500
0.657
0.567 0.571 0.599
0.605
0.61
0.655
0.718
0.60
0.171
0.48
0.503
0.504
0.504
0.517
0.656
20
-0.72 0.581 0.589 0.604
0.636
0.756
-0.78
0.503
0.515
0.522
0.653
0.48
0.01
0.05
0.01
0.02
12.55
AUC scores (RSRAB: 0,833)
(RSRAE: 0.727)
001
0.776
0.795
0.01
0.573
0L577
I1589
0.602
0.616
0647
0.65
0.68
0.68
0,00
0.723
0.727
0.733 11744 0.753 0.756
0.75
0.769
0.780
0x02
00573
0.578
0.588 0,602 0.616
0.6
0.655
0.09
-0 0,722 0.724
0.735
0.755
0.6
079
0.76
6.55
0.572
0.64
Fashion MNIST
0.723
0.765
0.1
0.573
0.577
0.583
0.599
0.618
0.643
0.671
10
0.722 0.726 0.733
0.741
0.75
0.768
0.168
0.792
62
06344
0.750
57 00.722 0.726
0.734
1.745
0.751
0.77
0.786
0.573
0.593
0.588
0.601
0.612
0.64
0.65
0.671
0,60
0.723
0.753
0.785
0L.35
0.573
0.578
0.59
0.602
0.615
0.64
0.677
-0.233
0.726
0.732
0.744
0.757
0.764
0.177
0.773
0.02
0.01
0.02
0.05
AUC (RSRAE: 0.967)
(RSRAE: 0.926)
0.01
0.882
0.889
0.99
0.904
0919
0.92
0.91
0.927
0.923
0.01
0.506
0.819
0.844
0.862
0.866
858
0.577
0.873
0.82
0.88
0.891
9006
91
0.9118
923
0.9
91919 0.25
0.92
0x02
0880
0,533
846
857
0.844
088
867
878
0,86
0.0
0,05
0.88
0.89
0.907
0912
0.919
0.919 0.918
0.1
0,801
0.521
0.848
0.848
0.854
0.866
0
868
0.866
0.84
Tiny Imagenet
0,874 0.891
40.917
0.121
0.900
6.2
0.791
0.N72
0.879
0.892
0.900
0.914
0.92
0.921
0.93
0.501
0.822
0.847
0.84700858
0.86
0.882
0.82
0.59
0.878
0.891
0.977
0.770991
4
0.933
0.924
0.929
798
0.82
1.84K 0.
0.856
08560.800
0.869
0.87
0.87X
0.87
0.9
0.916
0.88
20
0.863
0.01
0.05
0.61
0.02
0.8
20
Figure 10: AUC and AP scores for RSRAE+ with various choices of A and Ag for Caltech 101, Fashion MNIST and Tiny Imagenet with deep features, where e 0.5.
25

---

Published as a conference paper at ICLR 2020
AUC scores (RSRAE: 0.849)
scores
(RSRAE: 0.748)
a.1
0.58
0.579
0.714
0.792 0.818 0.81 0.825
0.853
0.11
0.436
0.436
0.453
0,58
0
0.70
0.714
0.75
0,2
0.578
768
0.80
0,02
0.504
646
0
747
0.05
0.599
0.583
0.6220.730
0.73
0.829
0.844
0.85
0,05
0.43
0.448
0.495
0.61
0.668
0.72
0.744
0.445
0,66
0.75
-0584
0.573
0.58
0.723
0.773
0.835
0.844
-0.39
0.439
0.457
595
0.615
0.716
0.743
0.60
Reuters- 21578
0.58
0.615
0.84
0.770
01438
55
0.586
0.552
0.6190.707
0.793
0.833
0.836
0.844
-0.65
0.44
0.444
0.489
0,584
0.75
0.722
0.74
0.579
0.770
0.848
0.595
0654
0.777.0
04770.744
0.48
28
0.583
0.573
0.605
0.681
0.714
0.734
0.523
0.855
2.0
0.446
0.439
0.488
0.568
0.655
0.71
0.727
0
0122
0.01
0.02
scores
(RSRA 0.831)
AP
(RSRAE:
0.01
0.754
0 7992
0.797
070 841 0.843
0.843
0.542
0.843
0.54
0.01
0.6
0.642
0.702
713
0.
0.02
0967
012
0.903
0.706
0.050.70
711
0.116
0.
0. 0.719
0.700
0.744
0.796
0.84
0.842
0.843
0.8
0.843
0.592
00695
7..7170.117
0.675
0.759 0. 0.786
0833
10 8.842
8-3
0
8843
0.844
20 Newsgroups
0.842
0,603
0.64
0.696
712
716
0.7.1
0.718
0.755
0.332
703
0.832
0.84
0.843 8-2
0.843
0.843
0.005
0.71
0.
01700
0.625
10
0.751
0.84
0.77.
0.75
0.788
0.835
0.84
0.843
0.8
13
0.813
0.811
00.97
0.64
077
712
0
716
0.72
0.716
0.718
0.600
0,11
0.02
0,55
02
0.91
20
Figure 11: AUC and AP scores for RSRAE+ with various choices of t and A2 using Reuters-21577 and Newsgroup, where c = 0.5.
H RUNTIME COMPARISON
Table records runtimes for all the methods and datasets in Section 4.2 with the choice of 0.5. More precisely, a runtime is the the time needed to complete single experiment, where 200 epoches were used for the neural networks. The table averages each runtime over the different classes.
Note that LOF OCSVM and IF are faster than the rest of methods since they do not require training neural networks. We also note that the runtime of RSRAE is competitive in comparison to the other tested methods, that is, DSEBMs, DAGMM, and GT. The neural network structures of these four methods are the same, and thus the difference in runtime is mainly due different pre and post processing.
Table 1: Runtime comparison: runtimes (in seconds) reported for all methods and datasets in Section 4.2 where the outlier ratio is 0.5. Since GT was only applied to the image datasets without deep features, its runtime available (N/A) for the last three datasets.
Datasets
Benchmarks
Caltech 101
Fashion MNIST
Tiny Imagenet
Reuters-21578
Newsgroups
LOF
0.233
7.163
0.707
25.342
10.316
OCSVM
0. 120
3.131
0.473
8.726
4,169
IF
0.339
1,485
0.511
20.481
6.751
GT
21.681
87,729
N/A
N/A
N/A
DSEBMs
14.293
46.933
25.194
41 11.3
33,852
DAGMM
21.066
71.632
41.211
83.551
60.720
RSRAE
6.305
33.853
10.940
32.061
18.869
26

---

Published as a conference paper at ICLR 2020
I ADDITIONAL RESULTS
show the results for Tiny Imagenet without deep features. In Section [.2 we extend the results reported in section 4.3 for the other datasets.
We include some supplementary numerical results. Section [.]
I.1
TINY IMAGENET WITHOUT DEEP FEATURES
Fig. 12 presents the results for Tiny Imagenet without deep features. We see that RSRAE performs the best, but in general all the methods do not perform well. Indeed, the performance is significantly worse to that with deep features.
1.0
1.0
Tiny Imagenet
AP scree
aUC
ESRAF
RSEAF
0.4
0.4
0.2
0.2
DAGMM
DWGkK
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The
Figure 12: AUC and AP scores for the Tiny Imagenet without using the deep features.
1.2
ADDITIONAL COMPARISON WITH VARIATIONS OF RSRAE
Figs. 13 and 14 extend the comparisons in Section 4.3 for additional datasets. The conclusion is the same. general, RSRAE performs better by a large margin than AE and AE-1. On the other hand, RSRAE+ is often in between RSRAE and AE/AE-L. However, for 20 Newsgroups, RSRAE+ performs similarly to RSRAE, and possibly slightly better, than RSRAE. It seems that in this case our choice of ) and X is good.
1.0
Fashion MNIST
0.8
AUC score
AP sooee
0.6
0.4
0.4
0.2
AE-1
0.2
AE-1
AE
AF
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant
The constant
Tiny Imagenet (deep)
1.0
1.0
0.8
0.8
AP soore
AUC
0.6
0.6
0.4
0.4
ISRAE ESRAE
ESRAE
0.2
AE-1
0.2
RAIAEI
AE-1
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant e
The constant
Figure 13: AUC and AP scores for RSRAE and alternative formulations using Fashion MNIST and deep features of Tiny Imagenet, where 0.5.
27

---

Published as a conference paper at ICLR 2020
0.8
0.8
Tiny Imagenet
AP score
0.6
0.6
AUC
0.4
0.4
SSRAE ISRAE-
RSRAE
0.2
AE-1
0.2
ESHAAY
AEE
AB
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
The constant
The constant
1.0
1.0
0.8
20 Newsgroups
AP score
0.6
AUC
0.4
0.4
0.2
AE-1
0.2
AE
0.0
0.0
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
constant
The
Figure 14: AUC and AP scores for RSRAE and alternative formulations using Tiny Imagenet (im- ages) and 20 Newsgroup, where = 0.5.
28


Reviews:
[{"review_id": "ryl4G2X15S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After reading all the reviews and the comments, I feel more positive about the paper. I appreciate the feedback of the Authors and I have decided to increase the rating.\n\n============================\n\nThe paper proposes using Robust Subspace Recovery in combination with an autoencoder (and possibly GANs) for anomaly detection. The encoder maps input data to the latent space of dimensionality D, which then is linearly projected to a subspace of dimensionality d (d < D). The projection of the latent space then goes to a decoder that reconstructs the input.\nA transformation matrix A is trained jointly with the autoencoder. Two additional terms are added to the loss: one to encourage the subspace of A^TA to approximate the latent space z and the second one to force it to be an orthogonal projector.\n \nThe paper claims to generalize the existing RSR framework to the nonlinear case. However, the linear RSR is applied to the latent space of the autoencoder. In addition to that, all the following discussion and proofs are limited to the linear case. \n\nSince the proposed method is using RSB as it’s core part, and claims to be a non-linear extension of it, it would be crucial to have a comparison with RSB, at least on those experimental setups, where high-level features are used (Tiny Imagenet with ResNET features, Reuters-21578, and 20 Newsgroups). However, there is no such comparison.\n\nSince autoencoders can potentially learn any, arbitrary entangled latent space, it is not clear why outliers should necessarily have such embedding that is outside of the learned subspace. In the case of the original RSR it happens due to the dimensionality reduction by the orthogonal projector. However, autoencoders already perform dimensionality reduction at each layer down to the bottleneck layer.\n\nThe matrix A and the parameters of the AE are trained jointly. So, it can be seen that two processes can occur:\n- The AE in order to minimize the reconstruction error would learn such latent space z, that would fit into the subspace of A^TA, so that projection \\tilde z =Az doesn’t cause data loss.\n- The AE in order to minimize the reconstruction error would learn such A, so that the subspace that z approximates is the best possible.\n\nIt is not clear, which of the two cases would take place. If the first one would dominate, then it is not clear if such method would have any discriminating capabilities.\n \nMy point is mainly that the presented work is not really a generalization of RSR as it claims to be, but rather it is just using RSR on a leaned embedding of the data. \n\nSome citations are missing, as well as it is missing a comparison to some state-of-the art methods such as OCNN ‘Robust, Deep and Inductive Anomaly Detection’ ECML 2017;   ‘Adversarially Learned One-Class Classifier for Novelty Detection’ CVPR 2017; DSVDD ‘Deep one-class classification.’ ICML, 2018; ODIN  ‘Enhancing The Reliability  Of Out-of-distribution Image Detection  In Neural Networks’ ICLR 2018; ‘Generative Probabilistic Novelty Detection with Adversarial Autoencoders’ NeurIPS 2018.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxIlEaNFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use the robust subspace recovery layer (RSR) in the autoencoder model for unsupervised anomaly detection.\nThis paper is well written overall. Presentation is clear and it is easy to follow.\nThe proposed approach is a simple combination of existing approaches.\nAlthough its theoretical analysis with respect to the performance of anomaly detection is limited, experiments show that the proposed method is effective and superior to the existing anomaly detection methods.\n\nI have the following comments:\n- Parameter sensitivity should be examined.\n    The proposed method has the number of parameters including \\lambda_1, \\lambda_2, and parameters in neural networks.\n    Since parameter tuning is fundamentally difficult in the unsupervised setting, the sensitivity of the proposed method with respect to changes of such parameters should be examined.\n- Since the efficiency is also an important issue for anomaly detection methods, runtime comparison would be interesting.\n- It would be also interesting whether the proposed method is also effective for non-structured data, where a dataset is given as just a set of (real-valued) feature vectors, with its comparison to the standard anomaly detection methods such as LOF and iForest.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkxvUjYsKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper adapts the concept of Robust Subspace Recovery (RSR) as a layer in an auto-encoder model for anomaly detection. A loss function is proposed that combines reconstruction error and a regularizer that enforces robustness against outliers. The reconstruction error expresses the accuracy of the nonlinear dimensionality reduction imposed by the autoencoder. The regularizer is the sum of absolute deviations from the latent subspace that represents a linear structure robust against outliers. An alternative procedure is applied where the loss terms are applied iteratively during training. Once trained, the reconstruction error is used directly for anomaly detection with a threshold. The AUC is used as a performance measure. The method is compared against 6 other methods (LOF, OCSVM, IF, DESBM, GT, DAGMM). The setting is fully unsupervised, meaning that the training data contains various amounts of anomalies, and the results are parametrized with the amount of corruption. The results show that the proposed approach outperforms the other methods in most cases, especially for larger amounts of corruption. An ablation study compares the approach with auto-encoder-only and a non-alternating gradient descent (fixed factors for each part of the loss function) and shows that the alternating method outperfroms all by a wide margin.\n\n\nPROS:\n\n* A novel approach to fully unsupervised anomaly detection that beats the state of the art.\n\n* The RSR layer is a simple fully connected layer and the loss function is simple to calculate, making the approach computationally efficient.\n\n* A pseudo-code algorithm is provided in the appendix, which should help reproducibility. \n\n* The paper is well written and the math is clearly laid out.\n\n* The result benchmarks are sufficiently exhaustive in both the methods that are compared and the datasets used.\n\n* The ablation study is informative and shows the effect of the regularization term of the loss function as well as the effect of alternating the gradient descent with the separate losses.\n\n\n\nCONS:\n\n* There is a serious problem in the results (Figure 1) as the AP curves show better scores for larger corruption factors. Are the AP-score graphs flipped ? Please explain.\n\n* The AUC and AP scores need to be defined. \n\n* The results should include the case where the training data is not contaminated with outliers (c=0). This would correspond to the semi-supervised scenario and it would be very interesting to see how the method compares to DAGMM and GT which are build for that scenario.\n\n* It would be interesting to see the effect of varying the subspace dimension. The authors chose 10 for all experiments, why is this number chosen, what would be the effect of choosing a smaller one ? This is a key parameter as it defines the structure of the projection subspace. Should this parameter be systematically tuned for each dataset ?\n\n\nOverall this is a good paper proposing a novel approach to fully unsupervised anomaly detection with state-of-the art results.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers have assessed this paper and they have scored it as 6/6/6/6 after rebuttal. Nonetheless, the reviewers have raised a number of criticisms and the authors are encouraged to resolve them for the camera-ready submission.
Decision: Accept (Poster)