Title: VERSATILE OUTLIER DETECTION WITH OUTLIER PRE-SERVING DISTRIBUTION MAPPING AUTOENCODERS

Abstract: State-of-the-art deep learning methods for outlier detection make the assumption that outliers will appear far away from inlier data in the latent space produced by distribution mapping deep networks. However, this assumption fails in practice, because the divergence penalty adopted for this purpose encourages mapping outliers into the same high-probability regions as inliers. To overcome this shortcoming, we introduce a novel deep learning outlier detection method, called Outlier Preserving Distribution Mapping Autoencoder (OP-DMA), which succeeds to map outliers to low probability regions in the latent space of an autoencoder. For this we leverage the insight that outliers are likely to have a higher reconstruction error than inliers. We thus achieve outlier-preserving distribution mapping through weighting the reconstruction error of individual points by the value of a multivariate Gaussian probability density function evaluated at those points. This weighting implies that outliers will result in an overall penalty if they are mapped to low-probability regions. We show that if the global minimum of our newly proposed loss function is achieved, then our OP-DMA maps inliers to regions with a Mahalanobis distance less than δ, and outliers to regions past this δ, δ being the inverse Chi Squared CDF evaluated at 1 -α with α the percentage of outliers in the dataset. Our experiments confirm that OP-DMA consistently outperforms the state-of-art methods on a rich variety of outlier detection benchmark datasets.

1. INTRODUCTION:

Background and Motivation. Outlier detection, the task of discovering rare or abnormal instances in a dataset, is critical for many applications from fraud detection, error identification in measurements, to fault detection in systems (2) . Which points are outliers is often unknown in practice, and thus labeling for which points are outliers versus inliers is scarce or even completely unavailable. For this reason, in this work we focus on unsupervised methods for outlier detection (1) .

In the ideal case in which inliers follow a simple unimodal distribution and outliers occur "far away" from the mean compared to the inliers, outlier detection has a simple solution. In this special case, outliers can be found by simply hardcoding some fixed distance as the cutoff between which points are classified as inlier or as outlier, such as is done by EllipticEnvelope (7) . Unfortunately, in practice data is often not distributed in such a convenient manner (13) . Rather, inliers are distributed in a complex, unknown fashion potentially with multiple clusters of inliers in the feature space (6) .

Other methods with not quite as strict assumptions on the distribution of the data can work on arbitrary distributions, such as One-Class methods (4) and IsolationForest (3) to name just a few. These methods typically use a density-based approach (3; 4; 23) . However, these methods are known to become infeasible in high dimensional data sets, because in sufficiently high dimensional spaces, all data points are known to be roughly equidistant and the space around all points will be sparse (5) .

State-of-Art Deep Learning Methods for Outlier Detection. Deep learning methods for outlier detection not only overcome the limitations of density and distance based methods, but they can also leverage the inherent featurization capabilities of deep networks. Recently, deep learning methods use the reconstruction error of an autoencoder-based model for outlier detection, either by considering the reconstruction error itself as an outlier score (18; 20) or by leveraging the reconstruction error in a more sophisticated way (10; 19; 9) . However, it has been shown that the usage of the mere reconstruction error can be a suboptimal choice for an outlier score because outliers tend to converge to an average reconstruction error that is indistinguishable from that of inliers as the network converges (19) . This is a greater issue for the case where outliers occur in clusters as opposed to uniform noise, as shown in Figure 1 . The cluster outlier case is is likely to arise when the outliers represent a small minority class or when they are caused by a systematic error. b) The erroneous assumption of many methods is that outliers are mapped to regions far from the high probability region of the prior distribution.

To go beyond this problem of the pure reconstruction error, recent works have leveraged the distribution-mapping capabilities of generative models such as Variational Autoencdoers (VAEs) that encourage the data in the latent space to follow a prior distribution (19; 21) . These methods assume that due to their anomalous nature outlier points will not be mapped to the encouraged prior distribution while the inliers will be, and consequently outliers will occur in low-probability regions of the prior distribution (19; 21) [Figure 2 (b)]. However, it was observed that this widely held assumption is faulty in practice (21) , with the distribution mapping continuing to map both inliers and outliers to high probability regions of the prior distribution for a wide variety of applications [Figure 2 (a)].

OP-DMA: Our Approach. In this work, we propose a method which leverages the distribution mapping capabilities of generative models, but unlike other distribution mapping outlier detection methods we no longer conveniently assume that outliers are not well mapped to the enforced prior distribution. Our core idea instead is to design a novel prior probability-weighted loss function that actively encourages outliers to be mapped to low probability regions in the latent space. Our method is an autoencoder architecture that we henceforth refer to as the Outlier Preserving Distribution Mapping Autoencoder (OP-DMA). The network is trained to minimize both the Maximum Mean Discrepancy (MMD) distance between the distribution of the data in the latent space and a multivariate Gaussian distribution, and what we call a prior-weighted L2 distance between the input and the reconstruction of the input. This prior-weighted distance weights each input datapoint point by the corresponding value of the multivariate Gaussian PDF evaluated at that point's latent representation. The prior-weighted L2 distance encourages points with a high reconstruction error, as we assume outliers have, to be placed in low-probability regions in the latent space. This corresponds to the important observation that outlier will be mapped far from the mean of the data. The beauty of this mapping is that it thus allows us to use a simple off-the-shelf distance-based metric to identify outliers post-transformation. As the original distribution of the data in the feature space is arbitrary and no distance or density assumptions are placed on the data, OP-DMA thus corresponds to a highly versatile outlier detection strategy. Our key contributions are summarized as follows:

