Data Imputation by Pursuing Better Classification: A Supervised Learning Approach

Thank you for your recognition and detailed feedback on our work. We have addressed your concerns as follows.

R4.1 The settings and the choice of the model parameters.

Thank you for pointing out this issue in detail. It is indeed a meaningful consideration for users. We empirically offer some suggestions regarding the parameter settings. Regarding the adjustment of the parameter $\gamma$, we adopt the traditional "grid search" approach commonly used in SVM to select the parameter value. For $\eta$, which controls the extent to which the similarity between samples can be modified, if there is still room for improvement in the predictive accuracy of the training set, reducing $\eta$ can be explored to seek better similarity relationships among samples. As for $r$, which governs the robustness of the classifier, if the predictive accuracy during training is already high but the performance on the holdout set is unsatisfactory, increasing the value of $r$ can help alleviate this issue. We wish that the above response partially addresses your concerns.

R4.2 Studying on more data sets.

We sincerely appreciate your valuable feedback. Following your suggestion, we conducted experiments on two new data sets. For detailed results of the experiments, please refer to R0.1 in the Author Rebuttal.

R4.3 Studying on other works and other missingness processes.

We sincerely appreciate your insightful comments. Based on your suggestions, we have included a comparison of results on two data sets with inherent missing values. And we compare the results with a recent neural network-based method, NeuMiss [1]. For more details, please refer to R0.1 in the Author Rebuttal.

R4.4 Elaboration of the adversarial optimization of the classifier.

In Section 3.2, our approach is primarily inspired by the principles of robust optimization, which shares similarities with the adversarial optimization you mentioned. Both approaches aim to ensure good performance of the model even under worst-case scenarios.

R4.5 The difference among the results of different methods.

We have indeed observed the issue you pointed out, and this phenomenon has also been observed in other studies. For example, Table 1 in [2] and Table 1(c) in [3] demonstrate that there is no significant difference in test accuracy between MI, 0-imputation, and the proposed method in certain scenarios. We think that these observations may be attributed to several factors, including the proportion of missing data and intrinsic characteristics of the data. Firstly, for simple cases where the proportion of missing data is low, as shown in Table 3 with the example of Australian $(m=20\%)$, all the methods performed well. In more challenging scenarios, data imputation becomes exceedingly difficult, causing each method to struggle in achieving improved results, as seen in Table 3 with the example of German under high missingness.

R4.6 Missing values: Presence in training/test sets or not.

In our experimental setup, the training set contains missing values while the test set does not, which follow the settings in [4].

R4.7 The influence of dealing with the PSD constraint.

Such an operation does not affect the results and is a widely applicable operation. For detailed theoretical references, please refer to the Theorem 2.1 in [5] and the Equation (9) in [6].

R4.8 The outcome when skipping the Step 2 in the first phase.

If we skip Step 2, the flexibility of our framework (allowing changes in both data similarity and classifier) makes it susceptible to overfitting. In such a scenario, if the allowed range for $K_\Delta$ to change is large (i.e., when the value of $\eta$ is set too small), it can lead to the situation you mentioned as "perfect data"，where the resulting kernel matrix tends to approach the ideal kernel matrix $yy^T$ as closely as possible. Although it results in high classification accuracy on the training set, it may not generalize well to the test set.

R4.9 Discussions about the $\mathcal{E}^\ast$.

a) We set $\mathcal{E}^\ast$ as positive semi-definite (PSD) to ensure that the kernel matrix used in SVM remains PSD, as supported by the Schur Product Theorem [7].

b) It is important to note that that we pursue the similarity relationship between data with better classification performance by optimizing $K_\Delta$, and use these relationships to guide the data imputation process. The introduction of $\mathcal{E}^\ast$ is solely intended to enhance the robustness of the classifier. Therefore, in Stage II, where we focus on data feature imputation, we only utilize $K_o\odot K_\Delta$.

R4.10 The modification on writing.

Thank you very much for your valuable suggestions and careful reading. In response to each of your suggestions, we have presented the modified sentences below.

a) Page 1. we typically use the set of observable features $o_i\subseteq 2^{\lbrace 1,\cdots,d\rbrace }$ and missing features $\ast$ to represent the missing data $x_{o_i}^i\in(\mathbb{R}\cup \{\ast\})^d$. This sequence is then consolidated into an incomplete data set $\mathcal{D}=\lbrace x_{o_i}^i, y_i\rbrace _{i=1}^N$.

b) Page 1. However, the effective utilization of label information has not been fully explored yet.

c) Page 2. This step is relatively easy, particularly in the traditional scenario where $N \gg d$. Because for each data, there is $N – 1$ available supervised information stored in the kernel matrix to guide the imputation of $d$ or fewer elements.

