Model-Agnostic Feature Selection with Additional Mutual Information
Authors: Mukund Sudarshan
Aahlad Manas Puli
Lakshmi Subramanian
Sriram Sankararaman
Rajesh Ranganath
Venue:  (2020)
Keywords: feature selection
interpretability
randomization
fdr control
p-values

Abstract: Answering questions about data can require understanding what parts of an input X influence the response Y. Finding such an understanding can be built by testing relationships between variables through a machine learning model. For example, conditional randomization tests help determine whether a variable relates to the response given the rest of the variables. However, randomization tests require users to specify test statistics. We formalize a class of proper test statistics that are guaranteed to select a feature when it provides information about the response even when the rest of the features are known. We show that f-divergences provide a broad class of proper test statistics. In the class of f-divergences, the KL-divergence yields an easy-to-compute proper test statistic that relates to the AMI. Questions of feature importance can be asked at the level of an individual sample.  We show that estimators from the same AMI test can also be used to find important features in a particular instance. We provide an example to show that perfect predictive models are insufficient for instance-wise feature selection. We evaluate our method on several simulation experiments, on a genomic dataset, a clinical dataset for hospital readmission, and on a subset of classes in ImageNet. Our method outperforms several baselines in various simulated datasets, is able to identify biologically significant genes, can select the most important predictors of a hospital readmission event, and is able to identify distinguishing features in an image-classification task. 

Under review as a conference paper at ICLR 2020
BLACK Box FEATURE SELECTION WITH ADDITIONAL MUTUAL INFORMATION
Anonymous authors Paper under double-bling review
ABSTRACT
Many times, working with data starts with writing code to build model from the features x to the response y. Answering questions about the data can require understanding what parts of the features x influence the response y. We show that using the KL-divergence within randomization test discovers important fea- tures, while allowing for the reuse of model code. We call this method AMI-CRT. AMI-CRT requires running models for each randomization. We develop a faster variant called FAST-AMI-CRT, and show it is robust to errors in the randomization. Questions of feature importance can also be asked at the level of an individual sample. We provide an example to show that optimal predictive models are in- sufficient for instance-wise feature selection. We show that the estimators from FAST-AMI-CRT can also be reused to find important features in a particular in- stance. We evaluate our method on several simulation experiments, on a genomic dataset, a clinical dataset for hospital readmission, and on a subset of classes in Im- ageNet. Our methods outperform several baselines in various simulated datasets, identifies biologically significant genes, selects the most important predictors of a hospital readmission event, and identifies distinguishing image regions in an imsge-Clasiification task.
INTRODUCTION
Model interpretation techniques aim select features important for response by reducing models (sometimes locally) to be human interpretable. However, the phrase model interpretation can be a bit of misnomer. Any interpretation of model must be imbued to the model by the population distri- bution that provides the data to train the model. In this sense, interpreting a model should be viewed as understanding the population distribution of data through the lens of model. Existing methods for understanding the population distributions only work with particular models fit to the popula- tion, particular choices of test statistic, or particular auxiliary models for interpretation (Ribeiro et al., 2016; Lundberg and Lee, 2017). Such structural restrictions limit the applicability of these methods to smaller class of population distributions. To able to work black-box manner, feature selection methods use models but must not require particular structure in models used in selection processes.
Understanding the population distribution can be phrased assessing whether a response is inde- pendent of feature given the rest of the features; this test is called conditional randomization test (Candes al., 2018). Conditional randomization tests require test statistics. Test statisties like linear model coefficients (Barber et al., 2015) or correlation may miss dependence between the re- sponse and outcome. To avoid missing relationships between variables, we develop the notion of a proper test statistic. Proper test statistics are those whose power increases to one as the amount of data increases. Conditional independence implics the vonditional-join factorizes into conditional- marginals. Measuring the divergence between these distributions yiclds a proper test statistic. Of the class of integral probability metrics (Müller, 1997) and f-divergences (Csiszár, 1964), the KL- divergence simplifies estimation and allows for reuse of the model structures and code from the standard task of predicting the response from the features. Using the KL-divergence in this con- a measure of the additional information each feature provides
text has a natural interpretation; about the outcome over the rest. This measure of information is known as the additional mutual information (AMI) (Ranganath and Perotte, 2018).
Our proposed procedure is called the additional mutual information conditional randomization test (AMI-CRT). AMI-CRT uses regressions to simulate data from the null for each feature and compares the additional mutual information (AMT) of the original data to the AMI of the simulations from

---

Under review as a conference paper at ICLR 2020
the null to assess significance. AMI-CRT works with any regression with probabilistic outputs like cross-entropy--rriiee -rranned neural networks. Training many regressions for each sample from the null can require substantial computation. While this is an embarrassingly parallel computation, FAST-AMI-CRT that only requires a single model trained from null data. FAST-AMI-CRT uses an average of the model from the null with the model from the original data. We show this mixture guards against both variance in model training and poor estimation of the null. Though simple, AMI-CRT outperforms popular procedures for feature importance on wide variety of simulated data, hospital records, and biological data.
develop
Working with data sometimes requires interpreting individual datapoints. For example, a doctor may benefit from knowing which features for particular patient relate their health. The process of identifying features at a datapoint-level is called instance-wise feature selection (Ribeiro et al., 2016; Lundberg and Lee, 2017; Gimenez and Zou, 2019). We identify issue in instance-wise feature selection, where even features selected using the true population distribution do not yield the features that were used to generate the response of an instance. The crux of this disparity is that the response generation process, conditional on the features, may use randomness to select features. We provide an example to demonstrate where instance- waise feature selection can go awry. We develop sufficient conditions for instance-wiss feature selection to avoid this issue. The same regression estimates from AMI-CRT can be used to estimate feature-importances with minimal computational overhead, resulting in method we term additional mutual information instance-wise feature selection (AMI- IW). We demonstrate AMI-IW on multiple simulations and image data. Across all of these tasks AMI-IW outperforms popular baselines.
Related Work. Permutation tests (Fisher, 1937) provide a test for marginal independence be- tween each feature and the outcome. However, they fail to test conditional independence, which is required when covariates are dependent on each other. To address this, solutions like Sure Inde- pendence Screening (Barut et al., 2016; Fan and Lv, 2008) and Conditional Randomization Tests (Barber et al., 2015; Candes et al., 2018) have been proposed. These outline frameworks for condi- tional independence testing. However, they often make linearity or additive noise assumptions about the data generating distribution. Furthermore, they require the choice of test statistic to capture some notion of conditional independence. The user of such frameworks is often burdened with the task of choosing this test statistie, which may require strong assumptions about the data generating distribution. Extending this approach to neural networks, Lu et al. (2018) propose a fully connected test statistic. Though moving beyond linear models, their
network whose weights are used method is specific to fully connected networks. Tansey et al. (2018) propose holdout randomization tests (HRTS) that use empirical loss as a test-statistic. The loss they use for continuous-valued distri- butions of response is the mean-squared-error (MSE), which may ignore higher order dependencies between the response and features. Using AMI inside an HRT would capture these higher order de- pendencies. In our results, we adapt our stst-statistic AMI to HRTs and show that this produces better calibration than other choices of loss. HRTS provide computational speed-ups over CRTs. However this speedup comes at the cost of robustness to poor estimations of the null feature distribution. We demonstrate empirically that FAST-AMI-CRT is robust to such poor estimations.
Beyond understanding the population distribution, some tasks require interpreting population dis- tribution on the level of an individual datapoint. Methods that test for conditional independence work under distributional notions of feature selection, but are not designed to identify the relevant features for a particular sample. To address this issue of "instance-wise feature selection," several methods have been proposed, including local perturbations (Simonyan al., 2013; Sundararajan et al., 2017; Ribeiro et al., 2016) and fitting simpler auxiliary models to explain the predictions of large model (Chen et al., 2018; Lundberg and Lee, 2017; Yoon et al., 2019; Turner, 2016; Štrumbelj and Kononenko, 2014; Shrikumar et al., 2017). Our instance-wise wise work is most similar to that of Burs et al. (2019), who repurpose the HRT framework to perform instance-wise feature selection, or Gimenez and Zou (2019), who define a conditional randomization test (CRT) procedure for subsets of the feature space. In general, however, the conditions under which instance-wise feature selec- tion with predictive models may be possible are not well developed. We address this issue by first identifying& set of sufficient conditions under which instance-wise feature selection is always pos- sible. We then show how estimators used in AMI-CRT can be repurposed for use in an instance- wise setting, yielding a procedure called the A MI-IW.

