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. Model interpretation techniques aim to select features important for a response by reducing models (sometimes locally) to be human interpretable. However, the phrase model interpretation can be a bit of a misnomer. Any interpretation of a model must be imbued to the model by the population distribution 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 a model. Existing methods for understanding the population distributions only work with particular models fit to the population, 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 a smaller class of population distributions. To be able to work in a black-box manner, feature selection methods can use models but must not require a particular structure in models used in selection processes. Understanding the population distribution can be phrased as assessing whether a response is independent of a feature given the rest of the features; this test is called a conditional randomization test (Candes et al., 2018) . Conditional randomization tests require test statistics. Test statistics like linear model coefficients (Barber et al., 2015) or correlation may miss dependence between the response 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 implies the conditional-joint factorizes into conditionalmarginals. Measuring the divergence between these distributions yields a proper test statistic. Of the class of integral probability metrics (Müller, 1997) and f -divergences (Csiszár, 1964) , the KLdivergence 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 context has a natural interpretation; it is a measure of the additional information each feature provides about the outcome over the rest. This measure of information is known as the additional mutual information (AMI) . 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 (AMI) of the original data to the AMI of the simulations from Beyond understanding the population distribution, some tasks require interpreting a population distribution 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 et al., 2013; Sundararajan et al., 2017; Ribeiro et al., 2016) and fitting simpler auxiliary models to explain the predictions of a 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 work is most similar to that of Burns 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 selection with predictive models may be possible are not well developed. We address this issue by first identifying a set of sufficient conditions under which instance-wise feature selection is always possible. We then show how estimators used in AMI-CRT can be repurposed for use in an instance-wise setting, yielding a procedure called the AMI-IW. We develop AMI-CRT for testing for conditional independence of each feature x j ⊥ y | x −j from a finite sample from the population distribution. AMI-CRT uses the KL-divergence to cast independence 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-wise feature selection and develop the AMI-IW, an instance-wise 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 biologically significant genes, selecting the most indicative features to predict hospital readmissions, and in identifying distinguishing features in an image classification task. where Lβ is an log-likelihood estimate using q (k,m) β end end Let x be a dataset such that x −j = x −j , and x j is randomly sampled from q θ ( Let x (k) be a dataset such that x −j = x −j , and x j is randomly sampled from and . We first list the assumptions here: 3. The cumulative distribution functions of t(D N ) and t( D j,N ) are both continuous everywhere. 4. We have access to complete conditionals q( Proof. We prove that t is a proper test statistic if and only if t(E n ) is a consistent estimator of We do this by showing t 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: Under the alternate hypothesis Consider the case where whereq j − → indicates a convergence in probability. Since x j ⊥ y | x −j , notice also that Therefore, the term inside the expectation in the p j (D N ) above is always 0, yielding a p-value of 0 in the limit of N . Since these p-values converge in probability to a single point, the p-values converge in distribution to a delta mass at 0. Under the null hypothesis In the case where x j ⊥ y | x −j , the samples in q N (y, x) and q j,N (y, x j , x −j ) are both sampled from the same distribution q =q j . Therefore, the distribution of t(D N ) as a function of q N , is the same as that of t( D j,N ) as a function ofq j,N . Let F N be the cumulative distribution function of t( D j,N ) which in this case is the same as that of t(D N ). We rewrite the p-value expression as p N (·) be the generalized inverse cumulative distribution function which exists because F N is a continuous everywhere function. With this, we derive the distribution of the p-value: Discontinuities could occur when the event t(D N ) = t( D j,N ) occurs with some non-zero probability c. This means that the p-value does not take all the values in [0, 1]. To see this, note that To remedy this, we can replace the indicator function in our test-statistic with the following function: where Uniform([0, 1]) is a continuous uniform random variable. ,N ) , the distribution of the p-value is the same as the uniform random variable : N ) ) is continuous everywhere in its support because t(D N ) = t( D j,N ) occurs with zero probability.
We develop a simple regression-based model-agnostic feature selection method to interpret data generating processes with FDR control, and outperform several popular baselines on several simulated, medical, and image datasets. This paper proposes a practical improvement of the conditional randomization test and a new test statistic, proves f-divergence is one possible choice, and shows that KL-divergence cancels out some conditional distributions. This paper addresses the problem of finding useful features in an input that are dependent on a response variable even when conditioning on all other input variables. A model agnostic method to provide interpretation on the influence of input features on the response of a machine level model down to instance level, and proper test statistics for model agnostic feature selection.