Interpretable Generalized Additive Models for Datasets with Missing Values

Authors: hayden  mctavish
jon  donnelly
margo  seltzer
cynthia  rudin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:06:25

Abstract: Many important datasets contain samples that are missing one or more feature values. Maintaining the interpretability of machine learning models in the presence of such missing data is challenging. Singly or multiply imputing missing values complicates the model’s mapping from features to labels. On the other hand, reasoning on indicator variables that represent missingness introduces a potentially large number of additional terms, sacrificing sparsity. We solve these problems with M-GAM, a sparse, generalized, additive modeling approach that incorporates missingness indicators and their interaction terms while maintaining sparsity through $\ell_0$ regularization. We show that M-GAM provides similar or superior accuracy to prior methods while significantly improving sparsity relative to either imputation or naïve inclusion of indicator variables.

Main paper: 
 introduction: 
 Interpretability is essential for a wide range of machine learning applications Rudin et al. (2022) . Missing data pose a challenge to interpretability, because many simple models (e.g., linear models) are not well-defined when data are missing. This raises the question: how can interpretability be maintained for datasets with missing values?We introduce an interpretable model class, M-GAM, that extends Generalized Additive Models (GAMs) to handle missing data. GAMs take the form of a linear combination of univariate component functions, with one function corresponding to each feature; this univariate nature is the core reason for their interpretability (Rudin et al., 2022) . We introduce two sets of boolean variables for each feature. The first consists of missingness indicators that identify which features have missing values. The second consists of missingness adjustment terms that adjust the shape curves for other features for each missing features in a sample. This maintains our ability to view a GAM as a sum of univariate shape functions even when modeling interactions with missing data. As such, an M-GAM is much simpler to interpret than a GAM built on imputed data, since it avoids creating multivariate features as happens when imputing features from multiple others. This is illustrated in Figure 1 .(All Variables Present)Impute Then Predict (bottom row) behave when a feature is missing. Top: When no data are missing, the overall output logit for both models is the sum of three univariate shape functions. Middle: When X3 is missing, it is imputed as X3 = X1+2X2, producing a 3D shape function that is difficult to understand. Bottom: M-GAM uses simple adjustments to existing univariate shape curves when X3 is missing (using the green curves instead of the light blue ones), making its reasoning process simple to follow. If the data were more than 3 dimensional, we would not be able to visualize the model with imputation, but M-GAM would still be easily visualized.M-GAMs explicitly encourage sparsity. This reduces overfitting, which has been identified as a concern in prior work using missingness indicators (Van Ness et al., 2023) , since realistic data may produce an overwhelming number of missingness indicators. Unlike prior methods that leverage missingness indicators, we use ℓ 0 regularization (Liu et al., 2022; Dedieu et al., 2021; Hazimeh & Mazumder, 2020; Hazimeh et al., 2023) , which directly optimizes for sparser, more interpretable models. Our ability to create sparse models allows us to include not only simple missingness indicators but also combinations of missingness indicator variables with M-GAM's missingness adjustment terms, without overfitting. Figure 2 illustrates an M-GAM fit on real data.With this modeling framework, we make the following contributions: (1) We introduce M-GAM, a form of sparse generalized additive model that incorporates missingness directly into its reasoning.(2) We show that M-GAM provides substantial performance benefits relative to impute-then-predict models when synthetic missing-at-random (MAR) missingness is added to real datasets, while maintaining performance in real world settings with only naturally occurring missingness. (3) We show that M-GAM substantially reduces runtime relative to impute-then-predict methods built on multiple imputation while producing sparse, interpretable models.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The primary claims made in the abstract and introduction are that our method improves upon sparsity without sacrificing accuracy. We also claim that we improve performance in synthetic cases, and do not substantially harm runtime. All of these claims are directly supported by an experimental section.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 Missing data is a well studied problem in statistics. Traditionally, mechanisms by which data can be missing are organized into three categories: missing completely at random (MCAR), where missingness is independent of the value of all covariates; missing at random (MAR), where missingness in a variable X 1 is conditionally independent of the value of X 1 given all other variables; and missing not at random (MNAR) , where missingness may depend on any variable (Little & Rubin, 2019) .For supervised learning, there are two common approaches to dealing with missing data: imputethen-predict, in which a standard machine learning model is fit on top of imputed data and used for prediction, and incorporating missing data handling directly in the predictive model. A broad body of work studies imputation, particularly in the MAR setting -for a more thorough review, see Shadbahr et al. (2023) . Imputation methods can broadly be sorted into single imputation methods (see Van Buuren, 2018 , for a review of such methods), where each missing value is imputed once, and multiple imputation (Rubin, 1988; Van Buuren & Oudshoorn, 1999 2018) with missingness incorporated. This model handles missingness interpretably by explicitly providing alternative shape functions when a variable is missing. For example, in this model the shape function for variable 2 is adjusted when variable 3 is missing, and the shape function for variable 3 is removed. This model achieves comparable performance to convoluted black box approaches (such as random forests and/or MICE), but provides global interpretability (the entire model can easily be inspected) and local interpretability (the shape functions applied for a given sample can be easily visualized). An expanded version of this figure with variable names can be found in Appendix Figure 16 . Shape functions in the right section are shared across all missing variable combinations. The type of missingness is indicated in parentheses next to the missing variable. Section F visualizes additional M-GAMs. Graham, 2002; Stekhoven & Bühlmann, 2012; Mattei & Frellsen, 2019) , where many alternative imputations are provided for each missing value. Multiple imputation is convenient because it integrates uncertainty into its imputations by providing a range of alternatives (Van Buuren, 2018) .Recent approaches directly incorporate missing data in the predictive model. Le Morvan et al. (2020) showed that, even when the target of prediction is a linear function, in the presence of missing data, the optimal model need not be linear in the original features. Rather, their optimal model was linear in the observed data and interactions between indicators for missing data and the observed data. Van Ness et al. (2023) showed that when missingness contains information about an outcome, linear models that directly include missingness indicators outperform models excluding this information. This inclusion of missingness indicators is especially recommended in the practical setting of predictive modeling, rather than the setting of statistical inference where MCAR, MAR and MNAR concepts are more commonly used (Sperrin et al., 2020) .There are also a wide variety of ad-hoc methods for handling missing data in tree-based models (Kapelner & Bleich, 2015; Twala et al., 2008; Beaulac & Rosenthal, 2020; Therneau et al., 1997) and boosting models (Wang & Feng, 2010; Chen & Guestrin, 2016 ) that involve prediction without explicit imputation. Beaulac & Rosenthal (2020) learn decision trees which avoid splitting on missing data when missingness follows a deterministic structure based on other known features. This sidesteps any need to query features when data is missing, but does not generalize to settings with less structured missingness. More generally, tree-based models can learn a branch direction for each split to use when the queried feature is unknown. This effectively imputes the response to the query, but keeps the model itself simple. This is the method used in XGBoost (Chen & Guestrin, 2016 ) and SKLearn's decision tree classifier (Pedregosa et al., 2011) . Twala et al. (2008) and Kapelner & Bleich (2015) additionally incorporate the option to split on missingness itself, effectively encoding missingness as a value. Ding & Simonoff (2010) provides empirical support for incorporating this option to treat missingness as a value. We compare to XGBoost and SKLearn in our experimental section, finding that M-GAM better balances interpretability and performance, even when we allow missingness indicator splits like in Twala et al. (2008) ; Kapelner & Bleich (2015) ; Ding & Simonoff (2010) ; Wang & Feng (2010) . Most similarly to our own approach, Therneau et al. (1997) and Breiman (2017) discuss an alternative approach of surrogate splits: when a feature that is split on is missing, a set of other splits is used in place of the missing feature to evaluate the split. This practice of adjusting which features are used when one feature is missing bears some similarities to our use of missingness interaction splits that adjust the shape functions for some features when other features are missing, though these surrogate splits do not optimize for sparsity like M-GAM, and underperform more standard multiple imputation approaches Valdiviezo & Van Aelst (2015) ; Feelders (1999) . Further work explores the idea of developing distinct models for use under different cases of missing features (Fletcher Mercaldo & Blume, 2020; Stempfle et al., 2023) .It is critical to note that, for a dataset with d features, adding indicators for missing data results in 2d features, and adding first order interactions between features and missingness results in d(d -1) + 2d features. As such, without careful regularization, these models that explicitly handle missingness are complex and uninterpretable. This poses a challenge for their application in high stakes domains such as justice and medicine, where there have been calls to enshrine interpretability as a requirement for the use of machine learning methods (US Food and Drug Administration, 2021; European Commision, 2021) . In contrast, M-GAM provides sparse, transparent models that handle missingness indicators and interactions by extending sparse generalized additive models (Liu et al., 2022) . M-GAM provides an expressive model class for handling missingness while controlling the exploding number of missingness interaction terms through ℓ 0 regularization.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss that the ℓ 0 penalty we impose does not perfectly impose the prior we would like, and that missing data methods as a whole are vulnerable to distribution shift.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