---

Under review as a conference paper at ICLR 2020
2 PROPER TESTS FOR FEATURE SELECTION
Practitioners of machine learning use feature selection to identify important features for their pre- dictive task. One way filter out important features is find those that improve predictions given the rest of the features. This can be formalized through conditional independence. Let xj be the jth feature of x and let x-j be all features but the jth one. The goal to discover a set S such that Vx, & S,x, y x-j. where independence is with respect to the true population distribution
The only knowledge about y comes from finite set of samples Dx {(xx(t) y )) sam- pled from the population. This means that it is impossible to assess exact conditional independence. Therefore, in the finite sample setting, we must formulate a statistical hypothesis test.
A conditional randomization test (CRT) (Candes et al., 2018) defines hypothesis test for conditional independence. For the jth feature, CRTs first compute a test statistic using the N samples of data DN. CRTs place this statistic in null distribution where samples of the jthh feature x, are replaced by samples of X, x-j which by construction satisfy žJ 1 y x-j. Letting Dy,N be dataset where {mr) (9,. Ji=1 has been replaced by (ar) (6) Ji=1 the p-value for CRT is
((DN) [0.NN)]
[a (1(DN) s0]
Py (Dx))) #/ -
E Vi=I...N #) ~
VI=I..N
(1)
Under smoothness constraints, the p-value is uniform under the null because it computes the cumu- lative distribution function of the test statistic under the null. While CRTS provide a general method for conditional independence testing, they leave several components including the choice of test statistic unspecified.
2.1 CHOOSING THE RIGHT TEST STATISTIC
Imagine a test statistic ((.) = t((=)) y ( that uses only a feature x, and the outcome y. Any p-values computed using this test statistic would be meaningless when testing for conditional independence, as never considers the remaining features x-j- Therefore, particular choices for test statistics limit what can be tested. To address this, we introduce the concept of proper test statistic.
Definition Proper Test Statistic: A test statistic ((Dx) is proper if p-values produced by the statistic converge to O when the null must be rejected, and are uniformly distributed otherwise. Using in Equation (1), this is:
ifx; Ly x-j Pj (Dx) N-+20 (0 with probability 1 ifx, Ly x-j
Uniform(O.) 1)
where 4 indicates convergence in distribution. Under the alternate hypothesis, which in the case of feature selection is Xj yy x-j the power to reject the null hypothesis must be 1, implying P, + proper test statistic requires that Equation (2) must hold for all distributions of y.
Proper tests statistics in CRT select the features in S the data grows. Definition 1 mirrors the concept of a scoring rule (Gneiting and Raftery, 2007), which measures the calibration a probabilistic prediction by model. A proper scoring rule is one such that the highest expected score is obtained by model that uses the true probability distribution to make predictions.
Divergences are proper test statistics. tion r factorizes:
Conditional independence means the conditional distribu-
r(xj.y x-)) = =(x; x xx))r(y x x-)).
Divergences measure the closeness between two distributions. A divergence is zero when the two distributions are the same and positive otherwise. Computing any divergence K., like an integral probability metric (Müller, 1997) an f-divergence (Csiszár, 1964), between the left hand side and right hand side of Equation (3) would be a proper test statistic. Let KC(a, b) 2 0 with equality holding only when is equal in distribution to b, then proper test statistic Kr(r) == (KC,,, x (-j),(xx;
x-))r(y x=)))]. A consistent estimator of this quantity is proper test statistic (see

---

Under review as a conference paper at ICLR 2020
Appendix B.1). Casting conditional independence testing divergence estimation reduces this test to fitting univariate regressions that can reuse pre-developed model code from the features to the response.
Define the resampling distribution ūj ūJ (x,3x | xx)))((,, x x-,), Using a divergence in a CRT requires estimates of the following conditional distributions: g(x, x x-)). x) X,,X,)) and q(y x-z)- The first distribution g(x; x))) is required for any CRT. The next distribution q(y x) corresponds to the standard task of building a good regression model. The third distribution
Øy Xz,X-;) requires regression model with corrupted inputs. This regression can reuse the
model structure and code from the standard regression task g x). However, the last distribution q(y x-j) could require development of new model structures. For example, if x is image, good model for g(y x) could be a convolutional neural network. If the conditioning set x-j is subregion of that image, the convolutional neural network used for g(y x) would need to be modified for different padding and filter sizes. This means new models could be needed for each x-j. In the next section, we show that the KL-divergence removes the need for estimating this distribution, and therefore only requires the piece needed for all CRTS, gxx; x x-)), and model code to fit the response from the features.
2.2 AMT-CRT
Using the KL-divergence test statistic in Equation (1) requires the difference 6y:
89 = =Etxx_ [KKL (q()) x-)).
x=))4(y x-5))]
Eig (x-,) [DKL (7) y x-)): (X, x- x-ل) (y []]]
-x)) [ v/ x [og (x,, x-,) log(n(x) x [x,))]
- Bag (R, y x [lg 03 (x, y x-5) - -log(ū; |x-))ū (y xxx))]]
-R [F. (x, y xx_, [log q(y [y] x) - -logg(y x-j)]
-B, (R, y x [og 03 (y x x-)) - log कj (y x x-1)]]
= -Fx(x_)) 1 v _ [og q(y x)] F, (2, y xx_ [lo (y X,, x)حll
= (x (logg(y x)] Egy( ,.y) , [log कe (y x)]]=
The second equality above follows from ((x_;) = و. و): and the fourth from g(y x-)) T (y | x-j). This simplification of 5, means that for the computation of the average KL-divergence as test statistic, the distribution g(y x-,) unecessary, thereby reducing computation and allow- ing the reuse of training infrastructure for predicting the response The KL-divergence provides this reduction since log splits products into sums. This expected KL-divergence is called the addi- tional mutual information (AMT) (Ranganath and Perotte, 2018).
Computing the expected value of oj to get the p-value in Equation (1) requires estimation from finite sample. Recall that Dx is collection of N datapoints sampled iid from y) These samples from the population come from the provided data. Similarly, DjAN is sampled iid from ((x-5. () x-)). The samples X-j. come from the population distribution, however sam- pling (xx, x_y) requires learning a model for this distribution also known as the complete condi- tional. The other two pieces of ó, require building a model from to y and (X,, x-)) to y. To learn these models, the data D is split into training and test sets. Let 0, P. be parameters, qo go(;, xx)) and gy x) are fit to the training set. The distribution g- xx,x-;) is fit to the training part of Dj.N. To compute the expectations in 6,. these models are evaluated on their corresponding test sets. Finally, Monte Carlo estimate of the expectation for the p-value in Equation (1) requires replicating this procedure K times. We call this procedure AMI-CRT (A (Algorithm 1).
The models Ox(x; xxx)) and g x) can be shared across the replications, however (y Xj. must be recomputed for each replication. While this is an embarrassingly parallel problem, it involves the computation of a new model for each draw from the null distribution. To speed up the computation of AMI-CRT, we use the average of the original model q3(y x) and a single model trained for (y x,,x,,) This averaged model is used to estimate the two terms in the AMI-difference 5z. Under the null, the estimates are identically distributed because each estimate
I
evaluates the same function on identically distributed samples. Thus, averaging produces p-values
that are uniform under the null, but the average may not result in proper test-statistic. However,

---

Under review as a conference paper at ICLR 2020
the averaged model performs almost as well as AMI-CRT empirically. We call this procedure the FAST-AMI-CRT, which is summarized in Algorithm 2.
Averaging needed because models trained on data drawn from the same distribution have variance (Friedman al,, 2001). The averaged model provides is more conservative than using just the original model as in HRTs (Tansey et al., 2018) since the averaged model both predicts better on the null data and worse on the real data. We show empirically that this guards against errors in the estimation of the complete conditional distribution. Second, requires only a single null model per feature instead of one per replication.
with several advantages. First,
To estimate each of qo and g3, standard regression models like logistic regression, neural networks, and random forests can be used at no more computational cost than training. Nonparametrie regres- sion can be used as well. The choice between these estimators should be made by using the best fitting regression on validation data. The estimation procedure is straightforward, yet effective as we demonstrate in Section 4. In the next section, we show how the building blocks for FAST-AMI-CRT can be used to provide feature importances on an instance- wise level.
TESTS FOR INSTANCE-WIN FEATURE SELECTION
So far, we show how to recover features important across the whole population. We have not yet addressed the issue that different samples could have different important features. We call this prob- lem of recovering important features for each sample, instance-wise feature selection (IWFS). To identify important features instance-wise, can use the probability of observing particular label ( given a set of features (*), This suggests a candidate definition for important features:
Definition 2. (Candidate) Feature importance in IWFS: Let q be the true population distribution.
Let ((x11) ) be a dataset where each (xx(6) ()) q The jth feature for the ith sample,
(i) is an important feature if q(y y x x ()) > <(y = y (0) x_, = xx "
2j
(3) Definition 2 says that a feature 2) is important if observing it increases the probability of ()) This formulation is exploited in (Yoon et al., 2019; Chen et al., 2018) to obtain instance-wise important features. However, Definition 2 can sometimes fail to identify relevant features, even with access to the true conditional distribution g x). While important features may satisfy this condition, so will a few unimportant features. As demonstrative example, consider the data generating process where y = 2x1 + (1 tc, z ~ Bernoulli(0.5), X1, X2 ~ (O, od), and c ~ ~N(0, o?). Assume
we have the true q(y X1; X2). and let z be unobserved. Pick any sample (ar .22
(i) (1) (0) where the
corresponding z (6) = 1, meaning that x; is important for this instance. We can expand:
(2)
g(y 11 22
(4) (5) 403 (4) 1
(8)
o²
NN 00,00 +o:)
2
2
For all such that (0) lies in a non-O interval around x² we see that (0 (3) (0)(()))) (²) O. For example if o: 0% = 1, and x22 (i) 5, then (0()) E [3,7] will violate this inequality. In all of those cases, the wrong feature will be selected as important as per the candidate Definition 2. We show the full derivation of this example in Appendix C.I. The funda- mental issue with the formulation in Definition 2 is that noise can act as a "selection" mechanism, but cannot be estimated because it is unobserved. While predictive models qa for q(y x) suffice for understanding population distributions, they might not be sufficient to perform IWFS.
3.1 SUFFICIENT CONDITIONS FOR INSTANCE- WISE FEATURE SELECTION
We develop the following condition under which g(y x) is sufficient to perform IWFS:
Proposition 1. Sufficient conditions for instance-wise feature selection: For each sample (x(() ()),, let s(1) be a set of features that contribute to the prediction of y defined as:
5()) = (a))) (i) g(y = =y 1x x(0) > -ly=
x xx)=
(4)
If y is discrete, and q(y ()) xx = (0) for each sample (a)(),, ,y())), i.e. we have perfect predictions on our dataset, then it is possible recover such set 8(1) for all i.

