Outlier Detection for Time Series with Recurrent Autoencoder Ensembles

1 Introduction

As part of the ongoing digitalization of societal and industrial processes, many sensor-equipped devices, such as mobile phones, GPS navigators, and health care monitors, produce large volumes of time-ordered observations that form time series [Hu et al., 2018]. Such time series are produced widely and are used in many application domains [Chia and Syed, 2014; Yang et al., 2018; Ding et al., 2016], e.g., finance, biology, transportation, and healthcare. For example, a tenelectrode electrocardiography (ECG) device monitors the tiny electrical changes on the skin of a patient over a time period. Each electrode detects and records changes in the form of a 1-dimensional time series, and the combined records from all the electrodes form a 10-dimensional time series.

Analyses of time series yield knowledge of the underlying processes that generate the time series and in turn enable us to understand those processes [Yang et al., 2013]. In this paper, we focus on detecting outliers in time series, thus identifying observations that differ significantly from the remaining observations [Aggarwal, 2013]. Such outliers can offer important insights. For example, outliers in ECG time series may indicate potential heart attacks while the remaining observations represent normal physical conditions [Chia and Syed, 2014]. Further, we consider outlier detection in an unsupervised setting, where we do not rely on prior labels that indicate outliers. Rather, we aim at identifying outliers in unlabeled time series.

∗Corresponding author.

Most existing methods for outlier detection are based on similarity search [Yeh et al., 2016] and density-based clustering [Breunig et al., 2000]. Recently, neural network based autoencoders [Xia et al., 2015; Chen et al., 2017; Kieu et al., 2018b] are proposed for the detection of outliers, achieving competitive accuracy. The idea is to compress original input data into a compact, hidden representation and then to reconstruct the input data from the hidden representation. Since the hidden representation is very compact, it is only possible to reconstruct representative features from the input, not the specifics of the input data, including any outliers. This way, the difference, or reconstruction errors, between the original data and the reconstructed data indicate how likely it is that observations in the data are outliers. Next, autoencoder ensembles are used to further improve the accuracy that can be achieved when using a single autoencoder that may often overfit to the original data [Chen et al., 2017]. However, effective autoencoder ensembles only exist for non-sequential data, and applying them to time series data directly gives poor results (e.g., cf. the RN columns in Table 2 in Section 4.) We aim at filling this gap by proposing two recurrent neural network autoencoder ensemble frameworks to enable outlier detection in time series.

We use recurrent neural network autoencoders since they have been shown to be effective for time series learning, including for outlier detection [Kieu et al., 2018b]. Autoencoder ensembles rely on the availability of multiple recurrent neural network autoencoders with different network connection structures. We propose to use sparsely-connected recurrent neural networks to achieve such autoencoders. In particular, we propose two ensemble frameworks, an independent framework IF and a shared framework SF that incorporate multiple sparsely-connected RNN autoencoders. Specifically, IF trains multiple autoencoders independently. In contrast, motivated by the principles of multi-task learning, SF trains multiple autoencoders jointly through a shared feature space.

For both frameworks, we use the median of the reconstruction errors of multiple autoencoders as the final reconstruction error that quantifies how likely an observation in a time series is an outlier. As a result, the two frameworks benefit from the combination of multiple encoders and decoders.

To the best of our knowledge, this is the first proposal for using recurrent neural network autoencoder ensembles for outlier detection in time series. We make three contributions.

• We propose sparsely-connected recurrent units that enable autoencoders with different network structures.
• We propose two ensemble frameworks that combine multiple autoencoders based on sparsely-connected recurrent neural networks to advance time series outlier detections.
• We report on experiments using both univariate and multivariate time series, thus offering evidence of the effectiveness of the proposed ensemble frameworks.

2 Preliminaries

2.1 Time Series

