Tabular data imputation: quality over quantity
Authors: Florian Lalande
Kenji Doya
Venue: NeurIPS 2022 Submitted (2022)
Keywords: data imputation
density estimation
nearest neighbors
likelihood
multimodality

Abstract: Tabular data imputation algorithms allow to estimate missing values and use incomplete numerical datasets. Current imputation methods minimize the error between the unobserved ground truth and the imputed values. We show that this strategy has major drawbacks in the presence of multimodal distributions, and we propose to use a qualitative approach rather than the actual quantitative one. We introduce the kNNxKDE algorithm: a hybrid method using chosen neighbors ($k$NN) for conditional density estimation (KDE) tailored for data imputation. We qualitatively and quantitatively show that our method preserves the original data structure when performing imputation. This work advocates for a careful and reasonable use of statistics and machine learning models by data practitioners.

Tabular data imputation: quality over quantity
Anonymous Author(s) Affiliation Address email
Abstract
Tabular data imputation algorithms allow estimate missing values and incomplete numerical datasets. Current imputation methods minimize the error between the unobserved ground truth and the imputed values. We show that this strategy has major drawbacks in the presence of multimodal distributions, and we propose use qualitative approach rather than the actual quantitative one. We introduce the kNNxKDE algorithm: a hybrid method using chosen neighbors (kNN) for conditional density estimation (KDE) tailored for data imputation. We qualitatively and quantitatively show that our method preserves the original data structure when performing imputation. This work advocates for a careful and reasonable use of statistics and machine learning models by data practitioners.
2
10
Introduction
11
12
Big data is often referred to as the "gold of the 21st century". But with ubiquitous large databases, missing data are pervasive problem. They can introduce bias, lead to wrong conclusions, prevent from using data analysis tools that require complete datasets. 14
15
To mitigate this issue, data imputation algorithms have been developed. From the straightforward mean/mode imputation to recent artificial neural networks (ANN) models, a wide range of tools are available to impute incomplete datasets. This study focuses on tabular datasets, i.c. numerical data arranged in rows and columns a form matrix. For tabular datasets, recent benchmarks argue that complex imputation methods do not perform better than simple traditional algorithms Bertsimas et al., 2018 Poulos and Valle 2018 Jadhav et 2019 Woznica and Biecek] 2020 Jäger et al. 2021]. In particular, the consensus is that the INN-lmputer [Troyanskaya et al. [001 and
16
17
18
20
21
22
Fosstorest Stekhooen and Bühlmann] 2012), in spite of being traditional and simple algorithms,
generally perform better over large range of datasets in various missing data scenarios.
24
Data may be missing because was not recorded, the record has been lost, degraded, or the data may also be censored. Missing data scenarios are usually classified into three types [Little and Rubin 2014]: missing completely at random (MCAR), missing at random (MAR) and missing not at random (MNAR). In MCAR the missing data mechanism is assumed independent of the dataset. In MAR, the missing data mechanism assumed to only dependent on the observed variables. The MNAR scenario encompasses all other possible scenarios: the reason why data is missing may depend on the missing value itself. Most comparisons focus on the MCAR scenario.
25
26
27
28
29
30
31
Tabular data imputation methods have always been evaluated using the RMSE between the estimated value and the ground truth. The higher the mean RMSE, the poorest the imputation method. This approach is of course intuitive, but is too restrictive for multimodal datasets: it assumes that for set of observed variables, there exists only unique answer to recover. For multimodal datasets, density estimation methods like the familiar Kernel Density Estimation (KDE) [Rosenblatt] 1956 Parzen appear of interest for data imputation. But despite some attempts [Titterington and Mill 1983
32
33
34
35
36
1962.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37
Leibrandt and Günnemann 2018]. density estimation methods do not handle well observations with missing values.
38
39 In this paper, we propose to step back and look at simple datasets to demonstrate that current approaches for data imputation have serious shortcomings. To tackle them, introduce local density estimator tailored for data imputation. By leveraging the convenient properties of the kNN- Imputer and KDE, we develop kNNxKDE: simple yet efficient algorithm for stochastic local data imputation. We visually show that our method performs better than standard methods, and evaluate the performances using the likelihood when available. We provide the code and the data used in this work for reproducibility. Interested readers may experiment with the hyperparameters of our algorithm.
41
42
43
44
45
46
47
2
Current methods perform poorly for multimodal dataset
48
This section demonstrates that conventional data imputation methods provide poor imputation with basic multimodal datasets. For this purpose, generate three simple two-dimensional datasets and visually assess the imputation performances of four standard methods.
49
50
51
2.1
Three simple datasets
The first dataset is bijection. 21 is sampled from a mollified uniform distribution [0, 1] with standard deviation a = 0.05. Then 22 21 + E, where ~ 0.,0..).
53
54
The second dataset is surjection, using sine wave: distribution on [0, 1] with standard deviation The surjection allows to show that most imputation algorithms perform well in the unambiguous case (when 22 missing), but not with multimodal distributions (when 21 missing).
4Tu, where u is sampled from mollified 0.05. Then x22 sin 2 + E, where (0, 0.2).
55
57
58
Finally, Dataset 3 displays ring. It has been generated in polar coordinates: 0 ~ ([0, 2m] and 1.0 + where N (0, 0.1). Euclidean coordinates are I cos and x2 sin 0.
59
60 All three datasets have = 500 observations and are plotted in Figure I The code used for generation and the datasets themselves provided in supplementary materials. We have used mollified uniform distribution for æı in Datasets 1 and 2 to prevent from zero likelihood computation problems the edges of the uniform distribution.
62
Dataset 1
Dataset
Dataset 3
1.2
1.0
0.5
0.5-
2 0.0-
0.2
0055
-055
-1.0
-1.0
7.5
16.
Figure 1: Three basic synthetic datasets with = 500 observations. Dataset is a bijection, Dataset 2 is surjection, and Dataset 3 uses polar coordinates (not function in the euclidean space).
64
2.2 Four standard data imputation methods
85
Here, we present the four data imputation methods used in this work: the ANN-Imputer MissForest, MICE and GAIN. This choice is of course arbitrary, but illustrates well the current state of affairs
86
87
regarding tabular data imputation [Bertsimas et al. 2018 Poulos and Valle 2018 Yoon et 2018
68
Jadhav et al. 2019 Woznica and Biecek] 2020 Jäger et al. 2021
89
The INN-tmptter (Troyanskaya al. 2001 computes distances between pairs of obser- vations using a Euclidean distance that handle missing values (called nan nan-uuclidean

---

71
distance). It imputes missing values by looking at one column at a time and averaging over the k nearest neighbors that have an observed value for that column. Therefore, different neighbors can be used to impute two missing entries in the same observation. One needs to tune the hyperparameter for the number of neighbors. The scientific consensus puts the kNN-Imputer often on par with MissForest as for the best tabular data imputation method.
72
78
74
75
76
MissForest [Stckhoven and Bühlmann 2012] is an iterative imputation algorithm. It begins by filling all missing values with initial estimates (c.g. the column mean), and then loops through all columns, one at a time, performing a regression of that specific column onto all other columns using Random Forests. It stops when the imputed dataset is stable enough (following a user-defined threshold). The number of trees has to be tuned. MissForest has shown great flexibility and successful data imputation results.
78
80
81
82
MICE stands for Multiple Imputation Chained Equations vvan Buuren and Groothuis Oudshoorn 2011]. J. Similar to MissForest, is an iterative imputation algorithm that uses a regressor (linear regressions for MICE) to predict each column successively after filling all missing entries with initial guesses. This algorithm has no hyperparameter to optimize. MICE has shown good imputation results and is appreciated for its simplicity and absence of hyperparameter tuning, but it fails at capturing non-linear dependencies.
83
84
85
86
87
Finally, GAIN is GAN neural network tailored for tabular data imputation which claims -fe-----thhrrrr imputation results (Yoon et al. 2018). GAIN smartly revisits the GAN architecture by working with individual cells rather than whole observations. It has benefited from a lot of attention for tabular data imputation. However, recent benchmarks show that its performances hyperparameters to tune: batch size, hint rate (amount of correct labels provided to the discriminator), number of training iterations, and weight parameter for the generator loss (balances RMSE loss for the observed cells and adversarial loss for the generated cells). We decide follow the authors' recommendations and fix: batch size Nbathh 128, hint rate 0.9 and a = 100. We only optimize the number of iterations.
89
81
mediocre in practice (Jäger et al., 2021]. GAIN has several
88
95
96
87
96
2.3
Imputation results
99
We introduce missing values for each dataset in MCAR scenario with 20% missing rate. If an observation has both features removed, we repeat the process until at least one feature is present. After missing values have by injected, we normalize the dataset in the range [0, 1] using the minimum and maximum value of each feature.
100
102
For each data imputation algorithm and for each dataset, we perform grid search of the hyperparam- eter than best minimizes the normalized RMSE (NRMSE):
d (res Tis 3 2mij
NRMSE
Nauiss 1=1 1=
where m,y 1 if cell (i,j) is missing (may O otherwise) and Nuuis E.= Σ/=1 my is the total number of missing entries in the dataset. The best hyperparameters, presented in Table] I used to impute each dataset one more time. The optimized imputation results are plotted in Figure 2
105
Table 1: Hyperparameter search results for each imputation method and dataset
Data imputation method
ANN Imputer
MissForest
MICE
GAIN
Dataset 1
neighbors
Nuross 10
Ni 500
Dataset 2 k: = 30 neighbors
Nesoa 30
X
Nim 200
Dataset 3
& = 75 neighbors
Niress 30
X
Nuter 100
106 We believe that Figure 2 provides meaningful insight regarding the current state of tabular data
107
imputation. The scientific consensus that the &-NN-Imputer and MissForest provide overall better
data imputation quality, which is somewhat recovered here. MICE uses linear regression between 109 features and cannot capture non-linear dependencies. Despite its flexible architecture, GAIN do not recover missing values, even for Dataset 1. GAIN is hard to train properly.
3

---

KNN Imputer
MissForest
MICE
GAIN
122
1.0
1.0
Complate
0.8
3.8
Datavet
0.4
0.2
32-
02
0.2
0.00
0.5
0.50
075
0.25
0.50
0.75
1.50
0.00
0.50
6.5
1.00
0.30
0.50
0.5
1.00
1.5
1.5
1.0-
Dataset 2
9.5
0.0
0.0
-0.5
-2.--
-1.0
-1.0-
1.0
Dataset 3
0.5
0.0
-5
-05
-25
Figure 2: Imputation results for the three synthetic datasets by the four selected imputation methods with optimized hyperparameters. Blue dots correspond to complete observations, orange dots have observed 12 but imputed I1, and red dots have observed xi but imputed T2- The ANN-Imputer, MissForest and MICE perform well on Dataset 1. The &NN-Imputer and MissForest impute 22 for Dataset 2, but they cannot impute Iı. No method can properly impute Dataset GAIN provides the worst imputation results and cannot even impute Dataset 1.
I11 Both the INN-tmputer and MissForest average over several predictions. This why the imputation of in Dataset 2 lies between the two sine waves, and imputations for both ø and 22 in Dataset
113 3 are inside the ring. While averaging over several predictions often lead to better estimates, this
strategy deteriorates the imputation quality if the missing value distribution is not unimodal.
115
MICE performs imputation by assuming linear dependency between features the dataset. It is therefore no surprise if MICE can very well impute Dataset 1 but fails at imputing Dataset 2 and Dataset 3. Once the MICE algorithm has converged, the imputed orange and red dots follow almost perfectly the center of mass of all points in the dataset.
116
117
GAIN provides surprisingly disappointing imputation results. While ANNs flexible models, the generator and the discriminator of GAIN fail to capture the non-linear relationship between æ and 22 in all three datasets. Because of its innovative and complex framework, GAIN suffers from complicated training process, which leads to bad imputation results. We have tried to train GAIN several times with various hyperparameters, but always end up with similar imputation quality.
120
121
122
123
KNNxKDE
124
125
To address the issues presented in Section 2
we propose a local stochastic imputer using kernel density estimation with Gaussian kernels. We adapt the KDE algorithm to missing data settings: only the conditional density of missing features given the observed features is estimated.
127
We use a methodology analogous to the JNN-emputer to look for neighbors, but we work with missing patterns instead of working column by column. The reason this choice is that working with one column at time may lead to incoherent imputations the selected neighbors for different
129

---

columns are different. Therefore, some imputed observations may be incompatible with the dataset structure. For a dataset with D columns, we have up 2n possible missing patterns. Indeed, each cell may either be missing or not (hence 2D choices) but we do not account for complete cases (nothing to impute) and completely unobserved cases (without even an observed cell).
132
134
For each pair of observations in the normalized dataset, we compute the distance di using the nan-Euclidean distance [Dixon 1979
D Pohs
du
Σ KE Dobe
(I x22)2
where D is the total number of columns in the dataset, Dabs (k E [1, P] ma = mys = =] is the set of indices for commonly observed features in observations i and j and |oobal is its cardinality. These pairwise distances are then passed to a softmax function in order to define probabilities:
E-
Pij = ΣS
135
We use the "soft" version of the KNN algorithm, and introduce the temperature hyperparameter т. Instead of selecting a fixed number of neighbors per observation. we use a neighborhood where nearest neighbors have stronger weights. In similar fashion Frosst et al. [2019]. the notion of temperature controls the tightness of each observation' 's neighborhood.
136
137
138
Given a missing pattern, first select all data impute and potential donors. Data to impute is the subset of data which has the current missing pattern. and potential donors are the subset of data where at least all columns in the current missing pattern are observed. For incomplete observation i in the subset of data to impute, Pij is the probability of choosing observation j from the subset of potential donors. We have E3 Pij Algorithm 1 shows the pseudo-code of the kNNxKDE.
140
142
143
144
The kNNxKDE has three hyper- parameters. The temperature for the softmax probabilities, the (shared) standard deviation h of the Gaussian kernels, and the num- ber Naraws of total sampled neigh- bors. The temperature controls the breadth of the selected neigh- borhood. The standard deviation corresponds to the width of the Gaussian kernels. The effects of and are discussed in Section [ The last hyperparameter is the num- ber Naraws of imputation samples to be returned. It determines the resolution of the estimated density. Besides the obvious computational resources, there are no drawbacks to setting high number of imputa- tion samples Ndraws-
Algorithm 1: Pseudo-code for the kNNxKDE
Data: The incomplete dataset X min/max normalization;
for each missing pattern do
X Ximp <- datt_tt_impplt
Xdon + potential_donoo
dij +- nanEuclDist (Ximp, Xdon);
if di is NaN then
di 00;
end
Pij + softmax (-rdiy): for each row in Ximp do
r + sample Naraws indices in Xeton with prob piy:
e e sample Ndraws from ~ A/ h);
imputation_sane sampllesssalsssseeeeeeeeeeeeeeee t- X [r] + e,;
end end min/max renormalization; Return: imputationn_sampll
4 Results on synthetic datasets
145
146
we show the performances of the kNNxKDE on the three artificial datasets and we discuss the effect of the hyperparameters т and h. In Subsection 4.2 we use the log-likelihood the imputed sample as attempt quantify imputation quality. We show that, for multimodal datasets, using the likelihood is more appropriate than the RMSE. All experiments use the MCAR setting to artificially introduce missing data with 20% missing rate.
In Subsection 4.1
147
149
5

---

4.1
Qualitative evaluation of the kNNxKDE algorithm
152
We show that the proposed method provides imputation samples that preserve the structure of the original dataset. For now, fix the hyperparameters of the kNNxKDE at their default values: 0.03, т = 50.0 and Ndraws = 10000. Figure 3 shows the imputation with a sub-sampling size &s 10. The sub-san sub-sampling size only used show the variability in the imputation results by sampling several times. If æ1 is missing, we sample Nas possible values given 22 (the orange horizontal trails of dots), and if zg missing, we draw N possible estimates given 21 (the red
154
155
158
157
158
vertical trails of dots).
1.2
Campaen wie
Miss X
1.0
Plas Az
0.5
-0.5
-0.-
-10-
-1.0
-1.5
0.0
10.0
125
1.0
Figure 3: Several imputation results from the kNNxKDE algorithm. Each missing entry has been imputed Nes 10 times to show the variability of the estimates. The imputed values match with the structure of the observed data (larger blue dots).
159
Another way to visualize the distribution of the conditional distribution for each missing value to look the univariate density provided by the kNNxKDE algorithm. For each dataset, we have selected two observations: one with missing and one with missing x22 Figure T shows six univariate densities returned by the kNNxKDE algorithm with default hyperparameters values. the
180
182
upper left corner of each panel, the observed value is shown for reference. On each panel, thick dashed line indicates the (unknown) ground truth. We see that the ground truth always falls in one of the modes of the estimated imputation density.
164
Data set 1
Dataset 2
Dataset
0.45
-0.88
-061
Dersiyy for
0.0
0.2
0.4
0.6
0.8
2.5
5.0
7.5
10.0
12.5
-1.0
-0.5
0.0
0.5
1.0
Densiy for
X;
0.27
Figure 4: Example of conditional density distributions from the kNNxKDE algorithm with default hyperparameter values. Each histogram has Ndraws 10000 samples. Thick dashed lines correspond to the (unobserved) ground truth and the observed value is in the upper-left corner.
For Dataset 2, when Ij is missing (upper middle panel of Figure 4 the kNNxKDE returns multimodal distribution. Indeed, given the observed 22 = -0.88, three separate ranges of values could correspond to the missing 21. Similarly, Dataset 3 shows bimodal distributions both for æ1 Iz. corresponding to the two possible ranges of values allowed by the ring structure.
167
189
We now focus Dataset 2 to experiment with the hyperparameters / and r. Figure 5 shows how the imputation quality changes when we vary the softmax temperature т, and the effects of the Gaussian
171
kernel bandwidth are shown in Figure

---

t= 10
T=
= 300
Complete
Miss
1.0
1.0
0.5
0.5
0.0
-.5
-95-
0.0
2.5
5.0
10.
12.5
0.0
2.5
5.0
10.0
125
0.0
2.5
5.0
10.0
12.5
Figure 5: Evolution of the imputation quality the softmax temperature varies. The Gaussian kernel bandwidth is fixed at h=0.03. We see that if is too low, the imputation has large variance. If is too high, the imputation could be biased.
178
The value of the softmax temperature plays important role in the data imputation quality, as can be seen in Figure Recall that constrains the neighborhood range for each observation. The lower the looser the neighborhood, and irrelevant observations could be sampled. This results in large scatter (leftmost panel). Conversely, the higher т, the tighter the neighborhood. Missing values will 176
174
be imputed using very few other observations and multimodality can be overlooked. This can be seen 178 on the rightmost panel, where the sampling variability only due the Gaussian kernel bandwidth.
Tuning means finding good balance in the bias/variance tradeoff.
0.01
0.03
Complete Miss in Viss As
1.0
0.5
0.5
0.0
0.0
-0.5-
-0.5
-05-
-10-
-1.0-
-1.0-
-1.5-
-1.5
-1.5
10
15.0 125
Figure 6: Change the imputation quality when the Gaussian kernel bandwidth h varies. The softmax temperature is fixed at r 50. We see that if / is too low, the imputation sample is very close to the observed data. is too high, the imputation sample too scattered.
Now, the kernel bandwidth I controls amount of to the observed data (c.f. Figure 6 The lower ht and the closer to the observed data the imputation sample will be. This can result in spiky univariate distributions. the limit where h = 0.0, the conditional distribution for each missing value becomes multinomial distribution with probability given by the softmax function computed with the pairwise distances. On the contrary, the higher and the higher the variability of the imputation sample. Unlike bandwidth h too narrow does not mean that multimodality will be overlooked. With low h, the univariate distribution for multimodal conditional probability will show distinct pronounced peaks. If h is too high, the different modes may collapse into larger distribution with high variance.
180
182
184
196
188
189
4.2
The logelikelihood to measure imputation quality
190
Here, we compute the normalized RMSE (NRMSE) for the three datasets after imputation with all standard methods and the kNNxKDE algorithm. We compare the NRMSE with the log-likelihood
191
score, which we can also compute since we know the generative process of the synthetic datasets.
193
When performing single imputation with the KNNxKDE algorithm, we draw unique random sample from the resulting imputation distribution.

---

195
For each dataset and each imputation method, we repeat 100 times the following process: we introduce missing values, normalize the dataset, impute with the selected method using best hyperparameters
196
197
(c.f. Table and compute the NRMSE. Table 2 shows the mean and the standard deviation of the
196
NRMSE, As already discussed in Section 2 the I-NN-mmptte, MissForest and MICE have a low
199
RMSE for Dataset 1, meaning that these methods recover well missing values. Larger NRMSEs for
200
Datasets and quantify the poorer imputation quality. GAIN has a large RMSE, even for Dataset 1,
as it could be anticipated from Section 2
Table 2:
Normalized RMSE for the three datasets with all imputation methods. kNNxKDE does not perform particularly well in terms of minimizing the NRMSE.
Data imputation method
ANN-Imputer
MissForest
MICE
GAIN
kNN*KDE
Dataset
0.075 + 0.005
0.096 + 0.005
0.075 = 0.004
0.228 + 0.026
0.111 + 0.006
Dataset
0.192 + 0.011
0.252 = 0.019
0.250 = 0.009
0.271 = 0.023
0.267 + 0.017
Dataset
0.295 + 0.010
0.374 + 0.022
0.294 = 0.010
0.309 + 0.027
0.419 + 0.024
202
The kNNxKDE does not perform well with the RMSE. It has the largest NRMSEs, if we disregard GAIN. The justification we provide is that the kNNxKDE is not designed to accurately recover missing values. When performing a single imputation, the kNNxKDE algorithm selects a unique sample from the resulting imputation distribution. This is equivalent to selecting a single neighbor with the softmax probabilities - which may not even be the closest neighbor- and using noisy copy of its observed values for imputation. This is an audacious choice, while the other imputation methods look for an optimal compromise. For multimodal distributions, sampling with the kNNxKDE cannot
203
204
205
207
208
209
guarantce that we sample from the mode where the ground truth lies. For Dataset 3, where kNNxKDE shows the highest NRMSE, the imputation may be completely off (i.e., on the other side of the ring).
211
We now compute the log-likelihood of the resulting imputed sample. Like with the NRMSE, for each dataset and each imputation method, we repeat 100 independent experiments with the best hyperparameters. The imputed data are renormalized back to their original range to compute the oggliikeihood of the imputed samples. Table 3 shows the mean and the standard deviation of the log-likelihodd.
212
213
214
215
Table 3: methods. The first column shows the log-likelihood of the original sample for reference.
Mean and standard deviation of the log-likelihood for the three datasets with all imputation
Data imputation method
Ref.
ANN-Imputer
MissForest
MICE
GAIN
kNN*KDE
Dataset
425
494 + 9
450 + 14
495 + 11
-234 231
408 + 15
Dataset 2
79
-2214 + 299
-525 + 150
-2691 - 261
-1482 - 600
-54 33
Dataset 3
-481
-2251 +: 196
-893 + 117
-2361 - 209
-2177 = 319
-509 + 15
216
This time, KNNxKDE performs best for Datasets 2 and 3. For Dataset 1, the ANN-Imputer, MissForest and MICE have a larger log-likelihood than the original sample because these methods average over several predictions and therefore remove the variability their predictions: the imputed sample is
217
218
219
very close to the ground truth and shows high likelihood under the generative model (c.f. Figure 2 The likelioid of the imputed samples by GAIN poor regardless of the dataset. MissForest shows interestingly decent results as it benefits from the iterative imputation mechanism and the random forest flexibility to capture non-linear dependency (unlike MICE).
220
221
222
223
With the log- likeliiold as the new evaluation metric, the kNNxKDE now provides the best imputed samples. Each imputed observation may be far from its ground truth hence the large NRMSE in Table 2 but it conforms to the data structure - hence the large log-likelihood in Table
224
225
5
Discussion
227
We have shown the limits of the RMSE for data imputation problems, and have introduced new data imputation method. In this last section, we talk about the limitations and the strengths of the
8

---

229
KNNxKDE algorithm, and summarize the main findings. We also provide recommendations for data scientists and statisticians, be it for industry, research or public organizations.
230
5.1
Limits
The obvious major drawback of the kNNxKDE is that we do not provide clear way to optimize it. We showed that our method performs best in terms of likelihood, but real-world datasets do not come with likelihood. Therefore, we are left with two options: either use visual inspection and plots
233
235 to assess the data imputation quality, or we optimize T to minimizing the RMSE (c.f. Appendix A).
236
Also, the kNN*KDE algorithm may not be suited for highly dimensional datasets. Not only can become computationally expensive, but its performances shall also worsen. Indeed, because of the curse of dimensionality, initially close observations may end up far apart if similar features are unobserved. This effect becomes even more problematic in high missing rates settings: as we work with missing rate patterns, observations with few observed features will have small number of potential donors. This problem can be mitigated if the dataset has many observations. As a consequence, calibrating the kNNxKDE algorithm in high dimensions is particularly challenging. Pairplots may be used to visually assess the imputation quality, but become inconvenient in high- dimension settings. Also, pairplots only display pairwise correlations and may overlook higher order structures (c.f. Appendix B
237
238
239
241
243
245
5.2
Strengths
If minimizing the imputation RMSE is intuitive strategy for tabular data imputation, it cannot capture the complexity of multimodal datasets. In practice, given an incomplete observation, if two different imputations
248
consistent with the rest of the observed dataset, have objective way of choosing one over the other. The kNNxKDE offers to not choose between these two options instead of averaging them both. It returns imputation sample that provides more information that single point estimate.
250
252
Unlike the ANN-Imputer which impute column after column, the kNNxKDE works with successive missing patterns. This allows to generate imputed samples which are consistent with the whole dataset. Since all missing features are imputed at the same time, this strategy cannot return anomalous imputed samples.
254
256
257
5.3
Conclusion
The main motivation of this work was to design algorithm capable of imputing missing features of a dataset with several modes. Multimodality makes imputation ambiguous, as clearly distinct values may still be valid imputations. In this respect, decide to the likelihood of imputation quality, instead of the standard RMSE between ground truth and imputed samples. The kNNxKDE method does not aggregate estimations. Instead, it returns imputation samples all consistent with the observed dataset. If needed, minimizing the imputation RMSE is possible by averaging the imputation samples, although discourage from straightforwardly doing so may lead to inconsistent imputed observations (c.f. Appendix A)
259
metric
261
263
265
Ultimately, this work advocates for qualitative approach of data imputation, rather than the current quantitative one. We believe that missing data imputation should be done carefully and meaningfully, it influences subsequent data analysis. We provide the kNNxKDE algorithm, and we suggest trying for practical tabular data imputation in various domains.
267
269
270 References
271
Dimitris Bertsimas, Colin Pawlowski, and Ying Daisy Zhuo From predictive methods to missing data imputation: An optimization approach. Journal of Machine Learning Research, 18, 2018. ISSN 15337928.
272
273
274
John K. Dixon. Pattern recognition with partly missing data. IEFE Transactions on Systems, Man and Cybernetics, 9, 1979. ISSN 21682909. doi: 10. 1LLLL//TSM...199944300000000

---

278
Nicholas Frosst, Nicolas Paperno, and Geoffrey Hinton. Analyzing and improving representations with the soft nearest neighbor loss. In ICML2019, volume 2019-June, 2019.
277
278
Allison Marie Horst, Alison Presmanes Hill, and Kristen B Gorman. palmerpenguins: Palmer Archipelago (Antarctica) penguin data, 2020. URL https://allisonhorss wttpiiorrrtttttt.......eg. 1o/
279
280
palmerpenguins/ R package version 0.1.0.
281
Anil Jadhav, Dhanya Pramod, and Krishnan Ramanathan. Comparison of performance of data imputation methods for numeric dataset. Applied Artificial Intelligence, 33, 2019. ISSN 10876545.
285
doi: 10. 10.1080008839514 2249..1111137777
284
Sebastian Jäger, Arndt Allhorn, and Felix Bicßmann. A benchmark for data imputation methods. Frontiers in Big Data, 4, 2021. ISSN 2624909X. doi: 00.3389/idata.2221669933
Richard Leibrandt and Stephan Günnemann. Making kernel density estimation robust towards missing values in highly incomplete multivariate data without imputation. In SIAM2018, 2018. doi: 0137//997816119999
287
Roderick J.A. Little and Donald B. Rubin. Statistical analysis with missing data. Wiley, 2014. doi: 10.1002/9781 190135663
290
291
Emauuel Parzen. On estimation of a probability density function and mode. The Annals of Mathe- matical Statistics, 33, 1962. ISSN 0003-4851. doi: 10. 1214/aoms// 177704472.
Jason Poulos and Rafael Valle. Missing data imputation for supervised learning. Applied Artificial Intelligence, 32, 2018. ISSN 10876545. doi: 10. 00.1080008839514220188 248411...11111114444. 1448143.
294
285
Murray Rosenblatt. Remarks on some nonparametric estimates of a density function. The Annals of Mathematical Statistics, 27, 1956. ISSN 0003-4851. doi: 10. 22144//m//117722111
296
297
Daniel J. Stekhoven and Peter Bühlmann. Missforest-non--araaeel missing value imputation for mixed-type data. Bioinformatics, 28, 2012. ISSN 13674803. doi: 10. /i..////iooiooomattc/ttsss/
298
299
D. M. Titterington and G. M. Mill. Kerne--baee density estimates from incomplete data. Journal of the Royal Statistical Society: Series B (Methodological), 45, 1983, doi: 10. 11.21166..1.-6661.. 1983.bb01249.x.
300
301
302
Olg ga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat Brown, Trevor Hastie, Robert Tibshirani, David Botstein, and Russ B. Altman. Missing value estimation methods for dna microarrays. Bioinformatics, 17, 2001. ISSN 13674803, doi: 10. (0093//oiinfommmttsi/7.6662222
303
304
305
Stef van Buuren and Karin Groothuis Oudshoom. mice: Multivariate imputatioo by chained equations in r. Journal of Statistical Software, 45, 2011. ISSN 15487660.
308
doi: 10. 181317/jss..0045.000
307
Katarzyna Woznica and Przemyslaw Biecek. Does imputation matter? benchmark for predictive models. Artemiss2020, ICML workshop, 2020. doi: 10. 4444555///rii2220000233333
308
309
Jinsung Yoon, James Jordon, and Mihaela Van Der Schaar. Gain: Missing data imputation using generative adversarial nets. 35th International Conference on Machine Learning, 2018, 13: 9042-9051, 2018.
310
A
Real-world dataset: minimizing the RMSE with kNNxKDE
312
For practical purposes, may remain interested in minimizing the RMSE between the imputed sample and the ground truth. This appendix shows how to use the kNNxKDE to obtain similar RMSE performances standard data imputation methods. The imputation samples returned by the kNNxKDE allow for many ways of performing a single imputation. Rather that sampling the conditional distributions only once for imputation like did in Section 4 can compute appropriate statistics to estimate the missing values. Here, we use the mean for imputation.
314
316
318
The hyperparameter of the kNNxKDE is tuned to minimize the imputation NRMSE when using the mean for the imputation. We use the Penguins dataset [Horst et al. [020]: 342 penguins with
320
features (beak length, beak depth, flipper length and body mass) organized in 3 classes. This dataset
10

---

Table 4: Mcan and standard deviation of the NRMSE on the Penguins dataset with all imputation methods. Optimal hyperparameters (shown below each method name) are obtained minimize the NRMSE. kNNxKDE(m) stands for imputation performed with the mean of the returned samples from the kNNxKDE.
A-N--mmuter
MissForest 30 trees
MICE
GAIN
kNNxKDE
kNNxKDF(()
40 neighbors
X
1200 iterations
default
= 15
0.136 + 0.008
0.147 + 0.012
0.154 + 0.008
0.186 + 0.026
0.219 + 0.014
0.140 + 0.012
322
similar to the famous iris dataset. Results are reported in Table where hyperparameters are optimized to minimize the NRMSE.
324
As we can see, averaging over the conditional distributions leads to similar performances as with the standard kNN-Imputer. The difference is that we now tune the continuous hyperparameter which defines how loose the neighborhood of each observation is, rather than the number of neighbors &s for the standard NNN-Imputer.
326
327
328
Note that, while the resulting imputation minimizes the RMSE, this may not preserve the structure of the original dataset any longer. If the original dataset is multimodal, the imputed dataset can present inconsistent observations.
329
330
331
B
Synthetic data in 3d: visualizing higher-order correlations
332
We generate dataset in 3-dimensions using spherical coordinates. Pairplots cannot help visualizing beyond pairwise correlations. But some structures may involve higher-order dependencies which traditional data imputation algorithms do not capture. For example, Figure compares the imputation
333
334
335
of the 3-d synthetic dataset with the ANN-Imputer and with the kNNxKDE. Table presents the
338
NRMSE and the log- likelihood for each method.
Complete
KNN-Imputer
Miss X3
kNNxKDE h = 0.03 and 50
N neigh 20
Miss
Miss
Miss
Miss X3.x3
Miss Xs
55
3 50
35
-2.
-3.0
-1.0
-10 -35
-10
1.0
X3
30
95
0.2
-05
Figure 7: Visualization of the imputed 3-d spherical dataset (MCAR scenario with 20% missing rate): kNN-Immuter (left panel) and kNNxKDE (right panel). Points colors indicate imputed components. The kNN-Imputer creates artifacts (points inside the sphere) while the kNNxKDE preserve the original dataset structure.
337
Regarding the NRMSE, the kNNxKDE performs bad. But using the log-likelihood as benchmark, we that the random sample generated by the kNNxKDE is much more probable under the generative model, ie. the imputed sample consistent with the original dataset. The scatter of the imputed observations (right panel of Figure 7 can be adjusted with and h.
339
340
341
Visual animations of the imputed samples with all five imputation methods are provided as supple- mentary materials, where we can notice the characteristies of each imputation method.
11

---

Table 5: Mcan and standard deviation of the NRMSE on the Penguins dataset with all imputation methods. Optimal hyperparameters (shown below each method name) are obtained minimize the NRMSE. kNNxKDE(m) stands for imputation performed with the mean of the returned samples from the kNNxKDE.
&NN- Imputer
MissForest 15 trees
MICE
GAIN
kNNxKDE default
(kyperparams)
20 neighbors
x
1200 iterations
NRMSE
0.252 - 5683
0.276
0.248 6309
0.257 -5793
0.385
Log-Lik. (Ref=-2130)
-4023
-3008
Checklist
343
344
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No] or
345
346
[N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
347
Did you include the license to the code and datasets? [Yes] See Section xxx
349
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
350
351
Did you include the license the code and datasets? [N/A]
352
Please do not modify the questions and only use the provided macros for your answers. Note that the
353
Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
354
355
1. For all authors...
356
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Emphasis on quality imputation and multimodal datasets
357
358
(b) Did you describe the limitations of your work? [Yes] See Section 5
359
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
380
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] To our knowledge, no potential negative harmful societal impact. We have done our best for transparency and reproducibility
381
362
363
2. If you are including theoretical results...
364
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
365
(b) Did you include complete proofs of all theoretical results? [N/A]
386
3. If you ran experiments...
367
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] See supplemen-
369
tary materials
370
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Methodology and training procedures are extensively explained in
371
Sections 2 3 and 4
372
373
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] Standard deviation are used for error bars (Section Seeds have been used in the code (supplementary materials) when needed for reproducibility
374
376
377
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We thought it was irrelevant, because rather fast with CPUs
378
379
380
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
381
(a) If your work uses existing assets, did you cite the creators? [Yes] We use one existing dataset, whose creators have been credited
12

---

(b)
Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [Yes]
385
Code and synhtetic data in Supplementary materials
386
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
388
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
390
5. If you used crowdsourcing or conducted research with human subjects...
391
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
396
13


Reviews:
[{"review_id": "lFVhT2VWfFR", "reviewer": "Reviewer_4E75", "summary": "The paper addresses the limitations of current state-of-the-art (SOTA) data imputation algorithms at accurately modeling multimodal data.  The authors demonstrate this ineffectiveness using three toy synthetic datasets (2 dimensional with 500 samples each) and 4 SOTA algorithms.  An algorithm which combines the popular kNN-Imputer with kernel density estimation, called kNN-KDE, is presented and shown to well capture the three patterns in the toy datasets: linear, sinusoidal, and spherical.  The paper also makes a case for measuring imputation quality via the log-likelihood as opposed to the commonly used RMSE, while also admitting this is impractical on real-world datasets.", "questions": "\"The best hyperparameters, presented in Table 1, are\nused to impute each dataset one more time\" <- This overfits each\nimputation method and is not reflective of generalization\nperformance.  Given the data is synthetic and easily generated, why\nnot produce more samples and use cross-validation?\n\n-Some discussion of the plausbility of the synthetic data seems\nwarranted.", "limitations": "The authors address several limitations of their work.  However, one important limitation is that the devised algorithm, kNN-KDE, is particularly designed to handle the three synthetic datasets presented (i.e., use of Gaussian kernels is ideal for spherical data).  This is an extremely limited representation of multimodal data, and non-spherical datasets could also be studied to determine the efficacy of kNN-KDE on a much wider variety of data.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\nStrengths: The presented data imputation algorithm is novel.  Updating the popular kNN-imputer to utilize a Gaussian kernel is interesting.\n\nWeakness: In the main paper, the effectiveness of the proposed algorithm is not demonstrated either in a practical setting on real world data or on complicated/higher-dimensional synthetic datasets.  Furthermore, existing methods tackle the exact problem being tackled by kNN-KDE;  imputation methods using Gaussian copulas have been explicitly designed to accurately model multimodal data :\nZhao, Yuxuan, and Madeleine Udell. \"Missing value imputation for mixed data via gaussian copula.\" Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.\n--------------\nQuality:\nWeakness: Major weakness in the paper are inherent in the evaluation and the underlying motivation of the problem being tackled.\n\"real-world datasets do not come with a likelihood\" <- \nFor the latter, the main paper does not consider real world datasets.  A major concern is the main problem being tackled--failures of existing SOTA imputation methods to model multimodal data--are motivated by synthetic datasets, rather than actual trends observed in real data.  It is also important to note that kNN-KDE is particularly designed to handle the three synthetic datasets presented (i.e., use of Gaussian kernels is ideal for spherical data), but this is an extremely limited representation of multimodal data and and may not reflect trends commonly encountered in ML data.  Furthermore, while kNNxKDE is described, the presented work is not an end-to-end solution: \"Therefore, we are left with two options: either we use visual inspection and plots to assess the data imputation quality, or we optimize τ to minimizing the RMSE \" <- At a minimum, the problem of how to run the algorithm on real data should be solved and presented in the paper.  Otherwise, researchers cannot put kNNxKDE into practice and the presented imputation framework is incomplete.\n\nWith regards to evaluation, while real data does not come with a log-likelihood, other evaluation exists with which to determine the\neffectiveness of a data imputation approach (as is apparent in many of the works cited, e.g., Jager et al, 2021).  For instance, using a\nUCI classification dataset with missing values, values could be imputed and downstream classification performance used to show the\nperformance of different imputation algorithms.\n\nWith regards to the advocacy of qualitative (log-likelihood) vs quantiative (RMSE) measures, the authors state:\n\"Ultimately, this work advocates for a qualitative approach of data imputation, rather than the current\nquantitative one.\" <- As the authors have pointed out, this is impractical for real world data due to an inability to compute the log-likelihood.\n--------------\nClarity:\nThe writing is clear and the work, as presented, is easy to parse and understand.\n--------------\nSignificance:\nStrengths: Data imputation is an important practical problem in machine learning.  As kNN-imputer is one of the most popular SOTA imputation algorithms, improvements to the algorithm may be widely appreciated and put to use by ML researchers.\n\nWeakness:  As mentioned in the section on quality, practical evaluation of kNN-KDE remains lacking, so that the performance and significance of the algorithm on commonly encountered real-world datasets is unknown.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TKhtERNYw1K", "reviewer": "Reviewer_xjdE", "summary": "This study presents a strategy for imputing missing values in tabular data in the presense of multi-modal distributions. The motivation is that existing imputation methods tend to give poor imputations for multi-modal datasets, the examples of which are described in the manuscript. \n", "questions": "Questions regarding baseline methods.\n- Please provide the details of what you have tried for the baseline methods.\n- Particually, I'm curious how you set the hyperparameters of GAIN, including the architecture and optimization. My experience says the performance of GAIN is not that bad (althuogh it's fairly sensitive to the hyperparemeter settings.)\n\nQuestiions regarding the proposed method.\n- What would be the expected effert if the hyperparameter setting changes? How do we optimize it for the practical use?\n- Will it work well on real-world datasets involving high-dimensionality?", "limitations": "Suggestions to improve experimental validation\n- The authors used only two-dimensional toy datasets, which are not usual in real-world. The effectiveness of the proposed method should be evaluated on the datasets with various dimensionalities and also various sizes.\n- The evaluation also need to be performed further under various missing rates as well as 20%.\n- Among the baseline, for the k-NN imputation, a widely used way to improve the imputation is to use of median/mode over the observsed values in the k-NN, instead of using the average. This can give much better imputation for multi-modal datasets, including the toy datasets used in this study. This can be used as a baseline to be compared with the proposed method.\n- An intuitive way to evaluate a imputation method is to use classificaiton/regression datasets. if it improves the performance for a classification/regression problems under the presense of missing values in input features.\n- What would be the expected effect of the hyperparameters \n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- I like the motivation of this study. Most existing imputation methods tend to give poor imputations under the multimodality. As authors mentioned, among plausable values for a missing value, using their average can be a very bad choice over simply picking one. \n- I agree that the RMSE evaluation for the imputed values is not sensible in the evaluation of a missing value imputation method. the likelihood-based evaluation makes sense and seems better.\n\nWeakness\n- My main concern is that the scope of experimental validation is narrow and very limited. The details regarding this are listed in \"Questions\" section.\n- It seems the hyperparameters baseline methods are not carefully tuned. \n- Also, the effect of hyperparameters on the proposed method is not well-studied.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5s7v5HfSHqE", "reviewer": "Reviewer_WFqA", "summary": "The authors via this paper tried to highlight the shortcomings of the current imputation methods which tend to focus on minimizing the error between the unobserved and the imputed values. Authors propose a new qualitative approach with kNNxKDE algorithm i.e. a hybrid method using kNN and KDE capable of imputing missing features of a dataset with several modes. Authors use NRMSE to compare and evaluate the performance of their algorithm with other imputation methods.", "questions": "I understand RMSE cannot be used as an evaluation metric for all imputation methods, however, even NRMSE assumes smaller values for simulations underestimating the observations. Did the authors notice shortcomings (if any) by using NRMSE as an evaluation metric in their experiments?", "limitations": "Authors did a fairly good job in addressing the limitations of their study. However, these limitations are very critical in developing machine learning applications especially data imputation being the earliest stage in data preprocessing.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors have rightly highlighted the shortcomings or the limits of root mean square error (RMSE) as an evaluation metric for the data imputation problems. Also, briefly discussed and emphasized the current available standard imputation methods and how they operate and key differences in each method. \\\nI believe the major weakness of this paper is lack of rigorous experimentation. Authors chose only a few simple datasets to run their experiments and compare with the current imputation methods, the study is only suitable for a narrow selection of datasets. In the real world, data is not always simple! Also, I recommend authors to expand the study to show the performance of their proposed algorithm with other evaluation metrics.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject