E²GAN: End-to-End Generative Adversarial Network for Multivariate Time Series Imputation

1 Introduction

Recent advances in sensors and hardwares promote the rapid emergence of electronic data especially the multivariate time series data. Examples of multivariate time series appear in fields like medicine, meteorology, economics and transportation science [Chatfield, 2016]. Applications of multivariate time series include predicting the health status of patients [Hyland et al., 2018], weather forecasting [Bright et al., 2015], stock market analysis [Granger and Newbold, 2014], adjusting the traffic flow of big cities [Lv et al., 2015], etc. The analysis of time series can also lead to a deep and thorough understanding of the time series itself.

Nevertheless, missing values in multivariate time series data poses a challenge for engineers and researchers, due to the broken of collection sensors, the ill designed collection process and mistakes made by humans. Taking PhysioNet challenge 2012 dataset [Silva et al., 2012], a public medical dataset, as an example, the average missing rate of this multivariate time series data is above 80%. The missing values hinder the advanced analysis of time series [Berglund et al., 2015].

∗Corresponding author.

Traditional missing values processing methods can be summarized into two categories. The first one tries to delete the observations which are partially missing. Deletion methods prevent the further analysis in some way [Graham, 2009]. The imputation method that imputes the missing values with reasonable values is the other type of method to deal with missing values. State-of-the-art imputation algorithms include K-Nearest Neighbor (KNN) based imputation [Hudak et al., 2008], Matrix Factorization based imputation [Acar et al., 2010] and Recurrent Neural Networks (RNN) based imputation [Berglund et al., 2015; Che et al., 2018; Cao et al., 2018].

Recently, Generative Adversarial Networks (GAN) [Goodfellow et al., 2014] based methods, which first learn to generate new samples that follow the distribution of the training dataset and then impute the missing values, have achieved state-of-the-art performance. [Luo et al., 2018] proposes a two-stage time series imputation method. This method first trains a GAN model. At the second stage, for each sample, it tries to optimize the "noise" input vector and find the best matched input vector of the generator so that the generated sample is most similar to the original one. However, this twostage method needs a lot of time to find the best matched input vector and this vector is not always the best especially when the initial value of the "noise" is not properly set.

Inspired by [Sabokrou et al., 2018], this paper propose an end-to-end GAN-based imputation model E2GAN, which not only simplifies the process of time series imputation but also generates more reasonable values for the filling of missing values. E2GAN takes a compressing and reconstructing strategy to avoid the "noise" optimization stage in [Luo et al., 2018]. In the generator, we add a random vector to the original sample and try to map it into a low-dimensional vector. Then we reconstruct it from the low-dimensional vector. The generator seeks to find a network structure that can not only best compress and reconstruct the multivariate time series but also fool the discriminator. The proposed method automatically learns internal representations of the time series and try its best to reconstruct this temporal data. The new architecture also improves the imputation performance by getting a better feature representation of samples, which contributes to a better reconstructed samples and improves the imputation results.

Finally, we use the reconstructed sample to impute the missing values. The experiments conducted on two real datasets show that our method achieves a new state-of-the-art imputation accuracy and achieves better time efficiency than the two-stage method.

In summary, the main contributions of this paper are as follows: (1) We propose a novel end-to-end generative adversarial network that simplifies the process of time series imputation, i.e., reduces the training time. (2) The noised compressing and reconstructing strategy makes sure that the imputed values more reasonable than [Luo et al., 2018]'s. (3) Experiments on multiple real-world datasets show that the proposed method achieves new state-of-the-art imputation accuracy.

2 RelatedWorks

There is a lot of literatures on the processing and imputation of missing values. Due to the limited space, we only describe a few closely related ones. Deletion method, who simply deletes the partly missed observations, prevents the further analysis of dataset due to the deleted information [Graham, 2009]. Statistical imputation tries to fill missing values by mean value [Kantardzic, 2011], last observed value [Amiri and Jensen, 2016] and mode value [Purwar and Singh, 2015]. Many previous works show that machine learning based imputation methods are useful for data imputation or time series imputation. Multivariate Imputation by Chained Equations (MICE) [White et al., 2011] fills the missing values by using iterative regression model. MICE imputes each incomplete variable by a separate model. ARIMA [Box et al., 2015], ARFIMA [Galbraith and Zinde-Walsh, 2001] and SARIMA [Hamzac¸ebi, 2008] are representative autoregressive methods that can be used to predict and impute missing values. K-Nearest Neighbor (KNN) [Hudak et al., 2008] algorithm uses the mean value of k nearest neighbors to fill missing values. Matrix Factorization [Acar et al., 2010] algorithm factorizes the incomplete dataset into low-rank matrices and adopts the product of these two matrices to impute the missing values.