---

Under review as a conference paper at ICLR 2020
Feature
ami
ert
fast ami crt
loss hrt corr ert 1ime shap rf
Provides p-vauues Well calibrated p-values
Instance-wist wise feature selection No distributional assumptions Robust g(X, x-x) estimation
Table Both AMI-CRT and FAST-AMI-CRT produce well-calibrated p-values, provide false discovery rate (FDR) control (Benjamini and Hochberg, 1995), allow instance-wise feature selection, and make no distri- butional assumptions about the data generating process. This table compares these methods to widely-used feature selection methods.
The set in Equation (4) consists of only features a/" that help increase the likelihood of observing (() given the remaining features x= If the perfect predictions property of q(y x) is true, then <(y - y X-j = ===") can only be less than equal to g(y = y x= x0)),, with equality (8)
when 3 is not important to ( Assuming the sufficient conditions in Proposition 1, we can now construct an IWFS procedure using the same estimators from AMI-CRT or FAST-AMI-CRT.
3.2 AMI INSTANCE-WISS WISE FEATURE SELECTION
Instance-wiss feature selection can be performed using the building blocks of the FAST-AMI-CRT. Starting from Definition
begin by manipulating q(y ( xx)) and marginalizing
We then use Jensen's 's inequality to upper-bound the log of this expectation as follows:
llog log "o (y = =y X, x,,,,, ["]]] N -log q(y (0) x =
E
2 Ng (
(5)
This suggests the following instance-wise test. If the inequality in Equation (5) is strict, the feature considered important. If equality holds in Equation (5), the feature is considered unimportant. Notice that Jensen's 's inequality could introduce slack in this bound that could make a feature seem relevant when it is not. We use Proposition to show that this is not issue.
Recall that given model qo for g(y x) that satisfies the instance-wise sufficient conditions in =
In the case where (6) does not help predict y (0)) (y = ()) x, 2 x- x cannot be greater than q(y = (0) x = x ")), as the former does not depend on x. Then the left-hand side of
Proposition 1, g = (d)) x = x (0) 2 g = (5) x
x
Equation (5) becomes - log gly ( x-j = = a constant with respect to T implying an equality. Therefore, checking for equality in Equation (5) is valid test see if feature is either important or unimportant. In Appendix C.2, we detail an example that shows how scores computed using Equation (5) can help rank features from
least helpful for prediction. We term this procedure the additional mutual information instance-wise feature selection (AMI-IW).
If we computed an expectation over (+)) ( of Equation (5), this procedure resembles FAST- compute these instance-wise log-
AMI-CRT. We can reuse the estimators from FAST-AMI-CRT probability differences for AMI-IW. Therefore, we only use one null estimator for ă (y X,, x-j)- Like FAST- AMI-CRT, we can potentially use a mixture of estimators in AMI-IW, but at the cost of power select important features.
EXPERIMENTS
We compare methods, the AMI-CRT [ami-crt] and fast additional mutual information condi- tional randomization test (FAST-AMI-CRT) [fast -crt] ] to widely-used approaches on vari- ous performance metrics. The basclines are:

---

Under review as a conference paper at ICLR 2020
Dataset
ami mni- fast-ami-crt
loss-hrt
corr-crt
lime
shap
rf
orange 0.97
0.95
0.94
0.22
0.94
0.95
0.94
xor
1.00
0.97
0.95
0.45
1.00
0.99
0.95
Table 2: Simulated data results: Here we use scores provided by each method to select features. AMI-CRT's area under the receiver operating characteristic (ROC) curve is better than other of state-of-the-art methods.
Dataset
ami -1
Toss-hrt
carr-crt
1 me
shap
rf
selector
0.93
0.78
0.34
0.58
0.64
0.33
Precision
noisy-selector
0.67
0.45
0.33
0.57
0.61
0.33
selector 0.95
0.88
0.34
0.35
0.39
0.33
Selector identification
molss--sllece 0.97
0.33
0.25
0.37
0.33
Table 3: Instance-wise fcature selection results. The precision experiment measures the ability of cach selec- tion method to identify relevant features while restricted to 7 features. The selector identification experiment counts the instances where each method identified the selector feature x1 (relevant for all instances).
Correlation [corr-ce crt]: ence between Correlation(x;; Correlation(x,, y) as a test statistic for a CRT
Differ- and
Random forest [rf] feature importance scores
Zero-one loss [loss-hrt]: Binary classifi- cation loss of (y | x) where ga is model for y is used as test statistic in a IRT
Local interpretable model-agnostic explana- tions (LIME) [1 ime] (Ribeiro et al., 2016)
(Tansey et al., 2018)
Shapley additive explanations (SHAP) [shap] (Lundberg and Lee, 2017)
HRTS construct a test by comparing a loss function evaluated x and x; x-j. The choice of loss, however, is left to the practitioner. We study the 0-1 loss, which a proper scoring rule, all of our experiments. In specific settings, we equip IRT with our AMI test-statistic. This method is called the ami -rrt. We show that ami ami-hrt is better calibrated than 0-1 URT. Table presents a sum- mary comparison of the properties of each selection method. We use the regression approach using conditional categorical distribution parameterized with neural networks highlighted in (Miscouridou et al., 2018) to model q(x, |x=}) for all experiments unless specified otherwise.
We simulate data for evaluating each selection method. These tests are designed to highlight the differences between each method.
Simulations:
[xor]: To test the where features on their formation, we use the xor dataset. We first sample x ~ (0, Ep) N times, where Ep is a D- dimensional covariance matrix. We translate the first two dimensions of each sample ( away from the origin in 4 different directions {(s, s), (-s, 8), (s, -s), (-s, -s}} with uniform probability. If the resulting translation has first two coordinates with the same sign, the label is one. Otherwise, it zero. All but the first two features are independent of y. We set N 2000, D 20.
not informative, but together provide in-
[orange]]] (Chen et al., 2018): To test the case where is some nonlinear function of orange dataset. In this dataset, x ~ (N, Ep). y = if exp Σ x 2) > and otherwise, where é < D is the number of important features. We choose N = 3000, D = 20, and = 4.
the
[selector, noisy-selectone selector]: These experiments test instance-wise feature selection meth- ods. We first sample x (O, En) N times, where Ep is D-dinensional covariance matrix, and D 2 11. The first feature X1, called the "selector" feature, determines the feature selection mechanism. We generate y E 10, }} Equation (6). We also investigate the effectiveness of each feature selection method in the presence of noise, and generate E {0, 1] as Equation (7). We set the parameter N- 2000, D 20.
(31,))a) > 0 x
((((B1,x20)) if > ((((2),7.11)) if 5
q(y 1 11
(6)
qly 1|
(32, x7.11 0
if

---

Under review as a conference paper at ICLR 2020
Results. For methods based on CRTs or HRTS, we select features using p-values. For the base- lines that do not produce p-values, we select features using the importance scores provided by each method. We threshold p-values importance scores respectively, and compute ROC curve for each method. We present the mean area under each curve over 100 simulations for the xor and orange datasets in Table 2. We notice that this task is easily solved by most methods apart from corr-crt, This test fails to account for dependencies between features. The ami - -crt achieves a higher AUROC than baselines, while fast aaai--ami-- crt achieves similar performance.
To identify important features in practice, a threshold for importance scores must be chosen. If method produces p-values, we can control the false discovery rate (FDR) (Benjamini and Hochberg, 1995). This is the expected proportion of falsely identified features. An assumption for standard FDR-Controlling procedures is independent p-values (Benjamini and Hochberg, 1995). Therefore, investigate the calibration of p-values across ami -crt, fast past-ami- -crt, corr-crt, and loss-hre We omit other baselines in this comparison as they do not produce p-values and there- fore have no direct FDR-control.
To evaluate each method, use the generating process for the orange dataset, and set N 3000, D = 104, L = 4. the p-values are independent, null p-values should resemble iid draws from Uniform(0.1) 1) distribution. Figure (Appendix D) shows quantile-quantile plot of null p-values. We also perform a Kolmogorov-Smimon (KS) (Massey Jr, 1951) test where the null distribution is Uniform(O,1). All CRT-based methods produce independent p-values, while loss-ha produces deflated and significantly non-uniform p-values (p = 0.0006), implying dependence. As result loss- incorrectly identifies many null features as important. Models for each replication of null features ami crt potentially decrease the correlation of the p-values. The Fast-ani -ort achieves middle ground between the hrt and ami-crt. by yielding well-calibrated p-values while requiring only one null model 9- (y Xj.X_ xxj) per feature. We also investigate the use of ami anit which uses the AMI as a test statistic an HRT in Figure 3.
To better understand the difference between refitting (CRTs) and not refitting (IRTS), we inspect the robustness of each method to poor simulations from the null (poor estimation of q(x; x x=j)). D) We use the orange dataset and set all off-diagonal values of Ep to 0.5. We sample X, from (0, 1). We see in Figure 4 (Appendix D) that refitting protects against poor approximations of gxx, xx5); the p-value distribution for fast East-ami-st mirt is uniform, while the p-value distribution for both HRT methods is significantly non-uniform (p- = 5 x 10-6 for ami -hrt and p = 10-7 for The robustness of f fast-ami -ert t comes from averaging which makes predictions for the original data worse and predictions on the null better regardless of the quality of the null simulations.
For instance-wise feattrr selection, we perform two tests for each selection method. To test HRTS in this setting, we use the procedure prescribed by Burns al. (2019) but with different test statistics. For precision, we identify the 7 (the true # of relevant features per instance) most important features as dictated by each selection method and report average precision scores across held-out test set in Table 3. For selector identification, we count the number of instances where the selector variable was identified. For the se 1 ector task, we notice that the ami-i w achieves the highest precision, followed by the 1 oss-hrt. In the noi sy-sel--eeeee seeeccorrreeeeeeee task, we notice a decrease in scores across all methods with the largest decrease for ami- -iw and loss-hre The noisy-see selesseeeotooooo or case violates the sufficient conditions for instance-wiss feature selection (Equation (4)) meaning that the noise in sampling the response can obscure which features are important. This explains the reduction in performance. Even with the decrease in performance, ami- performs best.
The ami-iw and loss-hrt identify the selector variable x₁ in nearly every sample in our test set. Linear methods like 1 Lime fail because the selection mechanism is highly non-linear. Further, rf and corr-cre are not designed to assign importance at the level of an individual sample and therefore do not provide meaningful scores per instance.
Wellcome Trust Celiac disease: We study data from genomic analysis on Celiac disease (Dubois et al., 2010). For each individual in this dataset, we have a set of single nucleotide polymorphisms (SNPs). SNPs represents genetic variance in the individual with respect to some reference population. This dataset consists of two classes of individuals: cases (n 3796) and controls (n 8154), where the cases are those with Celiac disease. After standard preprocessing steps as prescribed by Bush

---

Under review as a conference paper at ICLR 2020
1759 SNPs remain. To model (x,x(xx-)) we use the same procedures as (Candes et al., 2018) where we estimate g(x, (Xs,) where Sj is only the set of SNPs (not including x,) known to be correlated with xj. To model ( use L -logisticc regression model.
and Moore (2012).
Results. In Table 4, we show the results for all methods with FDR-control. We identify the SNPs that most likely contribute to distinguish- ing between those with Celiac disease and those without it. Since these methods produce p- values, we can select features at a theoretical FDR of 20% using the Benjamini and Hochberg (1995) procedure. We report the percentage of selected SNPs that have been previously shown to be associated with Celiac disease in a bio- logical context as reported by one of (Dubois et al., 2010; Sollid, 2002; Adamovic et al., 2008; Hunt et al., 2008). There are 40 SNPS in total that are both in our dataset and in these papers. Ami-crt: outperforms all other methods tested; fast-ami- cert performs similarly. We also list the SNPs returned by ami-crt in Appendix E. As expected, corr-crt crt selects a large set of features, but achieves fairly low precision. This is because many SNPs are correlated with each other, and all of these seem relevant marginally. The AMI-based methods have better precision and recall compared to Loss-hre potentially both due to aforementioned deviation from uniform and that the zero-one loss may not change when only one out of more than a thousand features gets perturbed.
Method # Selected
Precision
Recall
ami-crt
17
76.47%
32.5%
fast cest-ami-cre
16
68.75%
27.5%
loss-brt
14
57.14%
20.0%
corr-crt 185
6.40%
30.0%
Table 4: The number of significant features reported at a 20% FDR level for cach test, and the percentage of features previously identified in biological study.
Hospital readmission: We use a dataset consisting of ten years of medical logs from over 130 hospitals (Strack et al., 2014). Features in the dataset include time spent in the hospital, medical specialty of attending doctor, age, and various other diagnostic information. Labels for each sample represent one of three events: readmitted within the next 30 days (n 35, 545), readmitted after 30 days (n = 11, 357), or not readmitted (n 54, 864). Due to class imbalance, we grouped all readmitted patients into one category (n 46, 902). We detail further preprocessing steps in Appendix F. To model g we use a random forest classifier with 100 estimators.
Results. The ground truth features come from clinical validation done by (Strack et al., 2014). We use importance scores (or p- values) estimated by each selection method with these ground truth features to compute ROC curve. Figure shows these curves for each method. We observe that ami-crt. and fast-ami-ent under the ROC curve than state-of-the-art ap- proaches. The loss-hrt performs well, but achieves low power at false positive rates less than 0.5. These methods, unlike locally-lineal methods such as 1ime and shap, do not as- sume that relevant features are marginally dependent of irrelevant features (Lundberg and Lee, 2017).
ROC curve for selected features
1.0-
True Positive Rate
0.7
0.6
achieve higher area
0.5
0.4
0.3
0.2
ami-ert loss-hrt
lime shap
0.1
fast-ami-rr
0.0
0.2
0.4
0.6
0.8
1.
ImageNet experiments: We consider the task of differentiating between ambulances and po- licevans. This task is interesting as both objects are physically very similar and there are only few features that can be used differentiate the two. For example, both objects have win- dows, wheels, and doors, so other features must be used to distinguish between the two classes. Rather than consider each pixel as an individual feature X,. we consider a patch of pixels Xş as single feature, such that two patches contain overlapping pixels. To model the distribution
False Positive Rate
Figure 1: Using results from (Strack al., 2014) as clinically validated ground truth, we observe that AMI-CRT is able to achieve the highest area under the receiver operating characteristic curve (AUROC) when compared to state-of-the-art benchmarks.

---

Under review as a conference paper at ICLR 2020
FBI POLICE
PBI POLICE
Instance-wis wise feature selection using AMI. The first and third columns show the original image of ambulances or policevans respectively. The second and fourth columns show only the patches which were found to have non-zero AMI with the label, given the rest of the patches.
Figure 2:
((X3|X x-s), make use of generative inpainting model Ty (Yu et al., 2018). We split the image into an x grid so that there are 64 non-overlapping Xş patches. To model g(y x), we use a VGG-16 network (Simonyan and Zisserman, 2015). To perform instance-wisg wiie test, compute log-probability differences using fifty generated samples from (xxs|x_5) for each patch.
we show a subset of results of AMI-IW. The first and third columns show the original images for each class: ambulance and policevan respectively. The second and fourth columns mask out the original image in patches where the patch is not found to be relevant to the prediction. The model used estimate q(y'x) x) is able to achieve roughly 90% accuracy a held- out test set. We see that our predictive model uses relevant details like the words "ambulance" or "police" printed on the vehicle to distinguish between each class. The model also tends to ignore objects like windscreens and other features shared across classes, as is expected. These results indicate that the difference in log probabilities between model using the true data, and one using Xs sampled from xxxs x-s) works well in determining a relevant set of features even on an instance- wise level. We show several additional images in Figure 5, Appendix G. We also compare our method to local interpretable model-agnostic explanations (LIME) and shapley additive explanations (SHAP) (Figures 6 and 7). Both methods perform reasonably well on this task, but identify objects that are known be common to both classes like wheels and headlamps. Neither method identifies writing on the vehicles the images. This likely because the simplifying assumptions made by these locally- linear methods. They assume that the set of relevant features is independent of the set of irrelevant features, which may not be the case in images. For example, the location of the word "ambulance" may depend on the window position.
Results. In Figure 2,
DISCUSSION
We develop AMI-CRT for testing for conditional independence of each feature xj y x-j from a finite sample from the population distribution. AMI-CRT uses the KI.-divergence to cast inde- pendence testing as regression and allows for the reuse of code from building the original model from the features to the response. We develop FAST-AMI-CRT which requires less computation than AMI-CRT and is robust to poor estimation of the null conditional. We define sufficient conditions under which to perform instance-wist wise feature selection and develop the AMI-IW, an instance-wist feature selection method built from the pieces of FAST-AMI-CRT: AMI-CRT, FAST-AMI-CRT, and AMI-IW all outperform several popular methods. in various simulated tasks, in identifying biolog- ically significant genes, selecting the most indicative features to predict hospital readmissions, and in identifying distinguishing features in image classification task.
REFERENCES
Adamovic, S., Amundsen, S., Lie, B., Gudjonsdottir, A., Ascher, H., Ek, J., Van Heel, D., Nilsson, S., Sollid, L., and Naluai, Å. T. (2008). Association study of i12/i121 and fegriia: significant association with the i12/i121 region in scandinavian coeliac disease families. Genes and immunity, 944:366
Barber, R. F., Candès, E. J., et al. (2015). Controlling the false discovery rate via knockoffs. The Annals of Statisties, 23(5):2055-2085.

---

Under review as a conference paper at ICLR 2020
Barut, E., Fan, J., and Verhasselt, A. (2016). Conditional sure independence screening. Journal of the American Statistical Association, 111(515):1266-1222
Benjamini, Y. and Hochberg, Y. (1995). Controlling the false discovery rate: practical and powerful approach to multiple testing. Journal of the Royal statistical society: series B (Methodological), 57(1):289-300.
Burns, C., Thomason, J., and Tansey, W. (2019). Interpreting black box models with statistical guarantees. arXiv preprint arXiv: 1et.11944000555
Bush, W. S. and Moore, J. H. (2012). Geneme-wide association studies. PLoS computational
biology, 1002822..
Candes, E., Fan, Y., Janson, I.., and Lv, J. (2018). Panning for gold: modd''mdel-x'knooeee knockoffs for high dimensional controlled variable selection. Journal of the Royal Statistical Society: Series (Sta- fistical Methodology), 80(3)5511-577.
Chen, J., Song, L., Wainwright, M. J., and Jordan, M. I. (2018). Learning to explain: An information-thcoree perspective model interpretation. arXiv preprint arXiv:1802.07814.
Csiszár, (1964). Eine informationsthhorrtichhe ungleichung und ihre anwendung auf beweis der ergodizitaet von markoffschen ketten. Magyer Tud. Akad. Mat. Kutato Int. Koezl., 8:85-108.
Dubois, P. C., Trynka, G., Franke, L., Hunt, K. A., Romanos, J., Curtotti, A., Zhernakova, A., Heap, G. A., Ádány, R., Aromaa, A., et al. (2010). Multiple common variants for celiac disease influencing immune gene expression. Nature genetics, 42(4):295.
Fan, J. and Lv, J. (2008). Sure independence screening for ultrahigh dimensional feature space. Journal of the Royal Statistical Society: Series (Statistical Methodology). 70(5):849-911.
Fisher, R. A. (1937). The design of experiments. Oliver And Boyd; Edinburgh; London.
Friedman, J., Hastie, T., and Tibshirani, (2001). The elements of statistical learning, volume 1. Springer series in statistics New York.
Gimenez, R. and Zou, J. (2019). Discovering conditionally salient features with statistical guar- antees. arXiv preprint 1rXiv:1905.12117
Gneiting, T. and Raftery, A. E. (2007). Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-377
Hunt, K. A., Zhernakova, A., Turner, G., Heap, G. A., Franke, L., Bruinenberg, M., Romanos, J., Dinesen, L. C., Ryan, A. W., Panesar, D., al. (2008). Novel celiac disease genetic determinants related to the immune response. Nature genetics, 40(4):395.
Lu, Y., Fan, Y., Lv, J., and Noble, W. S. (2018). Deeppink: neural networks. In Advances in Neural Information Processing Systems, pages 8676-8686.
reproducible feature selection in deep
Lundberg, S. M. and Lee, S.-I. (2017). A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pages 4765-4774
Massey F. J. (1951). The dolmogorov-smimat test for goodness of fit. Journal of the American statistical Association, 46(253):68-777
Miscouridou, X., Perotte, A., Elhadad, N., and Ranganath, R. (2018). Deep survival analysis: Non- parametrics and missingness. In Machine Learning for Healthcure Conference, pages 244-256.
Müller, A. (1997). Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443.
Ranganath, R. and Perotte, A. (2018). Multiple causal inference with latent confounding. arXiv preprint arXiv: 002.08273.

---

Under review as a conference paper at ICLR 2020
Ribeiro, M. T., Singh, S., and Guestrin, C. (2016). Why should trust you?: Explaining the pre- dictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1 1135-1144, ACM.
Shrikumar, A., Greenside, P., and Kundaje, A. (2017). Learning important features through prop- agating activation differences. In Proceedings of the 34th International Conference on Machine Learning-Vool Voluue 70. pages 3145-3153. JMLR. org.
Simonyan, K., Vedaldi, A., and Zisserman, A. (2013). Deep inside convolutional networks: Visual- ising image classification models and saliency maps. arXiv preprint arXiv: (512.613116604
Simonyan, K. and Zisserman, A. (2015). Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations.
Sollid, L. M. (2002). Coeliac disease: dissecting complex inflammatory disorder. Nature Reviews Immunology, 2(9):647.
Strack, B., DeShazo, P., Gennings, C., Olmo, L., Ventura, S., Cios, K. J., and Clore, J. (2014). Impact of hbalc measurement on hospital readmission rates: analysis of 70,000 clinical database patient records. BioMed research international, 2014.
Strumbelj, E. and Kononenko, I. (2014). Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41(3):647-665
Sundararajan, M., Taly, A., and Yan, Q. (2017). Axiomatic attribution for deep networks. In Pro- ceedings the 34th International Conference Machine Cearning-Vollume 70, pages 3319- 3328. JMLR. org.
Tansey, W., Veitch, V., Zhang, H., Rabadan, R., and Blei, D. M. (2018). The holdout randomization test: Principled and easy black box feature selection. arXiv preprint arXiv:181 1.00644
Turner, R. (2016). model explanation system. In 2016 IEEE 26th International Workshop on Machine Learming for Signal Processing (MLSP), pages 1-6. IEEE.
Yoon, J., Jordon, J., and van der Schaar, M. (2019). INVASE: Instance-wise variable selection using neural networks. International Conference on Learning Representations.
Yu, J., Lin, Z., Yang. J., Shen, X., Lu, X., and Huang, T. S. (2018). Generative image impainting with contextual attention. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5505-5514.

---

Under review as a conference paper at ICLR 2020
A ALGORITHMS
A.1 AMI-CRT ALGORITHM
We show the AMI-CRT procedure in Algorithm 1, and the FAST-AMI-CRT procedure in Algo- rithm
Algorithm 1: k-fold AMI feature selection
Input: a E RRNDD feature matrix; E R labels
Output: p. the p-values for æ; y x- Vj
Split x and into M folds, G1. G2. GM
for j E [1. D] do
Estimate 4o == go (x) x)-))
0
for m E 21,
M] do
Estimate 93 (m) = ( (G (()
h h + M (y (Gm) ((Gm)), where La is an log-likelihood estimate using 93 end
(m)
Let h be K-dimensional vector of Os .K]
for & E .., do
Sample Ø; Q0
for m E [1.2....,A) M do
(k,m)
q3 y (G-m) (G m) D- m))
Estimate 93
Let h
(k)
+ M f (Gm) (m(0m) x (Gm)), where Lg is log-likelihood
(k)))
estimate using
end end
1 K+I 1+ Ek=1 1 (hh )
Let Dj
end
A.2 EAST-AMI-CRT ALGORITHM
Algorithm 2: FAST-AMI-CRT
Input: æ E NR feature matrix; E R., labels
Output: p. the p-values for æj y x- Vj
Fit qo 43 (y σ²)
for j (1....... do
Fit qo == (=( x=
Let be a dataset such that .-j = x and By is randomly sampled from go(a) x x>-))
Fit g. ( T.. x
Let h, + E [log (1 ( x)) (4 x))] with respect to dataset (æ:, y)
for k E [1. ...., K] do
Let (ik) be dataset such that ブ-, = x -z and ā. is randomly sampled from
qo (x x=))
Let (.(
E llo ( x)) ( ] with respect dataset (ă;
end
1+ K 1 [n
Let Dj = K+
end

---

Under review as a conference paper at ICLR 2020
B PROOFS AND DERIVATIONS
B.1 DIVERGENCES ARE PROPER TEST STATISTICS
In this section, we prove that divergences are proper test statisties. Let DN = f .y xx ,-) and 2 == {arj ( (5) Jiz-- We first list the assumptions here:
1. Let ((Dx) be a consistent estimator of (x(x_))(((((x))) x-)). | x-5)q(y
x x-))]].
2. Let ((D),n) be consistent estimator of (X) | x-)) (x) {x
x x-j)]].
3. The cumulative distribution functions of t(Dx) and t(Dg,v) are both continuous every- where.
4. We have access to complete conditionals g(X, x-
Proof. We prove that is proper test statistic if and only if t(En) is consistent estimator of E [ x-j).
x-j)rly x-;))]. We do this by showing yields p-values that are zero under the alternate hypothesis and uniformly distributed under the null.
Recall that the p-value for our test is:
[ -(D,,) s =0]]
Pj (DN)
E M ())
Under the alternate hypothesis Consider the case where x; y X-j. j. As N - oc.
t(D,,)) & Ei (ā, (K x-y) (x) x-1) (y x-))) = 0,
where L indicates convergence in probability.
Since x, I X-j. notice also that
t (Dx) 2 x
x-)) (xxx) |x5))(y) ( > 0,
Therefore, the term inside the expectation in the p. (Dx) above is always 0, yielding p-value of 0 in limit of N. Since these p-values converge in probability to a single point, the p-values converge in distribution delta mass at O.
x-j. the samples in qN (y,x) and @y (y, Xj, x-;) are both sampled from the same distribution q Qj. Therefore, the distribution of t(Dxx as a function gv. is the same as that of (D),.)) as a function of Nj
Under the null hypothesis In the case where x,
Let Fy be the cumulative distribution function of ((D,,N) which in this case is the same that of ((Dx).
We rewrite the p-value expression as PIN = P2(Dx) = - (((D)N)&((D>) = (x(((D)))
Now let (-) be the generalized inverse cumulative distribution function which exists because FN is continuous everywhere function. With this, we derive the distribution the p-value:
PO = $F)) - = F (p)
FF (p) = p.
This means p N uniformly distributed under the null. This result holds for all values of N. Thus p forms sequence of random variables, indexed by N, that are identically distributed uniform random variable over [0, 1]. This means that the sequence converges in distribution to a uniform distribution over [0, 1].

---

Under review as a conference paper at ICLR 2020
This shows that t is a proper test statistic.
Continuity of Fy Earlier, we assumed the cumulative distribution function (CDF) (((N)))) P(I(D),)) & I(Dx)) was continuous everywhere. This is required for the generalized inverse distribution function FN" to be well-defined on the full range [0, 1].
Discontinuities could oceur when the event ((D)) (D),,) occurs with some non-zero proba- bility This means that the p-value does not take all the values in [0. 1]. To see this, note that (x(() ø [a, + e) for some x [0, c).. c).
To remedy this, we can replace the indicator function in our test-statistic with the following func- tion:
if < b if > b, if a = b where Uniform([O, 1)) is continuous uniform random variable.
1(a 6)
(Uniform[0). ((0, 1])
With this new function, consider the events, ((Dx) = ((D,,x) and I(DN) # ((D),v). Conditioning on t(Dx) t(D).v). the distribution of the p-value is the same as the uniform random variable: : Uniform( (0, 1]). Also note that the distribution F- t(Dx) * t(D,,)) continuous everywhere in its support because t(Dx) = t(D,,v) occurs with zero probability.
Thus, this modification ensures that the p-values are distributed uniformly.
C INSTANCE-WEL FEATURE SELECTION EXAMPLES
C.I CONSISTENT PREDICTIONS ALONE ARE INSUFFICIENT FOR INSTANCE- FEATURE SELECTION
Recall our sufficiency condition for instance-wise feature selection as mentioned in Proposition 1. In this example, we what happens when this condition does not suffice to reject an unimportant feature. Consider a simple data generating process:
met. We notice that this definition
= zx1 + (1 z) x)x² +
~ Bernoull((0.5)
X1, X2 NO x)
e~ -00,00
where is not observed. We can now write out the probability distributions care about. Note that taking an expectation like (x X1x2) yields q(y|x²) For simplicity, we leave out the of complete conditions and work directly with the latter probability distributions:
p(y|x1, x2, = N (2x1 + (1 o?)
p(ylx1,x2) = / p(y|xi, x2, z) z)p(zz X1, x2)dz= / p(y|xi, z)p(2)dz 2))
1
V (xI, o?) + 2 N (x2,
2
1
p(y[x)) = V (0. of + o.) + / (x,, 0?)
2
p(y[x)) 5 N (x), + N (0, oz + o?)
Now consider an instance (a , x2 y 2(0) where z(1 = which means that ( depends only
on feature x; (8) Now check if p |oo(1) (10)) ply (1) (1)())))) (0)) Using our definitions from