methodology: 
 We denote a dataset of n samples by D = (X, y) = {(x i , y i )} n i=1 , where x i ∈ (R ∪ {NA}) d is a d-dimensional vector of features, NA denotes a missing entry, and y i ∈ {0, 1} is our target label. We use x i,j to denote the j-th feature of the i-th sample. We use bold capital letters (X) to denote matrices, bold lowercase letters to denote vectors (x i ), capital letters to denote random variables (X), and lowercase letters to represent scalars (x i,j ). ε denotes noise; any other Greek characters denote model parameters. We encode all binary comparisons to the value NA as 0. That is, we follow the convention that 1 [NA≤a] = 0 for any value a ∈ R, where 1 [•] denotes the indicator function.Note that, in practice, data are often missing for distinct yet identifiable reasons; for example, a measurement for one sample may be missing because it was never taken, while another may be missing because a researcher spilled coffee on the notes containing the data. As such, we explicitly consider distinct reasons for missing data. For a dataset with c ∈ N potential reasons for data to be missing, define the mapping mcat : R ∪ {NA} → {0, 1, . . . , c} to map from an entry of X to a natural number indicating the reason that entry is missing (0 if the entry is not missing).With notation established, we begin with a motivational proposition. Proposition 3.1 states that even if we can perfectly impute missing values, we may find greater predictive power by using missingness itself as a feature rather than by imputing missing values.Proposition 3.1. Let I : (R ∪ NA) d → R d be an oracle imputation function that replaces all missing values in a vector with the correct non-missing entry. For a random variableX ∈ R d , let f 1 (X) := 1 [E[Y |I(X)]>0.5] be the Bayes' optimal model using perfectly imputed data and f 2 (X) := 1 [E[Y |X]>0.5] be the Bayes optimal model using missingness as a value. There exist data generating processes for X and Y whereP (Y = f 1 (X)) < P (Y = f 2 (X)).Section A of the appendix provides a proof by construction for Proposition 3.1. The key insight behind Proposition 3.1 is that, when missingness is dependent on the label Y, missingness itself can be a powerful predictor of the label (this setting is called informative missingness in Van Ness et al., 2023) . In particular, we can gain information about our label that is not available in other covariates (e.g., information from ε 1 ).Proposition 3.1 may appear to conflict with Theorem 3.1 of Le Morvan et al. (2021) , which states that a Bayes optimal model may be produced using impute-then-predict with almost any imputation model. This theorem hinges on the idea that, for most imputations, it is still possible to distinguish imputed data entries from non-missing entries. This is not the case for perfect imputation, which yields Corollary 3.2. Corollary 3.2. Let R(f, X, y) denote the risk of a model f for data X, y, and R * the optimal risk. Let I : (R ∪ NA) d → R d denote the oracle imputation function of Proposition 3.1. Under perfect imputation, it is possible for there to be no Bayes optimal model built on imputed data. That is,∃(X, y) [∄f : R(f • I, X, y) = R * ] .Corollary 3.2 states that perfectly imputing missing data can reduce the best possible performance of a predictive model. This has substantial implications for how imputation is understood for prediction: if perfect imputation is achieved, then impute-then-predict models sacrifice expressiveness. If imputation is optimized to maintain the downstream performance of impute-then-predict models, the imputed data loses some of its meaning since it is no longer our "best guess" of the missing data's value, as we need to deliberately avoid perfect imputation to guarantee that we maintain performance.Motivated by Proposition 3.1 and Corollary 3.2, we are interested in constructing predictive models that explicitly use missingness as a value in their prediction rather than imputing first. More generally, we may also consider using the indicator for each type of missing data directly in a prediction. Generalized additive models (GAMs) provide a natural choice for such a model. A GAM g : R d → R consists of a bias term β 0 ∈ R and d shape functions f 1 , . . . , f d : R → R parameterized by vectors β 1 , . . . , β d . Given a sample x i , a GAM forms a prediction as:g(x i ; β) = β 0 + d j=1 f j (x i,j ; β j ).(1)In practice, it is common for each shape function to be a linear combination of different thresholds on its input variable, i.e., f j (x i,j ;β j ) = len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ], where len(t j ) ∈ N is the number of thresholds applied to variable j, each t j,k ∈ R is a threshold value, and each β j,k ∈ R is a learned weight.These functions provide a convenient framework for considering missing values. In particular, we can form a new shape function h j (x i,j ; β j , β missing j ) that explicitly handles missing data by introducing additional "missingness indicator" terms, such that our shape functions take the formh j (x i,j ; β j , β miss j ) = f j (x i,j ; β j ) + c m=1 β miss j,m 1 [mcat(xi,j )=m] ,where β miss j ∈ R c is an additional vector of parameters. Recall that there are c distinct reasons for missingness, with mcat(x i,j ) = 0 if x i,j is not missing and mcat(x i,j ) = m if x i,j is missing for the m-th reason.We may further extend this augmentation to include interaction terms between missingness indicators and standard threshold functions. The "missingness interaction" function between feature j and feature j ′ takes the formh j,j ′ (x i,j , x i,j ′ ; α j,j ′ ) = c m=1 len(tj ) k=1 α j,j ′ ,k,m 1 [mcat(xi,j )=m and x i,j ′ ≤t j ′ ,k ] ,where each α j,j ′ ,k,m ∈ R is a learned weight. We thus define a missingness-GAM (M-GAM) g miss as follows: Definition 3.3. Given parameters α, β miss , and β, an M-GAM is defined asEQUATIONwhereh j,j ′ (x i,j , x i,j ′ ; α j,j ′ ) = c m=1 len(tj ) k=1 α j,j ′ ,k,m 1 [mcat(xi,j )=m and x i,j ′ ≤t j ′ ,k ] and h j (x i,j ; β j , β miss j ) = f j (x i,j ; β j ) + c m=1 β miss j,m 1 [mcat(xi,j )=m] .These augmentation terms are quite powerful. Theorem 3.4 shows that, for any impute-then-predict approach using an affine imputer and a GAM predictor, we can construct an M-GAM that recovers the expected classification score over imputations. Theorem 3.4. Consider any GAM g : R d → R, parameterized by β, with shape functions defined as linear combinations over boolean features (either thresholds f j (x i,j ; β j ) = len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ] or a feature that was originally boolean). Suppose some observations are missing boolean feature b, and that this feature is imputed such that the modeled probability of x i,b being true, P(x i,b = 1|x i,-b ) (where x i,-b refers to all covariates except b) is an affine function h :x i,-b → [0, 1]. For any parameterization β of a GAM g, let E[g(x i ; β)] := P(x i,b = 1|x i,-b )g(x (b+) i ; β) + P(x i,b = 0|x i,-b )g(x (b-) i ; β), where x (b+) i denotes x i with x i,b = 1 and x (b-) i denotes x i with x i,b = 0.Then, there exists a model in the model class M-GAM (which does not use imputations), that recovers this score E[g(x i ; β)] for all i.More broadly, Theorem 3.4 suggests that M-GAM is able to express scores comparable to those of any impute-then-predict GAM, if the imputation probabilities can be approximated by an additive model. One advantage is that M-GAM can be optimized directly for classification performance -rather than first optimizing an imputation step to recover missing values, and then optimizing a model on the imputed data. Together, Proposition 3.1 and Theorem 3.4 show that M-GAM is comparable to impute-then-predict in a broad range of settings and that M-GAM is strictly better than impute-then-predict in some settings. Appendix C contains the proof for Theorem 3.4.Building a GAM with missingness indicators and interaction terms provides superior expressive power but causes an explosion of the number of covariates the model must consider. The GAM in Equation (1) consists of d j len(t j ) + 1 coefficients, while the M-GAM in Definition (3.3) consists of cd j j ′ ̸ =j len(t j ′ ) + d j (len(t j )) + cd + 1 coefficients (or, d d j (len(t j )) + d + 1 when c = 1).This increases the risk of overfitting and may lead to complex, uninterpretable models. The same problem arises when adding similar interaction terms to a linear model, as diagnosed by Van Ness et al. (2023) , who propose a hypothesis testing style framework for variable selection. Notably, this framework does not explicitly encourage sparsity -it only discourages overfitting.Rather than applying a pre-processing step for variable selection, we use ℓ 0 regularization, which we can optimize directly alongside accuracy. This encourages the model coefficients to be 0, resulting in sparse models despite the potentially large number of input features. We optimize classification performance using the exponential loss, as it yields faster convergence rates than logistic loss during optimization (Liu et al., 2022) . Thus, our goal is to solve the following optimization problem:EQUATIONwhere λ 0 is a hyperparameter that determines the strength of the ℓ 0 regularization.To simplify (3) so it can be solved directly, we construct a new set of features X ∈ {0, 1} c d j ( j ′ ̸ =j len(t j ′ ))+ d j (len(tj ))+cd+1 consisting of the indicator for each threshold, missing value, and interaction term for each feature in the original dataset. For a large coefficient vector γ ∈ R c d j ( j ′ ̸ =j len(t j ′ ))+ d j (len(tj ))+cd+1 and bias coefficient γ 0 ∈ R, our optimization problem becomes:EQUATIONwhich is solved using the optimization framework of Liu et al. (2022) . This allows us to quickly produce sparse M-GAMs, overcoming the large number of input values.some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