There are also some recurrent neural networks based imputation methods. [Berglund et al., 2015] have proposed two probabilistic interpretations of bidirectional recurrent neural networks that can be used to reconstruct missing samples efficiently. [Che et al., 2018] have proposed GRUD, which imputes missing values of clinical dataset with a smooth fasion. GRUD takes the advantage of last observed value and mean value to represent missing patterns of incomplete time series. BRITS [Cao et al., 2018] is a novel neural network method that directly learns the missing values in a bidirectional recurrent dynamical system, without any specific assumption.

Recently, Generative Adversarial Networks (GAN) [Goodfellow et al., 2014], which seeks to generate new samples that obey the distribution of training dataset, has been used to impute missing values. The generated samples, which are designed to fill the missing values, significantly boost the imputation accuracy. GAIN [Yoon et al., 2018], a GAN-based imputation method, uses a hint vector that is conditioned on what we actually observed to impute missing values. GAIN has made tremendous advances in data imputation. However, the main drawback of GAIN is the weak ability to impute time series. [Luo et al., 2018] have proposed a two-stage GAN based time series imputation method. This method first train a GAN model that can produce new sample from a input vector. In the second stage, this method tries to find a "best" matched input "noise" vector of the generator so that the generated sample is most similar to the original one. This two-stage training strategy needs a lot of time to train and the "best" matched vector is not always the best at some point.

3 ProblemFormulation

A d-dimensional multivariate time series x, observed at t=(t0, . . . , tn-1), is denoted by x=(x0, . . . , xn-1) ∈ Rd×n , where t is the observing timestamp, and xt is the tth observation. The locations of the missing values is of great importance. We record the locations of missing values and the time lags of two adjacent values.

Suppose that m∈ Rd×n is a mask matrix that takes values in {0, 1}. mmeans whether the values of x exist or not, for example, if xji exists, mji =1, otherwise, 0. The purpose of multivariate time series imputation is to impute the missing values in x as accurate as possible.

The following part is an intuitive explanation of a 3dimensional multivariate time series x and its corresponding m.

We define a matrix δ ∈ Rd×n that records the time lag between current value and last observed value. The following part shows the calculation and a calculated example of the δ.

4 Approach

In this part, we show the details of the proposed method. A Generative Adversarial Network (GAN) [Goodfellow et al., 2014] is composed by a Generator (G) and a Discriminator (D), whose goal, respectively, is to map low-dimensional vectors (random noise) to high-dimensional samples and distinguish between the fake data and the real data. They are jointly trained by adopting a min-max game. The ultimate aim of the GAN is to produce new samples that obey the distribution of the training dataset, by the adversarial training of the generator and discriminator. However, the original GAN can rarely get out of the mode collapse problem. Recently, [Arjovsky et al., 2017] have proposed the Wasserstein GAN (WGAN), which can improve the learning stability and get away from the problem of mode collapse. The formulations of WGAN is a little different from the original one:

In our generator, we take advantage of auto-encoder and recurrent cell. We compress the input incomplete time series x into a low-dimensional vector z with the help of recurrent neural network. Then we use this vector to reconstruct a complete time series x′ to fool the discriminator. Meanwhile, we also force the x′ as close as possible to x by using a squared error loss function. The discriminator of our method attempts to distinguish actual incomplete time series x and the fake but complete sample x′ through the adoption of recursive neural network.

4.1 GRUCell for Imputation

In the previous subsection, we have mentioned the mapping from high-dimensional incomplete time series to lowdimensional vector with the help of recurrent neural network. In this subsection, we will show the structure of this recurrent neural network that can not only compress the incomplete time series x but also reconstruct complete time series x′ from a low-dimensional vector z.