d) Page 4. The set of real numbers is written as $\mathbb{R}$. The set of integers from 1 to $N$ is written as $[N]$. The cardinality of the set $\mathcal{A}$ is written as $|\mathcal{A}|$ denotes. We take $a$, $\boldsymbol{a}$, and $\boldsymbol{A}$ to be a scalar, a vector, and a matrix, respectively. Let $\boldsymbol{0}$ and $\boldsymbol{1}$ denote vectors consisting of all zeros and all ones with the appropriate size. The inner product of two vectors in the given space is written as $\langle\cdot, \cdot\rangle$. We take $\mathrm{diag}(\boldsymbol{a})$ to be an operator that extends a vector to a diagonal matrix. The Frobenius norm of a matrix is written as $\lVert \cdot \rVert_\mathrm{F}$. The set of positive semi-definite (PSD) matrices is written as $\mathcal{S}_{+}$. The Hadamard product is written as $\odot$.

e) Page 4. Initially, we compute the observed kernel matrix $K_o$, and then optimize an adjustment matrix $K_{\Delta}$ with the same dimension to derive $\tilde{K}=K_o\odot K_{\Delta}$ as the imputed kernel matrix.

f) Page 5. The problem above is a semi-definite program, which is generally computationally expensive to solve.

g) Page 6. The essence of this task involves solving a nonlinear system of equations. Additionally, by defining the missing ratio of data features as $m$, the aforementioned system consists of $N(N-1)/2$ equations and $Ndm$ variables.

h) Page 7. We chose four real-world data sets from libsvm (Chang & Lin, 2011), namely australian, german, heart and pima (a.k.a. diabetes).

Referneces

[1] Le Morvan M, Josse J, Moreau T, et al. NeuMiss networks: differentiable programming for supervised learning with missing values[J]. Advances in Neural Information Processing Systems, 2020, 33: 5980-5990.

[2] Chechik G, Heitz G, Elidan G, et al. Max-margin Classification of Data with Absent Features[J]. Journal of Machine Learning Research, 2008, 9(1).

[3] Hazan E, Livni R, Mansour Y. Classification with low rank and missing data[C]//International conference on machine learning. PMLR, 2015: 257-266.

[4] Pelckmans K, De Brabanter J, Suykens J.A.K, et al. Handling missing values in support vector machine classifiers[J]. Neural Networks, 2005, 18(5-6): 684-692.

[5] Cai J F, Candès E J, Shen Z. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on optimization, 2010, 20(4): 1956-1982.

[6] Liu F, Huang X, Gong C, et al. Learning data-adaptive non-parametric kernels[J]. The Journal of Machine Learning Research, 2020, 21(1): 8590-8628.

[7] Styan G.P.H. Hadamard products and multivariate statistical analysis[J]. Linear algebra and its applications, 1973, 6: 217-240.

Dear reviewer UxXs,

We've taken your feedback on board and implemented the necessary revisions in the paper before submitting it to the OpenReview system. Here are a few of the main changes we made:

• We've expanded the discussion on existing work in the related work section on page 4, and we've added a comparison with a recent neural network method called NeuMiss in Appendix B.
• Appendix B also includes a discussion of the algorithm's results on non-missing completely at random data.
• We have provided clearer explanations in the "Data sets and preprocessing" section in Section 4.1 regarding whether missing values exist in the training and test sets.
• We have made the necessary modifications in the text to address all eight of your meticulous suggestions on writing.

We sincerely appreciate your valuable suggestions and detailed feedback. They have helped enrich the content of our paper and make it more rigorous. We hope that the modifications we have made meet your standards. If you find any areas where our responses may still be inadequate or if you have any other specific concerns, we welcome your additional insights. We will make every effort to respond and engage in further discussion before the end of the discussion period.

Thank you very much for finding our two-stage procedure interesting. Indeed, both the optimization of pairwise data similarity relationships in the first stage and the subsequent data recovery using the kernel matrix are novel aspects that contribute to the effectiveness of our imputation task. We also appreciate your recognition of our comprehensive testing of algorithm performance under various data missing ratios. We have addressed your concerns as follows.

R3.1 Studying data sets beyond artificial MCAR settings.

We sincerely appreciate your highlighting the need for result validation in non-artificial MCAR settings. As you rightly pointed out, obtaining results under different missing mechanisms would provide stronger support for the superiority of our algorithm. Reviewer Jet1 also raised a similar question. Therefore, we have addressed this issue in R0.1, and please let us know if it is appropriate. If you have any further questions or if there are other specific aspects of the results that interest you, we would be more than happy to engage in further discussions with you.

Dear reviewer VYgf,

Following your suggestions, we've completed the revisions and uploaded the revised version of the paper to the OpenReview system. We have made the following additions to the paper:

• We have addressed the algorithm comparison results beyond the artificial MCAR setting in Appendix B. Additionally, we have included a comparison with a recent neural network-based method.