experiments: 
 We now evaluate the performance, runtime, and sparsity of M-GAM in comparison to other methods.To evaluate M-GAM in a realistic setting, we require datasets with some missing entries. We primarily consider four datasets: the Explainable Machine Learning Challenge dataset (FICO et al., 2018) (referred to as FICO), a breast cancer dataset introduced by Razavi et al. ( 2018) (referred to as Breast Cancer), the MIMIC-III critical care dataset (Johnson et al., 2016) (referred to as MIMIC), and a dataset concerning the prediction of pharyngitis introduced by Miyagi (2023) (referred to as Pharyngitis). FICO contains 10,459 individuals, measuring 23 predictor variables used to predict whether each individual will repay a line of credit within 2 years. FICO contains three distinct encodings for missingness: -7, indicating no information of a given type is available, -8, indicating there was no usable information, and -9, indicating that a credit bureau report was not investigated or not found. Breast Cancer measures 27 features for 1,756 patients, MIMIC measures 49 features for 30,238 patients, and Pharyngitis measures 19 features for 676 patients. We use AUC, rather than accuracy, when evaluating model performance for Breast Cancer and MIMIC because these two datasets are heavily imbalanced. Breast Cancer, MIMIC, and Pharyngitis contain only one missingness encoding. Two additional datasets are studied in Section E of the appendix.Each dataset contains missing entries. Because these are real datasets, we do not know the exact mechanism(s) (i.e., MCAR, MAR, or MNAR) by which data are missing. These datasets allow us to evaluate M-GAM on data with (Section 4.1) and without (Section 4.4) added MAR missingness.We then study the interpretability/accuracy tradeoff for M-GAM using sparsity versus accuracy plots (Section 4.2) and evaluate the runtime of M-GAM (Section 4.3). We use multivariate imputation by chained equations (MICE) (Van Buuren & Oudshoorn, 1999) , MIWAE (Mattei & Frellsen, 2019) , and MissForest (Stekhoven & Bühlmann, 2012) as multiple imputation baselines.We compare M-GAM to a variety of standard machine learning models used in an impute-then-predict framework. We further compare to standard machine learning models used with both the missingness augmentation described by Van Ness et al. ( 2023) and imputation. Section D.3 of the appendix contains full experimental details.To demonstrate the added expressive capability of our model relative to impute-then-predict models, we created versions of each dataset with added synthetic missingness. Missingness is added to an arbitrary column of the data according to an MAR mechanism, where missingness is dependent on the outcome Y and one other randomly chosen predictor variable. We encode this added missingness as a new value distinct from the value(s) used to indicate missingness in the original dataset. A conditional probability table for this synthetic missingness is provided in Appendix Section D.1.This adjustment falls under the MAR setting where imputation is often suggested. Nevertheless, as shown in Figure 3 , M-GAM with interactions provides much greater accuracy than imputation, because the missingness depends on the outcome. The gain in performance due to considering interaction terms grows larger with increasing MAR missingness (from left to right).Note that missingness depending on the outcome of interest is realistic. For example, individuals who are unlikely to have a particular disease are unlikely to receive medical tests related to that disease. One theory about why polls were wrong before the 2016 US presidential election was that non-response bias was associated with less education and distrust in the media, both predictors of votes for Donald Trump (Kurtzleben, 2016) .The most important benefit of the missingness handling in M-GAM is that it enables simple, sparse models. As such, we show the tradeoff between complexity and performance for M-GAM.Figure 4 demonstrates the sparsity-accuracy trade-off for M-GAM relative to a GAM fit using Scikit Learn's logistic regression package (Pedregosa et al., 2011) over binarized features, trained on data from 10 imputations using a multiple imputation method. We also contrast two different levels of missing variable parameterization: the full set of indicators and interactions versus using just indicators.We quantify interpretability using the number of nonzero coefficients selected by M-GAM, since a large number of non-zero coefficients leads to a dense, complicated mapping from the input data to a prediction. Meanwhile, running impute-then-predict is not interpretable: the method and 50% (right column) of entries in FICO (top row) and Breast Cancer (bottom row). We compare to several alternatives for GAMs with missing data: ensembling 10 GAMs fit on multiple imputation (for MIWAE, MICE, and MissForest), 0-value imputation ("GAM"), mean-value imputation ("GAM w/ MVI"), and selective addition of missingness indicators ("SMIM"). The number of non-zero coefficients for multiple imputation cannot be evaluated because the models depend on both the GAM coefficients and the underlying imputation mechanisms, resulting in high dimensional shape functions as in Figure 1 . Error bars report standard error over 10 train-test splits.requires ensembling many different GAMs, and the imputations themselves introduce complicated relationships between the raw data and the classifications, similar to what was illustrated in Figure 1 . We show that with fewer than 40 total coefficients (including all step functions for all variables), M-GAM can achieve accuracy comparable to that of GAMs with multiple imputation. On FICO, M-GAM -using just 20 non-zero coefficients -achieves superior accuracy to a variety of dense, complicated alternatives.We next turn to a runtime comparison between the impute-then-predict framework and M-GAM. For impute-then-predict models, we first imputed 10 datasets and recorded the time required to do so. We then fit a predictive model on each imputed training dataset and recorded the total time required. We recorded the time required to fit an M-GAM with missingness indicators and an M-GAM with missingness interactions for comparison. This was repeated for each of ten distinct train-test splits of the original dataset.Figure 5 shows the runtime of our approach relative to each impute-then-predict baseline, as well as decision trees and random forests without imputation. M-GAM consistently produces models at least an order of magnitude more quickly than impute-then-predict with any non-trivial imputation. While decision trees without imputation tend to be produced faster than M-GAM, they tend to have lower accuracy than M-GAM as discussed in the next section. We repeat this experiment for four distinct subsamples of each dataset (1/4, 1/2, 3/4, and all of the data) to study how each method scales in the number of samples in Appendix E.3. For each imputation method, we report the total time required to impute missing data and fit the best performing impute-then-predict classifier for that dataset and imputation method. M-GAM (Ind) is an M-GAM with indicators and M-GAM (Int) is an M-GAM with indicators and interaction terms. Error bars report standard error of total runtime over 10 train-test splits.While M-GAM outperforms imputation on semi-synthetic data, there is a risk that this comes at the cost of performance on real data. To evaluate whether this is the case, we used several multiple imputation methods to impute 10 distinct datasets for each setting, then fit a variety of predictive models on these datasets. We used cross validation to select hyperparameters separately for each imputed training dataset and ensembled the resulting 10 models for each model class to produce a single predictive model for each model class. We repeated this procedure for ten distinct train-test splits for each dataset considered.Figure 6 shows the test accuracy of each model. We find that, on real datasets, no alternative method substantially outperforms M-GAM. This suggests that M-GAM does not harm predictive performance on real datasets, while providing substantial benefits in interpretability (Section 4.2) and superior power under informative missingness (Section 4.1).Figure 6 : Box-and-whiskers plots comparing test performance of baseline models to M-GAM on four datasets over ten train-test splits. All methods except M-GAMs, "DecisionTree No Imputation", and "RandomForest No Imputation" impute ten datasets using MICE then ensemble the models fit on each dataset. 