A time series T = 〈s1, s2, . . . , sC〉 is a time-ordered sequence of vectors. Each vector si = (s(1) i , s(2) i , . . . , s(k) i ) represents k features of an entity at a specific time point ti, where 1 ≤ i ≤ C. In addition, we have ti < tj when i < j. When k = 1, the time series is univariate; and when k > 1, the time series is multivariate.

2.2 Outlier Detection in Time Series

Given a time series T = 〈s1, s2, . . . , sC〉, we aim at computing an outlier score OS(si) for each vector si such that the higher OS(si) is, the more likely it is that vector si is an outlier.

Next, we proceed to cover the basics of autoencoders and autoencoder ensembles in the context of outlier detection.

2.3 Autoencoders

A classic autoencoder is a feedforward fully-connected neural network, where the number of neurons in the input layer and the output layer are the same and where there are much fewer neurons in the hidden layers than in the input and output layers [Xia et al., 2015]. An autoencoder aims to produce an output that reconstructs its input with noise removed. Since the hidden layers consist of much fewer neurons, to reconstruct the input as closely as possible, the weights in the hidden layers only capture the most representative features of the original input data and ignore the detailed specifics of the input data, such as outliers. In other words, inliers (i.e., normal data) are much easier to reconstruct than outliers. Based on the above, the larger the difference between the output (i.e., the reconstructed input) and the original input, the more likely it is that the corresponding input data is an outlier [Xia et al., 2015].

Classic autoencoders based on feedforward neural networks are often used for non-sequential data. To perform outlier detection in sequential data such as time series, autoencoders based on recurrent neural networks are proposed while reusing the idea that large reconstruction errors indicate outliers [Malhotra et al., 2016; Kieu et al., 2018b].

2.4 Autoencoder Ensembles

Following the principles of ensemble learning, autoencoder ensembles aim to further improve the accuracy of outlier detection based on autoencoders [Chen et al., 2017]. The main idea is to build a set of autoencoders and to consider the reconstruction errors from multiple autoencoders when detecting outliers. Using a set of classic, fully-connected autoencoders is not helpful since the network structures are the same across the different autoencoders. Instead, for each autoencoder, it is helpful to randomly remove some connections to obtain a sparsely-connected autoencoder (see Figure 1). Then, an autoencoder ensemble consists of multiple sparsely-connected autoencoders with different network structures, which helps reduce the variances of the overall reconstruction errors [Chen et al., 2017].

(b) Sparsely-connected layers

Figure 1: Fully-connected layers vs. sparsely-connected layers.

However, autoencoder ensembles are only available for nonsequential data, and these cannot be applied directly to sequential data such as time series (see a summary in Table 1). We fill this gap by proposing two autoencoder ensemble frameworks that are able to perform outlier detection in time series.

3 Autoencoder Ensembles For Time Series

We use recurrent neural network (RNN) autoencoders for time series because RNNs have proven to be effective for time series modeling and learning. We first discuss how to build sparsely connected RNNs, and then we propose two different ensemble frameworks that integrate multiple sparsely connected RNN autoencoders.

3.1 Sparsely-connected RNNs (S-RNNs)

A sequence-to-sequence model [Sutskever et al., 2014] is often used as an autoencoder for outlier detection in time series. Such a model has an encoder and a decoder, as shown in Figure 2.

In the encoder, each vector st in time series T is fed into an RNN unit (shown as a square in Figure 2) to perform the following computation.

Here, st is the vector at time step t in the time series and hidden state h(E) t-1 is the output of the previous RNN unit at time step t - 1 in the encoder. Next, f(·) is a non-linear function, ranging from the basic tanh or sigmoid to the more sophisticated Long-Short Term Memory (LSTM) [Hochreiter and Schmidhuber, 1997] or Gated Recurrent Unit (GRU) [Chung et al., 2014]. Based on the above, we obtain a hidden state h(E) t of the current RNN unit at time step t, which is then fed into the next RNN unit at time step t + 1.

