Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf
This work addresses the need for efficient and robust feature importance computations in machine learning interpretability, particularly for tree models, but it is incremental as it builds on existing explanation methods.
The paper tackles the problem of explaining predictions from tree ensemble models by comparing Shapley and Banzhaf values, showing that Banzhaf values offer advantages such as more intuitive interpretation, more efficient algorithms, and greater numerical robustness while providing similar explanations. It presents a new algorithm for Shapley values with improved runtime from O(TLD^2+n) to O(TLD+n) and an optimal O(TL+n) algorithm for Banzhaf values, with experiments showing order-of-magnitude speedups.
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(TLD^2+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.