RCA: A Deep Collaborative Autoencoder Approach for Anomaly Detection

1 Introduction

Anomaly detection (AD) is the task of identifying unusual or abnormal observations in the data. It has a wide range of applicability, from credit fraud detection to medical diagnosis. Current AD approaches can be divided into supervised or unsupervised learning methods. Supervised AD requires labeled examples to train the AD models whereas unsupervised AD, which is the focus of this paper, does not require label information but assumes there are more normal than anomalous instances in the data [Chandola et al., 2009]. Deep autoencoders are one of the most widely used unsupervised AD methods [Chandola et al., 2009; Sakurada and Yairi, 2014; Vincent et al., 2010]. An autoencoder compresses the original data by learning its hidden representation in a way that minimizes the reconstruction loss. It is based on the assumption that normal observations are easier to compress than anomalies. Unfortunately, such an assumption does not generally hold for DNNs, which are often over-parameterized and have the capability to fit well even to the anomalies [Zhang et al., 2016]. Thus, the DNN-based unsupervised AD methods must consider the trade-off between model capacity and overfitting to the anomalies to achieve good performance.

∗Contact Author

Our work is motivated by recent progress on robustness of DNNs for noisy labeled data by learning the weights of the samples during training [Jiang et al., 2017; Han et al., 2018]. For unsupervised AD, our goal is to learn the weights in such a way that normal observations are assigned higher weights than anomalies when calculating reconstruction error. The weights can be used to reduce the influence of anomalies when updating the model for learning a feature representation of the data. However, existing approaches for weight learning are inapplicable to unsupervised AD as they require label information. To address this challenge, we propose a robust collaborative autoencoders (RCA) method that trains a set of autoencoders in a collaborative fashion and jointly learns their model parameters and sample weights. Specifically, given a mini-batch, each autoencoder would learn a feature representation and selects a subset of the samples with lowest reconstruction errors. By discarding samples with high reconstruction errors, the learning algorithm focuses more on fitting the clean data, thereby reducing its risk of memorizing anomalies. However, by selecting only easy-to-fit samples, this may lead to premature convergence of the algorithm without sufficient exploration of the loss surface. To address this issue, the proposed approach selects samples from each autoencoder and exchange them between them, to update their model weights. The sample selection and exchanging procedures are illustrated in Figure 1. During the testing phase, we apply a dropout mechanism to produce multiple output predictions for each test point by repeating the forward pass multiple times. The ensemble of outputs are then aggregated to obtain a robust estimate of the anomaly score.

The main contributions of this paper are as follows. First, we present a framework for unsupervised deep AD using robust collaborative autoencoders (RCA) to prevent model overfitting due to anomalies. Second, we provide theoretical analysis to understand the mechanism behind RCA. Our analysis shows that the worst-case scenario for RCA is better than conventional autoencoders and provides the conditions under which RCA will detect the anomalies. Third, we show that RCA outperforms state-of-the-art unsupervised AD methods for the majority of the datasets used in this study, even if there are missing values present in the data. In addition, RCA also enhances the performance of more advanced autoencoders such as variational autoencoders in unsupervised AD tasks.

2 RelatedWork

Many methods have been developed over the years for unsupervised AD [Chandola et al., 2009]. Reconstruction-based methods, such as principal component analysis (PCA) and autoencoders, project the input data to a lower-dimensional manifold before transforming them back to the original feature space. The distances between the input and reconstructed data are used as anomaly scores of the data points. [Zhou and Paffenroth, 2017] combined robust PCA with an autoencoder to decompose the data into a mixture of normal and anomaly parts. [Zong et al., 2018] jointly learned a low dimensional embedding and density of the data, using the density of each point as its anomaly score while [Ruff et al., 2018] extended the traditional one-class SVM approach to a deep learning setting. Current deep AD methods cannot prevent the network from incorporating anomalies into their learned representation. One way to address the issue is by assigning a weight to each data point. For example, in self-paced learning [Kumar et al., 2010], the algorithm assigns higher weights to easier-to-classify examples and lower weights to harder ones. This strategy was adopted by other supervised methods for learning from noisy labeled data, including mentornet [Jiang et al., 2017] and co-teaching [Han et al., 2018]. Extending the weight learning methods to unsupervised AD is a key novelty of our work. Theoretical studies on the benefits of choosing samples with smaller loss to drive the optimization algorithm can be found in [Shen and Sanghavi, 2018].

