# Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf

arXiv: https://arxiv.org/abs/2108.04126 · HTML: https://mlsanity.com/paper/2108.04126/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 57 references that are in the map.
- First posted on arXiv 9 Aug 2021.

## Builds on (most cited first, 16 of 16)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [Striving for Simplicity: The All Convolutional Net](https://mlsanity.com/paper/1412.6806/) (2014)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Not Just a Black Box: Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1605.01713/) (2016)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [Learning how to explain neural networks: PatternNet and PatternAttribution](https://mlsanity.com/paper/1705.05598/) (2017)
- [Model Agnostic Supervised Local Explanations](https://mlsanity.com/paper/1807.02910/) (2018)
- [High Dimensional Model Explanations: an Axiomatic Approach](https://mlsanity.com/paper/2006.08969/) (2020)
- [Influence in Classification via Cooperative Game Theory](https://mlsanity.com/paper/1505.00036/) (2015)
- [Which criteria qualify power indices for applications? -- A comment to "The story of the poor Public Good index"](https://mlsanity.com/paper/1812.05808/) (2018)

## Built on by (most cited first, 4 of 4)

- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning](https://mlsanity.com/paper/2301.09138/) (2023)
- [Efficient XAI Techniques: A Taxonomic Survey](https://mlsanity.com/paper/2302.03225/) (2023)

## Abstract (arXiv)

Shapley values are one of the main tools used to explain predictions of tree ensemble models. The main alternative to Shapley values are Banzhaf values that have not been understood equally well. In this paper we make a step towards filling this gap, providing both experimental and theoretical comparison of these model explanation methods. Surprisingly, we show that Banzhaf values offer several advantages over Shapley values while providing essentially the same explanations. We verify that Banzhaf values: (1) have a more intuitive interpretation, (2) allow for more efficient algorithms, and (3) are much more numerically robust. We provide an experimental evaluation of these theses. In particular, we show that on real world instances. Additionally, from a theoretical perspective we provide new and improved algorithm computing the same Shapley value based explanations as the algorithm of Lundberg et al. [Nat. Mach. Intell. 2020]. Our algorithm runs in O(TLD+n) time, whereas the previous algorithm had O(TLD2+n) running time bound. Here, T is the number of trees, L is the maximum number of leaves in a tree, and D denotes the maximum depth of a tree in the ensemble. Using the computational techniques developed for Shapley values we deliver an optimal O(TL+n) time algorithm for computing Banzhaf values based explanations. In our experiments these algorithms give running times smaller even by an order of magnitude.