We have adopted the GRUI (GRU for Imputation), proposed in [Luo et al., 2018], to process the incomplete time series. The GRUI is inspired by the GRUD proposed by [Che et al., 2018]. Nevertheless, the GRUI is more simple than the GRUD. The time lag of two adjacent existent values is not always fixed due to the missing values. These irregular time lags should be made good use of. It's intuitive to decay the historical influence of the past observations if the current value is missed for a long time. The main idea of GRUI is to introduce a time decay vector β to decrease the memory of GRU cell. The following are the update functions of GRUI.

where δ is the time lag matrix introduced in the "Problem Formulation" part, and Wβ, W˜h , Wr, Wµ, bβ, bµ, br, b˜h are training parameters. The formulation of β guarantees that with the increase of time lags δ, the value of β decreases. The smaller the δ, the bigger the β. This formulation also make sure that β ∈ (0, 1]. The GRUI is not the research focus of this paper, nevertheless, we can process the incomplete time series successfully by using the GRUI.

4.2 Generator Network Architecture

The generator of proposed method is shown at Figure 2. Since the auto-encoder is designed to reconstruct target samples, we choose it to generate complete time series x′ . Different from traditional auto-encoder, we add a random noise η which is sampled from a standard distribution N(0, 0.01) to the original sample. We use a similar idea just like the denoising auto-encoder, that is, compress and reconstruct the original samples from the destroyed samples. The main idea of denoising auto-encoder [Vincent et al., 2008] is to drop out original samples and reconstruct the complete samples. However, the way to destroy original samples of our method is to add some noise rather than drop out some values of the input samples. The original samples is naturally missed, it is not a good idea to drop out the already missed samples especially the missing rates of some datasets are very high. For the naturally incomplete dataset, we just add some noise to the input samples and train an denoising auto-encoder.

Since the purpose of the generator is to produce new sample x′ that is most similar to x, we add a squared error loss to the loss function of the generator. The loss function of the generator is a lot different from the one of traditional WGAN:

where λ is a hyper-parameter that controls the weight of the discriminative loss and the squared error loss. In this way, x′ can be used to impute the missing values of x.

Figure 2 is a visual explanation of the generator network. To implement the generator network, we first feed the GRUI cell with the incomplete time series x and its time lags matrix

• δ. We use zero value to replace the missing values of x at the input stage of GRUI. After a recurrent processing of the input time series, the last hidden state of the recurrent neural network will flow to a fully connected layer. The output of this fully connected layer is the compressed low-dimensional vector z.

Next, we take z as the initial input of another fully connected layer. Then we use this output as the very first input of another GRUI layer. The current output of this GRUI layer will be fed into the next iteration of the same GRUI layer. At the final stage, we combine all the outputs of this GRUI layer as the generated sample x′ .

4.3 Discriminator Network Architecture

The network structure of discriminator is a decoder. In other words, the discriminator is also made up of a GRUI layer and a fully connected layer. The task of the discriminator is to distinguish between fake sample x′ and true sample x. The output of the discriminator is a probability that indicates the degree of authenticity. We try to find a set of parameters that can produce a high probability when we feed true sample x, and produce a low probability when we feed fake sample x′ . Therefore, the loss function of the discriminator can be designed as following shows.

We feed incomplete time series x or complete time series x′ , with their corresponding δ, into the discriminator. With the help of GRUI, the time series can be successfully handled. The last hidden state of GRUI layer is fed into one fully connected layer that outputs the probability of being true. In order to enhance the generator, we update k times for generator and 1 time for discriminator at one iteration.

4.4 Imputation

In this paper, for every incomplete time series x, we try to map it into a low-dimensional vector z and reconstruct a complete time series x′ from z, so that the fake time series x′ is most close to the original one. We use the corresponding values of x′ to fill in the missing values of x. The imputation formula can be summarized as follows.

5 Experiments

In this section, the proposed method is evaluated on two realworld datasets. The experimental results are analyzed and compared in details.

5.1 Datasets and Baseline Methods

We use two real-world datasets including a medical dataset and a meteorologic dataset for the evaluation of the proposed method.