---

Under review as a conference paper at ICLR 2020
earlier, we expand this inequality: ply | x2 ) ply (x()) 2 az o?.) 22 (, +
For all such that ( lies in non-O interval around 22 ( have that p/ xx,2) ((y(") (1) > O. For example let 0, dR = 1, then 22 we have that E [3, 17] satis- fies this. This means that 22 will be deemed important per the candidate Proposition
C.2 INSTANCE- WISE SCORE EXAMPLE
In this example, tures for a given instance, under the assumptions stated in Proposition 1. Consider simple data generating process:
how scores computed using Equation (5) can help identify important fea-
y
2|x²
2, X, X2 ~ Bernoulli(0.5)
where all random variables are observed. Let us now consider the following observed instance:
(y)
Ti 22 (0) = 01, We can now devise a test for each of æ 22 and (()) For
(i)
(())
(i)
aj we want to check:
p a
I2 (1)
p(y
(7)
(8)
We create similar tests for the other two variables well:
p [ 22 (i)
(e)
(5)
p 1 (1)
(9)
p
22 (0) p
(10)
We can use Table to help evaluate Equations (8) to (10):
p 1|2(1) x2 1,
0)
(1y 1|x2 (i)
1, x 0)
(0) = 1 = 0, (0) ( = 0) 0.5
pgy ( 1|m] 0, m2 1) 0.5
(1)
meaning x is not important to ( but x and (i) are important.
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
1
0
1
Table Full distribution for example in Appendix C.2
D SIMULATED DATA FEATURE SELECTION ADDITIONAL RESULTS
In this section, we present additional results that use AMI as test statistic in a HRT framework. This offers significant speedup as the IRTT framework avoids having to refit estimators using æ, g(,, x_,). Figure shows a -uantile-qaantile plot of the null p-values for each FDR-controlling feature selection method. We notice that both HRT-based methods tend to deflate p-values. This often results features being mistakenly selected as important. Using the same test statistic, AMI, in CRT helps mitigate this issue.

---

Under review as a conference paper at ICLR 2020
p-value Q-Q plot
1.0
ami-crt (p=0.8643)
fast-ami-crt (p=0 4459)
0.9
loss-hrt (p=0,0006)
ami-hrt (p=0.1033)
(p=0.0621)
0.8
0.7
Sample Quantiles
0.6
0.5
0.4
0.3
0.2
0.1
0.0
0.2
0.6 Theoretical Quantiles
0.4
0.8
1.0
Figure 3: Quantile-Quantil plot showing uniformity of p-values across various FDR-COntrolling methods. A Kolmogorov-Smirmov (KS) test is performed to test if each set of p-values is uniformly distributed.
E CELIAC DISEASE GENOMIC FEATURE SELECTION
Table shows the set of SNPS deemed significant by AMI-CRT. We annotate each SNP with its position in the human genome, and whether it was previously reported significant in a biological study.
Position
SNP
Featured previous study
chr2:102454108
rs917997
yes
chr2:68371823
1s17035378
yes
chr3:159947262
1s17810546
yes
chr3:188394766
rs1464510
yes
chr3:46193709
1s13098911
yes
chr4:122194347
rs13151961
yes
191
rs2327832
yes
chr6:26451325
rs2237236
yes
chr6:28423688
rs2859365
chr6:29505139
rs757256
no
chr6:29844253
rs2734994
1646:31642909
rs rs1052486
no
chr6:32638107
rs2187668
yes
chr6:90216893
rs10806425
yes
chri 1:1285110000
rs 12213332
yes
chr12:11 1hr12211156995
1569952
rs653178
yes
chr21 24:4222222538
rs4819388
yes
Table 6: This table details each SNP returned by AMI-CRT, whether was featured in previous biological study relating to Celiac disease, and its position on the human genome.

---

Under review as a conference paper at ICLR 2020
p-value Q-Q plot
1.0
fast-ami-crt (p=0.4248)
loss-hrt (p=1.1867e-07)
0.9
ami-hrt (p=5.1010e-06)
0.8
0.7
Sample Quantiles
0.6
0.5
0.4
0.3
0.2
0.0
0.2
0.6 Theoretical Quantiles
0.4
0.8
1.0
Figure 4: Quantile-Quantiee plot showing uniformity of p-values across various FDR-controlling methods in the of poor approximations of q(;; x-j)- A Kolmogorov-Smimov (KS) test is performed to test if each set of p-values is uniformly distributed.
F HOSPITAL READMISSION FEATURE SELECTION
For the hospital readmission dataset, we applied several standard pre-processing techniques. We filtered each sample the data in a manner similar to (Strack et al., 2014):
It is an inpatient encounter (a hospital admission).
It is diabetic encounter, that is, one during which any kind of diabetes was entered to the system as a diagnosis.
The length of stay at least day and most 14 days.
Laboratory tests were performed during the encounter.
Medications were administered during the encounter.
Further, binarized the labels so that a label of indicates a readmission event, and label of indicates no readmission event. We then encoded each categorical feature as one-hot encoding. We then imputed missing values using the median across the dataset, and dropped the "weight" feature as it was found to be 97% missing.
To sample from the complete conditional distributions q(x, x_)), we used neural network to fit the complete conditional regression detailed in (Miscouridou al., 2018). For continuous values of xj. we first discretized the data into bins, then used our neural network to predict the bins. To map the bins back values in the domain of x,, we used the mean of the range of values in each bin.
G IMAGENET INSTANCE-VE WISE FEATURE SELECTION
Figure shows some of the results instance-wixt wise feature selection on ImageNet data using AMI- CRT. Figures 6 and 7 show results the same task, using LIME and SHAP respectively. We notice

---

Under review as a conference paper at ICLR 2020
that AMI-CRT identifies patches that seem more likely to help differentiate between ambulances and policevans. AMI-CRT identifies relevant text like the words "ambulance" or "police" that are very likely to help distinguish between the two classes. LIME identifies some relevant features of the image like wheels and lights, but fails to identify relevant words. SHAP does a good job at identifying distinguishing symbols like the caduceus and the FBI logo, but occasionally misses on relevant text.
Ambulance (original)
Ambulance (masked)
Policevan (original)
Policevan (masked)
COANMSS
POLIZII
FDI
POLICE
FBI
POLICE
UKY BII
AMBULANCE
DUCE
DuicE.
Figure 5: Instance-wis feature selection using AMI-CRT. The first and third columns show the original image of ambulances or policevans respectively. The second and fourth columns show only the patches which were found to have non-zero AMI with the label, given the rest of the patches.

---

Under review as a conference paper at ICLR 2020
Ambulance (original)
Ambulance (masked)
Policevan (original)
Policevan (masked)
ORAMES
POLIZEI
FBI
POLICE
AMBULANC
DUICE
Figure 6: Instance-wist feature selection using LIME, The first and third columns show the original image of ambulances or policevans respectively. The second and fourth columns show only the patches which were found to be important.

---

Under review as a conference paper at ICLR 2020
Ambulance (original)
Ambulance (masked)
Policevan (original)
Policevan (masked)
PELRY,
0RAMSS
POLIZEI
FBI
POLICE
POLICE
AMBULANC
AMBULANC
DUICE
PONKS
POLICE
Figure Instance-wist feature selection using SHAP. The first and third columns show the original image of ambulances or policevans respectively. The second and fourth columns show patches that are found to contribute to the label. Green indicates patch found relevant for the ambulance class, and red indicates patch found relevant for the policevan class.


Reviews:
[{"review_id": "rkgGvZb3KS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a practical improvement of the conditional randomization test (CRT) of (Candes et al., 2018).\nIn the study of (Candes et al., 2018), the choice of the test statistic as well as how one estimates conditional distributions were kept open.\nThe authors proposed \"proper test statistic\" as a promising test statistic for CRT, and proved that f-divergence is one possible choice.\nThey further shown that KL-divergence has a nice property among possible f-divergences: KL-divergence cancels out some of the conditional distributions, and thus the users need to estimate only two conditional distributions to compute the test statistic.\nFor estimating those conditional distributions in the test statistic, the authors proposed fitting regression models.\n\nOverall, I think the paper is well-written and the idea is stated clearly.\nThe use of KL-divergence for CRT seems to be reasonable.\nThe proposed algorithms look simple and easy to implement.\n\nMy only concern is on the practical applicability of the proposed algorithms (which, however, may be not a unique problem for this paper, but for all the CRT methods).\nThey require fitting regression models for each feature xj.\nFor high-dimensional data with more than thousands of features, fitting regression models for all the features seem to be impractical.\nFor the imagenet data experiment, the authors successfully avoided this problem by using an inpainting model.\nHowever, this approach is apparently limited to image data.\nI am interested in seeing if there is any promising way to make the algorithms scalable to high-dimensional data.\n\n\n### Updated after author response ###\nThe authors have partially addressed my concern on the scalability of the proposed algorithm to high-dimensional data.\nI therefore keep my score unchanged.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1eV9y2k5r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a method to provide some level of interpretation on the influence of input features on the response of a machine level model all the way down to the instance level. The proposed method is model agnostic. Quoting the authors, they advocate for methods that look at interpretability “as understanding the population distribution through the lens of the model” without restriction on the models fit. The problem is posed as a hypothesis testing problem. The paper proposes “proper test statistics” for model agnostic feature selection. It is argued that f-divergence tests are proper statistic tests, with the KL being particularly interesting as it provides computational advantages. \n\nI have found the paper interesting. The topic is relevant and the approach is interesting. However, I have two main reservations for this work. First, I have found the method difficult to follow and sometimes unclear. Important results are only explained in the appendix. For instance, the derivation of Equation 5 is important but only shown in the appendix. Furthermore, that derivation in the appendix needs to be clarified in my view. For instance, on page 15, for the derivation of $\\delta_I$, can you explain how you went from the second equality to the third equality where references to \\tilde{x}_j are removed from one line to another? It could be due to your definition for the term with a conditional independence\twith the outcome assumed but I suggest that you clarify this as it is important for the paper and for the use of the KL. Also, in this equation, should it be $q(x_j|x_{-j}) instead of $q(x_j,x_{-j})$?\n\nThe second issue that I have is with the experiments. Any reason why the key results on the interpretability of the approach are mostly shown in the appendix (e.g., table 4,5,6)?  Why does table 6 not show results for all the baselines? For the hospital readmission use case, were you able to also get percentages of important features and have it compared with the baselines and vetted for clinical significance? This is more minor but worth double checking in my opinion. For this experiment on re-admission, the paper claims to have data from 130 hospitals for 10 years. Yet the n numbers seems pretty small to me. Total number of events < 100 000 for 130 institutions over 10 years. That would mean that we are dealing with less than an average of 80 admissions per institutions per year. Please confirm or explain if any filtering was done beyond what is described in appendix I. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xZGoOhFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Paper summary\n\nThis paper addresses supervised feature selection: given a D-dimensional input variable x = (x_1, ..., x_D), and a response variable y, the goal is to find a subset of \"useful\" features in x. Here, a feature x_j is useful if it is dependent on y even when conditioning on all other input variables (denoted by x_{-j}, which is a set). A generic procedure that can produce a p-value for each feature (allowing on to test each feature whether it is useful) is the conditional randomization test (CRT) proposed in Candes et al., 2018.  For the CRT to produce a valid p-value for each feature (input dimension) x_j, one needs to specify a test statistic that measures conditional dependence between x_j and y given the rest of the features.\n\nThis paper contributes the following results:\n\n1. Propose using an estimate of the f-divergence for the conditional dependence measure and use it with the CRT (section 2.2).  \n\n2. Measuring the conditional dependence with an f-divergence requires estimating a few conditional density functions. The paper considers the KL divergence as a special of f-divergence. This particular choice turns out the reduce the number of conditional density functions that have to be estimated (section 2.3). The paper also shows that the resulting conditional measure coincides with what is known as the Additional Mutual Information (AMI) studied in Ranganath & Perotte, 2018.  \n\n3. The paper also studies instance-wise feature selection i.e., selecting a subset of input features which can explain the response specifically for one instance (example) x.  Yoon et al., 2019 proposed a criterion to decide the importance of a feature for instance-wise feature selection (definition 2). Briefly, a feature x_j is deemed important if q(y | full x) > q(y | x without the jth feature), where q is the conditional density function of y given x. _Contribution_: The paper notes that this criterion may fail and derive sufficient conditions (Definition 3) under which this approach will always work.  \n\nIn simulation on toy problems, the paper shows that the proposed method (KL divergence + CRT) has the highest mean under the ROC curve (Table 2), compared to competing methods. In real problems on images, the paper shows that the proposed instance-wise feature selection can be used to select relevant image patches (features) that explain the class of the input images. The paper also conducts experiments on hospital readmission data (Section 4.3), and genomics data (Section 4.2).\n\n\n\n# Review\n\nThe paper is overall well written with some parts that can be improved (details below). Introduction and related work in section 1 are easy to follow. The paper is also mostly self-contained and friendly to non-specialists who may not work on feature selection primarily. My concerns are\n\n1. I find that the amount of contribution is not sufficient. CRT is known from Candes et al., 2018. The present paper proposes using KL-divergence with it. This can be interesting if the combination gives some clear advantages.  Unfortunately I do not find that this is the case. It turns out that one still needs to learn two conditional density functions (see lines 3-4 in Algorithm 1). Further and even more concerning, one has to refit another conditional density function *for each draw from the null distribution* (see \"Fit regression\" in the loop in Algorithm 1). As an intermediate step for solving the original feature selection problem, I find that learning conditional density functions is a much more difficult problem. All these limit the novelty of the idea. While the title of the paper contains \"model-agnostic\", the idea of fitting conditional density functions seems to contradict it. The paper could have considered some nonparametric conditional dependence measures but did not. For instance, see \n\nKernel-based Conditional Independence Test and Application in Causal Discovery\nKun Zhang, Jonas Peters, Dominik Janzing, Bernhard Schoelkopf\n2012\n\nand other papers that extend this paper.\n\nWhy was the approach of fitting conditional density functions chosen?\n\n2. Related to the previous point, refitting a conditional density model for each draw from the null distribution must be very costly computationally. This point is never addressed in the paper.\n\n3. Lemma 1 states that the expected f-divergence is a \"proper statistic\" (in the sense of Definition 1) i.e., p-value is uniformly distributed if the feature is not useful, and vanishes (asymptotically) if the feature is useful. This result unfortunately relies on a strong assumption that there is a consistent estimator for the f-divergence. In fact, the proof does not even rely on the fact that it is an f-divergence. It can be any divergence D(p,q) such that D(p,q) > 0 if  p!=q and D(p,p) = 0. In the proof in section C.2 in the appendix, existence of the quantile function $(F^{-1}_N)$ is never discussed. I can see the first part of the proof (under the alternative H1). But I do not see the second part (under H0). Since $\\hat{f}$ is a consistent estimator by assumption, as N goes to infinity, the two quantities in the indicator function (in expectation) should both go to the same constant. Isn't this the case? \n\n4. As a contribution, the paper states a sufficient condition in Definition 3 under which instance-wise feature selection with the approach in Definition 2 is *always* possible. When does the condition hold in practice? How do we know if it holds or not? If it does not, what can go wrong?\n\n5. Toy experiments: What is D in Xor and Orange? Where is the \"selector\" problem in Table 2? In table 2, \"lime\" and \"shap\" also seem to perform well. The paper never explains why the proposed approach is better than other methods (only reporting higher mean are under the ROC curve). This should be possible for toy problems.\n\n\n\n# Minor but does affect the evaluation\n\n* Paragraph after Lemma 1: it is unclear why those conditional distributions are required instead of conditional distributions in Eq. 3.\n\n* Section E.1 (appendix), page 16: I think you should have $N( 0.5x_1 + 0.5x_2, \\sigma^2_\\epsilon)$ instead of \n$0.5N(x_1, \\sigma^2_\\epsilon) + 0.5N(x_2, \\sigma^2_\\epsilon)$.\n\n\n\n# Things that can be improved. Did not affect the score.\n\n* Section 1.1: the sentence about permutation tests is vague.\n\n* Page 2, our contributions: \"necessary\" should be \"sufficient\"?\n\n* Section 2, conditional randomization tests: This paragraph is unfortunately not well written even though it is a very important prerequisite of this work. For instance, at \" ... replaced by samples of $\\tilde{x}_j^{(i)}$ that is conditionally independent of the outcome...\", at that point, it is unclear \"conditioning on what\". Following this sentence, one approach might be to replace $\\tilde{x}_j^{(i)}$ with a constant (which is independent of everything else). It is not until definition 1 that this becomes clearer. Also, the \"null hypothesis\" (which is in the first line of equation 2) is never stated throughout the paper.\n\n* Eq 1: that (i) is unclear. Should state that for i=1,...,N.\n\n* Eq 2: rewrite the second line. The left hand side states that the p-value \"converges in distribution to\". The second line should be just 0.\n\n* After eq.6, how to choose T (the number of bins) in practice?\n\n* Definition 3 is actually a proposition? It is unclear what is being defined there.\n\n* The word \"complete conditional knockoffs (CCKs)\" appears for the first time in Section 3.2 without any explanation.\n\n* Orange skin on page 8: what is \"~ exp(...)\"? An exponential distribution, or just exponential function?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an approach to feature selection. Reviews were mixed and questions whether the paper has enough substance, novelty, the correctness of the theoretical contributions, experimental details, as well as whether the paper compares to the relevant literature.  
Decision: Reject