1. Introduce OP-DMA, a novel distribution-mapping autoencoder that preserves ourliers in the latent space without making asumptions on the distribution of the data in the feature space.

2. Prove that the optimal solution for OP-DMA places outliers further than

1-α 0 t -n/2-1 e 1 2t 2 n 2 Γ( n 2 )

dt according to the Mahalanobis distance, where α is the probability that draw from a given dataset is an outlier. This allows us to use a distance-based outlier detection classifier 3. Show experimentally that OP-DMA routinely outperforms standard distribution-mapping autoencoders for outlier detection on a variety of real-world benchmark datasets (19) , for autoencoders the reconstruction error of outliers often converges to that of inliers. This negatively impacts the performance of such reconstruction error methods.

Generative Outlier Detection Methods. Perera et. al. (21) proposed adversarial autoencoders with two discriminator networks for outlier detection. The first discriminator encourages the representation of the data in the latent space to be uniform, while the second encourages the output of the decoder conditioned on random samples from the uniform distribution to match real data samples. Vu et. al. (20) used an adversarial autoencoder to map the latent representation of their data to a standard normal distribution. They then combine the outlier score from a One Class SVM on the latent data with the One Class score on the reconstructed data as the final outlier score. Liu et. al. proposed MO-GAAL ( 26), a deep generative model which uses multiple generator networks to create outlier datapoints near subsets of the input data. A dsicriminator network is used to identify boundaries around the subsets of real data such that the generated outliers are rejected. These distribution mapping methods rely on the assumption that unlike the inliers, the outliers will be mapped to low-orobability regions of the prior distribution. However, as we discussed in Section 1, in practice both inliers and outliers are often well mapped to the prior distribution. This is because outliers that are mapped to low-probability regions will generally incur a higher cost from the divergence term which matches the latent distribution to the prior, and unlike in our OP-DMA approach there is not a corresponding term to counteract this cost.

3. PROPOSED METHOD: OUTLIER PRESERVING DISTRIBUTION MAPPING:

The goal of OP-DMA is to find a latent representation of a dataset X such that outlier in X can be easily isolated from inliers in the latent representation of X. That is, we find a transformation f that we can apply to a given dataset X with a distribution P X such that f (X) ∼ P Z , where P X is an arbitrary and unknown distribution of our input dataset X and P Z is the target distribution. Further, if a ∈ X is an outlier, then f (a) should be an outlier in f (X) as well. That is, p Z (f (a)) should be small. For the purpose of outlier detection, we chose P Z to be a Gaussian distribution as low probability regions would then simply be values far from the mean. We chose an autoencoder architecture to accomplish this distribution mapping, where f is selected to be the encoder Q parameterized by weights θ that are learned through stochastic backpropagation.

OP-DMA accomplishes the goal of mapping outliers to low probability regions on P Z by weighing the autoencoder's reconstruction error by the likelihood of the latent data in the latent space with distribution P Z . In order to accomplish this, we need a one-to-one correspondence between each original datapoint, the latent representation of that datapoint, and the reconstructed point. Additionally, while we want the distribution of the latent data to follow P Z on the whole, we do not want all points to be mapped to high-probability regions of the prior. Rather, we must develop a solution that encourages some datapoints (i.e. outliers) to have a low likelihood in the prior distribution. For these reasons, a Wasserstein Autoencoder (WAE) is a more appropriate choice than the more common Variational Autoencoder (VAE). We chose WAEs, instead of the more commonly used VAEs, because the WAEs encourages the latent representations as a whole to match the prior, whereas the loss function of a VAE encourages each individual latent point to represent a distribution that matches the prior (15) . This is counter to the goal of OP-DMA, which is to have some points (i.e., the outliers) mapped away from the prior distribution. Additionally, by formulating the reconstruction process as a Wassertein distance we can leverage the distribution mapping capabilities of the generative model while still operating with both a deterministic encoder and decoder. This is important as this allows us to maintain a one-to-one correspondence between a given point in the original space and its corresponding mapped point in the latent space so we can weight the reconstruction error by the value of the prior PDF evaluated in the latent space.

3.1. WASSERSTEIN AUTOENCODERS:

As OP-DMA is an extension of WAE, we first briefly describe the structure of WAEs. WAEs are distribution-mapping autoencoders which minimize the Wasserstein distance between original data and its reconstruction. For original data X and reconstruction Y, it is defined as:

EQUATION

