PaperlayerView exact revision on arXiv

Source-linked AI summary

On the consistency of supervised learning with missing values

Julie Josse, Jacob M. Chen, Nicolas Prost, Erwan Scornet, Gaël Varoquaux

arXiv:1902.06931v5stat.MLcs.LGmath.STstat.TH

TL;DR

The paper addresses prediction when training and test inputs contain missing values, a setting less studied than inference. It examines consistency results for imputation and compares tree strategies, reporting that constant imputation can be consistent and that multiple imputation supports prediction on incomplete test data.

  • Problem

    The paper studies supervised prediction with missing input values, a setting with relatively few studies compared with inferential missing-data work.

    Source: §1 · p. 2

  • Method

    The paper analyzes consistency for imputation-based prediction and compares tree strategies for handling missing values directly.

    Source: §6 · pp. 41–42

  • Results

    Constant imputation is consistent when used with a powerful, non-linear learning model, and multiple conditional imputation supports a Bayes-consistent estimate with MAR missingness.

    Source: §6 · pp. 41–42

  • Takeaways & Limitations

    The paper concludes that constant imputation can be appropriate for prediction and that missing-value handling should adapt to different regimes.

    Source: §6 · p. 42

    More work is needed to establish theoretical results in the finite-sample regime and to control uncertainty.

    Source: §6 · p. 42

Abstract

from arXiv · show

In many application settings, the data have missing entries which make analysis challenging. An abundant literature addresses missing values in an inferential framework: estimating parameters and their variance from incomplete tables. Here, we consider supervised-learning settings: predicting a target when missing values appear in both training and testing data. We show the consistency of two approaches in prediction. A striking result is that the widely-used method of imputing with a constant, such as the mean prior to learning is consistent when missing values are not informative. This contrasts with inferential settings where mean imputation is pointed at for distorting the distribution of the data. That such a simple approach can be consistent is important in practice. We also show that a predictor suited for complete observations can predict optimally on incomplete data, through multiple imputation. Finally, to compare imputation with learning directly with a model that accounts for missing values, we analyze further decision trees. These can naturally tackle empirical risk minimization with missing values, due to their ability to handle the half-discrete nature of incomplete variables. After comparing theoretically and empirically different missing values strategies in trees, we recommend using the "missing incorporated in attribute" method as it can handle both non-informative and informative missing values.

1 Introduction

The introduction frames missing-value prediction as distinct from inference and motivates studying methods that work when both training and test data are incomplete. It previews consistency results for imputation and comparisons of tree-based strategies, including a recommendation for MIA.

1 Introduction

  • Missing entries arise from data aggregation and heterogeneous sources, and may also reflect mechanisms related to the prediction target.The introduction gives sensor failure, poll responses, and impractical medical measurements as examples of why values may be missing.Source: §1 · pp. 2–3
  • Supervised learning with missing values is under-studied relative to inference, despite prediction settings requiring methods that handle incomplete test data.The target is predicted from input variables with missing entries, and missingness nomenclature has seldom been discussed in supervised learning while accounting for the target.Source: §1 · pp. 2–3
  • Listwise deletion can discard nearly all observations in high dimensions and may bias the sample, while mean imputation is criticized in inference for distorting data distributions.Prediction also requires handling incomplete test data, and constant imputation’s predictive impact has received little study.Source: §1 · p. 3
  • An optimal predictor for complete data can be used on incomplete test data through multiple imputation to build a consistent procedure.The introduction describes this as the first of two consistency results for estimating the prediction function with missing values.Source: §1 · p. 4
  • Constant imputation before learning is consistent for supervised learning, and the paper presents this as a justification for a convenient practice.The introduction identifies this as its most striking theorem and, to the authors’ knowledge, the first result justifying the practice.Source: §1 · p. 4
  • The paper compares tree-based strategies with imputation and other learning approaches, recommending MIA for informative and non-informative missing values.Decision trees can handle missing values directly, and the introduction also notes benefits from adding binary missingness indicators as covariates.Source: §1 · p. 4

