提升深度决策树的解释效率，让高深度树也能快速计算准确的特征重要性。
WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees
- 用类似斯特拉森算法的矩阵乘法优化，将计算复杂度从3^D降到2^D。
- 在深度达21的树上实现精确背景SHAP，比之前方法快162倍。
- 适合需要高效解释深度模型的科研与工业用户。
决策树集成是预测建模的核心，而SHAP是解释其预测的标准框架。其中，背景SHAP通过背景数据集建模缺失特征，精度高，但历史上难以扩展，解释n个样本使用m个背景样本的时间复杂度含O(mn)项。近期方法如Woodelf和PLTreeSHAP将其降至O(m+n)，但引入了随树深D呈3^D增长的预处理瓶颈，导致深树不可行。本文提出WoodelfHD，通过类斯特拉森乘法方案，利用Woodelf矩阵结构，将矩阵-向量乘法从O(k^2)降至O(k*log(k))，实现完全向量化且非递归。此外，合并特征相同的路径节点，减少缓存与内存占用。在标准环境上，WoodelfHD可对深度达21的树进行精确背景SHAP计算，此前方法因内存超限无法运行；对于深度12和15的集成模型，分别实现33倍和162倍的加速，优于当前最优方法。
原文摘要 · Abstract (English)
Decision-tree ensembles are a cornerstone of predictive modeling, and SHAP is a standard framework for interpreting their predictions. Among its variants, Background SHAP offers high accuracy by modeling missing features using a background dataset. Historically, this approach did not scale well, as the time complexity for explaining n instances using m background samples included an O(mn) component. Recent methods such as Woodelf and PLTreeSHAP reduce this to O(m+n), but introduce a preprocessing bottleneck that grows as 3^D with tree depth D, making them impractical for deep trees. We address this limitation with WoodelfHD, a Woodelf extension that reduces the 3^D factor to 2^D. The key idea is a Strassen-like multiplication scheme that exploits the structure of Woodelf matrices, reducing matrix-vector multiplication from O(k^2) to O(k*log(k)) via a fully vectorized, non-recursive implementation. In addition, we merge path nodes with identical features, reducing cache size and memory usage. When running on standard environments, WoodelfHD enables exact Background SHAP computation for trees with depths up to 21, where previous methods fail due to excessive memory usage. For ensembles of depths 12 and 15, it achieves speedups of 33x and 162x, respectively, over the state-of-the-art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。