3 Methodology

Let X ∈ Rn×d denote the input data, where n is the number of observations and d is the number of features. Our goal is to classify each xi ∈ X as an anomaly or a normal observation. Let O ⊂ X be the set of true anomalies in the data and ϵ = |O|/n be the anomaly ratio, which is determined based on the amount of suspected anomalies in the data or the proportion the user is willing to inspect and verify.

The RCA framework trains a set of k autoencoders with different initializations. For brevity, we assume k = 2 even though RCA is applicable to more than 2 autoencoders. In each iteration during training, the autoencoders will each apply a forward pass on a mini-batch randomly sampled from the training data and compute the reconstruction error of each

Algorithm 1: Robust Collaborative Autoencoders

input: training data Xtrn, test data Xtst, anomaly ratio ϵ, dropout rate r, decay rate α, and max epoch for training; initialize autoencoders A1 and A2; sample selection β = 1; Training Phase while epoch ≤ max epoch do for minibatch S in Xtrn do ˆS1 ← forward(A1, S, dropout = 0), ˆS2 ← forward(A2, S, dropout = 0); c1 ← sample selection(ˆS1, S, β), c2 ← sample selection(ˆS2, S, β) ; ˆS1 ← forward(A1, S[c2], dropout = r), ˆS2 ← forward(A2, S[c1], dropout = r); A1 ←backprop(ˆS1, S[c2], dropout = r), A2 ← backprop(ˆS2, S[c1], dropout = r) ; end β = max(β - ϵ α × max epoch , 1 - ϵ) end return A∗1 = A1 and A∗2 = A2 ; Testing Phase ξ = []; for i = 1 to v do ξ1= forward(A∗1, Xtst, dropout = r) ; ξ2=forward(A∗2, Xtst, dropout = r) ; ξ.append((ξ1 + ξ2)/2); end return anomaly score = average(ξ) ;

data point in the mini-batch. Each autoencoder will then sort the data points according to their reconstruction errors and selects the points with lowest reconstruction error to be exchanged with another autoencoder. This is known as the sample selection step. A back-propagation step is then performed by each autoencoder to update its model parameters using the samples it receives from another autoencoder. Upon convergence, the averaged reconstruction error of each data point is treated as its anomaly score. A pseudocode for RCA with k = 2 autoencoders is shown in Algorithm 1.

3.1 Sample Selection

We present theoretical results to motivate our sample selection approach. First, we demonstrate the robustness of RCA against contamination (anomalies) in training data by showing that RCA converges to a similar solution as if it had been trained on clean (normal) data without anomalies. Next, we show that RCA is better than vanilla SGD when the anomaly ratio is large or when the anomalies are very different from normal data. Finally, we show that RCA will correctly select all the normal points under certain assumption.

Given a mini-batch, Xm ⊂ X, our sample selection procedure chooses a subset of points with lowest reconstruction error as "clean" samples to update the parameters of the autoencoder. The selected points may vary from one iteration to another depending on which subset of points are in the mini-batch and which points have lower reconstruction error within the mini-batch. To avoid discarding the data points prematurely, we use a linear decay function from β = 1 (all points within the mini-batch are chosen) until β = 1 - ϵ to gradually reduce the proportion of selected samples (see last line of training phase in Algorithm 1). The rationale for this approach is that we observe the autoencoders to overfit the anomalies only when the number of training epochs is large.

