Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles

Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles

22 Jan 2024 | Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, Eyke Hüllermeier
This paper introduces TreeSHAP-IQ, an efficient method for computing any-order additive Shapley interactions for predictions made by tree-based models. TreeSHAP-IQ is an extension of the TreeSHAP methodology, which efficiently computes the Shapley value (SV) for tree ensembles. The SV is a well-known concept in explainable artificial intelligence (XAI) for quantifying additive feature attributions. However, TreeSHAP-IQ goes beyond individual feature attribution by revealing the impact of intricate feature interactions of any order. The paper presents a mathematical framework that leverages polynomial arithmetic to compute interaction scores in a single recursive traversal of the tree, similar to Linear TreeSHAP. This approach significantly reduces computational complexity compared to previous methods. The authors apply TreeSHAP-IQ to state-of-the-art tree ensembles, such as XGBoost, and evaluate its performance on several benchmark datasets. The contributions of the paper include: 1. **TreeSHAP-IQ**: An efficient algorithm for computing any-order Shapley Interaction Quantification (SIQ) scores for tree ensembles. 2. **Unified Framework**: Application of TreeSHAP-IQ to a broad class of Cardinal Interaction Indices (CIIs). 3. **Application**: Efficient implementation of TreeSHAP-IQ on advanced tree-based models and demonstration of how interaction scores enhance single feature attribution measures on various benchmark datasets. The paper also discusses the theoretical foundation of TreeSHAP-IQ, including the definition of Shapley Interaction Indices (SIIs) and the extension of the path-dependent TreeSHAP to any-order interactions. The computational complexity and storage requirements of TreeSHAP-IQ are analyzed, showing that it is efficient for practical use. Finally, the paper presents experimental results using TreeSHAP-IQ on datasets such as German Credit, Bank, Adult Census, Bike, COMPAS, Titanic, and California. The visualizations and aggregation techniques used to present the interaction scores are discussed, highlighting the ability of TreeSHAP-IQ to reveal complex feature interactions that enrich Shapley-based feature attribution.This paper introduces TreeSHAP-IQ, an efficient method for computing any-order additive Shapley interactions for predictions made by tree-based models. TreeSHAP-IQ is an extension of the TreeSHAP methodology, which efficiently computes the Shapley value (SV) for tree ensembles. The SV is a well-known concept in explainable artificial intelligence (XAI) for quantifying additive feature attributions. However, TreeSHAP-IQ goes beyond individual feature attribution by revealing the impact of intricate feature interactions of any order. The paper presents a mathematical framework that leverages polynomial arithmetic to compute interaction scores in a single recursive traversal of the tree, similar to Linear TreeSHAP. This approach significantly reduces computational complexity compared to previous methods. The authors apply TreeSHAP-IQ to state-of-the-art tree ensembles, such as XGBoost, and evaluate its performance on several benchmark datasets. The contributions of the paper include: 1. **TreeSHAP-IQ**: An efficient algorithm for computing any-order Shapley Interaction Quantification (SIQ) scores for tree ensembles. 2. **Unified Framework**: Application of TreeSHAP-IQ to a broad class of Cardinal Interaction Indices (CIIs). 3. **Application**: Efficient implementation of TreeSHAP-IQ on advanced tree-based models and demonstration of how interaction scores enhance single feature attribution measures on various benchmark datasets. The paper also discusses the theoretical foundation of TreeSHAP-IQ, including the definition of Shapley Interaction Indices (SIIs) and the extension of the path-dependent TreeSHAP to any-order interactions. The computational complexity and storage requirements of TreeSHAP-IQ are analyzed, showing that it is efficient for practical use. Finally, the paper presents experimental results using TreeSHAP-IQ on datasets such as German Credit, Bank, Adult Census, Bike, COMPAS, Titanic, and California. The visualizations and aggregation techniques used to present the interaction scores are discussed, highlighting the ability of TreeSHAP-IQ to reveal complex feature interactions that enrich Shapley-based feature attribution.
Reach us at info@study.space