In the decoder, we reconstruct the time series in reverse order, i.e., ˆ T = 〈ˆsC,ˆsC-1, . . . ,ˆs1〉. First, the last hidden state of the encoder is used as the first hidden state of the decoder. Based on the previous hidden state of the decoder h(D) t+1 and the previous reconstructed vector ˆst+1, we reconstruct the current vector using Equation 2 and also compute the current hidden state using Equation 3, where f(·) and g(·) are again non-linear functions.

Following the idea from existing autoencoder ensembles on non-sequential data, we aim to construct multiple autoencoders with different network structures. However, randomly removing connections between RNN units does not work in this setting because no matter which connection is removed, the RNN units become disconnected, rendering it impossible to train the network.

To contend with this challenge, we consider Recurrent Skip Connection Networks (RSCNs) that employ additional auxiliary connections among the RNN units [Wang and Tian, 2016]. In particular, each RNN unit not only considers the previous hidden state but also considers additional hidden states in the past. Formally, we have:

Here, we consider the previous hidden state ht-1 and the state of the hidden state L steps earlier. And we often use two different functions f(·) and f ′ (·). Figures 3(a) and (c) show examples of RSCNs with L = 1 and L = 2.

Next, based on the RSCNs, we randomly remove some connections between hidden states. Specifically, we introduce a sparseness weight vector wt = (w(f) t ,w(f ′ ) t ) to control which connections should be removed at each time step t, where w(f ) t ∈ {0, 1} and w(f ′ ) t ∈ {0, 1}. And we ensure that at least one element in wt is not equal to 0, i.e., wt = (0, 1), wt = (1, 0), or wt = (1, 1).

Based on wt, we generate sparsely-connected RNNs (S-RNNs), where at each unit, the computation is as defined in Equation 5.

where ‖wt‖0 denotes the number of non-zero elements in vector wt. Figures 3(b) and (d) show examples of S-RNNs when L = 1 and L = 2.

S-RNNs differ from RNNs using Dropout [Gal and Ghahramani, 2016]. The network connections in sparselyconnected RNNs are fixed throughout the training phase, whereas RNNs with Dropout randomly remove connections at every training epoch.

3.2 S-RNNAutoencoder Ensembles

To enable an ensemble, we build a set of S-RNN autoencoders. We then propose two different frameworks for integrating the autoencoders into ensembles.

Independent Framework

Figure 4 shows the basic, independent framework of an S-RNN autoencoder ensemble. The ensemble contains N S-RNN autoencoders that each consists of an encoder Ei and a decoder Di, 1 ≤ i ≤ N. Further, each autoencoder has its distinct sparseness weight vectors.

Each autoencoder in the ensemble is trained independently by minimizing the objective function Ji that measures the difference between the input vectors in the original time series and the reconstructed vectors, defined in Equation 6.

where ˆs(Di) t denotes the reconstructed vector at time step t from decoder Di, and ‖ · ‖2 is the L2-norm of a vector.

Shared Framework

The basic framework trains different autoencoders independently, meaning that different autoencoders do not interact during the training phase. However, since all autoencoders try to reconstruct the same, original time series, it is relevant to enable interactions among the autoencoders. Motivated by the principles of multi-task learning [Long et al., 2017; Cirstea et al., 2018; Kieu et al., 2018a], we propose a shared framework that incorporates interactions among different autoencoders. More specifically, given N tasks where each task reconstructs the original time series, we let the N tasks interact through a shared layer. The shared framework is shown in Figure 5.

The shared framework, shown in Figure 5, uses a shared layer, denoted as h(E) C , to concatenate the linear combinations

(using linear weight matrices W(Ei) ) of all the last hidden states of all the encoders. Formally, we have:

Each decoder Di employs the concatenated hidden states h(E) C as the initial hidden state when reconstructing time series ˆ T (i) = 〈ˆs(i) C , . . . , ˆs(i) 2 , ˆs(i) 1 〉. In the shared framework, all autoencoders are trained jointly by minimizing the objective function J that sums up the reconstruction errors of all autoencoders and an L1 regularization term on the shared hidden state:

