Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper demonstrates a connection between Shapley values and a tree-based measure of global feature importance, then proposes a local version of that tree-based feature importance measure. The paper also offers a discussion of the properties satisfied by the proposed method and runs empirical tests of feature importance methods on a few datasets.
main_review: I would rank the overall originality and quality of the current form of this paper rather low. While methods for identifying important features in tree-based models are generally of great interest due to the wide-spread use of these types of models in deployment, the significance of the proposed method is not well demonstrated (either theoretically or empirically), and several of the contributions of the paper have been discussed already in prior works.

One of the major contributions of this paper is the connection of MDI variable importance scores to Shapley values under certain conditions (randomized trees under asymptotic conditions). While developing the understanding of connections between older, more established tree-based methods for variable importance and more recent Shapley value-based methods is certainly of value and of interest, the connection between these methods has already been discussed in prior work, and in my opinion has been explained in a more intuitive way there. 

Specifically, the method discussed in this paper can be thought of as a modified version of the Saabas algorithm [1], where output differences are replaced by impurity reductions (see lines 296-297 in this paper). The connection between algorithms like Saabas/MDI and the Shapley value was already made in Lundberg et al.’s 2019 paper (see the bottom of pg. 20-21 in the arxiv version of that paper) – Saabas/MDI only consider a single ordering to add players to the coalition, while the Shapley value averages over all orderings. When there are randomized trees under asymptotic conditions, all possible feature orderings will be considered in equal proportions, making these equivalent [2].

Furthermore, this paper incorrectly states that TreeSHAP only decomposes model predictions. A significant portion of that work involves an algorithm called “Independent Tree SHAP” (see methods 10.2 of [2]), that allows for the attribution of a model’s loss to individual features at the local level, which is also discussed in [3]. TreeSHAP loss attributions should certainly be more thoroughly discussed theoretically or at least compared to empirically.

I think there are a variety of avenues that could make this work significantly more impactful – either a theoretical analysis outside of the asymptotic conditions, or empirical results for more representative datasets (i.e. not toy examples like the digits/LED used in this paper) that the MDI values were of similar quality to SHAP while being meaningfully faster on these more realistic datasets.

As a minor comment, the notation is pretty dense, confusing, and occasionally overloaded – leading to ambiguity (like $v$ referring to both the characteristic function of a TU game [see line 48] and the variable tested in a certain node [see line 98]).

[1] Ando Saabas. Interpreting random forests. 2014. http://blog.datadive.net/interpreting-random-forests/
[2] Lundberg, Scott M., et al. "From local explanations to global understanding with explainable AI for trees." https://arxiv.org/abs/1905.04610
[3] Covert et al. "Understanding global feature contributions with additive importance measures." https://arxiv.org/abs/2004.00668

limitations_and_societal_impact: The authors adequately addressed potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper’s contributions are on variable importance measures in tree and tree ensembles. In particular, the paper provides an interpretation of the “mean decrease of impurity” measure (MDI) of totally randomised trees as Shapley values where the characteristic function of the underlying game is the mutual information between a feature variable set and the target variable. Moreover, a novel local variant of MDI measure is introduced that quantifies the impact of variable for the classification of a specific input point, which can again be interpreted as Shapley values in the case of totally randomised trees.
main_review: Given their availability in popular ML packages, MDI is widely used in practice to assess variable importance. However, its interpretation is not straightforward. Hence, results are important that characterise MDI in terms of other known quantities. The given results strongly build on previous work that connected MDI to mutual information. While the step from there to Shapley values is relatively small, it is still an important novel insight. Moreover, the proposed local variant of MDI is appealing for its simplicity and natural connection to global MDI which can be decomposed as an average over all local MDIs. Overall, the paper is a pleasantly well-written and provides a useful collection of results that help to interpret the classification of randomised tree ensembles.

Some minor suggestions for improvement:
- The experiments are nice to illustrate the measures, but perhaps some stronger experiments (potentially with synthetic data) could be devised that demonstrates that MDI can become misleading for large K when it is no longer a Shapely value 
- The paper manages to be mostly self-contained despite the relatively wide set of concepts it needs to introduce. What feels is missing, is a minimal introduction to mutual information and its properties as they are essential for the main results.
- In the definition of strong monotonicity, the index of the MC function should be m
- In Definition 2, it seems more readable to avoid the all quantifier over labels and simply require equality of the two conditional distributions of Y
limitations_and_societal_impact: The paper should have a positive societal impact because its contributions help to make machine learning more interpretable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors provide conditions under which tree-based mean decrease in impurity (MDI) measures are Shapley values. This is an interesting and potentially useful connection, with particular implications for computation time of Shapley values in certain settings.

main_review: - More discussion of totally randomized trees is necessary: when are these reasonable or feasible to compute? What happens in finite samples?
- Local MDI has a strange interpretation; the local MDI for an observation appears to depend on other instances, and thus is not truly local. Please provide more discussion of this measure and when it has a useful interpretation.
- Does the summation from local to global MDI in Equation 9 hold? It seems that local MDI can be negative, but global MDI cannot.
- I would redefine "asymptotic local MDI" as "future local MDI", since the term "asymptotic" doesn't really fit for local importance
- Please define notation (e.g., $I$ and $H$) prior to its use
- In the related work section, please discuss totally randomized trees in more detail
- The figures are difficult to read, both due to their small size and the information contained. Please consider a different format (e.g., a table of values to replace Figure 2) to facilitate easier comparisons, and please increase the font size in all cases.
- Please include more discussion of how to handle continuous variables in this framework
- Please consider editing the section headings to make the manuscript flow more logically, and check for typos and other formatting
- The proof of Theorem 3 provided in the supplement is too sparse: only an if-then relation (not an if and only if) appears to be proved there.
limitations_and_societal_impact: No negative impacts are discussed, but as in all cases in explainable AI there is potential for results to be misused; this should be discussed.
review_title: null

Meta-review: This paper presents previously unknown connection between the global Mean Decrease of Impurity (MDI) variable importance scores and Shapley values under certain conditions. The authors also derive local MDI feature importance measure link with Shepley values.  The paper presents novel insights, and the local MDIs are likely practically useful for its simplicity. This paper is clearly written and structured well. Overall, this paper constitutes an important contribution to the field and passes the bar for the acceptance to NeurIPS.
Decision: Accept (Poster)