2 Definitions, problem setting, prior art

This section formalizes supervised prediction with incomplete features as risk minimization and reviews missing-data mechanisms and approaches such as imputation and EM. It distinguishes predictive evaluation from reconstruction and parameter inference, noting that prior work has focused mostly on inference.

2.1 Supervised learning

  • Supervised learning seeks a predictor minimizing expected loss, while a finite training sample leads to empirical-risk minimization and test data estimate generalization error.A procedure is Bayes consistent when its infinite-data prediction achieves Bayes loss.Source: §2.1 · pp. 5–6

2.2 Background on missing values

  • Classic missing-data work focuses on inference from a single dataset rather than distinguishing training from test data, and precise notation for incomplete features is challenging.The paper notes that insufficiently explicit notation has contributed to confusion.Source: §2.2 · p. 6
  • Incomplete observations are represented by a missingness mask and an observed vector whose missing entries are marked NA, with observed and missing components tracked separately.The mask M identifies which features are unobserved; the notation distinguishes the incomplete vector from the complete vector and its observed and missing subvectors.Source: §2.2 · pp. 7–8

2.2.1 Missing data mechanisms

  • Missingness mechanisms range from MCAR, independent of values, through MAR, dependent only on observed values, to MNAR, which cannot be ignored; MAR permits ignoring the mechanism for likelihood inference under stated conditions [Rubin, 1976].The likelihood result assumes MAR, a parameter-space factorization, and positive missingness probabilities.Source: §2.2.1 · pp. 9–10
  • There is little literature on missing-data mechanisms for supervised learning or discriminative models; Kapelner and Bleich [2015] formalize the problem by separating…The supplied passage ends mid-sentence, so it does not specify what they separate.Source: §2.2.1 · p. 10
  • In supervised learning, missingness mechanisms may need to account for the response; Ding and Simonoff [2010] classify them by dependence on Y, always-observed X, and potentially missing M.Source: §2.2.1 · p. 10

2.2.2 Imputation prior to analysis

  • Imputation commonly completes data for existing pipelines, but this paper evaluates it through downstream prediction rather than standalone reconstruction.Source: §2.2.2 · pp. 10–11
  • Although easy to implement, comparing values with the truth by RMSE has been criticized because optimal imputation is the conditional mean, reducing imputed-data distribution variability relative to the actual true distribution [see, e.g., N¨af et al., 2023].Source: §2.2.2 · p. 11
  • Single imputation treats imputed and observed values alike and underestimates parameter variance; multiple imputation represents uncertainty with many completed datasets and combines their analyses.Source: §2.2.2 · p. 12

2.2.3 EM algorithm

  • Under MAR, EM estimates parameters by maximizing the observed-data likelihood, and each iteration increases that likelihood without guaranteeing a global maximum.Unlike generic imputation, EM proceeds directly in one step but requires a problem-specific algorithm.Source: §2.2.3 · p. 13

3 Supervised learning procedures with missing data on train and test set

The section adapts missing-values methods to supervised learning, where test observations share the training distribution and missingness mechanism. It presents out-of-sample imputation and prediction, EM-based prediction, and empirical risk minimization for incomplete inputs.

3 Supervised learning procedures with missing data on train and test set

  • Supervised-learning procedures must predict on new observations with missing values drawn under the training data’s missingness mechanism.The section assumes train and test data come from the same distribution.Source: §3 · p. 14

3.1 Out-of-sample imputation

  • Fit an imputation model on training data, use it to impute training inputs before learning, then apply the same fitted model to test inputs before prediction.Many general-purpose imputation methods are black boxes that do not separate parameter estimation from data completion, making out-of-sample imputation difficult.Source: §3.1 · p. 14