conclusion: 
 We introduced M-GAM, a framework for producing accurate, sparse GAMs in the presence of missing data. We demonstrated that M-GAM achieves comparable accuracy to impute-then-predict on real datasets and superior accuracy under informative synthetic missingness. M-GAM produces models substantially more quickly than impute-then-predict models with multiple imputation, and provides simple, transparent reasoning on missing data.While the ℓ 0 penalty in M-GAM encourages sparsity, it is limited in that the ℓ 0 regularization is applied uniformly across all coefficients. Consider the case when we are adding interaction terms to handle missingness. We might encourage the model to rely on features it is already using to predict y, rather than using new features. It may be more effective regularization -and more interpretable -to have a reduced ℓ 0 penalty for such cases. Future work should investigate applying distinct levels of regularization to observed variables, missingness indicators, and missingness interactions when a variable is already included in the model.An important caveat to models that reason on missing features is that missingness can be especially vulnerable to distribution shift, particularly in a medical domain (Sperrin et al., 2020; Groenwold, 2020) . The interpretability enabled by M-GAM is crucial in allowing models to be closely monitored and adjusted in the presence of potential distribution shift. Future work could more thoroughly investigate potential distribution shift and ways to adjust a model which reasons on missing data.On the whole, M-GAM quickly produces accurate, interpretable models, providing a new degree of transparency to predictions in the presence of missing data. The code used for this work is available at https://github.com/jdonnelly36/M-GAM.Societal Impacts. M-GAM offers an interpretable way to deploy machine learning in high stakes domains like medicine, even when data is missing. Modeling decisions for missing data risk introducing or perpetuating unfairness Jeanselme et al. (2022) . We view interpretability as a key tool for addressing this. X ∈ R d , let f 1 (X) := 1 [E[Y |I(X)]>0.5] be the Bayes' optimal model using perfectly imputed data andf 2 (X) := 1 [E[Y |X]>0.5] be the Bayes' optimal model using missingness as a value. There exist data generating processes for X and Y whereP (Y = f 1 (X)) < P (Y = f 2 (X)).Proof. We prove Proposition 3.1 by construction.Let X 1 , X 2 ∼ Bernoulli(p = 0.5) and Y := |X 1 X 2 -ϵ 1 | where ϵ 1 ∼ Bernoulli(p = k 1 ) is unobserved noise. Let M denote missingness in X 1 , where M := |Y -ϵ 2 | with ϵ 2 ∼ Bernoulli(p = k 2 ) being unobserved noise. Let k 2 < k 1 < 0.5.Consider two oracle models f 1 and f 2 , defined as:f 1 (X 1 , X 2 ) := 1 [E[Y |I(X)]≥0.5] = 1 [E[Y |X1,X2]≥0.5] f 2 (M, X 2 ) := 1 [E[Y |X]≥0.5] = 1 [E[Y |M,X2]≥0.5] .Intuitively, f 1 perfectly imputes X 1 when X 1 is missing, then predicts Y using X 1 and X 2 , while f 2 predicts Y using M and X 2 .We first evaluate the expected accuracy of the imputation model, i.e., P(f 1 (X 1 , X 2 ) = Y ). Using the law of total probability, we have:P(f 1 (X 1 , X 2 ) = Y ) = x1,x2 P(x 1 , x 2 )P(f 1 (x 1 , x 2 ) = Y |x 1 , x 2 ) = x1,x2 P(x 1 )P(x 2 )P(f 1 (x 1 , x 2 ) = Y |x 1 , x 2 ) Since X 1 ⊥ X 2 = 0.25 x1,x2 P(f 1 (x 1 , x 2 ) = Y |x 1 , x 2 )Noting that, whenX 1 = X 2 = 1, we have Y = |1 -ϵ 1 |, so P(Y = 1|X 1 = 1, X 2 = 1) = P(ϵ 1 = 0) = 1 -k 1 . When at least one of X 1 and X 2 is 0, we have Y = |0 -ϵ 1 |, so P(Y = 1|X 1 X 2 = 0) = P(ϵ 1 = 1) = k 1 .Since f 1 simply evaluates whether the expectation of Y given X 1 and X 2 is greater than 0.5, if k 1 < 0.5, we have f 1 (1, 1) = 1 and f 1 (0, 1) = f 1 (1, 0) = f 1 (0, 0) = 0. Thus, the expected accuracy is:P(f 1 (X 1 , X 2 ) = Y ) = 0.25 x1,x2 P(f 1 (x 1 , x 2 ) = Y |x 1 , x 2 ) = 0.25 x1,x2 P(ϵ 1 = 0) = P(ϵ 1 = 0) = 1 -k 1 Similarly, P(f 2 (m, x 2 ) = Y ) = m,x2 P(m, x 2 )P(f 2 (m, x 2 ) = Y |m, x 2 ) = m,x2 P(x)P(m|x 2 )P(f 2 (m, x 2 ) = Y |m, x 2 ) = 0.5 P(m = 1|x 2 = 1)P(f 2 (m, x 2 ) = Y |m, x 2 ) + P(m = 1|x 2 = 0)P(f 2 (m, x 2 ) = Y |m, x 2 ) + P(m = 0|x = 1)P(f 2 (m, x 2 ) = Y |m, x 2 ) + P(m = 0|x 2 = 0)P(f 2 (m, x 2 ) = Y |m, x 2 )We can compute each term in the conditional probability table P (M |X 2 ) as follow:P(m = 0|x 2 = 0) = y P(m = 0|x 2 = 0, y)P(y|x 2 = 0) = (1 -k 2 )(1 -k 1 ) + k 2 k 1 P(m = 1|x 2 = 0) = y P(m = 1|x 2 = 0, y)P(y|x 2 = 0) = k 2 (1 -k 1 ) + (1 -k 2 )k 1 P(m = 0|x 2 = 1) = y P(m = 0|x 2 = 1, y)P(y|x 2 = 1) = k 2 (0.5k 1 + 0.5(1 -k1)) + (1 -k 2 )(0.5(1 -k 1 ) + 0.5k1) = 0.5 P(m = 1|x 2 = 1) = y P(m = 1|x 2 = 1, y)P(y|x 2 = 1) = (1 -k 2 )(0.5k 1 + 0.5(1 -k 1 )) + k 2 (0.5(1 -k 1 ) + 0.5k 1 ) = 0.5Plugging these values in, we haveP(f 2 (M, X 2 ) = Y ) = 0.5 (1 -k 1 -k 2 + 2k 1 k 2 )P(f 2 (m, x 2 ) = Y |m = 0, x 2 = 0) + (k 2 + k 1 -2k 1 k 2 )P(f 2 (m, x 2 ) = Y |m = 1, x 2 = 0) + 0.5P(f 2 (m, x 2 ) = Y |m = 0, x 2 = 1) + 0.5P(f 2 (m, x 2 ) = Y |m = 1, x 2 = 1) ≥ 0.5 (1 -k 1 -k 2 + 2k 1 k 2 )P(f 2 (m, x 2 ) = Y |m = 0) + (k 2 + k 1 -2k 1 k 2 )P(f 2 (m, x 2 ) = Y |m = 1) + 0.5P(f 2 (m, x 2 ) = Y |m = 0) + 0.5P(f 2 (m, x 2 ) = Y |m = 1) = 0.5(1 -k 1 -k 2 + 2k 1 k 2 + k 2 + k 1 -2k 1 k 2 + 0.5 + 0.5)(1 -k 2 ) = 1-k 2 Thus, we have P(f 1 (X 1 , X 2 ) = Y ) = 1 -k 1 and P(f 2 (M, X 2 ) = Y ) ≥ 1 -k 2 . Since k 2 < k 1 , we have k 2 < k 1 1 -k 2 > 1 -k 1 P(f 2 (M, X 2 ) = Y ) > P(f 1 (X 1 , X 2 ) = Y ),as required, where the last step follows because P(f 1 (X 1 , X 2 ) = Y ) ≥ 1 -k 2 .Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] All datasets used are openly accessible (although MIMIC-III requires an application process) and code will be released. We also thoroughly describe each experimental setup in the appendix.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]The procedure and random seed used to split data, all hyperparameters, selection methods, and implementation details are provided in the code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] All experimental figures include uncertainty quantification through error bars.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. The appendix provides details around all computational hardware used. Timing experiments are provided throughout the paper.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]We have reviewed and are in compliance with the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] We discuss the broader impacts of this work in the conclusion.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] This work poses no substantial risks for misuse, beyond those associated with any predictive model. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] The license under which each asset is used is given in the appendix, and we comply with the license for each asset. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes]Complete code associated with our framework and experiments will be released.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Neither crowdsourced research nor research with human subjects was conducted.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] No such research was involved in this work.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: While the above offers a proof of Proposition 3.1, one might wonder whether the proposition holds outside of the case we constructed. In the previous proof, we aimed for a case that resulted in an easy to follow proof. Here, we prove Proposition 3.1 by a second construction, to show that imputation can be worse than missingness-as-a-value even if there is more noise in the informative missingness than in the data itself, and even when missingness is relatively rare.Proof. Consider a case similar to that used for the proof in proposition 3.1, where we add an additional variable X 3 and have the noise for the missingness be higher than any other noise.EQUATIONWe also adjust the probabilities for X 1 and X 2 being true so that this is a balanced classification problem:X 1 , X 2 ∼ Bern( 1 √ 2 ), so X 1 X 2 ∼ Bern( 1 2), Note that we now also have missingness at well under 50% of the data (missingness happens a quarter of the time).The bayes optimal model with perfect imputation of X 1 , and no access to M , is still just to predict in accordance with X 1 X 2 for P(X1 X 2 = Y ) = 11 12 . When X 1 X 2 = X 3 , all information available suggests X 1 X 2 is correct. When X 1 X 2 ̸ = X 3 , we still have the bayes optimal prediction aligning with X 1 X 2 : P(Y = 1|X 1 X 2 = 1, X 3 = 0) = 11 21 > 0.5 and P(Y = 0|X 1 X 2 = 0, X 3 = 1) = 11 21 > 0.5.If we instead only have access to X 1 when it is not missing, but we also know when X 1 is missing (i.e. we know M ), then the following approach will perform better than the above model:Y = X 3 , if M = 1 X 1 X 2 X 3 , if M = 0When M = 1, we make additional errors relative to the previous approach at rateP(M = 1)(P((X 3 ) ̸ = Y ) -P((X 1 X 2 ) ̸ = Y )) = 1 4 ( 1 11 - 1 12 ) = 1 528When M = 0, we improve our classifier's accuracy by: P(Imputation model is wrong, model with missingness is right and M = 0) -P(Imputation model is right, model with missingness is wrong and That is, the proportion of cases the classifier that uses missingness will gain is greater than the proportion it will lose relative to the imputation approach. So, the model that uses missingness outperforms the imputation model.M = 0) =P(X 1 X 2 ̸ = Y = X 1 X 2 X 3 , M = 0) -P(X 1 X 2 = Y ̸ = X 1 X 2 X 3 , M = 0) =P(X 1 X 2 = 1, X 3 = 0, Y = 0, M = 0) -P(X 1 X 2 = 1, X 3 = 0, Y = 1, M = 0) =P(X 1 X 2 = 1)P(Y = 0|X 1 X 2 = 1)P(X 3 = 0|Y = 0)P(M = 0|Y = 0) -P(X 1 X 2 = 1)P(Y = 1|X 1 X 2 = 1)P(X 3 = 0|Y =Corollary B.1. Let R(f, X, Y) denote the risk of a model f for data X, Y, and R * the optimal risk. Let I : (R ∪ NA) d → R d denote the oracle imputation function of Proposition 3.1. Under perfect imputation, it is possible for there to be no Bayes optimal model built on imputed data. That is,∃(X, Y) [∄f : R(f • I, X, Y) = R * ] .Proof. Recall that, in Proposition A.1, we constructed a distribution of X, Y such thatR(f 1 , X, Y ) > R(f 2 , X, Y )wheref 1 = arg min f R(f, I(X), Y ) f 2 = arg min f R(f, X, Y ) By definition of R * , we have that R(f 2 , X, Y ) ≥ R * , immediately yielding R(f 1 , X, Y ) > R(f 2 , X, Y ) ≥ R * .C Proof of Theorem 3.4Theorem 3.4 states: Theorem C.1. Consider any GAM g : R d → R, parameterized by β, with shape functions defined as linear combinations over boolean features (either thresholds f j (x i,j ; β j ) = len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ] or a feature that was originally boolean). Suppose some observations are missing boolean feature b, and that this feature is imputed such that the modeled probability of The general GAM, as per equation ( 1), is g(x i ; β) = β 0 + d j=1 f j (x i,j ; β j ), or with the shape functions incorporated,g(x i ; β) = β 0 + d j=1 len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ]where 1 [xi,j ≤t j,k ] values corresponding to a missing feature j are replaced with some imputed value based on a GAM. To highlight the sometimes-missing boolean feature b, we may rewrite this asg(x i ; β) = β 0 +   j̸ =b len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ] β b 1 [x i,b ]   + β b 1 [x i,b ]For examples x i with feature b missing, the value 1 [x i,b ] must be imputed prior to being used. Under the setting of this proof, the feature b is imputed by modeling the probability as an affine function of an additive score. Without loss of generality, that means there exists some additive model with score:s(x i,-b ) = C 0 + j̸ =b len(tj ) k=1 C j,k 1 [xi,j ≤t j,k ]for some set of real-valued coefficients C, with corresponding probability of x i,b = 1 given, WLOG, by:P(x i,b = 1|x i,-b ) = a s(x i,-b ) -min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) + dwhere a > 0, d > 0, a + d = 1. Note that we can set C 0 = 0 without loss of generality because it will appear in both terms in the numerator and both terms in the denominator, having no impact on the overall probability.The values max i ′ (s(x i ′ ,-b )) and min i ′ (s(x i ′ ,-b )) denote, respectively, the maximum and minimum of the score function over any possible x i .If we take the expectation of the score function over the probability distribution learned by the imputing additive model, we get:g(x i ; β) = β 0 +   j ′ ̸ =b len(tj ) k=1 β j ′ ,k 1 [x i,j ′ ≤t j ′ ,k ]   + β b 1 [x i,b ] + β b 1 [mcat(x i,b )̸ =0] P(x i,b = 1|x i,-b ) (Recalling that 1 [x i,b] is defined to always be false when x i,b is missing, and1 mcat(x i,b )̸ =0 is true iff x i,b is missing.)We can put the β b 1 mcat(x i,b )̸ =0 term back in the summation over thresholds and have:g(x i ; β) = β 0 +   d j=1 len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ]   + β b 1 [mcat(x i,b )̸ =0] P(x i,b = 1|x i,-b )Simplifying further:g(x i ; β) = β 0 +   d j=1 len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ]   + β b 1 [mcat(x i,b )̸ =0] a s(x -b ) -min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) + d g(x i ; β) = β 0 +   d j=1 len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ]   + β b 1 [mcat(x i,b )̸ =0] a s(x -b ) -min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) + β b 1 [mcat(x i,b )̸ =0] d g(x i ; β) = β 0 +   d j=1 len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ]   + β b a s(x -b ) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) -β b 1 [mcat(x i,b )̸ =0] a min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) + β b 1 [mcat(x i,b )̸ =0] d g(x i ; β) = β 0 + d j=1 len(tj ) k=1 β j,k 1 [xi,j ≤t j,k ] + s(x -b )1 [mcat(x i,b )̸ =0] β b a max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) + 1 [mcat(x i,b )̸ =0] β b d - β b a min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b ))We can return to our shape function notation and write:g(x i ; β) = β 0 + d j=1 f j (x i,j ; β j ) + 1 [mcat(x i,b )̸ =0] s(x -b ) β b a max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) (5) + 1 [mcat(x i,b )̸ =0] β b d - β b a min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b ))Recall from section 3, Equation (3.3), that the form of M-GAM is:g miss (x i ; β, βmiss , ᾱ) = β0 + d j=1 h j (x i,j ; βj , βmiss j ) + d j=1 d j ′ =1 h j,j ′ (x i,j , x i,j ′ ; ᾱj,j ′ ).Filling in the shape functions, we have:EQUATIONTo show this, it is sufficient to show that for any coefficients of a linear imputation model, there exists a parameterization of M-GAM such that Equation ( 6) is equivalent to Equation (5).Start from Equation ( 6):g miss (x i ; β, βmiss , ᾱ) = β0 + d j=1 f j (x j , βj ) + c m=1 βmiss j,m 1 [mcat(xi,j )=m] + d j=1 d j ′ =1 c m=1 len(tj ) k=1 ᾱj,j ′ ,k,m 1 [mcat(xi,j )=m and x i,j ′ ≤t j ′ ,k ] .Rearranging:g miss (x i ; β, βmiss , ᾱ) = β0 + d j=1 f j (x j , βj ) + d j=1 c m=1 βmiss j,m 1 [mcat(xi,j )=m] + d j=1 d j ′ =1 c m=1 len(tj ) k=1 ᾱj,j ′ ,k,m 1 [mcat(xi,j )=m and x i,j ′ ≤t j ′ ,k ] .We can pick the non-missing coefficients β for Equation ( 6) to match those from Equation ( 5), leaving β0 +d j=1 f j (x j , βj ) = β 0 + d j=1 f j (x j , β j ).Now pick βmiss j,m = 0 except when j = b, and βmiss b,1 = β b d -β b a min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b ))-min i ′ (s(x i ′ ,-b )). Then we have:g miss (x i ; β, βmiss , α) = β 0 + d j=1 f j (x j , β j ) + 1 [mcat(xi,j )=m] β b d - β b a min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) + d j=1 d j ′ =1 c m=1 len(tj ) k=1 ᾱj,j ′ ,k,m 1 [mcat(xi,j )=m and x i,j ′ ≤t j ′ ,k ] . g miss (x i ; β, βmiss , ᾱ) = β 0 + d j=1 f j (x j , β j ) + d j=1 d j ′ =1 c m=1 len(tj ) k=1 ᾱj,j ′ ,k,m 1 [mcat(xi,j )=m and x i,j ′ ≤t j ′ ,k ] . + 1 [mcat(xi,j )=m] β b d - β b a min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) Now, parameterize d j ′ =1 c m=1 len(tj ) k=1 ᾱb,j ′ ,k,m 1 [mcat(x i,b )=m and x i,j ′ ≤t j ′ ,k ] to match s(x -b ) β b a max i ′ (s(x i ′ ,-b ))-min i ′ (s(x i ′ ,-b )) by, for each j ′ , setting ᾱb,j ′ ,k,1 = C j ′ ,k β b a max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b ))Set ᾱj,j ′ ,k,m = 0 for all j ̸ = b. Then we have:g miss (x i ; β, β miss , α) = β 0 + d j=1 f j (x j , β j ) + 1 [mcat(xi,j )=m] β b d - β b a min i ′ (s(x i ′ ,-b )) max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )) + 1 [mcat(x i,b )=1] s(x -b ) β b a max i ′ (s(x i ′ ,-b )) -min i ′ (s(x i ′ ,-b )).Now, as required, we have shown that Equations 6 and 5 are equivalent.In Section 4.1, we evaluated the predictive power of M-GAM when additional synthetic missingness was added to each dataset we studied. Let X 1 denote the variable missingness is being added to, X 2 another column from the dataset used to determine whether to add missingness, and Y our target outcome. Let M denote whether synthetic missingness is added to X 1 , and let Q X2 (p) denote the p-th quantile of X 2 . For a target missing rate r, Table D .1 shows the conditional probability of X 1 being missing given each value of Y and X 2 . Note that missingness does not depend on X 1 , making this an MAR setting.Y = 0 Y = 1 X 2 ≥ Q X2 (0.6) P (M = 1|Y, X 2 ) = 0 P (M = 1|Y, X 2 ) = r X 2 < Q X2 (0.6) P (M = 1|Y, X 2 ) = r P (M = 1|Y, X 2 ) = 0 Table 1:The conditional probability table obeyed when adding synthetic missingness.We follow the structure from (Shadbahr et al., 2023) for running our imputation baselines and selecting train/test splits. To collect the data for MIMIC, we used the process in (Johnson et al., 2018) , and additional steps by (Zhu et al., 2023) to convert the data to a single tabular dataset.For every GAM we fit (M-GAM, FastSparse, and non-L0 GAMs), we created an indicator for each of 8 quantiles (the 0.125 quantile, the 0.25 quantile, and so on). On FICO, we include missingness indicator and interaction terms as appropriate for four encodings of missingness: the three types in the original dataset (no information, no usable information, and no report available) and an added indicator which is true for any type of missingness. All other datasets contain only one type of missingness.We fit all M-GAMs using FastSparse (Liu et al., 2022) , and in all cases set the "max support size" variable to 100. This prevents the algorithm from exploring models with greater than 100 non-zero coefficients. For all experiments that did not report complete sparsity versus accuracy curves, we used 5-fold cross validation to select the value for the ℓ 0 sparsity penalty. We searched over the following set of values for λ for each GAM: 20, 10, 5, 2, 1, 0.5, 0.4, 0.2, 0.1, 0.05, 0.02, 0.01, and 0.005. We optimized for AUC on Breast Cancer and accuracy on all other datasets when using cross validation. We fit all non-sparse GAM's using SKLearn's implementation of logistic regression over binned data.We evaluated the performance of a variety of classifiers on all datasets in Section 4.4. For each datasets, we used MICE to impute 10 distinct datasets, and fit a variety of predictive models (a logistic regression, an AdaBoost model (Freund & Schapire, 1997) , a random forest (Breiman, 2001) , a decision tree, a shallow neural network, and an XGBoost classifier Chen & Guestrin (2016)) on these datasets. For each baseline classifier, we also provide accuracy for a model fit with and without missingness indicators added via the SMIM procedure Van Ness et al. (2023) . We used cross validation to select hyperparameters separately for each imputed training dataset, and ensembled the 10 models for each model class to produce a single predictive model. Cross validation was performed using 5 folds via GridSearchCV from SKLearn (Pedregosa et al., 2011) , and the SKLearn implementation was used for each model class considered other than XGBoost. The hyperparameters we considered are:• Logistic regression: {"C":[0.01, 0.1, 1, 10], "penalty": ("l2"),"max iter": [10,000], "tol":[5e-2]}• Random forest: {"n estimators": [25, 50, 100, 200] , "criterion": ["gini","entropy"]}• AdaBoost: {"n estimators": [10, 25, 50, 100, 200 ]}• Decision tree: {"max depth":[3, 5, 7, 9, None], "criterion":("gini", "entropy")}• Neural Network: {"hidden layer sizes":[(50,), (100,), (200,), (50, 50), (50, 100), (100, 100), (100, 200), (200, 200) ], "tol": [5e-2], "max iter": [1000]} • XGBoost: { 'n estimators':[100, 500, 1000], 'gamma':[0, 0.1], 'lambda': [.5, 1, 2] , 'alpha':[.5, 1, 2] }We repeat this procedure for ten distinct train-test splits for each dataset considered.All experiments were performed on an institutional computing cluster. All experiments that involved timing were conducted using one Tensor TXR231-1000R D126 Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz (512GB RAM -40 cores), except for MIWAE timing experiments, which use one NVIDIA Tesla P100 GPU. When runtime was not reported, experiments were run on whatever hardware was available on the cluster at that time.Throughout this section of the appendix, we will consider two new datasets in addition to the four datasets introduced in the main body of the paper (FICO, Breast Cancer, MIMIC, and Pharyngitis). We add the Chronic Kidney Disease Rubini et al. (2015) and Heart Disease Janosi et al. (1988) datasets from UCI, refered to simply as CKD and Heart Disease respectively. CKD consists of 400 samples with 24 features, and involves prediction of chronic kidney disease using medical features. Heart Disease concerns predicting heart disease using medical and demographic features, with 303 samples and 13 features. Note that the outcome in Heart Disease is an integer between 0 and 4; we binarize this label such that we classify no heart disease (0) versus any heart disease (1, 2, 3, 4). Both of tshese datasets contain only one missingness encoding.In the main body of this paper, we focused our evaluation of baseline classifiers on impute-then-predict using the MICE method for multiple imputation. However, a wide variety of multiple imputation methods are available. Using all six datasets, we evaluate the runtime and accuracy of four imputation methods: MICE (Van Buuren & Oudshoorn, 1999) , MIWAE (Mattei & Frellsen, 2019) , mean value imputation, and MissForest (Stekhoven & Bühlmann, 2012) . We impute ten alternative datasets for each of ten distinct train-test splits for both FICO and Breast Cancer. For a given train-test split, we fit a model from each of the model classes described in D.3 for each imputed training dataset. We ensemble these ten models to produce a single predictive model per train-test split, and evaluate the test accuracy (FICO) or test AUC (Breast Cancer) of this ensembled model.Figure 8 contains box-and-whiskers plots for the accuracy of each method considered across all six datasets. The imputation method does not generally have a substantial impact on the performance of the resulting impute-then-predict classifier. We also see that, across the two datasets not considered in the main body of the paper (CKD and Heart Disease) M-GAM continues to provide comparable accuracy to all baseline methods.Figure 9 shows the time required to produce a predictive model under each method for each dataset.As in the main body of the paper, we show the sum of the time required to impute data and the time required to produce the most accurate model. We see that, despite resulting in models with comparable accuracy to those produced by MICE and Mean imputation, MissForest and MIWAE take longer to compute on the majority of datasets. On all six datasets datasets, M-GAM is at least an order of magnitude faster than all three multiple imputation methods, although mean imputation tends to be fastest.This section studies how well each method scales in terms of the number of samples in the dataset.For each dataset, we take subsamples of increasing size (25%, 50%, 75%, and 100% of samples in each dataset) and run each impute-then-predict predict procedure, as well as M-GAM over 10 distinct train-test splits. Figure 10 reports the total time taken to produce a model for each imputation method and M-GAM on each dataset/subsample combination. We find that M-GAM scales no worse than any of the imputation alternatives in terms of runtime.Throughout the main body of this work, we reported results using 8 evenly spaced quantiles to threshold our input variables for both M-GAM and FastSparse GAMs fit on imputed data. In this section, we evaluate the sparsity versus accuracy curve for M-GAM under different binning strategies.In particular, we evaluate the performance of M-GAM on FICO with 4, 8, 16, and 32 evenly spaced quantiles. Figure 11 shows the results of this analysis. As the number of quantiles increased, M-GAM remained sparse despite the exploding number of interaction terms, and in fact for 32 quantiles the interaction terms lead to an especially sparse and accurate model. Beyond these observations, we found that reasonable changes to the number of thresholds we consider did not significantly impact performance.Figure 8 : Test accuracy of M-GAM compared against a variety of baselines for four imputation methods and six datasets. Each column corresponds to a different imputation method, and each row to a different dataset.Figure 9 : Runtime of different methods on Breast Cancer, CKD, FICO, Heart Disease, MIMIC, and Pharyngitis. For each imputation method, we report the total time required to impute missing data and fit the best performing impute-then-predict classifier for that dataset and imputation method. M-GAM (Ind) is an M-GAM with indicators and M-GAM (Int) is an M-GAM with interaction terms. Error bars report standard error of total runtime over 10 train-test splits.Since MICE is a multiple imputation method, we needed to choose how many datasets we allow MICE to impute for each of our experiments. In this section, we evaluate the runtime versus test accuracy for models built on various numbers of imputed datasets for FICO. We evaluated each non-GAM baseling model considered in the main paper when ensembled over 1, 5, 10, 20, and 30 MICE imputed datasets.Figure 12 shows the accuracy versus runtime for each number of imputations. In Figure 12 , we see that there is a slight improvement in the accuracy of our classifiers when increasing from 1 to 5 imputations, but no significant performance gain for any larger numbers of imputed datasets. As such, we opted to use the moderately fast and performant choice of 10 imputations.We focus on the FICO and Breast Cancer datasets for much of the main paper, alongside Pharyngitis and MIMIC. In Figure 13 we show the superset of our sparsity-accuracy results that includes the two UCI repository datasets, Heart Disease Janosi et al. (1988) and CKD Rubini et al. (2015) . In Figure 14 we show the superset of our results for the data with added MAR missingness, for all 6 datasets.As we discuss in the main text, allowing our model to encode different reasons for missingness allows the ability to handle multiple reasons for missingness, improving the model's power. However, using only a single, overall reason for missingness could potentially allow for handling a larger set of missing data cases with fewer coefficients. These two encodings are not mutually exclusive; we could augment in both ways, as described in Equation E.1. For this reason, we investigate sparsity and test accuracy on the FICO dataset across a range of choices for whether to use distinct encodings, overall encodings, or some combination of the two. We explore a variety of combinations in Figure 15 , allowing nonzero values for different subsets of α (specific indicators), α overall (overall indicators), β miss (specific interactions), and β overall miss (overall interactions). We find no dramatic differences across these choices. Definition E.1. Given parameters α, α overall , β miss , β overall miss , and β, an M-GAM is defined asEQUATION+ d j=1 d j ′ =1 h j,j ′ (x i,j , x i,j ′ ; α j,j ′ , α overall j,j ′ ),whereh j,j ′ (x i,j , x i,j ′ ; α j,j ′ , α overall j,j ′ ) = c m=1 len(tj ) k=1 α j,j ′ ,k,m 1 [mcat(xi,j )=m and x i,j ′ ≤t j ′ ,k ] + len(tj ) k=1 α overall j,j ′ ,k 1 [mcat(xi,j )̸ =0 and x i,j ′ ≤t j ′ ,k ]and h j (x i,j ; β j , β miss j , β overall miss ) = f j (x i,j ; β j ) + NeurIPS Paper ChecklistNote that it is sufficient to show that this this theorem holds for a single missingness reason, m = 1. Showing that this theorem holds for M-GAM in the less expressive case where there is only a single reason for missingness, also shows that the theorem holds when there is added expressiveness to the model class. As such, we do not include notation for distinct missingness reasons in the proof. 


