Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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. 

I 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	with 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})$?

The 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. 
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: # Paper summary

This 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.

This paper contributes the following results:

1. Propose using an estimate of the f-divergence for the conditional dependence measure and use it with the CRT (section 2.2).  

2. 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.  

3. 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.  

In 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).



# Review

The 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

1. 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 

Kernel-based Conditional Independence Test and Application in Causal Discovery
Kun Zhang, Jonas Peters, Dominik Janzing, Bernhard Schoelkopf
2012

and other papers that extend this paper.

Why was the approach of fitting conditional density functions chosen?

2. 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.

3. 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? 

4. 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?

5. 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.



# Minor but does affect the evaluation

* Paragraph after Lemma 1: it is unclear why those conditional distributions are required instead of conditional distributions in Eq. 3.

* Section E.1 (appendix), page 16: I think you should have $N( 0.5x_1 + 0.5x_2, \sigma^2_\epsilon)$ instead of 
$0.5N(x_1, \sigma^2_\epsilon) + 0.5N(x_2, \sigma^2_\epsilon)$.



# Things that can be improved. Did not affect the score.

* Section 1.1: the sentence about permutation tests is vague.

* Page 2, our contributions: "necessary" should be "sufficient"?

* 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.

* Eq 1: that (i) is unclear. Should state that for i=1,...,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.

* After eq.6, how to choose T (the number of bins) in practice?

* Definition 3 is actually a proposition? It is unclear what is being defined there.

* The word "complete conditional knockoffs (CCKs)" appears for the first time in Section 3.2 without any explanation.

* Orange skin on page 8: what is "~ exp(...)"? An exponential distribution, or just exponential function?

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper proposes a practical improvement of the conditional randomization test (CRT) of (Candes et al., 2018).
In the study of (Candes et al., 2018), the choice of the test statistic as well as how one estimates conditional distributions were kept open.
The authors proposed "proper test statistic" as a promising test statistic for CRT, and proved that f-divergence is one possible choice.
They 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.
For estimating those conditional distributions in the test statistic, the authors proposed fitting regression models.

Overall, I think the paper is well-written and the idea is stated clearly.
The use of KL-divergence for CRT seems to be reasonable.
The proposed algorithms look simple and easy to implement.

My 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).
They require fitting regression models for each feature xj.
For high-dimensional data with more than thousands of features, fitting regression models for all the features seem to be impractical.
For the imagenet data experiment, the authors successfully avoided this problem by using an inpainting model.
However, this approach is apparently limited to image data.
I am interested in seeing if there is any promising way to make the algorithms scalable to high-dimensional data.


### Updated after author response ###
The authors have partially addressed my concern on the scalability of the proposed algorithm to high-dimensional data.
I therefore keep my score unchanged.
review_title: Official Blind Review #1

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