3.2 EM and out-of-sample prediction

  • Under the stated MAR assumptions, EM estimates model parameters from the observed log-likelihood for out-of-sample prediction based on observed features.The prediction distribution can be related to that for fully observed data; its expectation can be approximated by Monte Carlo sampling.Source: §3.2 · pp. 15–16
  • Monte Carlo sampling is straightforward in simple models, but logistic regression has no explicit solution and may require Metropolis-Hastings algorithms.Source: §3.2 · p. 16

3.3 Empirical risk minimization with missing data

  • Empirical risk minimization can be adapted to incomplete inputs, but common learning algorithms require vector-space inputs rather than mixed values such as R ∪ {NA}.The possible missingness patterns make the optimization problem difficult; their number grows exponentially with the number of variables.Source: §3.3 · pp. 16–17
  • Decision trees are particularly well suited to the difficult empirical-risk optimization problem created by numerous possible missing-data patterns.Source: §3.3 · p. 17

4 Consistency of imputation procedures

This section establishes theoretical consistency results for prediction with missing covariates, examining conditional multiple imputation and constant single imputation followed by a universally consistent learner under stated conditions.

4.1 Test-time imputation

  • With access to the complete-data Bayes predictor, multiple imputation can produce optimal predictions when covariates are missing at test time under MAR.The result concerns test-time imputation using the predictor f⋆ for complete data.Source: §4.1 · p. 19

4.1.1 Test-time conditional multiple imputation is consistent

  • Under Assumptions 1 and 2, conditional multiple imputation is Bayes optimal for every complete or incomplete input.It draws missing values from their conditional distribution given observed values and evaluates the regression function on completed observations.Source: §4.1.1 · pp. 19–20

4.1.2 Single mean imputation is not consistent

  • Single test-time imputation is not consistent even under MAR; in an example where the learner is trained only on complete cases, unconditional mean imputation is not optimal, while the square-loss minimizer is 1/3.Source: §4.1.2 · pp. 20–21

4.1.3 Conditional mean imputation is consistent if there are deterministic relations

  • Conditional mean imputation can work with deterministic redundancy, but without deterministic links it can fail to recover a nonlinear regression function.Source: §4.1.3 · pp. 21–22

4.1.4 Pathological case: missingness is a covariate

  • When missingness itself carries response information, single and multiple imputation fail unless missingness is added as an input; complete covariate data alone are insufficient.Source: §4.1.4 · pp. 22–23

4.2 Constant imputation at train and test time is consistent

  • Using the same constant imputation in training and testing with a universally consistent learner yields a consistent procedure under the stated regression and MAR conditions.The method replaces missing values in X1 with a fixed constant α in both datasets.Source: §4.2 · pp. 23–24
  • Under Assumptions 3 and 4, single imputation with a universally consistent learner equals the Bayes function almost everywhere.The result supports consistency for prediction with missing values when the imputation procedure is applied to the data.Source: §4.2 · pp. 24, 25, 27
  • Use the same imputation for training and testing: the learner can recognize the imputed value as a missingness signal, while changing it can cause failure.Different train- and test-set imputations can make their imputed data distributions differ.Source: §4.2 · p. 25
  • Theorem 3 also holds with multiple missing variables when the stated conditional missingness-pattern probabilities are continuous in the always-observed variables.The extension covers missingness in X1 through Xj, conditional on variables Xj+1 through Xd that are always observed.Source: §4.2 · p. 25
  • For a universally consistent learner, the chosen constant need not be the mean: any imputation value in the support of X1 yields consistency.The mean is presented as a default, not as a uniquely necessary choice.Source: §4.2 · p. 25
  • The equality is almost everywhere, not pointwise: at the imputed value, the single-imputation prediction can differ from the complete-data Bayes prediction.Imputing outside the true distribution’s range is identified as a way to obtain pointwise equality.Source: §4.2 · pp. 25–26
  • For discrete variables, the result extends by imputing missing entries with an extra “missing” category for each variable.The resulting consistency claim follows from estimating the conditional expectation for that category.Source: §4.2 · p. 26
  • The result also applies to binary classification through a universally consistent plug-in estimate of E[Y | X].Thresholding the estimate at 1/2 yields a universally consistent plug-in classifier.Source: §4.2 · p. 26
  • The guarantee requires universal consistency and does not generally extend to learners consistent only for specific distributions, such as a linear estimator after imputation.The imputed-data submodels need not be linear, so one linear model may not achieve Bayes loss.Source: §4.2 · pp. 26–27