Here, λ is a weight that controls the importance of the L1 regularization ‖h(E) C ‖1. The L1 regularization has the effect of making the shared hidden state h(E) C sparse. This avoids cases where some encoders overfit to the original time series and helps make the decoders robust and less affected by outliers. Hence, when autoencoders meet outliers, the difference between original time series and reconstructed time series is more pronounced.

3.3 Ensemble Outlier Scoring

Following the principles of autoencoder ensembles for nonsequential data [Chen et al., 2017], we calculate the outlier score of each vector in a time series when using the ensemble frameworks. Recall that we have N autoencoders that reconstruct the original time series T = 〈s1, s2, . . . , sC〉. Thus, we obtain N reconstructed time series ˆ T (i) = 〈ˆs(i) C , . . . , ˆs(i) 2 , ˆs(i) 1 〉, where 1 ≤ i ≤ N. For each vector sk in the original time series T , we compute N reconstruction errors {‖sk -ˆs(1) k ‖22 , ‖sk-ˆs(2) k ‖22 , . . . , ‖sk-ˆs(N) k ‖22 }. We use the median of the N errors as the final outlier score of vector sk: OS(sk) = median(‖sk -ˆs(1) k ‖22 , ‖sk-ˆs(2) k ‖22 , . . . , ‖skˆs(N) k ‖22 ). Usingmedian instead of mean reduces the influence of the reconstruction errors from the autoencoders that overfit to the original time series.

4 Experiments

4.1 Experimental Setup

Data Sets

We use two real-world time series repositories, the univariate time series repository Numenta Anomaly Benchmark (NAB)∗ and the multivariate time series repository Electrocardiography (ECG)† . NAB comprises six sets of time series from different domains, where each set has ca. 10 univariate time series and each time series contains from 5,000 to 20,000 observations.

∗ https://github.com/numenta/NAB

† http://www.cs.ucr.edu/ eamonn/discords/ECG data.zip/

ECG comprises seven 3-dimensional time series from seven patients, where each time series has 3,750 to 5,400 observations. For both repositories, ground truth labels of outlier observations are available. However, consistent with the unsupervised setting, we do not use these labels for training, but only use them for evaluating accuracy.

Existing Solutions

We compare the proposed independent and shared ensemble frameworks (IF and SF) with seven competing solutions-(1) Local Outlier Factor (LOF) [Breunig et al., 2000], a wellknown density-based outlier detection method; (2) One-class Support Vector Machines (SVM) [Manevitz and Yousef, 2001], a kernel-based method, (3) Isolation Forest (ISF) [Liu et al., 2008], which is a randomized clustering forest, (4) Matrix Profile I (MP) [Yeh et al., 2016], which is the state-ofthe-art similarity-based outlier detection method, (5) RandNet (RN) [Chen et al., 2017], which uses the state-of-theart feedforward autoencoder ensembles for non-sequential data, (6) Convolutional Neural Networks based Autoencoder (CNN) [Kieu et al., 2018b], which treats time series as images and employ a CNN autoencoder to reconstruct the image, and (7) an LSTM based Autoencoder(LSTM) [Malhotra et al., 2016], which is the state-of-the-art deep learning outlier detection method for time series. In addition, we replace the LSTM units in method LSTM with RSCN units [Wang and Tian, 2016] to study the effect of using a single RSCN autoencoder (RSCN) versus the use of multiple S-RNN autoencoders in IF and SF. Methods LOF, SVM, and ISF were originally proposed for non-sequential data but can also be applied to sequential data with competitive accuracy [Aggarwal, 2013]. This is why we include them in the experiments.

Implementation Details