where Γ denotes the set of all joint distributions of X and Y , such that the marginal distributions Γ(X|Y ) and Γ(Y |X) are distributed according to P X and P Y respectively, and c is a Wassersteindivergence cost function. That is, the c-Wasserstein distance is the expectation of the cost function c taken with respect to the joint distribution γ with marginals equal to the two priors, such that γ is a joint distribution that produces the minimum expectation of Equation 1.

Simply finding the Wasserstein distance, which is the distance that a WAE is trained to minimize, is itself an optimization problem. However, it is shown in ( 17) that when the encoded data Q(X) ∼ P Z , where Q is the encoder network and P Z is the prior, then the search over all joint distributions previously required to compute the Wasserstein distance can be replaced with a search over all random encoders,

inf γ∈Γ E (X,Y )∼γ [c(X, G(Z))] = inf Q:P Q =P Z E P X E Q(Z|X) [c(X, G(Z))]

. This means we can minimize the c-Wasserstein distance by finding the weights of the encoder that produce the minimum expectation of cost c. As is done in (16) where WAE is defined, we can relax the constraint that P Q ∼ P Z by adding a penalty term D(P Q , P Z ), where D is some function that measures the divergence between P Q and P Z . Thus,

EQUATION

where λ is a constant weight term that determines how much the divergence of P Q from the prior P Z is penalized. In the case of the optimal solution for Q, W λ c (X, Y ) = W c (X, Y ). In that case the Wasserstein objective will equal the true c-Wasserstein distance. While the WAE objective function encourages the distribution of the latent data as a whole to match the prior distribution, WAEs do not encourage outliers in the feature space to remain outliers in the latent space. Even though the divergence term does not explicitly encourage every point to occur in a high probability region, in practice this is what happens. Consider when D is a discriminator network. The discriminator is likely to learn a boundary around the high probably region of the prior distribution, and the encoder network will be penalized for mapping an outlier to a low probablity region outside of the boundary as the discriminator would correctly identify it as a generated point. On the other hand, as described below, our proposed Outlier-Perserving Distribution Mapping Autoencoders actively encourages outliers to be mapped to low probability region in the latent space.

3.2. OUTLIER-PRESERVING DISTRIBUTION MAPPING AUTOENCODERS (OP-DMA):

So far, we have formulated the distribution mapping process in terms of random encoders and decoders Q and G. However, we can deterministically produce Q(X) and G(Q(X)|X) by requiring Q(X) = δ µ(X) , where µ is some function mapping X to Q(X). This allows us to have a one-to-one correspondence between input points X and output G(Q(X)) points, so that

E P X E Q(X) [c(X, G(Q(X)))

] can define a proper reconstruction error between each point x ∈ X and its corresponding output y ∈ Y . This reconstruction error can be used to determine which points should be mapped to low probability regions in the latent space. Let us define c := c(x, G(Q(x))) • p Z (Q(X)). We can thus define the OP-DMA objective function, W λ c , as:

EQUATION

We can think of p Z (Q(X)) as a weight on the reconstruction term. Thus, high-reconstruction error points that are mapped to high-probability regions will be penalized more than high-reconstruction error points which are mapped to low probability regions. Since outliers are assumed to result in a high reconstruction error (at least during early epochs of training), by lessening the penalty to the network for poorly reconstructed points that have been mapped to low-probability regions of the prior we encourage the network to map outlier to these low-probability regions. However, the encoder isn't encouraged to map every point (that is, both inliers and outliers) to low probability regions, as the D term makes it so that the distribution of all the encoded points on the whole should well match the prior.

Although we have made a significant modification to the Wasserstein loss function, as Theorem 1 states minimizing this cost function also corresponds to minimizing a lower bound on the nonprior-weighted Wasserstein divergence:. The proofs of all theorems below are provided in the appendix for space reasons. Theorem 1.

Let P Z = N (µ, Σ). Then W c (X, G(Q(X))) ≤ W c (X, G(Q(X))) 1 (2π n/2 )|Σ| 1/2 . Ad- ditionally, if |Σ| ≤ 1 (4π n ) then W λ c (X, G(Q(X))) ≤W λ c (X, G(Q(X))) 1 (2π n/2 )|Σ| 1/2 .

Additionally, not only is the cost function of OP-DMA a lower bound on the c-Wasserstein divergence, but also itself is a Wasserstein divergence (the c -Wasserstein divergence): Theorem 2. Let W c be a Wasserstein divergence. Then W c is a Wasserstein divergence, with c' the prior-weighted c.

As stated previously, our ideal mapping would place all inliers within regions where the probability was greater than some value, and all outliers into some regions where the probability is less than that value. Theorem 3 shows that this scenario is the optimal solution for the loss function of OP-DMA. Theorem 3. Let Q be an encoder such that D(P Q , P Z , F) = 0, where D(A, B, F) is the Maximum Mean Discrepancy between A an B, F is the set of unbounded continuous functions and P Z = N (0, Σ). Let X : Ω → R n be a centered random variable, X ∼ P X . Let X(A), A ⊂ Ω, be outliers and let H = Ω -A be the inliers, where X

