Improving Missing Data Imputation with Deep Generative Models
Ramiro D. Camino Christian A. Hammerschmidt Radu State


[
Improving Missing Data Imputation with Deep Generative Models














equal*


Ramiro D. Caminounilu
Christian A. Hammerschmidtunilu
Radu Stateunilu


uniluUniversity of Luxembourg, Luxembourg

Ramiro D. Caminoramiro.camino@uni.lu
Christian A. Hammerschmidtchrishammerschmidt@posteo.de
Radu Stateradu.state@uni.lu




Machine Learning, Deep Learning, Generative Models, Missing Data Imputation, ICML

0.3in
]









  








Datasets with missing values are very common on industry applications, and they can have a negative impact on machine learning models.
Recent studies introduced solutions to the problem of imputing missing values based on deep generative models.

Previous experiments with Generative Adversarial Networks and Variational Autoencoders showed interesting results in this domain, but it is not clear which method is preferable for different use cases.

The goal of this work is twofold: we present a comparison between missing data imputation solutions based on deep generative models, and we propose improvements over those methodologies.

We run our experiments using known real life datasets with different characteristics, removing values at random and reconstructing them with several imputation techniques.

Our results show that the presence or absence of categorical variables can alter the selection of the best model, and that some models are more stable than others after similar runs with different random number generator seeds.




§ INTRODUCTION



Analyzing data is a core component of scientific research across many domains. 

Over the recent years, awareness for the need of transparent and reproducible work increased. 
This includes all steps that involve preparing and pre-processing the data.
An increasingly common pre-processing step is the imputation of missing values <cit.>.

Data with missing values can decrease model quality and even lead to wrong insights <cit.> by introducing biases. 
Likewise, dropping samples with missing values can cause larger errors because of the scarce amount of remaining data.

One solution is performing data imputation, which consists in replacing missing values with substitutes.

However, the reason behind the missingness needs to be clarified before imputing <cit.>.

For example, <cit.>  show that in political sciences, results often do not hold up if missing data is imputed improperly.

Values are considered to be missing completely at random (MCAR) when the probability that they are missing is independent both on the value and on other observable values of the data.

The case when data is missing at random (MAR) happens when the missing probability can be estimated from variables where the value is present.

Finally, the case when missing data is neither MCAR nor MAR, is defined as missing not at random (MNAR).
This means that the reason for a value to be missing, can depend on other variables, but also on the value that is missing.

In order to be able to compare the desired models in the same framework, we assume for the this study that missing values are MCAR.


In this paper, we survey the quickly evolving state-of-the-art of deep generative models for tabular data and missing value imputation.

We propose using a backpropagation technique to correct the imputed values iteratively.

We also adapt the analyzed models by changing the inputs and outputs of the architectures, taking into account the size and the type of each sample variable.

Furthermore, we compare the imputation power of every technique using real life datasets.





§ RELATED WORK


Work related to our approach falls into three groups.
The first one consists of state-of-the-art imputation algorithms.
The second group is composed by generative models based in neural networks, and in particular, networks focusing on generating tabular data and handling issues related to categorical variables, rather than generating one high-dimensional image or text variable.
Lastly, the third group is constituted by methodologies using deep generative models for imputation in the domain of tabular data.

Within the field of missing value imputation, traditional methods can be classified into discriminative and generative imputation models.
Examples of discriminative models with state-of-the-art performance are MICE <cit.>, MissForest <cit.>, and Matrix Completion <cit.>.
Autoencoders <cit.> and Expectation Maximization <cit.> are instances of generative models.
Key distinguishing factors of these methods are limitations coming from necessary assumptions about the nature and distribution of the data and the ability to learn from samples with missing data (rather than only learning from complete data samples).



Deep generative models like Variational Autoencoders (VAE) <cit.> and Generative Adversarial Networks (GAN) <cit.> proved to be very powerful in the domain of computer vision <cit.>, speech recognition and natural language processing <cit.>.

It is expected for the scientific community to extend the application of these models to other areas.

The authors of medGAN <cit.> applied GANs to generate synthetic health care patient records represented by numerical and binary features.

The multi-categorical GANs <cit.> extended medGAN and other architectures by splitting the outputs of the networks into parallel layers depending on the size of categorical variables, and used gumbel-softmax activations <cit.> to handle discrete distributions.

<cit.> proposed a GAN based architecture to generate synthetic passenger name records, dealing with missing values and a mix of categorical and numerical variables.

Tabular GAN (TGAN) <cit.> presented a method to generate data composed by numerical and categorical variables, where the generator outputs variable values in an ordered sequence using a recurrent neural network architecture.


There are numerous studies related to image completion with deep generative models like <cit.>, that uses denoising autoencoders for image imputing.

