DEGAIN as tool for Missing Data Imputation

Abstract

This paper focuses on the use of machine learning methods to deal with missing data imputation. In particular, we describe a generative adversarial network (GAN) based model called DEGAIN to estimate the missing values in the dataset. We present the performance of the presented method comparing the results with some of the existing methods on the publicly available Letter Recognition and SPAM datasets. The Letter dataset consists of 20000 samples and 16 input features and the SPAM dataset consists of 4601 samples and 57 input features. The results show that the proposed DEGAIN outperforms the existing ones in terms of root mean square error and Frechet Inception distance metrics.

Keywords

• eol>Machine Learning
• Missing Data
• Data Imputation
• Generative Networks

1. Introduction

(GPR) [ 14 ], support vector machine (SVM) [ 15 ], long short-term memory (LSTM) [ 16 ], decision trees (DT) [ 17 ], random forests (RF) [ 18 ], auto-encoder (AE) [ 19 ], Expectation Maximization (EM) [ 20 ] and Generative adversarial networks (GAN) [ 21 ]. One of the main diferences of the traditional methods and the machine learning based methods to handle the missing data is the capability of the optimization in ML. The ML based methods follow an optimization process. ML based methods can also extract the relation between data points, and therefore more precise estimation on the missing values.

Among the ML based algorithms, Generative Adversarial Networks (GANs) has attracted many researchers in recent years. The GAN has many applications, mostly with focus on generating synthetic data. The missing value estimation could be considered as synthetic data generation. Therefore, it is possible to use such networks in handling the missing data problem. However, the performance of the algorithms are dependent to many variables such as data type, for instance, if the data belongs to the category of image, clinical dataset, energy dataset or etc. Accordingly, many variations of the GAN are introduced in the literature.

In this paper we present the fundamentals of GAIN [ 21 ], a GAN-based algorithm and describe an improved version of GAIN called DEGAIN recently presented in [ 22 ]. In our method we improve the GAIN by applying the idea of network deconvolution [ 23 ]. Convolutional kernels usually re-learn redundant data because of the strong correlations in many image based datasets. The deconvolution strategy is proven to be efective on images, however, it has not been applied to the GAIN algorithm. DEGAIN is capable of removing the data correlations. We evaluate the performance of the proposed DEGAIN with the publicly available Letter Recognition dataset (Letter dataset, for short) and SPAM dataset. In particular, we use Root Mean Square Error (RMSE) and Frechet Inception Distance (FID) metrics and compare the performance of the proposed DEGAIN with the GAIN, the Auto-Encoder [ 24 ] and the MICE [ 25 ] algorithms.

The reminder of this paper is organized as follows. In Section 2, we introduce the system model with mathematical relations and describe the proposed DEGAIN algorithm. The performance evaluation is presented in Section 3. Finally, Section 4 concludes the paper.

2. From GAIN to DEGAIN

A GAN-based data imputing method, called Generative Adversarial Imputation Nets (GAIN), has been introduced in [ 21 ]. In GAIN the generator component takes real data vectors, imputes the missing values conditioned on the really observed data, and gives a completed vector. Then, the discriminator component gets a completed vector and tries to determine which element is really observed and which one is synthesized. To learn the desired distribution in the component, some additional information is deployed for the discriminator in the form of a hint vector. The hint vector shows the pieces of information about the missingness of the real data to the component, and concentrates its heed on the quality of imputation for particular missing values. In other words, the hint vector assures the component to be learned for generating data based on the actual data distribution [ 21 ].

Convolution, which applies a kernel to overlapping sections shifted across the data, is a crucial operation in many Convolutional Neural Networks. Although utilizing CNN to synthesize images is not required in GANs, it is frequently done in order to learn the distribution of images [ 26 ]. The generator architecture is typically composed of the following layers: • Linear layer: The noise vector is fed into a fully connected layer, and its output is reshaped into a tensor. • Batch Normalization Layer: Stabilizes learning by normalizing inputs to zero mean and unit variance, avoiding training issues such as vanishing or exploding gradients and allowing the gradient to flow through the network. • Up sample Layer: Instead of using a convolutional transpose layer to up sample, it mentions using upsampling and then applying a simple convolutional layer on top of it.