5 Simulations

The simulations compare finite-sample prediction strategies for missing data across missingness mechanisms, learner types, and settings, including approaches that impute values and tree methods that handle missingness directly. They examine how performance and convergence vary by model and setting, with MIA a strong tree option and Gaussian imputation often performing well or better.

5 Simulations

  • The simulations compare imputation-before-learning with procedures that handle missing values directly, using decision trees for the latter comparison.The section motivates this evaluation as a finite-sample assessment beyond the asymptotic guarantee for constant imputation in a specific MAR setting.Source: §5 · pp. 27–28

5.1 Dealing with missing values using decision trees

  • Tree methods either omit missing entries when choosing splits and later route them, or incorporate missingness into split selection.The described routing options include surrogate splits, probabilistic splits, and block propagation; MIA considers assigning missing values to either side or splitting missing from observed values.Source: §5.1 · pp. 28–29
  • MIA and surrogate splits are the two best strategies theoretically, with their relative performance depending on covariate dependence.Block propagation can be viewed as a greedy way of successively optimizing choices among MIA options.Source: §5.1 · pp. 30–31

5.2 Simulation settings

  • The simulations use four regression models and consider MCAR, censoring MNAR, and predictive-missingness patterns.The stated noise in all four models is centered Gaussian with standard deviation 0.1.Source: §5.2 · pp. 31–32
  • Methods were evaluated by repeatedly drawing training and equally sized testing sets 1,000 times, with performance reported as the percentage of explained variance (test-set R²). Experiment 1 used Model 1 (d = 9).Source: §5.2 · pp. 33–34

5.3 Results comparing strategies for fixed sample sizes

  • Under MCAR, decision-tree methods performed similarly except for underperforming out-of-range imputation, while Gaussian conditional imputation slightly improved prediction.The reported comparison uses 20% missingness, n = 1000, d = 9, and ρ = 0.5.Source: §5.3 · p. 34, Figure 1 · p. 35
  • For more complex missingness, adding masks usually helped imputation strategies, MIA performed well, and mean imputation worked well with forests and boosting but not KNN or SVM.Out-of-range imputation was an exception to the mask benefit, and pairing it with SVM led to sub-optimal performance under every mechanism.Source: Figure 1 · p. 35, §5.3 · pp. 35–36
  • Random forests and gradient boosting predicted significantly more accurately than tree-based models, with conditional imputation offering them less benefit over MIA.The missing-value mask was not important for the more powerful models.Source: Figure 1 · p. 35, §5.3 · p. 35
  • Most Figure 1 differences appeared significant; under MCAR, Gaussian/Gaussian+mask and Mean/Mean+mask were not statistically different for decision trees and random forests at level 0.05.Source: §5.3 · p. 36
  • Adding masks generally increased computation time, except for forests; KNN was quickest and forests and boosting most computationally intensive, while imputation had minimal impact.The timing comparison was for MCAR with 20% missingness, n = 1000, d = 9, and ρ = 0.5.Source: §5.3 · p. 36, Figure 2 · p. 37
  • At fixed sample sizes, MIA was a strong tree-based option across the tested scenarios, while Gaussian imputation with a missingness mask could outperform it under MCAR.With nonlinearities, Gaussian imputation often performed as well as or better than mean imputation or MIA, likely because the supervised model compensated for nonlinearity.Source: §5.3 · p. 38