In the domain of natural language processing, <cit.> presented a VAE model with a recurrent architecture for sentence generation and imputation.

This use case was also translated to the topic of missing value imputation on tabular data.

Generative Adversarial Imputation Nets (GAIN) <cit.> adapted the GAN architecture to this problem and proved to be more efficient than state-of-the-art imputation methods.

The Heterogeneous-Incomplete VAE (HI-VAE) <cit.> proposed an imputation technique for tabular data based on VAE, and also compared their results to state-of-the-art imputation methodologies.



§ APPROACH




 §.§ Problem Definition



We define a tabular dataset X as a collection of samples {x_1, …, x_n}.

Each sample x_i is a collection of values {v_i1, …, v_im} for the variables {V_1, …, V_m}, where each variable V_j has a type t_j ∈{numerical, categorical}.

The value of a numerical variable V_j is represented only by one real valued feature, hence we define the size of a numerical variable as s_j = 1.

A categorical variable V_j can take one of s_j > 1 possible categories.
We one-hot encode each value v_ij into s_j binary features, by turning on the feature corresponding to the selected category and turning off the remaining s_j - 1 features.

Combining the amount of features of each variable, we define the amount of features (or size) of every sample as s = ∑_j=1^m s_j.


We can now define a dataset with missing values X̅ as a copy of a dataset X where one or more variable values from one or more samples were dropped.

An imputation algorithm or model ℳ takes a dataset with missing values X̅ and outputs a dataset X̂ by filling the missing values of X̅.
The goal of these algorithms is to minimize the difference between the original dataset X and its reconstructed version X̂.


In addition, we define a the mask M of X̅ that will be used in the following method definitions.
We represent M as a matrix ∈{0, 1}^n × s, where each position m_ik contains a 1 if the feature on x̅_ik is present or a 0 if it is missing.

Also for the training of deep learning models, we note subset of sample indices B ⊂{1, …, n} as a mini-batch.



 §.§ Gumbel-Softmax


The output of a neural network can be transformed into a multinominal distribution by passing it through a softmax layer.
However, sampling from this distribution is not a differentiable operation, which blocks the backpropagation during the training of generative models for discrete samples. 
The Gumbel-Softmax <cit.> and the Concrete-Distribution <cit.> were simultaneously proposed to tackle this problem in the domain of variational autoencoders (VAE) <cit.>.
Later <cit.> adapted the technique to GANs for sequences of discrete elements.

For i.i.d samples  g_1, …, g_d  drawn from Gumbel(0, 1) = -log(-log(u_i)) with u_i ∼ U(0, 1), 
the gumbel-softmax generates sample vectors b ∈[0, 1]^d based on inputs a ∈ R^d (that can be the output of previous layers) and a temperature hyperparameter τ∈ (0, ∞) by the formula:


    [ b_i = exp((log(a_i) + g_i) / τ)∑_j=1^d exp((log(a_j) + g_j) / τ)                                                        i=1, …, d ]




 §.§ GAIN



GAIN <cit.> is composed of a modified generator and discriminator network.
Compared to the original GAN architecture <cit.>, the differences are as follows:

The generator G takes as input some data X̅, a suitable mask M, and a source of noise. 
In practice, the noise is inserted inside X̅ in the positions of the missing values.
The model then returns an imputation X̂.

The discriminator D of the GAN architecture receives X̂, and instead of trying to determine if each sample from the input is either real or fake, the model tries guess for every sample if each variable value is either original or imputed.

In other words, the discriminator needs to be trained to maximize the probability of predicting the mask M.
Hence, we note the output of network D as M̂.

The discriminator loss only takes into account the binary cross entropy of the positions corresponding to missing values:



    ℒ_D(M_i, M̂_i) =
    - ∑_k=1^s m_iklogm̂_ik + (1 - m_ik) log (1 - m̂_ik)



for every sample i. Then, for a mini-batch B, the discriminator D with parameters θ_D is trained to optimize:


    min_θ_D∑_i ∈ Bℒ_D(M_i, M̂_i)



Given that M̂ = D(X̂) and X̂ = G(X̅, M), the generator G with parameters θ_G is trained to maximize the probability of fooling the discriminator predictions of M:


    ℒ_G(M_i, M̂_i) = - ∑_k=1^s (1 - m_ik) logm̂_ik



    min_θ_G∑_i ∈ Bℒ_G(M_i, M̂_i)
    + αℒ_rec(X̅_i, X̂_i, M_i)



where ℒ_rec(X̅_i, X̂_i, M_i) is a special reconstruction loss term weighted by the hyperparameter α.