All algorithms are implemented in Python 3.5. Methods IF and SF and the deep learning methods, i.e., CNN, LSTM, and RSCN, are implemented using TensorFlow 1.4.0, while the remaining methods, i.e., LOF, SVM, ISF, and MP are implemented using Scikit-learn 1.19. The source code is available at https://github.com/tungk/OED. Experiments are performed on a Linux workstation with dual 12-core Xeon E5 CPUs, 64 GB RAM, and 2 K40M GPUs.

Hyperparameters Settings

For all deep learning based methods, we use Adadelta [Zeiler, 2012] as the optimizer, and we set their learning rates to 10-3 . For the proposed ensemble frameworks, we use an LSTM unit and tanh as the functions f and f ′ in Equation 5; we set the number of hidden LSTM units to 8; we set the default number of autoencoders N to 40, and we also study the effect of varying N from 10 to 40; and we set λ to 0.005. We randomly vary the skip connection jump step size L from 1 to 10, and we randomly choose the sparse weight vector wt. For MP, we set the pattern size to 10. For RN and all the other baselines, we follow the settings used by [Chen et al., 2017] and [Kieu et al., 2018b], respectively.

Evaluation Metrics

A typical approach to decide which vectors in a time series are outliers is to set a threshold and to consider the vectors whose outlier scores exceed the threshold as outliers. However, setting the threshold is non-trivial and often requires human experts or prior knowledge. Instead, following the evaluation metrics used for evaluating autoencoder ensembles on nonsequential data [Chen et al., 2017], we employ two metrics that consider all possible thresholds-Area Under the Curve of Precision-Recall (PR-AUC) [Sammut and Webb, 2017] and Area Under the Curve of Receiver Operating Characteristic (ROC-AUC) [Sammut andWebb, 2017]. In other words, the two metrics do not depend on a specific threshold. Rather, they reflect the full trade-off among true positives, true negatives, false positives, and false negatives. Higher PR-AUC and ROCAUC values indicate higher accuracy.

4.2 Experimental Results

Overall Accuracy

We report PR-AUC and ROC-AUC for all methods in Table 2. First, the deep learning based methods and the non-deep learning methods show similar results w.r.t. PR-AUC. However, the deep learning based methods perform better when using ROC-AUC in most cases. This indicates that the deep learning based methods have lower false positive rates and higher true negative rates, which is highly desired for outlier detection. Second, SF and IF outperform RN, indicating that S-RNN autoencoder ensembles are better suited for sequential data than are feedforward autoencoder ensembles. Third, the two proposed ensemble methods most often outperform the individual methods. In particular, IF and SF outperform the other methods in most cases on both univariate and multivariate time series. Specifically, IF performs the best in 4 out of 13 cases, and SF is best in 6 out of 13 cases for both evaluation metrics, indicating that the proposed ensemble frameworks are capable of improving effectiveness and robustness. Fourth, SF performs better than IF on average-when considering average PR-AUC and ROC-AUC, SF is best and IF is often second best on both univariate and multivariate time series. This indicates that multi-task learning can be applied in an ensemble framework to further enhance accuracy.

Effect of N

We study the effect of the number of autoencoders N in the two ensemble frameworks. In particular, we vary N among 10, 20, 30, and 40. Figures 6 and 7 report PR-AUC and ROC-AUC, respectively. Due to the space limitation, we only report results on 4 NAB datasets and 5 ECG datasets. As N increases, both ensemble frameworks achieve better results, i.e., higher PRAUC and higher ROC-AUC scores. This suggests that having more autoencoders with different structures in an ensemble yields better accuracy.

IF vs. SF

Finally, we study the difference between IF and SF. In all previous experiments, IF and SF use randomly generated S-RNNs, meaning that the S-RNNs used in IF and SF may have different structures. In the final set of experiments, we make sure that both IF and SF use the same set of S-RNNs. We first generate 40 S-RNNs based autoencoders and then build IF and SF on top of the 40 autoencoders. Due to the space limitation, we only report the results on the remaining 2 NAB datasets and 2 ECG datasets.