5.4 Consistency and learning curves

  • Gaussian imputation performed best in linear settings; mean imputation, MIA, and surrogate splits were also consistent for trees and forests, but converged more slowly.Adding missingness indicators changed the curves little in this setting.Source: Figure 4 · p. 39, §5.4 · p. 40
  • For nonlinear associations, Gaussian imputation’s advantage persisted, though it was less pronounced for forests and boosting; in low-noise settings, MIA and mean imputation seemed equivalent.Gaussian imputation also outperformed mean imputation with KNN and SVM.Source: §5.4 · p. 40
  • For boosting, differences between methods vanished as sample size grew, consistent with boosting’s ability to turn weak learners into strong ones, while Gaussian imputation helped at small sample sizes.The study did not compute Bayes loss for the scenario with non-Gaussian features.Source: §5.4 · p. 40
  • Mean imputation is consistent when missingness is MAR and unrelated to the outcome, while tree-based methods—especially MIA—can target E[Y|observed values] and handle informative missingness.The paper’s take-home message presents these as complementary approaches for prediction with missing values.Source: §5.4 · p. 41

6 Discussion and conclusion

The discussion recommends prediction-focused approaches to missingness: conditional multiple imputation under MAR, constant imputation with a powerful nonlinear learner under stated conditions, and MIA for decision trees.

6 Discussion and conclusion

  • For MAR missing values, conditional multiple imputation followed by averaging predictions from the complete-data Bayes predictor yields a Bayes-consistent estimate.The procedure applies the complete-data predictor to conditionally imputed data and averages the resulting predictions.Source: §6 · pp. 41–42
  • Constant imputation is consistent when used with a powerful nonlinear learning model, provided the same imputation model is used at training and test time.The discussion also recommends adding missingness indicators when missingness is related to the prediction target, because imputation alone does not suffice.Source: §6 · p. 42
  • MIA jointly optimizes the split and missing-value handling, and is described as the most versatile tree strategy across different missing-data scenarios.The discussion points to empirical comparisons and theoretical analysis as support for this recommendation.Source: §6 · p. 42
  • The choice of imputation method at training and test time may reduce the samples needed to reach a given prediction performance.Figure 4 is cited in connection with this result.Source: §6 · p. 42
  • These recommendations target minimizing prediction error asymptotically; finite-sample theory and prediction-uncertainty control remain open concerns.The discussion says more work is needed for finite-sample theoretical results and that different practices may be needed to control uncertainty associated with a prediction.Source: §6 · p. 42

Declarations

The declarations report synthetic experiments, no competing interests, funding, acknowledgments, and publication and data statements.

Declarations

  • The authors report no competing interests.Source: Declarations · p. 42
  • The authors acknowledge ANR and DataIA funding and thank colleagues and reviewers for discussions, implementation suggestions, and feedback.Source: Declarations · p. 43
  • All experiments used synthetic data, and the declarations state that ethics approval and consent to participate were not applicable.The statement describes the work as purely mathematical and numerical.Source: Declarations · pp. 42–43

A Proofs of Section 4

The appendix gives proofs for the test-time conditional multiple-imputation and train-and-test mean-imputation consistency results, with the former proof using the MAR assumption.

A Proofs of Section 4

  • Theorem 2’s proof addresses consistency of test-time conditional multiple imputation under the MAR assumption.The proof combines the MAR condition with its preceding relations to obtain the stated result.Source: §A.1 · pp. 49–50
  • Theorem 3’s proof establishes the consistency result for mean imputation at both training and test time by separating cases for E[Y | X′ = x].Source: §A.2 · p. 50
  • For Theorem 2, the proof derives limiting conditional predictions for cases with observed and imputed values, then combines them for mean imputation.The displayed limits distinguish conditioning on M1 = 0 from M1 = 1.Source: §A.2 · pp. 50, 53

B Decision trees: an example of empirical risk minimization with missing data

This section examines decision trees as a way to perform empirical risk minimization with missing data, introducing tree-based approaches and comparing their behavior in theoretical single-split settings. It highlights MIA and includes a surrogate-split example whose criterion is minimized at s = 1/2.