This loss function is separated by variable and masked in order to calculate only the reconstruction error for the non-missing values:


    ℒ_rec(X̅_i, X̂_i, M_i) =
    ∑_j=1^m ∑_q=1^s_j m_ik rec_j(x̅_ik, x̂_ik)


where the feature index k is calculated as:


    k = ∑_j'=0^j-1 s_j' + q - 1


which is the index for the first feature of v_j plus the offset for the categorical value q (or no offset for numerical variables).
The reconstruction error for each feature of a particular variable v_j depends on the variable type t_j:


    rec_j(x̅_ik, x̂_ik) = {[     ( x̂_ik - x̅_ik)^2   if  t_j  = numerical;        - x̅_iklogx̂_ik if  t_j  = categorical ].




 §.§ VAE Imputation



We train a traditional VAE <cit.> using X̅_train as input, but inserting random noise on the positions with missing values.

We use the masked the reconstruction loss defined in Equation <ref> to calculate the reconstruction error between X̂_train and X_train only on the non-missing values.

We use the trained model to obtain X̂_test from X̅_test and use the reconstructed missing values for imputation.




 §.§ VAE Iterative Imputation



The method from <cit.> is an extension of the VAE imputation, related to the iterative PCA imputation algorithm <cit.>.

The training stage remains the same, but the imputation procedure is corrected iteratively.

The reconstruction error of the non-missing values is measured after each iteration, and if the error is small enough or too many iterations have been calculated, the algorithm stops.

If the procedure must continue, X̅_test is run through the model again, but instead of inserting random noise on the positions with missing values, the reconstructed missing values from the previous iteration are used.

Note that it makes no sense to use the reconstruction error of the missing values as a stopping criteria, because in a real case scenario, the missing values are supposed to be unknown.

A pseudocode for this method is presented in Algorithm <ref>.





 §.§ VAE Backpropagation Imputation



The thrid VAE technique is an altered form of the iterative imputation: on each iteration, the reconstruction error of the non-missing values is backpropagated to the input.

Instead of updating the weights of the model like in a traditional training, the noise itself is updated, keeping the model and the non-missing values untouched.

The stopping criteria remains the same: the algorithm iterates until the error is sufficiently small or the number of iterations is large enough.

This technique is inspired by <cit.>, where the authors detect anomalies on images by searching through the latent space used as input for the generator.

A pseudocode for this method is presented in Algorithm <ref>, highlighting the differences with Algorithm <ref>.





 §.§ Variable Splitting







The authors of multi-output GANs <cit.> introduced the notion of taking into account the structure of categorical variables from tabular data to modify the network architecture.

A multi-output GAN contains one dense layer per variable connected in parallel to the output of the generator.

Each dense layer transforms the output to the size of the corresponding variable.

A gumbel-softmax activation <cit.> (or concrete distribution <cit.>) is used after each parallel dense layer.

All the outputs are concatenated back into a complete synthetic sample.

The work on <cit.> also extended other GAN architectures involving autoencoders <cit.>, where the decoder is the altered model with multiple outputs, and the generator returns continuous latent codes for the autoencoders.
In this study we extend multi-output architecture in two ways:


    
    
  * We work with tabular data of mixed numerical and categorical variables.
    In order to do so, during the splitting of numerical variables, we do not apply size transformations with dense layers, but we apply sigmoid activations before concatenating the output. The changes can be observed on Figure <ref>.
    This extends <cit.> to settings with mixed numerical and categorical data.
    
    
  * We transfer the idea to the inputs too, by using one embedding layer per categorical variable with the corresponding size of each variable.The outputs of each parallel embedding layer are concatenated back to build the altered inputs. Numerical variables are concatenated directly with the outputs of the embeddings. Related architectures and applications can be found in <cit.>. A representation can be seen on Figure <ref>.



We propose to modify the GAIN architecture by adding the multiple-inputs and multiple-outputs both to the generator and the discriminator.

For the VAE, we propose to use multi-input on the encoder and multi-output on the decoder.


§ EXPERIMENTS






 §.§ Data and Pre-Processing



We evaluate the presented imputation methods using five real life datasets from the UCI repository <cit.>.
They are composed of different number of samples and variables, both categorical and numerical.
Originally, no dataset contains missing values.
A summary of their properties is defined in Table <ref>.


For all datasets, categorical variables are one-hot encoded, and each numerical variable V_j is scaled to fit inside the interval [0, 1] according to the equation:


    scaled(V_j) = V_j - min(V_j)/max(V_j) - min(V_j)


where max(V_j) and min(V_j) are the maximum and minimum values for the variable V_j from all samples that can be measured across the entire dataset.



 §.§ Running the Experiments



All the experiments are implemented using Python 2.7.15, PyTorch 0.4.0 <cit.> and scikit-learn 0.19.1 <cit.>.
The code is available in the supplementary material.
After the review process, we plan to port the implementation to Python 3 and release it to the public.


All models are trained with 90% of the original data and the other 10% is used to evaluate the performance of the imputation methods.

We generate different settings of missing value probabilities p ∈{0.2, 0.5, 0.8}.
Given a missing probability p, each variable of each sample is dropped if r < p, for a random number r ∼𝒰[0, 1].
The value of a dropped variable is replaced by random noise 𝒩(0, 1).


Each method has different amount of hyperparameters that need to be defined.

For GAIN, we use the same configuration defined in <cit.>, and we only experiment with different values for the weight of the reconstruction loss as the authors did originally.
Across all our experiments we get the best results with a value of 10.

We perform a random search for the hyperparameters needed by the VAE based methods.

Both the encoder's and the decoder's hidden layers (beside the special input and output layers) are implemented as a collection of fully connected layers with ReLU activations.
We experiment with one hidden layer with 50% of the input size, two layers with 100% and 50% of the input size respectively, and no hidden layers at all.

For the size of the latent space, we tried with 10%, 50% and 100% of the input size.

Other learning hyperparameters include the batch size, for which we explored the values {2^6, 2^7, 2^8, 2^9, 2^10}, and two different learning rates of 1e^-3 and 1e^-5.


Both of the iterative imputation also need to define the maximum number of iterations and the minimum acceptable error to stop, for which we fix 10000 iterations and 1e^-4.

Finally, the variable split adapted architectures use gumbel-softmax activations, and we experiment with the temperature or τ hyperparameter using the values {0.1, 0.5, 1, 2, 10}.


Furthermore, every experiment is repeated at least three times using different seeds on the random number generator.

For each collection of experiments that differ only on the seed, we calculate the mean and the standard deviation of the Root Mean Squared Error (RMSE) between the (normalized) imputed and the original test data values.



 §.§ Results











For the following experiments, we use the notation “+vs" for variable split, “+it" for iterative imputation and “+bp" for backpropagation iterative imputation.

In Figure <ref> we present the imputation RMSE by increasing proportion of missing values for datasets with only numerical variables, and in Figure <ref> the rest of the datasets that contain both numerical and categorical variables.

For the sake of clarity, we removed the iterative imputation methods from Figure <ref>.

Nevertheless, a full description of the imputation results can be seen on Tables <ref> and <ref>. 

From the plots and the tables we can extract the following observations:


    
    
  * As expected, the performance of every model decreases when the proportion of missing values increases.
    
    
    
  * The iterative and backpropagation alternatives for the VAE imputation do not seem to add improvements over the plain VAE imputation.
    
    
    
  * For the datasets with only numerical variables, GAIN seems to be better for the smaller dataset, but it is slightly worse than VAE for the other bigger datasets.

    
    
  * The variable splitting appears improve both models, but the improvement is more drastic in the case of VAE.

    
    
  * GAIN has some perceptible variance when trained with different seeds, but all VAE methods seems to be more stable, even when they have worse performance.




 §.§ Discussion


Deep generative models for missing data imputation proved to surpass state-of-the-art methods in previous studies <cit.>.
However, the power these models offer come at some cost.
The number of hyperparameters to tune is usually larger than traditional non deep learning solutions.
The training time or memory size required for the hyperparameter search using large datasets can be prohibitive in some cases.
Furthermore, the amount of research papers on this domain is growing rapidly, but in many cases, the matching code is either not available or incomplete.
In comparison, traditional methods are well established in the scientific community.
This can lead practitioners to rely on known and robust libraries instead of implementing deep learning alternatives themselves.


§ CONCLUSION



In this paper, we compare several deep generative models for missing data imputation on tabular data, and we propose improvements on top of each model to further improve their imputation quality:
first, using variable splitting to account for categorical variables, and second, an iterative backpropagation-based method for VAEs.


Our experiments with public datasets show that our proposals match and improve the performance of deep generative models, which already were shown to outperform state-of-the-art imputation methods in the literature.


Adding variable splitting techniques to separate variables, applied both on the inputs and the outputs, enhances the imputation power of GAIN and all the presented variants of VAE.
In contrast, both of the VAE iterative imputation procedures did not significantly increase the quality of imputations compared with the basic VAE model.


To support reproducible research, we provide open implementations for our research by
making our code public [Link blinded for review.].
We are looking forward to collaborate both with developers and the scientific community.






  §.§.§ Acknowledgments


The experiments presented in this paper were carried out using the HPC facilities of the University of Luxembourg <cit.> – see <https://hpc.uni.lu>.  


icml2019


