超越 TreeSHAP：用于树集成的任意阶 Shapley 互作用的高效计算
内容提要
本文综述了Shapley值在机器学习模型解释中的研究进展，涵盖交互值估计的SHAP-IQ采样法、多项式时间精确计算SHAP值的方法、Shapley-Taylor指数与公理化归因、图数据特征贡献的线性复杂度算法、KNN交互Shapley值的STI-KNN精确计算、加速计算的SimSHAP摊销估计器、树集成模型解释与可视化、非对称Shapley值框架、FastSHAP单次前向估计，以及高维近似与相关特征处理。
延伸解读
从单特征归因到交互归因的演进
文章梳理了Shapley值在模型解释中的发展脉络：早期工作聚焦于单特征贡献（如SHAP值），而SHAP-IQ等方法将目标扩展到任意阶的Shapley交互值，用于刻画特征间的协同或冗余效应。这一转变意味着解释粒度从“每个特征贡献多少”细化到“特征组合如何共同影响预测”，对理解复杂模型（如树集成）的内部机制更有帮助。
计算效率与精确性的权衡
文中提到的多项工作都在试图平衡计算成本与解释质量。例如，多项式时间精确计算SHAP值的方法针对不同模型结构信息（已知功能分解、已知模型顺序、未知模型顺序）设计；STI-KNN能在O(t n^2)时间内精确计算KNN模型的成对交互Shapley值；SimSHAP和FastSHAP则通过摊销估计或单次前向传播来加速。读者可据此判断不同场景下应优先选择精确算法还是近似加速方案。
公理化框架与解释的可靠性
文章强调了Shapley值的公理化基础（线性、对称、虚拟公理），SHAP-IQ保证了其逼近质量并提供方差估计，Shapley-Taylor指数则用交互分布公理进行公理化。这些公理约束为解释结果提供了理论上的可靠性保证，但也意味着不同方法在满足公理的程度和适用条件上存在差异。读者在选用解释工具时，需关注其是否满足所需公理以及是否提供不确定性度量。
面向实际应用的扩展与挑战
除了理论进展，文章还涉及图数据特征贡献的线性复杂度算法、非对称Shapley值框架（用于公平性测试、时序增量解释和特征选择）、以及高维近似与相关特征处理。这些扩展表明Shapley值正从标准表格数据走向图结构、时序和存在特征相关性的复杂场景，但相关特征处理仍是一个需要谨慎对待的挑战，可能影响解释的准确性。
Q&A
SHAP-IQ 是什么？它有什么理论保证？
SHAP-IQ 是一种基于采样的计算 Shapley 交互值的新方法，适用于所有符合线性、对称和虚拟公理的定义。它理论上保证了逼近质量，并提供了点估计的方差估计，从而简化了 Shapley 值的计算。
有哪些方法可以在多项式时间内精确计算 SHAP 值？
文章提到多种方法可以在多项式时间内准确计算 SHAP 值，适用于不同类型的模型结构信息，包括已知功能分解、已知模型顺序和未知模型顺序，这些方法在实际应用中计算效率高且准确性较高。
Shapley-Taylor 指数是什么？它如何被公理化？
Shapley-Taylor 指数是一种用于解决归因问题的方法，它使用交互分布公理进行公理化，并应用于模型中以识别有趣的定性洞见。
如何高效计算图结构数据中的特征贡献？
文章提出两种线性复杂度的算法来评估图结构数据中的特征贡献，作为实例级特征重要性评分方法，并与其他模型解释方法进行了比较。
STI-KNN 算法是什么？它的计算复杂度如何？
STI-KNN 是一种算法，可在 O(t n^2) 时间内计算 KNN 模型的精确对交互 Shapley 值，能有效且准确地评估个体数据点的价值，从而提高人工智能应用的效果。
SimSHAP 如何加速 Shapley 值的计算？
SimSHAP 是一种简单高效的摊销估计器，通过消除冗余技术来加速准确 Shapley 值的计算。它基于随机估计器可统一为特征子集重要性采样的线性变换的发现，在表格和图像数据集上的实验证实了其有效性。
FastSHAP 是如何在一次前向传递中估计 Shapley 值的？
FastSHAP 使用学习解释器模型在一次正向传递中估计 Shapley 值，通过启发 Shapley 值加权最小二乘估计的学习方法来分摊解释许多输入的成本，并可使用标准的随机梯度优化进行训练，与现有方法相比显示出高质量解释的数量级加速。
Asymmetric Shapley values 框架有什么用途？
Asymmetric Shapley values (ASVs) 是一种较少限制的框架，可以改善模型解释、为模型预测中的不公平歧视提供测试、在时序模型中支持逐步增量解释，以及支持特征选择研究而无需进行模型重新训练。
