Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors provide a simple yet effective extension of the recently proposed marginal feature importance criterion that allows a fast and accurate estimate of the marginal importance of each feature in the presence of feature correlation and non-linear interactions.
strengths_and_weaknesses: Strengths

A simple but clever extension of the marginal feature importance criterion allows to circumvent the need for enumerating all potential feature subsets, substantially increasing the practical applicability of the approach.

Weaknesses:

The main ingredients were already all in the original paper introducing marginal feature importance. From this perspective the novelty of the work is not dramatic.

There is a lack of intuition in introducing the ultra-marginal feature importance criterion. It would be useful to discuss the role of g and its use in dependency removal when introducing it, possibly providing an illustrative example. Overall, the methodological section is very shallow and should be expanded to better highlight the rationale and relevance of the contribution.

Minor: 

In theorem 3.1, S should be orthogonal to f, not to F.

I suggest to better contextualize the related work or move it to the end of the paper, as it's unclear why certain topics are being discussed (e.g. orthogonal predictors).

AFTER REBUTTAL
The authors improved the clarity of manuscript and better highlighted the significance of the contribution. 

questions: In the proof of Theorem 3.1, you seem to assume that the maximizer of eq. 3 is unique. But what if \tilde{S}^* is also a maximizer of 3? I guess for your scope it is enough that S^* is one of the maximizers, but this should be clarified for the sake of soundness.


limitations: The limitations of the approach are exhaustively discussed in the conclusion on the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes an ultra-marginal feature importance (UMFI) method by extending marginal conditional importance (MCI) methods for evaluating feature importance. Some experiments have been conducted on simulated and real-world data sets.

strengths_and_weaknesses: This paper studies an important problem. The authors have reviewed the related work well. 

The extension of the work from MCI methods is by introducing an information subset in feature importance evaluation. The authors do not justify why an information subset is necessary. I have a few questions about the proposed method.  

When evaluating the feature impotence of f, there needs to find the largest information subset S*, such that f and S* are independent. My question is if there is no such an S*, how the importance of f is evaluated? This is real when all features are correlated. 

I need to be convinced to use the largest information subset S* in evaluating the importance of f. I use a causal effect estimation to understand the solution since feature importance is related to the causal effect of f on Y. When S* is independent of f, it does not ``confound" f in a viewpoint of causal effect estimation. Why should we remove the effect of S* on Y when estimating the effect of f on Y?   

By reading the algorithm, the importance of a feature is related to a model, see Lines 3-5. Do authors mean to explain feature importance in the model? This is not clear in the paper. 

The predictions of a model depend on the parameters in practice. Based on Lines 4 and 5 in Algorithm 1, the importance of a feature can be dependent on the parameters. How do authors avoid the effect of parameter variation on evaluating the importance of a feature? 

---

After discussions.

The authors answered my queries, and their revisions have addressed my major concerns, I raise my overall rate.

questions: See above. 
limitations: Limitation statements are given.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work considers how to quantify the importance of different features in a ML model (for each feature $f$ from the set of all features $F$) to the response variable $Y$. To do so, they modify a method known as "marginal contribution feature importance" (MCFI). In simple terms, rather than measuring the maximum contribution that a feature makes to a subset of other features (where contribution roughly means how much it improves predictive performance), "ultra marginal feature importance" (UMFI) measures the maximum contribution to any random variable that is a function of the full feature set. 

This sounds like it could make computation harder, but in fact the authors prove that it can be computed efficiently by removing $f$'s dependencies/signal from $F$ (in a sense that isn't precisely defined, in my view), and then measuring how the newly trained model's performance degrades. Thus, the computational cost is significantly lower than computing the maximum contribution over $2^{d-1}$ feature subsets (where there are a total of $d$ features).

The authors' proof rests on several assumptions that won't hold in practice, but the method should still give reasonable results. And there is no gold-standard way of removing dependencies, but the authors demonstrate the method with a couple viable options (e.g., residualizing out with linear regression).
strengths_and_weaknesses: ### Strengths

- This work presents a new perspective on how to define feature importance in ML models. Rather than removing/corrupting subsets of features, it considers the maximum contribution that each feature $f$ makes to any random variable that's a function of the full feature set. Leave-one-out or Shapley value approaches wouldn't make sense in the context of arbitrary functions of the features (the value function $\nu$ is no longer a set function, but a function of any random variable), but it's a neat result that the random variable to which a feature $f$ contributes most is somewhat easy to approximate.
- UMFI seems to provide reasonable results in the experiments.

### Weaknesses