(A) p X (x)dx = α. Furthermore, let c (a, G(Q(a)) > c (h, G(Q(h)) ∀ a ∈ X(A), h ∈ X(H).

Then, the optimal solution of OP-DMA is to map such that Q(X(A)) m ≥ δ and Q(X(H)) m < δ, where δ = 1-α 0

t -n/2-1 e 1 2t 2 n 2 Γ( n 2 )

dt and

• m is the Mahalanobis distance.

Thus, the optimal solution for OP-DMA's cost function is one that maps outliers to regions with a larger Mahalanobis distance than that of inliers. This has the important implication that after transformation with OP-DMA, outliers can be separated from inliers with a simple distance metric. This motivates out outlier detection scheme outlined in Section 3.3, where due to Theorem 1 we use the EllipticEnvelope method to identify outliers.

3.3. UNSUPERVISED OUTLIER DETECTION WITH OP-DMA:

Lastly, we describe our end-to-end solution of outlier detection using OP-DMA. First, we transform the distribution of the dataset X to match a Gaussian distribution using OP-DMA. That is, the input dataset is transformed to match a prior distribution in the latent space of our autoencoder by a divergence term in the network's loss function that penalizes the divergence between the latent distribution and the prior distribution. For the purpose of outlier detection, we chose this prior to be a multivariate Gaussian distribution with 0 mean and identity covariance. Then, EllipticEnvelope (7) is used to determine outliers by fitting a Gaussian to the transformed data. Theorem 3 tells us that EllipticEnvelope is an appropriate choice for the outlier detection step, as it determines outliers based on Mahalanobis distance. However, other outlier detection methods such as IsolationForest (3) or OneClassSVM (4) could equally be leveraged. We use the empirical rather than the theoretical mean and covariance for the EllipticEnvelope as it is unrealistic to expect any such deep distribution mapping model to exactly match the prior. The outlier detection process is outlined in Algorithm 1 and in Figure 2 . As seen in Algorithm 1, we use the unbiased estimator of the MMD from Gretton et. al. (22) . For the kernel k of the MMD we use the inverse multiquadratics kernel as is used in ( 16), and Mean Squared Error (MSE) for c. A high-level overview of the training and outlier detection process of OP-DMA is given in Figure 3 .

4. EXPERIMENTAL EVALUATION 4.1 EXPERIMENTAL METHODOLOGY:

Synthetic Data Sets. We determine possible failure cases for our method OP-DMA versus a standard autoencoder (AE). We use two synthetic datasets: (D1) Multimodal distribution in R 4 with one cluster mean at (0,0,0,0) and another at (5,5,5,5) both with standard covariance and uniform noise added as outliers, and (D2) same multimodal distribution for inliers with a small cluster of outliers with a uniform probability in a small region between (-5,-5,-5,-5) and (-3,-3, -3, -3). In both cases, inliers account for 2.4% of the data.

Benchmark Data Sets. We compared OP-DMA to state-of-the-art methods from the ODDs database ( 8), a commonly used benchmark database of outlier detection datasets. Since we perform unsupervised outlier detection, we do not split each dataset into a training set and testing set. Instead, 

1 n n i=1 c(x i , G Θ (z i ))•λ•p z (z i )+ 1 n(n -1) h =j k(z h , z j )+ 1 n(n -1) h =j k(z h , zj )- 2 n 2 h,j k(z h , zj ) end Find D min = {Q Φ (x i ), Q Φ (x j ), ..., Q Φ (x k )}, D min = (1 -α) D with Minimum Covariance Determinant estimator, inf Σ Det{ Σ}. Find estimated mean μ from D min return Q Φ (x i ) m = (Q Φ (x i ) -μ) Σ(Q Φ (x i ) -μ) for x i ∈ D as outlier scores

outlier detection is performed in an unsupervised manner on the entire dataset. In each dataset all points are labeled as either inlier or outlier. We use these labels to calculate the weighted F1 score, but no method we test is trained on the labels. The datasets were chosen such that we could test our methods on datasets with a wide range of dimensionality in the feature space and with a wide range of outlier contamination percentage. Table (in Appendix B) breaks doen the number of featurs, datapoints, and percentage of outliers in each dataset.

Alternative Methods. In order to determine the validity of our OP-DMA, we compare it to several state-of-the-art distribution mapping outlier detection methods. These include methods that perform outlier detection on the latent space of a Wasserstein, a Variational Autoencoder, and an Adversarial Autoencoder (25) all with a Gaussian prior, here denoted as WAE, VAE, and AAE respectively. Additionally, we test against MO-GAAL (26) and ALOCC (27) , two state-of-the-art deep generative outlier detection models. We also test against LOF (23) and OC-SVM (4), two state-of-the-art non-deep learning outlier detection method.

Parameter Configurations of Methods. The encoders and decoders of all methods consist of 3layer neural networks, where the decoder in each encoder-decoder pair mirrors the structure of the encoder. The number of nodes in the hidden layer of each network is a hyperparameter chosen from {5, 6, 9, 15, 18, 100}. The number of nodes in the output/latent layer is chosen from {2, 3, 6, 9, 15}. The value of the regularization parameter λ is chosen such that the reconstruction error is on the same order of magnitude as the MMD error for the first epoch. We use the standard parameters of MO-GAAL from the authors' publically released code. Likewise, we use the standard configuration of ALOC from the authors code, although we add an additional dense layer at the beginning of each subnetwork. We do this as ALOCC is a convolutional method and assumes input to be images of a certain shape. The additional dense layer we add to the model transforms the inut data from its original dimensionality into the required shape. We use the standard parameters from Scikit-Learn for LOF and OC-SVM.

4.2. EXPERIMENTAL RESULTS:

Synthetic Experiments. Figure 4 A shows the ratio of the recreation error for outliers/inliers for OP-DMA versus an autoencoder (AE) for each synthetic dataset. For uniform noise (D1), both OP-DMA and AE feature a high ratio for the error of outlier/inliers. In this case, a standard AE would be adequate to find the outliers. However, for data where outliers are a small cluster (D2), the ratio between outliers to inliers goes quickly to 1 for AE whereas it levels off to ~10 for OP-DMA. In this case, our OP-DMA succeeds to identify the outliers, while AE cannot. We also verify that OP-DMA maps outliers to low-probability regions of the latent space. Figure 4 B shows the latent space of OP-DMA for the uniform outlier dataset. The outliers occur far from the mean in low-probability regions. The average probability in the prior for outliers after transformation was 0.02, whereas the average probability of the inliers according to the prior was 0.08 Outlier Detection Accuracy. The results reported in Table 2 are the maximum weighted F1-scores of each method over all contamination rates from 0.1 to 1.0 with a step size of 0. Running Time. In order to determine the feasibility of using OP-DMA instead of one of the leading methods in practice, we ran an experiment to determine the running times of each method. This consisted of performing 5 runs of OP-DMA, WAE, VAE, and AAE on the Satellite dataset (24) . The average running time of each method over the 5 iterations is shown in the following table. Each method was run on a machine with 32GB of DDR4 RAM and a Intel Xeon Platinum 8160 CPU.

5. DISCUSSION:

OP-DMA outperforms the state-of-the-art methods on the majority of the outlier detection datasets. This is because unlike the state-of-the-art methods, OP-DMA actively encourages outliers to be mapped to low probability regions instead of relying on outliers to be poorly mapped to the prior. While in this work, we focused on unsupervised outlier detection, OP-DMA could be extended to supervised outlier detection by making the following change to the objective function:

L = inf Q:P Q =P Z E P Xin E Q(Z|X) [c(X in , G(Q(X in )))] + E P Xout E Q(Z|X) [c(X in , G(Q(X out ))) • p Z (Q(X out ))] + λD(P Q , P Z ),

where X in corresponds to the set of labeled inlier points and X out is the set of outliers. OP-DMA can also be modified for semisupervised OP-DMA by pretraining on labeled inliers without weighting the reconstruction error by the likelihood, and then performing OP-DMA as is done in the unsupervised version on the remaining unlabeled datapoints.

6. CONCLUSION:

We have introduced OP-DMA, an autoencoder-based distribution mapping method for outlier detection that maps outliers in the feature space to low probability regions in the latent space in which a multivariate standard normal Gaussian prior distribution is enforced. Outliers are consequently easily identifiable in the latent space. Our experimental study comparing OP-DMA to state-of-the-art methods on a collection of different benchmark outlier detection datasets shows that it outperforms WAE, VAE, and AAE on the majority of the datasets. We have also demonstrated that there is not a significant increase in running time between our method and state-of-the-art methods.

Appendices:

A PROOFS

Theorem 1. Let P Z = N (µ, Σ). Then W c (X, G(Q(X))) ≤ W c (X, G(Q(X))) 1 (2π n/2 )|Σ| 1/2 . Ad- ditionally, if |Σ| ≤ 1 (4π n ) then W λ c (X, G(Q(X))) ≤W λ c (X, G(Q(X))) 1 (2π n/2 )|Σ| 1/2 .

Proof. We will first show that

W c (X, G(Q(X))) ≤W c (X, G(Q(X))) 1 (2π n/2 )|Σ| 1/2 , and then show that W λ c (X, G(Q(X))) ≤W λ c (X, G(Q(X))) 1 (2π n/2 )|Σ| 1/2 .

The maximum value of p Z (z) will occur at z = µ. Then,

sup p Z = 1 (2π n/2 )|Σ| 1/2 . Thus W c (X, G(Q(X))) = inf Q:P Q =P Z E P X E Q(Z|X) [c(X, G(Q(X))) • p Z (Q(X))] ≤ 1 (2π n/2 )|Σ| 1/2 ( inf Q:P Q =P Z E P X E Q(Z|X) [c(X, G(Q(X)))]) = 1 (2π n/2 )|Σ| 1/2 W C (X, G(Q(X)))

Similarly, to show that the prior-weighted c-Wasserstein divergence is a constant multiple of the true Wasserstein divergence:

W λ c (X, G(Q(X))) = inf Q:P Q =P Z E P X E Q(Z|X) [c(X, G(Q(X))) • p Z (Q(X))] + λD(P Q , P Z ) ≤ 1 (2π n/2 )|Σ| 1/2 ( inf Q:P Q =P Z E P X E Q(Z|X) [c(X, G(Q(X)))] + λD(P Q , P Z )) = 1 (2π n/2 )|Σ| 1/2 W λ C (X, G(Q(X)))

Theorem 2. Let W c be a Wasserstein divergence. Then W c is a Wasserstein divergence, with c' the prior-weighted c.

Proof. Since c is a Wasserstein divergence, we know that c(

x 1 , x 2 ) ≥ 0 ∀ x 1 , x 2 ∈ supp(P ), c(x, x) = 0 ∀ x ∈ supp(P ), and E γ [c(x 1 , x 2 )] ≥ 0 ∀ γ ∈ Γ[P, P z ]. Since P Z (z) ≥ 0 ∀ z, c

will also fulfill the three aforementioned properties of c. Thus, W c is a Wasserstein divergence.

Theorem 3. Let Q be an encoder such that D(P Q , P Z , F) = 0, where D(A, B, F) is the Maximum Mean Discrepancy between A an B, F is the set of unbounded continuous functions and P Z = N (0, Σ). Let X : Ω → R n be a centered random variable, X ∼ P X . Let X(A), A ⊂ Ω, be outliers and let H = Ω -A be the inliers, where X

(A) p X (x)dx = α. Furthermore, let c (a, G(Q(a)) > c (h, G(Q(h)) ∀ a ∈ X(A), h ∈ X(H).

Then, the optimal solution of OP-DMA is

to map such that Q(X(A)) m ≥ δ and Q(X(H)) m < δ, where δ = 1-α 0 t -n/2-1 e 1 2t 2 n 2 Γ( n 2 )

dt and

• m is the Mahalanobis distance.

Proof. The Mahalanobis distance of Q(X) can itself be expressed as a random variable, δ = Q(X)Σ -1 Q(X) T . Let Φ δ be the CDF of δ. Then, Φ δ (1 -α) = P (δ ≤ 1 -α) = P (δ 2 ≤ (1 -α) 2 ) = Φ δ 2 ((1 -α) 2 ).

Let Y = Q(X)M -1 , where M T M = Σ is the Choleski decomposition of the covariance Σ. Since D(P Q , P Z , F) = 0, and D(A, B, F) = 0 iff A = B, we thus know that Q(X) ∼ N (0, Σ). Thus since Q(X) is normally distributed and centered, Y thus is normally distributed with identity covariance. Since δ 2 = Q(X)Σ -1 Q(X) T = Y Y T , Φ δ 2 is the CDF of of the sum of squares of n normally distributed variables with mean 0 and σ = 1. Thus, Φ δ 2 is the Chi Squared distribution. The inverse Chi Squared CDF will therefore give us the distance δ such that 1 -α percent of the points are within δ: ). Thus, a mapping that places outliers δ away from the mean will have a lower loss than one that places some percentage of outliers less than δ from the mean. This analysis shows that as long as the contamination parameter is not significantly less than the true contamination percentage the F1-score is robust to different values of the contamination parameter.

δ = 1-α 0 t -n/2-1 e 1 2t

B DATASETS:



:



Figures and Tables:

Figure 1: Ratio of average reconstruction error of outliers/inliers for an autoencoder trained on Gaussian data with cluster outliers (a) or uniform noise outliers (b)

Figure2: a) Standard deep distribution mapping methods that enforce a certain prior distribution on the latent space (VAEs, WAEs) in practice map both outliers and inliers to high probability regions. b) The erroneous assumption of many methods is that outliers are mapped to regions far from the high probability region of the prior distribution.

Figure 3: An overview of OP-DMA. a) Input data is encoded into latent space. b) The divergence between the latent distribution P Q and the prior distribution P Z is calculated and added to the loss term. c) The latent data is reconstructed, and the reconstruction error of each datapoint is weighted by the likelihood of observing the latent point according to the prior distribution P Z . d) After training the network, outlier detection is performed by calculating the Mahalanobis distance of each point in the latent space