Decision: Paper proposes a novel variant of generalized additive model (GAM) for missing features (M-GAM) to provide comparable accuracy to popular imputation approach, keeping computational cost slow and producing sparse and interpretable model. Both theoretical and experimental analysis is done, showing the usefulness of the proposed model in certain benchmark problems.

Based on comments and scores, all the reviewers are on the positive side of margin. The strengths of the paper are related to novel and useful idea (Reviewers i65A, fLWT, 63xg, W4vf), well-written and structured content (Reviewers i65A, fBin, 63xg, W4vf), valuable method/model (Reviewer i65A), e.g., for practitioners (Reviewers fBin), and extensive experiments (Reviewers fLWT and W4vf). On weaknesses/limitations side, there have been some critics on the experiments (in general Reviewer fBIN, baseline methods Reviewer 63xg, 
and e.g., related to missing of synthetic examples with ground truth and where missingness is controlled, Reviewer i65A), performance of proposed method (Reviewers fLWT and fBin), detailed discussion of interpretability of the model (Reviewers i65A and fBin), and theoretical background / claims (Reviewer i65A).

Authors have provided some response to critics in rebuttal, including: 1) additional experiments against baselines of decision trees (DT) and random forest (RF),  and AUC validation metrics for imbalanced datasets (in global rebuttal file, Figure 1), 2) additional computational time analysis of DT and RF (in global rebuttal file, Figure 2), and 3) additional MCAR experiment (in global rebuttal file, Figure 3). Furthermore, more discussion of interpretability around Figure 2 in original manuscript (in discussion with Reviewer i65A) and discussion about DT handling missing values to related work (in discussion with Reviewer 63xg) are to be added. Overall, paper brings valuable information to community and interesting tool for practitioners. Based on these, I would recommended paper to be accepted as 
a poster. Authors are encouraged to revise the final paper, including all the improvements and suggestion raised during the rebuttal discussion.