Figure 8: IF vs. SF with the Same Set of Autoencoders

Figure 9: Effect of L, PR-AUC and ROC-AUC

Figure 8 shows that SF outperforms IF when both framework have the same set of autoencoders. This suggests that learning multiple autoencoders in a shared multi-task manner is indeed helpful. However, a disadvantage of SF is its high memory consumption that occurs because it is necessary to train many autoencoders together: the shared layer needs to combine the last states of all autoencoders before proceeding to the decoding phase. In contrast, we can train different autoencoders in IF in parallel and then calculate outlier scores at the end.

Effect of L

We study the effect of varying L when producing recurrent skip connection networks. We only report results on SF since IF yields similar results. We vary L among 1, 2, 5, 10, and 20. Figures 9(a) and (b) show PR-AUC and ROC-AUC, respectively. We only report results on the remaining 2 NAB datasets and 2 ECG datasets. We observe that from L = 1 to L = 10, L does not affect the accuracy significantly, indicating that the ensemble frameworks are insensitive to small jump steps. When L = 20, the accuracy starts to decrease, suggesting that (1) important temporal information was lost when combining large jump steps with sparse connections and that (2) the model was forced to employ obsolete historical information that adversely affects the accuracy.

5 RelatedWork

Outlier Detection using Autoencoders

Deep learning based outlier detection methods have been applied widely in many domains, e.g., computer vision [Zhao et al., 2017], network analysis [Luo and Nagarajan, 2018], and robotics [Park et al., 2016]. Autoencoders are at the core of these methods. In addition, studies exist that modify classic autoencoders to achieve denoising autoencoders [Tagawa et al., 2014] and variational autoencoders [Liao et al., 2018]. Our study falls into the category of outlier detection in time series using deep learning, where the fundamental problems are to learn a representation of the time series in a smaller vector space and to reconstruct the original time series from that vector space [Malhotra et al., 2016; Kieu et al., 2018b]. However, existing studies are limited to a single recurrent neural network autoencoder. In contrast, we propose two novel ensemble frameworks that exploit multiple recurrent neural network autoencoders for outlier detection in time series. The experimental results provide evidence that the ensemble frameworks are effective and are capable of outperforming existing methods that use only a single autoencoder.

Deep Ensemble Models

Ensemble models with deep learning have been applied to different supervised learning tasks, including classification [Akhtar et al., 2017] and regression [Lee et al., 2017]. Two popular approaches are bagging, where multiple models are trained with the same structure using randomly drawn subsets of training data [Guo et al., 2015], and stacking, where multiple models are trained with different structures using the entire training data [Deng and Platt, 2014]. However, only a few deep ensembles exist for unsupervised learning, specifically for outlier detection [Aggarwal and Sathe, 2017]. An ensemble outlier detection method is proposed [Chen et al., 2017] that works only for non-sequential data. This paper is the first to propose autoencoder ensembles for unsupervised outlier detection in time series. The proposed ensembles adopt the stacking approach.

6 Conclusion and Outlook

We propose two autoencoder ensemble frameworks based on sparsely-connected recurrent neural networks for unsupervised outlier detection in time series. One of the frameworks trains multiple autoencoders independently while the other framework trains multiple autoencoders jointly in a multi-task learning fashion. Experimental studies show that the proposed autoencoder ensembles are effective and outperform baselines and state-of-the-art methods.

In future work, it is of interest to study different autoencoder structures, e.g., denoising autoencoders [Vincent et al., 2008] and the use of advanced deep neural network structures, e.g., embedding [Chen et al., 2016] and attention [Luong et al., 2015], to further improve accuracy.

Acknowledgments

This research was supported in part by a grant from the Obel Family Foundation, a grant from Independent Research Fund Denmark, and by the DiCyPS center, funded by Innovation Fund Denmark.