About the method:
- The idea of removing dependencies of one random variable from another does not seem to be precisely defined anywhere in the paper. It seems like there is not a unique way to do this - for example, I can remove $f_1$'s dependencies from $f_2$ by setting $f_2$ to a constant. If the only requirement in this work is that the modified $f_2$ variable becomes independent from $f_2$, and the non-uniqueness of the transformation isn't a problem, that should be discussed more prominently.
- The name "information subsets" for $I(F)$ was a bit confusing, it doesn't seem like there are subsets involved here (the way they are in MCI or SAGE). It seems to mean the set of all possible functions applied to the features/input variables. I guess I get the spirit of the name, but it's confusing.
- On lines 55-57, one of the stated issues with MCI is that it underestimates the importance of correlated features. I didn't quite understand how MCI gets correlated features wrong, or how UMFI is supposed to fix the problem - can you elaborate on this? This point doesn't seem very well supported in theory, and it's only supported in a limited sense by the experiments.
- On lines 57-58, one of the stated issues with MCI is that it can give non-zero importance to features unrelated to the model. As UMFI yields strictly larger importance than MCI (this is mentioned later in the paper), UMFI should share this flaw rather than fixing it. The results in Figure 2 don't seem to reflect this, which is very strange.
- I believe the authors are potentially confusing two different meanings of the term "marginal." The authors labeled both MCI and UMFI as "marginal methods", but I don't think they are if you look at what the "marginal vs. conditional divide" is about. The divide is about whether a feature importance method handles held-out features with their marginal or conditional distribution; e.g., KernelSHAP often uses the marginal distribution, and SAGE advocates for using the conditional. Because MCI retrains models for each subset of features, it's actually a *conditional* method, at least approximately (if it's helpful, I can point to a paper that proves how retraining and sampling held-out features from their conditional distribution are approximately equivalent). UMFI on the other hand is *neither* - the models are trained on completely different features so there's no question of re-using a model and sampling replacement values for held-out features. For MCI, "marginal" refers to "marginal contribution" from the game theory context, which has nothing to do with the marginal vs. conditional label. UMFI is also roughly about marginal contributions (even though $\nu$) isn't a cooperative game, so I could see calling it a "marginal contribution" method. But calling both of these "marginal methods" isn't very helpful given the ambiguity.

Some potential issues with the experiments:
- The experiments don't seem to use any real datasets. Even the BRCA experiment synthetically modifies certain features to ensure that they're unimportant to the response variable. Would it be possible to use a real dataset, or at least present additional results with the unmodified BRCA data?
- Related to the request for a real dataset, another type of metric would be to measure the predictive performance of models trained with the most important features - and this would be simple to run even with real datasets. Would the authors consider adding something like this?
- Would it be possible to include other baselines in the experiments? For example, the methods examined in MCI or SAGE? 
- MCI giving large importance to randomized features in Figure 2a is a bit hard to believe, it's very counterintuitive. Can you verify that there isn't a mistake here, or explain why this occurs? 

The notation in this work was confusing at times. A couple choices that made this paper difficult to read were:
- $f$ denotes a function in most ML papers, but here it denotes a feature. Many papers instead represent the features as $x = (x_1, \ldots, x_d)$ when there are $d$ features, and the model inputs/outputs are usually written as $(x, y)$. $y$ is retained here, but not $x$ for some reason
- It would be helpful to write explicitly that $F$ is simultaneously used as both a set (e.g., $S \subseteq F$) and a random variable (e.g., $I(Y; F)$). Similar to the above, the notation that's often used is $S \subseteq D = ${$1, \ldots, d$} to denote the feature indices and $x_S$ to represent a random variable that concatenates the set of features
- It would be helpful to say explicitly that $g(A)$ represents a random variable resulting from applying a function $g$ to a subset of features (towards the beginning of section 3)
- The symbol used to denote independence (see theorem 3.1) is never defined and likely unfamiliar to some readers
- $g$ is overloaded to denote two different types of functions: one is a predictive model for $Y$ (equation 2) and one is an arbitrary function on the feature space (definition of $I(F)$)

Nits: 
- On line 49, there are methods that suggest training models with many feature subsets (another one is SPVIM, Williamson & Feng 2020), but several do not - including SAGE and permutation tests. There are a variety of tricks for handling the held-out features including setting to the mean, sampling replacement values (from the dataset or from a generative model), training a model to handle missing features, etc (see "Explaining by removing: a unified framework for model explanation" by Covert et al.)
- On lines 29-30, marginal (rather than conditional) methods are not typically thought of as being for interpreting the data. See "True to the model or true to the data" by Chen et al., it discusses how marginal methods are better suited for understanding the model rather than the data
- I think there's a typo in the subscript of the union operator on line 134 - shouldn't it be $f$ rather than $F$?
questions: On line 120, is it important that $g$'s domain is $A \subseteq F$ rather than simply $F$? I don't see why it can't simply be $F$. And is it important that the co-domain be $\mathbb{R}^{|A|}$ rather than some higher- or lower-dimensional Euclidean space? 

A couple points from above that would be helpful to comment on:
- Non-uniqueness of dependency-removing transformation
- How MCI handles correlated features wrong, and how UMFI is supposed to fix the problem
- Why MCI gives non-zero importance to unrelated features but UMFI somehow does not
- Various points about the experiments
limitations: The authors included a nice discussion of limitations towards the end of the paper. One additional point that I would have liked to see covered, besides the main challenge of properly removing dependencies: whether there are any downsides to finding the maximum contribution. For example, are there cases where finding the max would yield equal importance for two features $x_1$ and $x_2$, where $x_1$ is useful on its own but $x_2$ is only useful when present along with a complementary feature $x_3$? This seems like a potential issue for both MCI and UMFI (depending on what one wants out of their importance values).
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The problem of estimating feature importance is considered, specifically
estimating marginal contribution importance (MCI). In essence, MCI estimates the
value of a feature based on the performance drop when the feature is excluded.
This paper studies an extension which the authors dub ultra-marginal feature
importance (UMFI) that maximises over "information subsets" rather than the all
subsets of features (like the original MCI).

It turns out this slight change provides large computational benefits and
improved performance to boot. The authors prove a key result that allows the
maximising information subset to be approximated using dependency removal
techniques such as those from the fair learning literature. This reduction in
complexity allows scaling to previously unobtainable number of features.

strengths_and_weaknesses: This is a great extension to the MCI framework as it is simple, novel, and has a
large practical impact. The presentation is excellent, theorem proof
straightforward, and empirical experiments well chosen. Limitiations of the
study are well discussed.

One weakness is the authors have found a dataset where their choice of optimal
transport/linear regression for dependence removal failed, but it is relegated
to supplementary materials.

minor: line 301 is missing the word "features"

questions: It's clear many methods could be used as ν, and is discussed in the conclusion, but
no alternative is explored in the empirical results. It's quite natural to wonder how
critical the choice of supervised learning methods is: have this been explored?

The choice of ν can also be more generic dependency measures, so what about
easy to estimate measures of dependence like HSIC?

limitations: It's clear many methods could be used as ν, and is discussed in the conclusion, but
no alternative is explored in the empirical results. It's quite natural to wonder how
critical the choice of supervised learning methods is: have this been explored?

The choice of ν can also be more generic dependency measures, so what about easy
to estimate measures of dependence like HSIC? Exploration of supermodularity
might be more straightforward.
review_title: null

Meta-review: metareview: This work makes a significant contribution to establishing the theoretical foundations for feature importance. The authors suggest a set of axioms that a feature importance score should have and introduce an algorithm that computes a feature importance score that has these required properties. In addition to the theoretical work, a compelling empirical evaluation is conducted showing significant improvement over previous results.

After a good discussion between the reviewers and the authors and improvements to the paper introduced due to this discussion, the result is a good paper that is of great interest to the NeurIPS community. However, the added content also raised some concern about the accuracy of some statements, especially with respect to the blood relation. The main concern is that it is not clear that the algorithm provided has the blood relation property. Moreover, it is not clear that it is possible to fulfil this relation. Here are two scenarios that may be problematic:
1. In the fully observed setting if X is a confounder of Y and Z while Z is identical to X then X blocks the backdoor from Y to Z and therefore, according to the blood relation axiom the importance of Z should be zero while the importance of X should be positive since it has direct causal relation with Y. However,  the roles of X and Z are indistinguishable and therefore it might as well be that Z is the confounder and therefore should have a non-zero importance.
2. In the partially observed setting, if S is an unobserved uniformly distributed integer in the range 1..8, Y is the sign of S, and X is an indicator of S being greater then 4 the according to the blood relation axiom, since there is a backdoor between Y and X when S in unobserved then the importance of X should be non-zero. However, this setting is indistinguishable from the setting in which X and Y are uncorrelated Bernoulli variables in which case the importance of X should be zero.  

Hence, is looks as if the blood relation requirement might be too strong. When reviewer suggested that this problem might be eliminated by saying that the importance of a feature is 0 if there exists a graphical model in which the feature is not in the same connected component as the target (note that this is a graphical model and not a causal model). However, this corollary should be theoretically analyzed.   

Some additional comments that emerge in the revised paper:
1.	The axioms do not define a unique solution. Indeed, if a function Imp has all three required properties (axioms) then multiplying it by any positive constant would generate another valid feature importance score. It would be nice to add another requirement that will force a unique solution like Shapley Value or MCI.
2.	The proof in the appendix shows that UMFI has the three required properties only when certain assumptions hold on the distribution. However, in the body of the paper, these limitations are not mentioned.
3.	In line 211 it is stated that the proofs are presented in Section 3, however, the proofs are presented only in the appendix

confidence: Less certain
Decision: Reject