Reviews: review: paper_summary: paper_summary: The paper "Interpretable Machine Learning for Datasets with Missing Values" proposes generalized additive models incorporating missingness indicators and their interaction terms with sparseness ensured by l0 regularization. Therefore, the authors combine GAMs with the Missing indicator method and l0 regularization. The method is compared on real-world data sets with missing values and added synthetic missingness and against a variety of techniques used on imputed data with and without selective addition of missingness indicators.
strength_weakness: strength_weakness: I would have run 2 distinct experiments at least. One with synthetic missingness where the ground truth is known and the missigness can be increased. Additionally I would have liked to see also a mix of MCAR and MAR to demonstrate the results when the assumed mechanism is incorrectly chosen. 
The authors emphasize the interpretability enabled by M-GAM and figures are shown. It would have been nice to discuss the interpretation in the text.
questions: questions: Proof only works since the unobserved noise for k1 and k2 is chosen as it is. "Let k_2<k_1<0.5" 
To me this looks like circular reasoning. If I assume the noise is lower for knowing the missingness relationship with the predictor Y, than my uncertainty with the oracle -> of course the one with lower noise with reach higher probability. If the assumption is switched or equal signs added the proposition will fall apart. It seems the proposition needs to be far more limited than it is right now. 
In 108 should it than not say "Corollary 3.2 states that perfectly imputing missing data can reduce the best possible performance of
a predictive model, if the noise of the assumed predictor dependent missingness mechanism is lower than the measurement noise."?
I find this not very surprising. Adding correct information with higher certainty should always be better. Adding correct certain models of the missingness mechanism is of course preferable to high noise imputation. 
Why did the authors impute the data for RF? If C4.5 is used than the missingness can be handled without explicit imputation by change of the impurity function. There are also internal impute proposals: Stekhoven & Bühlmann (2012), "MissForest—non-parametric missing value imputation for mixed-type data", Bioinformatics, 28, 1.
limitations: limitations: see above. I think their proposition fails to emphasize a major assumption to their claim.
paper_summary: paper_summary: This paper introduces M-GAM, which incorporates concept of missingness into Generalized Additive Model(GAM). Since GAM represents arbitrary function with sum of univariate functions which take each input feature as input, M-GAM maintains sparsity and interpretability for inference with missing data.
strength_weakness: strength_weakness: - I think the main weakness of M-GAM is its performance which just barely match other baselines' performance. Since it is trained end-to-end manner, we can expect more performance gain than impute-then regress methods since it directly uses supervision during training. Since informative missingness is rare in real world dataset, predictive performance of M-GAM  on real world dataset can harm the applicability.
questions: questions: - why M-GAM especially good on MAR setup?
limitations: limitations: Yes
paper_summary: paper_summary: The paper introduces M-GAM, a novel extension of Generalized Additive Models (GAMs) designed to maintain interpretability while handling datasets with missing features. By incorporating missingness indicators and their interaction terms through ℓ0 regularization, M-GAM balances accuracy and sparsity. The model provides comparable or superior performance to traditional imputation methods while avoiding the complexity and overfitting issues associated with the naive inclusion of missingness indicators.
strength_weakness: strength_weakness: - The title should convey that the study is limited to GAMs
Runtime comparison in 4.3 is a bit vacuous because it depends on the exact implementation, etc. Maybe looking at computational complexity would be more interesting.
- Empirical evaluation is somewhat limited
questions: questions: - l.27, it seems strange to contrast the choice of (not) using missingness with the choice of using l0 regularization. They seems to be rather orthogonal choices.
- Why l0 and not some other regularization?
- It seems questionable to encode reasons for missingness with natural numbers, as these imply an ordering.
- It looks like all other methods have better mean accuracy than M-GAM in Figure 6, Breast Cancer dataset. Is this correct? If so, the text should discuss this rather than glossing over it.
limitations: limitations: - The authors state interpretability as one of M-GAM's main advantages. I would like to see this made explicit, e.g., with an example, especially in comparison to existing methods.
- Empirical performance is not great.
paper_summary: paper_summary: The paper presents M-GAM, a novel generalized additive model that that incorporates missingness indicators while maintaining a sparse model via l_0 regularization. Results shows that on augmented datasets with missing at randomness M-GAM provides better performance; on real-world (not augmented) datasets, M-GAM achieves similar performance but is faster than impute-then-predict.
strength_weakness: strength_weakness: - My understanding is that the setting considered in this paper seems to be limited to GAMs with main effects and not higher-order GAMs (in particular, GAM with pairwise interaction effects, GA2M [Lou et al., KDD 2013]). 
- There has been significant work on handling with missing values in decision trees (that are also a widely used interpretable model). There is very little both in terms of discussion (e.g., are the approaches there applicable to GAMs, does the proposed approach share some similarities to existing approaches in decision trees) as well as in terms of experimental results (how do decision trees with missing values compare to GAM with missing values, at the moment only SMIM with decision tree is considered and not approaches that are inherent to decision trees).
- The experimental results on real datasets do not demonstrate strong improvement in performance (but there is improvement in other factors, e.g., runtime compared to impute-then-predict).
- The analysis on other models, including decision trees (with and without SMIM) does not include runtimes so it is not clear if the new model is also significantly faster from, say, decision trees or logistic regression or random forests with SMIM.
questions: questions: I would appreciate the authors response to the weaknesses listed above. In addition I was wondering if the authors have considered incorporating this mechanism into one of the recent neural GAM approaches, e.g., Neural Additive Models [] which will allow potentially for better scalability?
limitations: limitations: Limitations are adequately addressed.
paper_summary: paper_summary: The paper discusses challenges posed by missing data in important datasets for machine learning models. Existing methods like imputation or using indicator variables for missingness can compromise model interpretability or introduce complexity and reduced sparsity. The authors propose M-GAM, a sparse, generalized additive modeling approach. M-GAM addresses these issues by incorporating missingness indicators and their interactions, while maintaining sparsity through l0 regularization. They demonstrate that M-GAM achieves comparable or better accuracy than existing methods while significantly improving sparsity compared to imputation or straightforward inclusion of indicator variables.
strength_weakness: strength_weakness: - The proposed method is constrained by its reliance on l_0 regularization.
questions: questions: N/A
limitations: limitations: N/A