We greatly appreciate your suggestions, as they have helped enrich the content of our paper. We hope that the additional experiments we have included further validate the performance of our algorithm. If you would like to see how our algorithm performs in other scenarios or have any other specific concerns, we will do our best to respond and discuss them before the end of the discussion period.

Thank you for recognizing the novelty of our approach in leveraging both unknown and observed feature information when optimizing the kernel matrix and the justification of our approach. In fact, it is precisely by considering this pairwise information among the data that we achieve better imputation results and, consequently, improve the classification performance (especially in scenarios with high data missing rates). We address your concerns as follows.

R2.1 Studing on more data sets and imputation methods.

We sincerely appreciate your valuable feedback. The additional comparisons you mentioned regarding the datasets and imputation methods are indeed important for validating the performance of our algorithm, and other reviewers have also expressed similar concerns. Therefore, following your suggestion, we conducted experiments using the latest neural network-based method, NeiMiss [1], on two additional datasets. And we have provided detailed results in R0.1 in the Author Rebuttal. We hope this addresses some of your concerns.

R2.2 Studing on larger data sets.

Regarding the issue of scalability to large-scale data in our proposed method, it is indeed a challenge due to the need for leveraging pairwise information in the samples. Additionally, some popular techniques used to accelerate kernel methods cannot currently be applied to the imputation problem. This issue will also be a research direction that we will dedicate efforts to in the future. For a more detailed discussion, please refer to R0.2 in the Author Rebuttal. If you have any specific questions, we are more than happy to engage in further discussions with you over the next week.

Reference

[1] Le Morvan M, Josse J, Moreau T, et al. NeuMiss networks: differentiable programming for supervised learning with missing values[J]. Advances in Neural Information Processing Systems, 2020, 33: 5980-5990.

Dear reviewer h2QN,

We've made the changes you suggested in the main text and uploaded the revised paper to the OpenReview system. And we have listed the main changes below.

• We added a discussion on some recent imputation methods in the related work section on page 4.
• In Appendix B, we included a separate discussion on the algorithm results obtained from two datasets with inherent missing values. Additionally, we introduced and compared a recent neural network-based method to further highlight the advancements of our approach.

We greatly appreciate your suggestions, which have helped enrich the content and improve the quality of our paper. In addition to the modifications made in the text, we have also addressed some discussions regarding the case of large scale data in our previous rebuttal. We hope that our responses have addressed your concerns. We would be more than happy to engage in further communication with you. If you have any other concerns or related questions, we will make every effort to respond before the end of the discussion period.

Thanks for appreciating the novelty of our work and for providing insightful comments. We address your concerns as follows.

R1.1 Studing on more and larger data sets.

We sincerely appreciate your valuable feedback. Following your suggestion, we conducted experiments on two new data set. For detailed results of the experiments, please refer to R0.1 in the Author Rebuttal. As for the lack of involvement with large-scale data sets, we provided a comprehensive discussion in R0.2 in the Author Rebuttal.

R1.2 New experimental results for two tested items in Australian and one tested item in German.

Your questions about the accuracy reported for MI, genRBF, and GEOM may be related to our experimental setup. For specific examples, we will discuss them as follows.

a) For MI, as described in [2], it allows leveraging feature information from the test set to aid in imputation. In our experimental settings, we only introduced missing features in the training set while utilizing complete holdout and test sets. Therefore, especially in cases of high feature missing rates, the information from the test set contributes to better classification performance for MI.

b) For genRBF, some abnormal results in extreme cases were due to the narrow range used to adjust hyperparameters. We have modified the grid search range for $C$ and $\gamma$ and made our best efforts to improve the performance, and then we have adjusted the values of genRBF for several tested items. For the case of Australian $(m=60\%)$, Australian $(m=80\%)$, and German $(m=80\%)$, based on our correction, genRBF should have the accuracy of $0.796 \pm 0.041$, $0.704 \pm 0.058$, and $0.687 \pm 0.045$, respectively. And for other scenarios, we carefully examined and confirmed that the previously used parameters were optimal. Thank you for meticulously pointing out this issue and we will revise these results in our manuscript.

c) For GEOM, we conducted experiments specifically for the data-missing scenario of $m=90\%$ (i.e., the experimental setup described in their paper), using the provided code by the authors. On the Pima dataset, we obtained a result of $0.658 \pm 0.029$ for the GEOM method, which aligns with the reported result of $0.66 \pm 0.05$ in the Table 1 of [2]. However, we obtained a result of $0.689 \pm 0.036$ for the MI, which is higher than the reported value of $0.65 \pm 0.04$ in the paper. This discrepancy arises from the utilization of the complete test set, as we mentioned above.

R1.3: Studing on the non-MCAR data.