B.1 Tree construction with CART

  • CART recursively partitions the feature space and predicts from labels in each leaf; minimizing squared error targets E[Y | X].With missing values, its split criterion must be adapted.Source: §B.1 · p. 54

B.2 Splitting criterion discarding missing values

  • One approach selects each variable’s split using observed cases only, then routes missing observations using surrogate, probabilistic, or block propagation.Discarding missing observations at every step would drastically reduce the data set and is not viable.Source: §B.2 · pp. 54–55
  • Conditional trees aim to improve split-variable selection, but their criterion can underselect variables with many missing values and does not ensure better prediction.The selection bias arises from multiple-comparison effects and favors variables with fewer missing values.Source: §B.2 · p. 56

B.3 Splitting criterion with missing values: MIA

  • MIA chooses the lowest-error split after trying to send missing values left or right, or to separate missing from observed values.Missing values are treated as a category in the split criterion.Source: §B.3 · p. 57
  • Block propagation greedily makes successive choices between assigning missing values left or right, but those choices are suboptimal.The paper establishes this result in Proposition 1.Source: §B.3 · p. 57
  • By splitting on missingness and using missing data to select splits, MIA suits informative missingness and requires no separate propagation method.Its leaves can group observations by missingness patterns.Source: §B.3 · p. 57

B.4 Theoretical comparison of CART versus MIA

  • Under MCAR, CART’s criterion does not depend on the percentage p of missing values; MIA’s threshold can differ from the observed-only threshold because missing entries influence it.Source: §B.4 · pp. 58–59
  • In the Proposition 2 model, MIA splits on the first variable when p≤η and on the second when p≥η.Here η measures the independence between X1 and X2.Source: §B.4 · p. 59, §B.7 · p. 65
  • MIA has lower risk than block propagation and probabilistic splitting, while surrogate splitting is better under strong covariate dependence and worse under weak dependence.The comparison of surrogate splitting with MIA therefore depends on the dependence structure between covariates.Source: §B.4 · pp. 59–60, Figure 6 · p. 60

Surrogate split

  • For both p ≤ 1/2 and p ≥ 1/2, the splitting criterion reaches its minimum at s = 1/2.The derivation evaluates the criterion over s ∈ [0, 1/2].Source: §B.7 · p. 66
  • The surrogate-estimate risk is reported as 1/48 + 6η/48.The risk expression is given across the result passages.Source: §B.7 · pp. 66–67

C Miscellaneous

The miscellaneous appendix examines how missingness affects tree variable selection and illustrates maximum-likelihood estimation with the EM algorithm.

C.1 Variable selection properties of the tree methods with missing values

  • When MCAR values affect both variables, CART and conditional trees give similar variable-selection results; when only X1 is missing, CART tends to underselect it.The stump experiments used 500 Monte Carlo repetitions and varied sample size and missingness percentage.Source: §C.1 · p. 67
  • With missingness only on X1, CART tends to underselect X1, while conditional trees select it more often in one 50-observation, 75%-missing example.That example contrasts selection of non-informative X2 by CART with more frequent selection of X1 by conditional trees.Source: §C.1 · p. 67

C.2 Example of EM algorithm

  • EM alternates conditional expectations for unavailable complete-data likelihood elements with maximization, repeating the E- and M-steps until convergence.For missing X2 values, the procedure replaces unavailable sufficient statistics with conditional expectations based on observed data and current parameters.Source: §C.2 · pp. 69–70
  • In the illustrated Gaussian setting, EM imputes sufficient statistics rather than data, and estimated parameters can be used to fit linear regression.The example has an explicit maximum-likelihood estimator, while EM can be used when such an expression is unavailable.Source: §C.2 · pp. 68–70

D Additional experiments

Supplementary figures compare normalized explained variance and paired-test p-values across missingness mechanisms, correlation strengths, and missing-value rates.

D.1 Varying the correlation strength and the missing rate

Loading 1902.06931v5…