将决策树与布尔逻辑结合,实现快速统一的SHAP解释方法。
From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithm
- 用布尔公式统一表示树结构与背景数据,实现高效计算
- 在300万样本数据上,GPU速度比现有方法快165倍
- 支持多种解释值计算,适合大规模模型可解释性分析
SHapley Additive exPlanations(SHAP)是解释决策树集成模型的重要工具,广泛应用于金融、广告、医疗等领域。现有两种主要计算方式:路径依赖型SHAP利用树结构提升效率,背景型SHAP则通过背景数据估计特征分布。本文提出WOODELF,一种融合决策树、博弈论与布尔逻辑的统一框架。对每个样本,WOODELF构建一个伪布尔公式,整合其特征值、树结构和完整背景数据集,进而在线性时间内计算背景型SHAP。该方法还可计算路径依赖型SHAP、Shapley交互值、Banzhaf值及交互值。算法基于NumPy、SciPy和CuPy实现,无需自定义C++或CUDA代码,可在CPU与GPU上高效运行。在包含300万行数据、500万背景样本和127个特征的数据集上,其在CPU上耗时162秒,在GPU上仅需16秒,相较最优现有方法分别提速16倍和165倍。
原文摘要 · Abstract (English)
SHapley Additive exPlanations (SHAP) is a key tool for interpreting decision tree ensembles by assigning contribution values to features. It is widely used in finance, advertising, medicine, and other domains. Two main approaches to SHAP calculation exist: Path-Dependent SHAP, which leverages the tree structure for efficiency, and Background SHAP, which uses a background dataset to estimate feature distributions. We introduce WOODELF, a SHAP algorithm that integrates decision trees, game theory, and Boolean logic into a unified framework. For each consumer, WOODELF constructs a pseudo-Boolean formula that captures their feature values, the structure of the decision tree ensemble, and the entire background dataset. It then leverages this representation to compute Background SHAP in linear time. WOODELF can also compute Path-Dependent SHAP, Shapley interaction values, Banzhaf values, and Banzhaf interaction values. WOODELF is designed to run efficiently on CPU and GPU hardware alike. Available via the WOODELF Python package, it is implemented using NumPy, SciPy, and CuPy without relying on custom C++ or CUDA code. This design enables fast performance and seamless integration into existing frameworks, supporting large-scale computation of SHAP and other game-theoretic values in practice. For example, on a dataset with 3,000,000 rows, 5,000,000 background samples, and 127 features, WOODELF computed all Background Shapley values in 162 seconds on CPU and 16 seconds on GPU - compared to 44 minutes required by the best method on any hardware platform, representing 16x and 165x speedups, respectively.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。