Let k be the mini-batch size and w be the current parameter of an autoencoder. Our algorithm selects (β × 100)% of the data points with lowest reconstruction errors in the mini-batch to update the autoencoder. Let pi(w) be the probability that a data point with ith smallest reconstruction error (among all n points in the entire dataset) is chosen to update the parameters of the autoencoder. Assuming sampling without replacement, we consider two cases: i ≤ βk and i > βk. In the first case, the data point with ith smallest error will be selected as long as it is in the mini-batch. In the second case, the point is chosen only if it is part of the mini-batch and has among the (βk)-th lowest errors in the mini-batch:

The objective function for the autoencoder with sample selection can thus be expressed as follows:

where f(xi,w) = fi(w) is the reconstruction loss for xi. Suppose Ω(w∗ sr ) is the set of stationary points for ˆ F(w) and Ωi(w∗ ) is the corresponding set of stationary points for each individual loss, fi(w). Let F(w) = ∑i/∈O fi(w) be the "clean" objective function, where anomalies have been excluded from the training data and Ω(w∗ ) be its set of stationary points. Furthermore, let ˜ F(w) = ∑ni=1 fi(w) be the objective function if no sample selection is performed and Ω(w∗ns ) is its corresponding set of stationary points.

Our analysis is based on the following assumptions:

Assumption 1 (Gradient Regularity). maxi,w ‖∇fi(w)‖ ≤ G.

Assumption 2 (Individual L-smooth). For every individual loss fi, ∀p, q : ‖∇fi(wp) -∇fi(wq)‖ ≤ Li ‖wp -wq‖.

Assumption 3 (Equal Minima). Same minimum value for every individual loss: ∀i, j : minw fi(w) = minw fj(w).

Assumption 4 (Individual Strong Convexity). For every individual loss fi, ∀p, q : ‖∇fi(wp) -∇fi(wq)‖ ≥ µi ‖wp - wq‖.

We denote Lmax = maxi(Li), Lmin = mini(Li), µmax = maxi(µi), and µmin = mini(µi). Since F(w) is the sum over the loss for clean data, it is easy to see that Assumption 2 implies F(w) is n(1 - ϵ)Lmax smoothness, while Assumption 4 implies that F(w) is n(1 - ϵ)µmin convex. We thus define M = n(1 - ϵ)Lmax, and m = n(1 - ϵ)µmin.

Remark 1. Assumptions 1 and 2 are commonly used in nonconvex optimization. Assumption 3 is not a strong assumption in an over-parameterized DNN setting [Zhang et al., 2016]. While Assumption 4 is perhaps the strongest assumption, it is only needed to demonstrate correctness of our algorithm (Theorem 3). A similar convex assumption was used in [Shah et al., 2020] to prove the correctness of their algorithm.

We define the constants δ > 0 and φ ≥ 1 as follows:

Note that under the convex assumption, the above equations reduce to: ‖w∗ i -w∗ ‖ ≤ δ ≤ ∥∥w∗ j -w∗∥∥ ≤ φδ, ∀i /∈ O, ∀j ∈ O. These inequalities provide bounds on the distance between w∗ j of anomalies and w∗ for clean data. Using Assumptions 1 and 2, the following theorem shows that optimizing ˆ F(w) yields a C-approximate solution to Ω(w∗ ).

Theorem 1. Let F(w) = ∑i/∈O fi(w) be a twice differentiable function. Consider the sequence w(1) ,w(2) , · · · ,w(t) generated by w(t+1) = w(t) - η(t)∇w(t) ˆ F(w(t) ) and let maxw(t) ‖∇w(t)F(w(t) ) -∇w(t) ˆ F(w(t) )‖2 = C. Based on Assumptions 1 and 2, if ∑∞t=1 η(t) = ∞, ∑∞t=1 η(t)2 ≤ ∞, then mint=0,1,··· ,T ∥∥∇F (w(t) )∥∥2 → C as T → ∞.