Convolutional transpose is sometimes used instead. • Convolutional Layer: To learn from up-sampled data, the matrix is passed through a convolutional layer with a stride of 1 and the same padding as it is up sampled. • ReLU Layer: for the generator because it allowed the model to quickly saturate and cover the training distribution space.

• TanH Activation: TanH enables the model to converge more quickly.

Convolutional kernels are in fact relearning duplicate data because of the high correlations in real-world data. The convolution makes the neural network training dificult. In the following, we review the mathematical presentation of GAIN.

Problem Formulation In a -dimensional space = 1 × ... × the X = (1, ..., ) is a random variable taking values in with distribution (X). M = (1, ..., ) is a random variable in {0, 1}. The X is called data vector, and M is called the mask vector.

A new space ˜ = ∪ {*} is defined for ∈ {1, ..., } where the start, * does not belong to any , and represents an unobserved value. Defining ˜ = ˜ 1 × ... × ˜ The variable X˜ = (˜1, ..., ˜) ∈ ˜ is presented in Eq. (1): ˜ = {︃, if = 1 otherwise where M indicates which components of X are observed. The M could be recovered from X˜ . In missing data re-construction, i.i.d. copies of X˜ are realized, denoted by x˜1, ..., x˜ and defined in the dataset = {(x˜, m)}=1, where m is simply the recovered realization of M corresponding to x˜. The goal is to estimate the unobserved values in each x˜. The samples are generated according to (X|X˜ = x˜), that is the conditional distribution of X given X˜ = x˜ , for each , to fill in the missing data points in .

The generator, , takes as input X˜ , M and a noise variable Z, and outputs X¯ . Where X¯ is a vector of synthetic data. Let : ˜ ×{ 0, 1}× [ 0, 1 ] → be a function, and Z = (1, ..., ) be -dimensional noise (independent of all other variables) [ 21 ]. The random variables X¯ , X^ ∈ is defined by Eq. (2) and Eq. (3).

X¯ = (X˜ , M, (1 − X^ = M ⊙

X˜ + (1 − (1) (2) (3) (, ) = E X^,M,H[︁M log (X^ , H) + (1 − M) log (︀ 1 − (X^ , H))︀ ]︁, where log is element-wise logarithm and dependence on is through X^ . The goal of GAIN is presented in Eq. (5).

min max (, ).

where the loss function ℒ : {0, 1} × [ 0, 1 ] → R is defined as presented in Eq. (6). where ⊙ denotes element-wise multiplication. X¯ corresponds to the vector of estimated values and X^ corresponds to the completed data vector.

The discriminator, will be used to train . However, unlike the standard GAN where the output of the generator is either real or synthetic, the output of GAIN is comprised of some components that are real and some that are synthetic. Rather than identifying that an entire vector is real or synthetic, the discriminator attempts to distinguish which are real (observed) or synthetic. The mask vector M is pre-determined by the dataset. Formally, the discriminator is a function : → [ 0, 1 ] with the -th component of (x^) corresponding to the probability that the -th component of x^ was observed. The is trained to maximize the probability of correctly predicting M and is trained to minimize the probability of predicting M. The quantity (, ) is defined as presented in Eq. (4).

ℒ(a, b) = ∑︁ [︁ log() + (1 − ) log(1 − )]︁.

=1 DEGAIN DEGAIN is originated from GAIN. The main idea behind the DEGAIN is to use the deconvolution in the generator and discriminator. Convolution applies a kernel to overlapping regions shifted across the data. However, because of the strong correlations in real-world data, convolutional kernels are in efect re-learning redundant data. This redundancy makes the neural network training challenging. The deconvolution can remove the correlations before the data is fed into each layer. It has been shown in [ 23 ] that the deconvolution can be eficiently calculated at a fraction of the computational cost of a convolution layer. The deconvolution strategy is proven to be efective on images, however, it has not been applied to GANs including the GAIN.

Given a data matrix × where is the number of samples, and is the number of features, the covariance matrix is calculated as = 1 ( − ) ( − ).

An approximated inverse square root of the covariance matrix could be calculated as = − 12 multiplied with the centered vectors ( − ) · . Accordingly, the correlation efects could be removed. If computed perfectly, the transformed data has the identity matrix as covariance: ( − ) ( − ) = − 0.5 · · − 0.5 = .

The process to construct and ≈ ( + · )− 21 is presented in Algorithm 1, where · improves the stability. The deconvolution operation is further applied via matrix multiplication to remove the correlation between neighboring pixels. The deconvolved data is then multiplied with . The architecture of proposed method is depicted in Figure 1. When the training phase is completed, the component is able to impute the dataset. There are two main loops for (4) (5) (6) real data with missing values

mask matrix 1 0 random noise matrix real data matrix hint generator hint matrix imputed matrix by generator estimated probabilites

Number of Iteration of inner loop ; Updating rates ( and );

( + · )− 12

Training of and 8: for ( = 0; < ; ++) do

for = 0; < ; ++ do 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: ( ) = 1 Σ

=

( );

+1 = + batch samples from noise ∈ × batch samples from noise ∈ × ;

∼ (); ( ) = 1 Σ

=

( ); +1 = − ; batch samples from noise ∈ ×

∼ (); =1(1 − ((, )))

=1(, ) + (1 − ((2), )); updating the parameters of the and components in Algorithm 1. First, batch samples from the noise and samples of real data are presented to the inner loop for updating the parameters of the component. The cost function of the component is then calculated by the given samples. Then, the component’s parameters are updated based on the initiated rate. 2‖22 + Tr(1 + 2 − 2((1, 1)(2, 2)) = ‖1 −

3. Performance Evaluation

We evaluate the performance of the DEGAIN and compare the results with MICE [ 25 ], GAIN [ 21 ] and AE [ 24 ]. Multivariate imputation by chained equations (MICE) has emerged in addressing missing data. The chained equations approach can handle variables of varying types, for instance the continuous or binary as well as complexities such as bounds. MICE is also a software package presented in R [ 25 ]. In multiple imputation algorithms such as AE, multiple copies of the dataset replaced by slightly diferent imputed values in each copy. In this method the variability is modeled into the imputed values [ 24 ].

We perform each experiment 10 times and within each experiment we use 5-cross validations in terms of RMSE, which directly measures the error distance, and FID, which takes the distribution of imputed values into account. We use the Letter and SPAM datasets for comparing algorithms, and samples are missed with the rate of 20%.

Evaluation Metrics In our experiments we consider the Root-Mean-Square Error (RMSE) and Frechet Inception Distance (FID) metrics to evaluate the performance of the proposed DEGAIN on handling the missing data. It should be noted that besides RMSE and FID, several other metrics are introduced in the literature including but not limited to Mean Absolute Error (MAE), Area under ROC curve or AUC score and F1-score. These metrics perform in diferent dataset or operations. For example, the F1-score is mostly used for binary classification. MAE is simialr to RMSE, however, RMSE is more common in the literature. Comparing our method with GAIN, AE and MICE, we have chosen the related RMSE and FID metrics. Remember that RMSE is used for continuous values and measures the error between real values and imputed values for an incomplete dataset. FID converts a group of imputed samples to a feature space using a particular inception net layer. Assuming the converted layer as continuous multivariate Gaussian distribution, the mean and covariance are predicted for both the imputed and real samples.

The mathematical presentation is shown in Table 1, where ^ is the number of missing values, is the real missing value, and ^ is the imputed value. Also the 1 and 2 denote the mean of the real and imputed data, respectively. 1 and 2 indicate the covariance of real and imputed data, respectively.

Dataset Here we use the Letter and SPAM datasets. Letter is publicly available in the UC Irvine Machine Learning Repository and can be accessed through https://archive.ics.uci.edu/. In this dataset, the objective is to identify each of a large number of black-and-white rectangular pixel displays as one of the 26 capital letters in the English alphabet. The character images are based on 20 diferent fonts and each letter within these 20 fonts are randomly distorted to produce a file of 20,000 unique stimuli. Typically, the first 16000 items are used for training and then the resulting model is capable to predict the letter category for the remaining 4000. The SPAM dataset consists of 4601 samples and 57 input features. In this dataset the goal is to predict the spam emails based on input features. SPAM is also publicly available at http://archive.ics.uci.edu/ml/datasets/Spambase/. These datasets have no missing values and therefore, we use a 20% rate of missed samples.

Results The evaluation are performed in google colab, on python 3 with 12 GB of RAM. We used the base codes of GAIN [ 21 ] publicly accessible in https://github.com/jsyoon0823/GAIN. We have modified the code and added the deconvolution to the Generator and Discriminator. The results are presented in Table 2. Both GAIN and DEGAIN are performing much better than the auto encoder (AE) [ 24 ] and MICE [ 25 ]. The DEGAIN is slightly better compared with the GAIN. The main advantage of the DEGAIN could be explored running on correlated large datasets of images. Therefore, as expected, the GAIN and proposed DEGAIN can be most profitable in image datasets.

4. Conclusions

Dealing with incomplete information is an important problem that includes diferent aspects. In this paper we described an algorithm called DEGAIN to estimate the missing values in the dataset. The DEGAIN is based on the known GAIN algorithm that is already used in missing data imputation. We added deconvolution to remove the correlation between data. We evaluated the performance of the presented method on two publicly available datasets, called Letter and SPAM. The RMSE and FID metrics on the results confirmed that the GANs are efective on re-constructing the missing values compared with the earlier Auto-Encoder or MICE algorithms. Also the proposed DEGAIN performs well and improves the performance of GAIN. We believe that the main advantages of DEGAIN could be explored running on large image datasets, although it shows improvement even on our chosen datasets. In this paper we presented DEGAIN as tool for Missing Data Imputation. Inconsistent information, which could be handled using methods such as arbitration [ 27 ], is still an open issue that GAN-based methods and the proposed DEGAIN need to address in future works.

Acknowledgments

This research was supported by MISE Project True Detective 4.0.

5. Online Resources

The datasets used in this paper are publicly available at https://archive.ics.uci.edu/ml/datasets/letter+recognition and http://archive.ics.uci.edu/ml/datasets/Spambase/

References

[1] S. Greco , C. Molinaro , I. Trubitsyna , Approximation algorithms for querying incomplete databases , Information Systems 86 ( 2019 ) 28 - 45 .

[2] G. Alfano , S. Greco , C. Molinaro , I. Trubitsyna , An approximation algorithm for querying inconsistent knowledge bases , Intelligent Systems with Applications 17 ( 2023 ) 200146 .

[3] M. Calautti , S. Greco , C. Molinaro , I. Trubitsyna , Query answering over inconsistent knowledge bases: A probabilistic approach , Theor. Comput. Sci . 935 ( 2022 ) 144 - 173 .

[4] M. Calautti , S. Greco , C. Molinaro , I. Trubitsyna , Preference-based inconsistency-tolerant query answering under existential rules , Artificial Intelligence 312 ( 2022 ).

[5] P. Guagliardo , L. Libkin , Making sql queries correct on incomplete databases: A feasibility study , in: 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , 2016 , pp. 211 - 223 .

[6] E. Toussaint , P. Guagliardo , L. Libkin , J. Sequeda , Troubles with nulls, views from the users , Proceedings of the VLDB Endowment 15 ( 2022 ) 2613 - 2625 .

[7] J. Hu , Z. Zhou , X. Yang , Characterizing Physical-Layer transmission errors in cable broadband networks , in: 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22) , USENIX Association, Renton, WA, 2022 , pp. 845 - 859 . URL: https://www.usenix.org/conference/nsdi22/presentation/hu.

[8] K. Yu , Y. Yang , W. Ding , Causal feature selection with missing data 16 ( 2022 ). URL: https://doi.org/10.1145/3488055. doi: 10 .1145/3488055.

[9] L. Peng , L. Lei , A review of missing data treatment methods , Intell. Inf. Manag. Syst. Technol 1 ( 2005 ) 412 - 419 .

[10] A. Folch-Fortuny , F. Arteaga , A. Ferrer , Pca model building with missing data: New proposals and a comparative study , Chemometrics and Intelligent Laboratory Systems 146 ( 2015 ) 77 - 88 .

[11] S. L. Mirtaheri , R. Shahbazian , Machine Learning: Theory to Applications , CRC Press, 2022 .

[12] G. Nagarajan , L. D. Babu , Missing data imputation on biomedical data using deeply learned clustering and l2 regularized regression based on symmetric uncertainty , Artificial Intelligence in Medicine 123 ( 2022 ) 102214 .

[13] T. Emmanuel , T. Maupong , D. Mpoeleng , T. Semong , B. Mphago , O. Tabona , A survey on missing data in machine learning , Journal of Big Data 8 ( 2021 ) 1 - 37 .

[14] Y. Ma , Y. He , L. Wang , J. Zhang, Probabilistic reconstruction for spatiotemporal sensor data integrated with gaussian process regression , Probabilistic Engineering Mechanics 69 ( 2022 ) 103264 .

[15] F. Camastra , V. Capone , A. Ciaramella , A. Riccio , A. Staiano , Prediction of environmental missing data time series by support vector machine regression and correlation dimension estimation , Environmental Modelling & Software 150 ( 2022 ) 105343 .

[16] A. J. Saroj , A. Guin , M. Hunter , Deep lstm recurrent neural networks for arterial trafic volume data imputation , Journal of Big Data Analytics in Transportation 3 ( 2021 ) 95 - 108 .

[17] D. Cenitta , R. V. Arjunan , K. Prema , Missing data imputation using machine learning algorithm for supervised learning , in: 2021 International Conference on Computer Communication and Informatics (ICCCI) , IEEE, 2021 , pp. 1 - 5 .

[18] F. Tang , H. Ishwaran , Random forest missing data algorithms , Statistical Analysis and Data Mining: The ASA Data Science Journal 10 ( 2017 ) 363 - 377 .

[19] S. Ryu , M. Kim , H. Kim , Denoising autoencoder-based missing value imputation for smart meters , IEEE Access 8 ( 2020 ) 40656 - 40666 .

[20] F. V. Nelwamondo , S. Mohamed , T. Marwala, Missing data: A comparison of neural network and expectation maximization techniques, Current Science ( 2007 ) 1514 - 1521 .

[21] J. Yoon , J. Jordon , M. Schaar , Gain: Missing data imputation using generative adversarial nets , in: International Conference on Machine Learning, PMLR , 2018 , pp. 5689 - 5698 .

[22] R. Shahbazian , I. Trubitsyna , DEGAIN: generative-adversarial-network-based missing data imputation , Inf . 13 ( 2022 ) 575 .

[23] C. Ye , M. Evanusa , H. He , A. Mitrokhin , T. Goldstein , J. A. Yorke , C. Fermüller , Y. Aloimonos , Network deconvolution, arXiv preprint arXiv: 1905 . 11926 ( 2019 ).

[24] L. Gondara , K. Wang , Multiple imputation using deep denoising autoencoders , arXiv preprint arXiv:1705.02737 ( 2017 ).

[25] S. Van Buuren , K. Groothuis-Oudshoorn, mice: Multivariate imputation by chained equations in r , Journal of statistical software 45 ( 2011 ) 1 - 67 .

[26] B. Benjdira , A. Ammar , A. Koubaa , K. Ouni , Data-eficient domain adaptation for semantic segmentation of aerial imagery using generative adversarial networks , Applied Sciences 10 ( 2020 ) 1092 .

[27] P. Z. Revesz , On the semantics of arbitration , International journal of Algebra and Computation 7 ( 1997 ) 133 - 160 .