Comments: title: Ack
comment: We appreciate you taking the time to review our response, and for increasing the score.

We’re sorry that you find this setting unrealistic, but we are unaware of any standard definition for what a realistic data generating process looks like. We have shown that, under a variety of different constraints, it’s possible to show that the proposition holds. We've shown that it holds in the most realistic setting we can imagine (missingness < 50%, signal from missingness weaker than from other variables), and include the proof at the bottom of this response. We hope this helps show that the setting for this proposition really is quite broad, even though we have not formally quantified this.

We do believe that, generally, settings with informative missingness are realistic - consider, for example, the result of a medical test being missing because a doctor judged that the patient was not at sufficient risk to need that test; on a survey about politics, an individual skipping questions because they distrust the pollster’s political leaning; or in loan default prediction, a credit report being missing because an individual has no credit history.

We apologize for missing your request that we add synthetic data - we misunderstood the suggestion, and thought that semi-synthetic data with a ground truth missingness mechanism would satisfy your concern. With this clarification, we’re happy to add fully synthetic examples to our paper (although we aren’t able to include those plots today because of the rules concerning the discussion period).

Thank you for the suggestion regarding survival analysis – that does sound like a very relevant setting, and we hope to explore it in the future!

Again, thank you for your feedback and discussion!

------

Proof:

Consider a case similar to that used for the proof in proposition 3.1, where we add an additional variable $X_3$ and have the noise for the missingness be higher than any other noise.

$$Y = |X_1X_2 - \epsilon_1|, \epsilon_1 \sim \textrm{Bern}(\frac{1}{12})$$
$$M = \begin{cases} |Y - \epsilon_2|, \epsilon_2 \sim \textrm{Bern}(\frac{1}{4}), \&\textrm{with probability $\frac{1}{2}$} \\\\
0, \&\textrm{with probability $\frac{1}{2}$}\end{cases}$$
$$X_3 = |Y - \epsilon_3|, \epsilon_3 \sim \text{Bern}(\frac{1}{11})$$

We also adjust the probabilities for $X_1$ and $X_2$ being true so that this is a balanced classification problem: $X_1, X_2 \sim \textrm{Bern}(\frac{1}{\sqrt{2}})$, so $X_1X_2 \sim \textrm{Bern}(\frac{1}{2})$

Note that we now also have missingness at well under 50\% of the data (missingness happens a quarter of the time)

The bayes optimal model with perfect imputation of $X_1$, and no access to $M$, is still just to predict in accordance with $X_1X_2$ for $\mathbb{P}(X_1X_2=Y) = \frac{11}{12}$. When $X_1X_2 = X_3$, all information available suggests $X_1X_2$ is correct.
When $X_1X_2 \neq X_3$, we still have the bayes optimal prediction aligning with $X_1X_2$: $\mathbb{P}(Y=1|X_1X_2=1,X_3=0) = \frac{11}{21} > 0.5$ and $\mathbb{P}(Y=0|X_1X_2=0,X_3=1) = \frac{11}{21} > 0.5$.

If we instead only have access to $X_1$ when it is not missing, but we also know when $X_1$ is missing (i.e. we know $M$), then the following approach will perform better than the above model:
$$Y = \begin{cases}
    X_3, &\textrm{if $M=1$} \\\\
    X_1X_2X_3, &\textrm{if $M=0$}
\end{cases}$$


When $M=1$, we make additional errors relative to the previous approach at rate

\begin{align*}
\mathbb{P}(M=1)(\mathbb{P}((X_3)\neq Y) - \mathbb{P}((X_1X_2)\neq Y))\\\\
    \&=\frac{1}{4} (\frac{1}{11}- \frac{1}{12})\\\\
    \& = \frac{1}{528}
\end{align*}

When $M=0$, we improve our classifier's accuracy by:
\\begin{align*}
\&\mathbb{P}(\text{Imputation model is wrong, model with missingness is right and }M=0)\\\\
\&- \mathbb{P}(\text{Imputation model is right, model with missingness is wrong and }M=0)\\\\
= \&\mathbb{P}(X_1X_2 \neq Y = X_1X_2X_3, M=0) - \mathbb{P}(X_1X_2 = Y \neq X_1X_2X_3, M=0)\\\\
= \&\mathbb{P}(X_1X_2=1, X_3=0, Y=0, M=0) - \mathbb{P}(X_1X_2=1, X_3=0, Y=1, M=0)\\\\
    = \&\mathbb{P}(X_1X_2=1)\mathbb{P}( Y=0|X_1X_2=1)\mathbb{P}(X_3=0|Y=0)\mathbb{P}(M=0|Y=0) \\\\ \&- \mathbb{P}(X_1X_2=1)\mathbb{P}( Y=1|X_1X_2=1)\mathbb{P}(X_3=0|Y=1)\mathbb{P}(M=0|Y=1)\\\\
    = \&\frac{1}{2}\frac{1}{12}\frac{10}{11}\frac{7}{8} - \frac{1}{2}\frac{11}{12}\frac{1}{11}\frac{5}{8}\\\\
    = \&\frac{15}{2112}\\\\
\> \&\frac{1}{528}
\\end{align*}

So the model that uses missingness outperforms the imputation model.
Updated now.
Once again, thank you for your review, and for raising your score. We've noticed that it seems like the rating update hasn't gone through on OpenReview. Would you mind updating this score? Thank you!
Once again, thank you for your review, and for raising your score. We've noticed that it seems like the rating update hasn't gone through on OpenReview. Would you mind updating this score? Thank you!
Thank you again for your feedback!
Thank you again for your feedback, and for increasing your score!
Yes it is formally correct that one can construct situations in which even perfect imputation can be outperformed. As the authors note in cases where the noise of the features is higher than the noise of the missingness model. Also when M is 0 or 1 with a 50/50 chance as seen in the rebuttal. I still find these situations not realistic and having very restricted practical use. Many approaches base on the idea that a missing feature is not essential for the task and information is still covered by the remaining observations accepting some increase in uncertainty. I appreciate the reviewer added such methods in the comparison. Furthermore,  I suggested making a fully synthetic experiment with controlled and increasing missingness in a toy situation where one can easily follow the method and its interpretation. Only as a second part of the sentence the mix of MCAR and MNAR was mentioned, which was less important than the first part. Synthetic missingness in real data is always a mix for which the influence and sensitivity of the method is less accessible. This has not been addressed. 
However, besides finding the existence claims on the trivial and less interesting side, I see a value in the method itself, also by the discussion with the other reviewers, so I will hire my score accordingly. 
I would like to point the authors to censoring in Survival analysis as potential interesting application area for which missing data and its interpretation is really important. There the data sets are small, very imbalanced and missigness can be high due to the longitudinal and medical nature.
Thank you for your response. I will increase my score by one point.
Thank you for your response. I've decided to keep my original score.
Thank you again for your constructive review, and for increasing your score!
Thank you for the response. With the additional explanation and background (provided also in responses to other reviewers), I would like to up my overall rating to 6. I hope this paper will be accepted.
Thanks again for your feedback, we're glad this was helpful! We're happy to discuss any further issues you might have, and we hope you will consider increasing your score if we have addressed them all :)
Thanks for answering my questions. Your answers are really helpful for my understanding of this paper.