• PhysioNet Challenge 2012 dataset (PhysioNet). The PhysioNet dataset, a public 80.67% missing medical dataset provided by [Silva et al., 2012], is made up of records from 4000 ICU stays. Every ICU stay is a 48 hours multivariate incomplete time series that includes
• 42 features. The focus of the PhysioNet dataset is to develop methods that can predict in-hospital mortality well (classification task). 554 (13.85%) patients died in hospital, i.e., with positive label. The area under ROC curve (AUC) score is used for evaluating the performance of proposed method because of the non-balanced dataset. It is impossible to directly calculate the imputation accuracy since we can not get the complete dataset. We impute this dataset by different imputation methods and then use these imputed datasets to train same type of classifiers. Finally, the mortality prediction results calculated by these classifiers are used to indirectly determine the performance of different imputation methods.
• KDD CUP 2018 Dataset (KDD). 1 The KDD dataset (15% missing) is a public meteorologic dataset that comes from the KDD CUP Challenge 2018. The KDD dataset contains air quality and weather data which is hourly collected between 2017/1/30 to 2018/1/30. There are two tasks that conducted on this dataset. 1) Imputation task. We randomly drop out p percent of all time series, where p ∈ {10, 20, . . . , 80}. Then we impute these time series and calculate the imputation accuracy by the mean squared error (MSE) between original values and imputed values. 2) Downstream task. We randomly drop out 50 percent of all time series. Then we use different methods to impute them and get different imputed datasets. We use these datasets to train same type of regression models that predict the mean air quality of the next 6 hours. Finally, we get the imputation accuracy indirectly by the performances of this downstream task.

The baseline models are:

• Statistical imputationmethods: We simply replace the missing values with zero value, mean value and last observed value.
• Matrix Factorization (MF) imputation [Acar et al., 2010]: MF method is used to factorise the incomplete matrix into low-rank matrices and fill the missing values.
• KNN [Hudak et al., 2008]: The missing values are replaced by using the k nearest neighbor samples.
• MICE [White et al., 2011]: Multivariate Imputation by Chained Equations (MICE) fills the missing values by using iterative regression model.
• GRUD [Che et al., 2018]: GRUD can be used to impute missing values. We use it as one of the baselines.
• GAN-2-stage [Luo et al., 2018]: This method uses a GAN based two-stage method to impute missing values. We call this method as "GAN-2-stage".
• GAIN [Yoon et al., 2018]: GAIN is another GAN based imputation method that uses a hint vector to impute the missing values.
• BRITS [Cao et al., 2018]: This method is one of the state-of-the-art methods that uses bidirectional recurrent network to impute time series.

1 KDD CUP. Available on: http://www.kdd.org/kdd2018/, 2018.

5.2 Implementation Details

We use ADAM algorithm to train networks. The hidden units number of all GRUI cells are 64. The dimension of lowdimensional vector z is also 64. The dropout rates of our experiments are always fixed with 0.5. We adopt the batch normalization technology on the GRUI layers. All input datasets are normalized with zero mean and unit variance. For all the experiments, we select 10% of dataset as validation set and another 10% as test set. Before the training of GAN, the generator is pre-trained for epochs with a mean squared error loss for fitting the next value in the training datasets.

5.3 Performance Comparison for Time series Imputation

Table 1 is the imputation results on KDD dataset by using proposed method and baseline methods which include statistical imputation, KNN imputation, MF imputation, MICE imputation, BRITS and GAN based imputation (GAN-2-stages and GAIN). The first column of Table 1 is missing rate which indicates how many percent values are dropped, and other columns are mean squared error. Our parameters for the KDD dataset are: epoch is 15, batch size is 16, learning rate is 0.005, pretrain epoch is 10, λ is 2. We can see that, in all cases, the GAN based methods gain the best imputation accuracies. The proposed method is one of the best methods and wins others methods in most cases. Furthermore, the proposed method gains huge advantage in time efficiency, we will show it at the latter part of this paper.

5.4 Performance Comparison for Downstream Applications

Since we can not always get the complete dataset, it is impossible to directly compare the imputation accuracies. We use the performances of downstream applications to indirectly measure imputation accuracies. The downstream applications mainly contain two type of tasks which include the classification task that uses the PhysioNet dataset, and the regression task which uses the 50% discarded KDD dataset.

