Introduces ProxySHAP, a novel method that uses tree-based proxy models and residual correction to efficiently approximate complex Shapley and Banzhaf interactions, establishing a new state-of-the-art for model explainability.
Shapley and Banzhaf interactions are crucial for understanding the complex dynamics in machine learning. Current estimators often suffer from trade-offs between speed and accuracy. This paper introduces ProxySHAP, which reconciles the high sample efficiency of tree-based proxy models with principled consistency through residual correction. Theoretically, the work derives a polynomial-time generalization of interventional TreeSHAP, effectively bypassing exponential dependencies in prior methods. The method further analyzes the residual adjustment strategy, showing that Maximum Sample Reuse (MSR) corrects proxy bias efficiently. Extensive benchmarking demonstrates that ProxySHAP achieves superior approximation quality compared to existing methods like ProxySPEX and KernelSHAP-IQ, particularly in large-scale applications with thousands of features.