Figure 4: A: Reconstruction error vs. epoch for OP-DMA and a standard autoencoder for both noise outliers and cluster outliers. B: Latent representation of data in OP-DMA for uniform outliers.

us assume that for some parameter choiceΘ for Q that αP (Q(X(A)|Θ ) ≤ δ) = β, β > 0. Consequently, (1 -α)P (Q(X(H)|Θ ) > δ) = β, since P (Q(X) > δ) = α and X(A) p X (x)dx = α. Conversely, let us assume that there is a parameter configuration Θ such that αP (Q(X(A)|Θ) ≤ δ) = 0 and so (1 -α)P (Q(X(H)|Θ) > δ) = 0. Since P Z ∼ N (0, Σ), p Z (d 1 ) < p Z (d 2 ) for d 1 m > d 2 m . Thus, since we assume c(a, G(Q(a)) > c(h, G(Q(h)) ∀ a ∈ X(A), h ∈ X(H), then E P X E Q(Z|X) c (x p , G(Q(x p |Θ ))) = E P X E Q(Z|X) c(x p , G(Q(x p |Θ )))p z (x p ) > E P X E Q(Z|X) c(x p , G(Q(x p |Θ)))p z (x p ) = E P X E Q(Z|X) c (x p , G(Q(x p |Θ))

SENSITIVITY TO CONTAMINATION PARAMETER While the contamination parameter α is not used during the training of OP-DMA, it is used to fit the Elliptic Envelope on the encoded data after training. We test the sensitivity of this method to the value of the contamination parameter by evaluating the F1 score of outlier detection on the Satellite dataset after encoding the data with OP-DMA. The results are shown in the figure below.

Figure 5: The F1 score after outlier detection using OP-DMA + Elliptic Envelope on the Satellite dataset, for various values of the contamination parameter α. The vertical dashed line shows the true percentage of outliers in the dataset.

Algorithm 1: Unsupervised Outlier Detection with OP-DMA Require :Regularization coefficient λ Contamination parameter α Initialized encoder network Q Φ and decoder network G Θ with random weights Φ and Θ Dataset X while Θ, Φ not converged do Sample {x 1 , x 1 , ..., x n } from X Sample {z 1 , z 1 , ..., z n } from N (0, I) Sample {z 1 , z1 , ..., zn } from Q Φ (Z|X) Update weights Φ and Θ by descending

Table content: <table/>

1. Running time for methods tested

Table content: <table><tr><td colspan="2">OP-DMA WAE</td><td>VAE</td><td>AAE</td></tr><tr><td>Running Time (seconds) 827.14</td><td colspan="3">723.51 857.46 971.51</td></tr></table>

Weighted F1 scores for OP-DMA vs state-of-the-art methods on datasets from the ODDs outlier detection database with 95% confidence interval.

Table content: <table><tr><td>Dataset</td><td colspan="2">OP-DMA WAE</td><td>VAE</td><td>AAE</td><td colspan="3">MO-GAAL ALOCC LOF</td><td>OC-SVM</td></tr><tr><td>Satellite</td><td>0.735</td><td>0.554</td><td>0.310</td><td>0.480</td><td>0.481</td><td>0.706</td><td colspan="2">0.413 0.417</td></tr><tr><td/><td>±0.012</td><td colspan="4">±0.009 ±0.007 ±0.008 ±0.001</td><td>±0.008</td><td/></tr><tr><td>Pima</td><td>0.625</td><td>0.520</td><td>0.23</td><td>0.497</td><td>0.518</td><td>0.517</td><td colspan="2">0.456 0.440</td></tr><tr><td/><td>±0.018</td><td colspan="4">±0.020 ±0.019 ±0.007 ±0.002</td><td>±0.010</td><td/></tr><tr><td>WBC</td><td>0.590</td><td>0.448</td><td>0.268</td><td>0.19</td><td>0.468</td><td>0.529</td><td colspan="2">0.480 0.199</td></tr><tr><td/><td>±0.011</td><td colspan="4">±0.013 ±0.011 ±0.018 ±0.060</td><td>±0.007</td><td/></tr><tr><td>Arrythmia</td><td>0.531</td><td>0.601</td><td>0.201</td><td>0.294</td><td>0.518</td><td>0.457</td><td colspan="2">0.464 0.254</td></tr><tr><td/><td>±0.017</td><td colspan="4">±0.015 ±0.010 ±0.010 ±0.011</td><td>±0.020</td><td/></tr><tr><td>Breastw</td><td>0.951</td><td>0.950</td><td>0.368</td><td>0.479</td><td>0.944</td><td>0.863</td><td colspan="2">0.292 0.824</td></tr><tr><td/><td>±0.014</td><td colspan="4">±0.011 ±0.009 ±0.007 ±0.014</td><td>±0.062</td><td/></tr><tr><td>Letter</td><td>0.182</td><td>0.091</td><td>0.048</td><td>0.10</td><td>0.159</td><td>0.165</td><td colspan="2">0.488 0.208</td></tr><tr><td/><td>±0.001</td><td colspan="4">±0.003 ±0.005 ±0.002 ±0.003</td><td>±0.001</td><td/></tr><tr><td>Cardio</td><td>0.590</td><td>0.290</td><td>0.221</td><td>0.204</td><td>0.542</td><td>0.432</td><td colspan="2">0.208 0.323</td></tr><tr><td/><td>±0.013</td><td colspan="4">±0.012 ±0.008 ±0.009 ±0.032</td><td>±0.071</td><td/></tr><tr><td>Lympho</td><td>0.585</td><td>0.443</td><td>0.341</td><td>0.310</td><td>0.719</td><td>0.958</td><td colspan="2">0.833 0.150</td></tr><tr><td/><td>±0.012</td><td colspan="4">±0.008 ±0.011 ±0.018 ±0.119</td><td>±0.083</td><td/></tr><tr><td>Musk</td><td>0.32</td><td>0.330</td><td>0.243</td><td>0.228</td><td>0.394</td><td>0.199</td><td colspan="2">0.069 0.101</td></tr><tr><td/><td>±0.007</td><td colspan="4">±0.010 ±0.009 ±0.025 ±0.090</td><td>±0.160</td><td/></tr><tr><td>Thyroid</td><td>0.29</td><td>0.173</td><td>0.130</td><td>0.170</td><td>0.225</td><td>0.084</td><td colspan="2">0.200 0.090</td></tr><tr><td/><td>±0.019</td><td colspan="4">±0.021 ±0.019 ±0.023 ±0.027</td><td>±0.026</td><td/></tr><tr><td colspan="2">Satimage-2 0.860</td><td>0.176</td><td>0.148</td><td>0.535</td><td>0.814</td><td>0.818</td><td colspan="2">0.122 0.019</td></tr><tr><td/><td>±0.039</td><td colspan="4">±0.013 ±0.007 ±0.015 ±0.049</td><td>±0.026</td><td/></tr></table>

Description of the dimensionality, number of datapoints, and contamination percentage of each dataset we tested our method on.

Table content: <table><tr><td>Dataset</td><td colspan="3"># Features # Datapoints % Outliers</td></tr><tr><td>Satellite</td><td>36</td><td>6435</td><td>32%</td></tr><tr><td>Pima</td><td>8</td><td>768</td><td>35%</td></tr><tr><td>WBC</td><td>30</td><td>278</td><td>5.6%</td></tr><tr><td>Arrythmia</td><td>274</td><td>452</td><td>15%</td></tr><tr><td>Breastw</td><td>9</td><td>638</td><td>35%</td></tr><tr><td>Letter</td><td>32</td><td>1600</td><td>6.25%</td></tr><tr><td>Cardio</td><td>21</td><td>1831</td><td>9.6%</td></tr><tr><td>Lympho</td><td>18</td><td>148</td><td>4.1%</td></tr><tr><td>Musk</td><td>166</td><td>3062</td><td>3.2%</td></tr><tr><td>Thyroid</td><td>6</td><td>3772</td><td>2.5%</td></tr><tr><td colspan="2">Satimage-2 36</td><td>5803</td><td>1.2%</td></tr></table>

Peer review (iclr2020):
This work proposes an outlier detection method based on WAE framework. WAE is trained to ensure that 1) latent distribution follows a prior distribution 2) weighted reconstruction error is low where prior PDF is used to weight the reconstruction error. Positives ------------ 1.I liked the intuition behind the proposed method and I felt its worth exploring. Paper points out that in previous works, there is no mechanism to prevent outliers from getting mapped to high probability areas in the model [21]. Authors claim that their method will over-come this issue. I believe this is the core contribution of the paper. 2.I agree with authors point that WAE is a better choice than VAE for outlier detection because, former *encourages the latent representations as a whole to match the prior *. 3.I agree training with a distributional divergence loss along with a weighed reconstruction loss will be helpful for learning a robust representation (as outliers in the training dataset would be assigned a lower weight). 4.Authors have compared the performance of their method on OOD dataset where they have compared against three other baseline methods, where they obtain better performance in majority of cases. Negatives -------------- A. Outlier detection and anomaly/novelty detection are two very different problems. Outliers are *bad eggs* coming from the same class as normal data. On the other hand, anomaly/novelty are unexpected data possibly coming from other classes. This is the taxonomy followed by majority of works. In my understanding this work is about *outlier detection*. I hope authors will use the term *outlier detection* consistency through the paper. B. Authors have not done a good survey on existing outlier detection methods. Eg: I. Chong You, Rene Vidal, Provable Self-Representation Based Outlier Detection in a Union of Subspaces, CVPR 17 II. Yan Xia, Xudong Cao, Fang Wen, Gang Hua, Jian Sun, Learning Discriminative Reconstructions for Unsupervised Outlier Removal, ICCV 15 III. Mohammad Sabokrou, Mohammad Khalooei, Mahmood Fathy, Ehsan Adeli, Adversarially Learned One-Class Classifier for Novelty Detection, CVPR 18. (they have experiments on outlier detection) C. Although existing methods have not explicitly stated the problem identified in (1) above, their proposals are indirectly solving this problem. Therefore, authors should have compared with papers listed in (B) to demonstrate the effectiveness of their method for a meaningful comparison. D. This is the first time I*m seeing the OOD dataset used in the paper. Have other works published their results on this dataset? Can they be included in your paper?. If not, consider reporting results on standard datasets used in papers (B). I believe reporting results on at least two datasets is necessary to demonstrate the generalizability of the method. Other comments ------------------------ a. What is the dimensionality used in the latent space? I believe a larger latent space may be required in modeling more complex data such as images. Is the weighting mechanism effective when a very large latent space is used due to the curse of dimensionality. b. I don*t think the synthetic dataset experiment is giving any interesting insights. This space is better used if an additional dataset is used instead. In conclusion, I like the idea presented in this paper; however, I believe experimental results needs to be improved significantly to demonstrate the effectiveness of the proposed method. I cannot recommend to accept the paper in its present condition. Post Rebuttal: Authors have partially addressed my concerns. In light of new experiments provided, I*m changing my decision to weak accept.