For the classification task which uses the PhysioNet dataset, we first impute this dataset with different comparative imputation methods. Then we use these datasets to train the same type of classifiers including logistic regression classifier, SVM (with RBF, Linear, Poly and Sigmoid kernels) classifiers, random forest classifier and RNN classifier. The RNN classifier is made up of a simple GRU layer and a fully connected layer. The parameters of PhysioNet are: epoch is 10, learning rate is 0.005, λ is 50, pretrain epoch is 5. Table 2 is the AUC scores of the classification task that uses the PhysioNet dataset. We can see that, the classifiers trained on the dataset that imputed by our proposed method always gain the best AUC scores. This phenomenon has shown the success of proposed method. We can also summarize that, the new state-of-the-art mortality prediction result (0.8724) on the PhysioNet dataset is achieved by using our method while the old one is 0.8603.

We also compare the mortality prediction results with other methods that do not impute missing values and directly classify the patients. Table 3 shows the detail results. It is obvious that simple RNN model trained on imputed dataset gains the best AUC score.

For the downstream task of 50% missed KDD dataset, we first impute it by using baseline models and proposed method. Then we take advantage of these datasets to train same tpye of regression models to predict the mean air quality of next 6 hours. We adopt the effects of these downstream applications, i.e., MSE, to indirectly measure the imputation accuracies. Figure 3 provides the detail results. We can see that, the regression models trained on the dataset that were imputed by the proposed method, achieve the best performance.

5.5 Discussions

Time Efficiency

We investigate the time efficiency of proposed method. The size of dataset and number of epochs are the most influential factors of time efficiency. It is difficult to compare the time efficiency of neural networks, especially the generative adversarial networks, because of different parameter settings. We try to compare our method with another GAN based time series imputation method. We fix the hardware, epoch, and some others parameters, and then compare the execution time of GAN-2-stages and our method. For the PhysioNet dataset, our method takes 204±5 seconds to reach the best AUC score, while the GAN-2-stages takes 2650±10 seconds. For the KDD dataset, our method costs 105±3 seconds and GAN-2-stages costs 1805±8 seconds. The main reason of this phenomenon is the drop of optimizing input "noise" vector of the generator. In other words, the proposed method only need to train a GAN model and directly impute missing values. This end-to-end imputation method saves a lot of time compared to the two stages imputation method.

Influence of Dimensions

We also investigate the influence of dimensions as shown in Figure 4. The red lines are performance and the blue lines are time. The performances of downstream applications improve with the increasing of dimensions. However, there are some peaks at the performance lines. This indicates that some dimensions are more or less influential than others. And this phenomenon can be used to judge the importance of features if we draw a more detailed figure. The blue lines show how long the imputation will take with different dimensional datasets. We can conclude that the execution time grows with the raise of dimension. Besides, it is obvious that the growth of execution time is linear. It proves the proposed method's superiority of time efficiency in some way.

Ablation Study

We have evaluated the effects of the discriminator and the noise vector η. Table 4 shows the results on the KDD dataset (measured by MSE). The first row is the missing rate. The second row shows results of E2GAN, and the third row shows results of E2GAN with no discriminator. The last row shows results of E2GAN with no noise vector η. As we can observe, the discriminator and the noise vector η are both helpful. The imputation accuracy decreases 8.35% without the discriminator and 8.5% without the noise vector η in average.

6 Conclusion

We propose a novel end-to-end model E2GAN for the imputation of missing values in multivariate time series by taking advantage of the generative adversarial networks. Autoencoder and GRUI are used to generate new complete sample that is most close to the original incomplete one with the help of discriminative loss and squared error loss. Thus, we can impute the missing values with this generated new complete sample within a short training time. Various experiments with real-world datasets show that the proposed method boosts the imputation accuracy and achieves better classification/regression results on the downstream applications. With the help of our proposed method, we also get a new state-of-the-art mortality prediction result.

Acknowledgments

We thank the reviewers for their constructive comments. This work is partially supported by National Natural Science Foundation of China (No. 61772289 and No. U1836109). This work is also partially supported by Natural Science Foundation of Tianjin (No. 18ZXZNGX00110 and No. 17JCQNJC00200)