Remark 2. The theorem shows how anomalies in training data affect the gradient norm of the clean objective function. If the training data has no anomalies and pi = 1N , then C = 0. When data is noisy, there is no guarantee that C = 0. Instead, C is controlled by the choice of pi.

Since ‖∇F(w∗ )‖ = 0, Theorem 1 shows our sample selection method enables convergence to a C-approximate solution of the objective function for clean data. The theorem below compares our solution against the solution found when trained on the entire data (with no sample selection).

Theorem 2. Let F(w) = ∑i/∈O fi(w) be a twice differentiable function with a bound C defined in Theorem 1. Consider the sequence {wRCA} generated by w(t+1) = w(t) - η(t)∇w(t) ˆ F(w(t) ) . Based on Assumptions 1 and 2 and assume C ≤ (min(nϵG,Mδ))2 , if ∑∞t=1 η(t) = ∞, ∑∞t=1 η(t)2 ≤ ∞, then there exists a large enough T and ˜wns ∈ Ω(w∗ns ) such that mint=0,1,...,T ∥∥∥∇F (w(t) RCA)∥∥∥ ≤ ‖∇F ( ˜wns)‖.

Remark 3. The above theorem provides a worst-case bound. A similar result is given in [Shah et al., 2020] but with a stronger convex assumption. Although it is for the worstcase scenario, our experiments show that our sample selection method generally outperforms DNN methods that use all the data. The condition C ≤ (min(nϵG,Mδ))2 will more likely hold when the anomaly ratio ϵ is large or when δ, distance between normal data and anomalies, is large, consistent with our expectation.

Below we give a sufficient condition for guaranteeing correctness when Assumption 4 holds. Suppose ∀i /∈ O : fi(w∗ ) = 0 and ∀j ∈ O : fj(w∗ ) > 0. Assuming f(w) is convex and its gradient is upper bounded, let Br (w∗ ) = {w | fi(w) < fj(w), ∀i /∈ O, j ∈ O, ‖w - w∗ ‖ ≤ r} . Br (w∗ ) describes a ball of radius r > 0 around the optimal point for which normal observations have a smaller loss than anomalies. The following theorem describes a sufficient condition for our algorithm to converge within the ball.

Theorem 3. Let F(w) = ∑i/∈O fi(w) be a twice differentiable function and κ = √ Lcmax µomin , where Lcmax = maxi/∈O(Li) is the maximum Lipschitz smoothness for clean data and µomin = minj∈O(µj) is the minimum convexity for anomalies. Consider the sequence {wRCA} generated by w(t+1) = w(t) - η(t)∇w(t) ˆ F(w(t) ) and assume maxw(t) ‖∇w(t)F(w(t) ) -∇w(t) ˆ F(w(t) )‖2 = C. Based on Assumptions 1-4, if ∑∞t=1 η(t) = ∞, ∑∞t=1 η(t)2 ≤ ∞, and C ≤ ( δ (1+κ)m )2 = O ( δκ )2 , then there exists r > 0 such that w∗ sr ∈ Br (w∗ ).

The proof is similar to the strategy used in [Shah et al., 2020] and is given in the longer version of the paper. This guarantee depends on having a sufficiently small C, which is related to δ, the nearest distance between anomalies and the normal points, as well as the landscape of the loss surface κ. A small κ suggests that the loss surface will be very sharp for anomalies (large µomin ) but flat for normal data (small Lcmax ). In this case, most regions in the loss surface will have smaller loss on the normal data and larger loss on the anomalies (under assumption of equal minima). As a result, the anomalies have smaller probability to be selected than normal points by our proposed algorithm since they have larger loss.