We sincerely appreciate your valuable feedback. Based on your suggestions, we have included a comparison of results on two data sets with inherent missing values, which are non-MCAR. For more details, please refer to R0.1 in the Author Rebuttal.

R1.4: Modifications in object definitions and the mathematics.

We sincerely appreciate your meticulousness in pointing out our oversights.

a) Regarding the definition of $K_o$, as you correctly noted, it should indeed be defined by the first term in the last line of Equation (3).

b) In regards to the symbol $\ast$, it represents an unknown real number in future manuscript, which aids in computing the range of values such as $x_p^i-\ast$, assuming that $x$ is normalized to the range [0,1].

c) Thank you very much for your detailed observation. Indeed, our wording was not precise. Clipping a matrix first and then projecting it into the PSD matrix space does not guarantee that every element of the resulting matrix remains within the proper range. Our intention in introducing the proper range was merely to prevent significant changes in $K_\Delta$. While there may be elements slightly exceeding the range after the projection, these modified values can still be bounded, which allows the original constraint to remain effective and leads to similar performance in subsequent algorithms.

We will make the necessary modifications and additions in the manuscript to address the issues you have pointed out in the manuscript.

Dear reviewer Jet1,

We've uploaded the revised paper to the OpenReview system. Based on your suggestions, here's what we've done:

• In Appendix B, we added experiments on non-MCAR data and included one of the recent works on supervised learning with missing values that you mentioned.
• We checked the accuracy reported for genRBF, and addressed the issue of abnormal values in extreme cases by adjusting the range of hyperparameters in the grid search. Consequently, we made modifications to the results of the three items in Table 3 on page 9.
• Under Equation 3 on page 5, we explained the meaning of the $\ast$ and added a description of $K_o$. We also corrected the name of $K_\Delta^\ast$ on page 5.
• We replaced the terms $\mathcal{E}$ and "imputed kernel matrix" with "perturbation" and "optimized kernel matrix", respectively.
• We added a discussion of the several pieces of work you mentioned to the last category of related work on page 4.

We truly appreciate your valuable suggestions and detailed feedback. We hope that these modifications meet your standards and make our paper more rigorous and reader-friendly. We're also curious if you'll have the opportunity to review our rebuttal. If you have any other concerns or related questions, we would be delighted to discuss and communicate with you before the end of the discussion period.

Thank you for your recognition of the modifications we made and for providing valuable feedback once again. We have addressed your questions as follows:

R1.7 Classification/Regression in NeuMiss

Firstly, you are absolutely right that NeuMiss (at least in their paper) is designed for regression problems with missing data. To fit the classification task, in NeuMiss, we utilize a certain threshold to convert the soft labels into binary labels 0 and 1. When using such weaker supervised information compared to regression, our algorithm yields better results than NeuMiss. In the future, we are certainly dedicated to extending the ideas presented in this paper to regression tasks, such as utilizing support vector regression models. We will continue exploring this direction in future research.

R1.8 Further discussion on constraints on $K_\Delta^\ast$

For optimization problem (5), we have two concerns: 1. The constraint of the matrix being PSD. This is a very hard constraint as it is a prerequisite for training SVM models effectively. 2. The constraint of the matrix falling within a proper range. Roughly speaking, this constraint acts more like regularization, as described in R1.4(c), aiming to limit excessive variations in the optimization variables. Therefore, we adopt a two-step approach of clipping and then projecting to ensure that the first constraint is satisfied while attempting to satisfy the second constraint as much as possible. Indeed, as you mentioned and as we explained in our previous reply, this cannot guarantee that the second constraint is satisfied. Regarding the idea of alternating projection you mentioned, it is indeed a good idea. However, considering the speed of the algorithm and the relatively lower importance of the second constraint, we have opted for the current approach.

R1.9 Further discussion on results of MI

Firstly, our algorithm and several other methods do not utilize test set feature information, while MI does. Therefore, in cases where the test set does not have missing values, this additional information becomes a strong prior for the entire data set, resulting in a significant improvement in the performance of MI. Due to time limitations, we conducted experiments with MI excluding test set feature information on the german dataset with $m=80$% and the cylinder dataset. The former yielded a result of $0.686 \pm 0.030$, and the latter resulted in $0.620 \pm 0.024$. Comparing these results with the results of $0.700 \pm 0.020$ and $0.648 \pm 0.014$ in Table 3 and Table 5, respectively, it can be observed that the performance of MI decreases to some extent when lacking the assistance of abundant information that originally exists in the test set. In practice, scenarios with or without missing values in the test set can occur. Therefore, we still highly value and consider the ideas and techniques provided by previous methods to be important.

R1.10 The way of normalization

This operation is performed before removing the missing values and does not involve the use of test set data.

It is worth noting that even with a high rate of missing data, we are still able to perform normalization based on the observed features.