The above analysis shows that sample selection helps RCA to have better convergence to the stationary points for clean data. Ultimately, our goal is to improve test performance, not just convergence to stationary points of clean data. When sample selection is applied to just one autoencoder, the algorithm may converge too quickly as we use only samples with low reconstruction loss to compute the gradient, making it susceptible to overfitting [Zhang et al., 2016]. Thus, instead of using only the self-selected samples for model update, we train the autoencoders collaboratively and shuffle the selected samples between them to avoid overfitting. A similar strategy was used in [Han et al., 2018] for learning with noisy labels.

3.2 Ensemble Evaluation

Unsupervised AD using an ensemble of model outputs has been shown to be highly effective in previous studies [Liu et al., 2008; Zhao et al., 2019; Emmott et al., 2015; Aggarwal and Sathe, 2017]. In this paper, we use dropout [Srivastava et al., 2014] to emulate the ensemble process. Dropouts are typically used during training to avoid model overfitting. RCA employs dropout during testing by using many networks of perturbed structures to perform multiple forward passes over the data in order to obtain a set of reconstruction errors for each test point. The final anomaly score is computed by averaging the reconstruction errors. We expect a more robust estimation of the anomaly score using this procedure.

4 Experiments

We performed extensive experiments to compare the performance of RCA against various baseline methods. The code is available at https://github.com/illidanlab/RCA.

4.1 Results on Synthetic Data

To understand how RCA overcomes the limitations of conventional autoencoders (AE), we created a synthetic dataset containing a pair of crescent-shaped moons with Gaussian noise [Pedregosa et al., 2011] representing the normal observations and anomalies generated from a uniform distribution. In this experiment, we vary the proportion of anomalies from 10% to 40% while fixing the sample size to be 10,000. Samples with the top-[(1 - ϵ)n] highest anomaly scores are classified as anomalies, where ϵ is the anomaly ratio.

Figure 2 compares the performance of standard autoencoders (AE) against RCA for 10% (left column) and 40% (right column) anomaly ratio. Although the performance for both methods degrades with increasing anomaly ratio, RCA is more robust compared to AE. In particular, when the anomaly ratio is 40%, AE fails to capture the true manifold of the normal data, unlike RCA. This result is consistent with the assertion in Theorem 2, which states that training the autoencoder with a subset of points selected by RCA is better than using all the data when anomaly ratio is large.

4.2 Results on Real-World Data

For evaluation, we used 18 benchmark datasets obtained from the Stony Brook ODDS library [Rayana, 2016] 1 . We reserve 60% of the data for training and the remaining 40% for testing. The performance of the competing methods are evaluated based on their Area under ROC curve (AUC) scores.

Baseline Methods We compared RCA against the following baseline methods: Deep-SVDD (deep one-class SVM) [Ruff et al., 2018], VAE (Variational autoencoder) [Kingma and Welling, 2013; An and Cho, 2015], DAGMM (deep gaussian mixture model) [Zong et al., 2018], SO-GAAL (Single-Objective Generative Adversarial Active Learning) [Liu et al., 2019], OCSVM (one-class SVM) [Chen et al., 2001], and IF (isolation forest) [Liu et al.,

1 Additional experimental results on the CIFAR10 dataset are given in the longer version of the paper.

2008]. Note that Deep-SVDD and DAGMM are two recent deep AD methods while OCSVM and IF are state-of-the-art unsupervised AD methods. In addition, we also perform an ablation study to compare RCA against its four variants: AE (standard autoencoders without collaborative networks) and RCA-E (RCA without ensemble evaluation), and RCA-SS (RCA without sample selection). To ensure fair comparison, we maintain similar hyperparameter settings for all the competing DNN-based approaches. Experimental results are reported based on their average AUC scores across 10 random initializations. More discussion about our experimental setting will be given in the long version of the paper.

Performance Comparison The results summarized in Table 1 show that RCA outperforms all the deep unsupervised AD methods (SO-GAAL, DAGMM, Deep-SVDD) in 16 out of 18 datasets. RCA also performs better than both AE and VAE in 11 out of the 18 datasets, IF in 10 of the datasets, and OCSVM in 11 of the datasets. These results suggest that RCA clearly outperforms the baseline methods on majority of the datasets. Surprisingly, some of the complex DNN baselines such as SO-GAAL, DAGMM, and Deep-SVDD perform poorly on the datasets. This is because most of these DNN methods assume the availability of clean training data, whereas in our experiments, the training data are contaminated with anomalies to reflect a more realistic setting. Furthermore, we use the same network architecture for all the DNN methods (including RCA), since there is no guidance on how to best tune the network structure given that it is an unsupervised AD task.

RCA for Missing Values As real-world data are imperfect, we compare the performance of RCA and other baseline methods in terms of their robustness to missing values. Mean imputation is a common approach to deal with missing values. In this experiment, we add missing values randomly in the features of each benchmark dataset and apply mean imputation to replace the missing values. Such imputation will likely introduce noise into the data. We vary the percentage of missing values from 10% to 50% and compare the average AUC scores of the competing methods. The number of wins, draws, and losses of RCA compared to each baseline method on the 18 benchmark datasets is given in Table 2. RCA was found to consistently outperform both DAGMM and DeepSVDD by more than 80%, demonstrating its robustness compared to other deep unsupervised AD methods when training data is contaminated. Additionally, as the missing ratio increases to more than 30%, it outperforms IF and OCSVM on more than 70% on the datasets. The results suggest that our framework is better than the baselines on the majority of the datasets in almost all settings.

Ablation Study We have also performed an ablation study to investigate the effectiveness of using sample selection and ensemble evaluation. The results comparing RCA against its variants, RCA-E, RCA-SS, and AE are given in Table 2. Without missing value imputation, RCA outperformed all the variants in at least 11 of the datasets. The advantage of RCA over its variants, AE, RCA-SS, and RCA-E, reduces with increasing amount of noise due to missing value imputation but is still significant until the missing ratio is 50%.

Sensitivity Analysis RCA requires users to specify the anomaly ratio of the data. Since the true anomaly ratio ϵ is often unknown, we conducted experiments to evaluate the robustness of RCA when ϵ is overestimated or underestimated by 5% and 10%. from their true values on all datasets. The results in Table 3 suggest that the AUC scores for RCA do not change significantly even when the anomaly ratio was overestimated or underestimated by 10% on most of the datasets.

RCA with VAE The results reported for RCA in Tables 1 - 3 use autoencoders as the underlying DNN. To investigate whether our framework can benefit other DNN architectures, we compared our Robust Collaborative Variational Autoencoder (RCVA) against traditional VAE. The results in Figure 3 showed that RCVA outperformed VAE on most of the datasets, which suggests that our framework can improve the performance of VAE for unsupervised AD.

RCA with Multiple Networks To extend RCA from 2 to multiple DNNs, we modified the shuffling step to allow each DNN to shuffle its selected data to any of the other DNNs. We varied the number of DNNs from 2 to 7 and plotted the results in Figure 4. The results suggest that adding more DNNs does not help significantly. This is not surprising since the shuffling step is designed to prevent the DNNs from converging too quickly rather than as an ensemble framework to boost performance. Increasing the number of DNNs also makes it more expensive to train, which reduces its benefits.

5 Conclusion

This paper introduces RCA framework for unsupervised AD to overcome limitations of existing DNN methods. Theoretical analysis shows the effectiveness of RCA in eliminating corruption in training data. Our results showed that RCA outperforms various algorithms under different experimental settings and is robust to missing value.

Acknowledgements

This research was supported in part by the grant National Science Foundation IIS-2006633, EF-1638679, IIS-1749940, Office of Naval Research N00014-20-1-2382, National Institute on Aging RF1AG072449. Any use of trade, firm or product names is for descriptive purposes only and does not imply endorsement by the U.S. Government.