分析多种SHAP变体的计算复杂度，揭示其在不同模型和分布下的可计算性差异。
On the Computational Tractability of the (Many) Shapley Values
- 系统比较条件、干预和基线SHAP的计算机制
- 在隐马尔可夫模型下，干预与基线SHAP可多项式时间计算
- 在神经网络和树集成中，多数变体为计算难问题
近期研究已探讨在不同模型与分布下计算Shapley加性解释（即SHAP）的计算复杂性，揭示了其在特定场景中的可计算性或不可计算性。然而，这些研究主要聚焦于一种称为条件SHAP的变体，而实际上存在多种其他变体以解决不同局限性。本文分析了更广泛的变体，包括条件、干预和基线SHAP，并考察其局部与全局计算的复杂性。我们证明，在隐马尔可夫模型分布下，各类干预与基线SHAP对于多种机器学习模型均可在多项式时间内计算，扩展了如TreeSHAP等算法的应用范围。另一方面，我们在广泛神经网络与树集成上证明了这些变体的计算困难性。结果表明，计算Shapley值的复杂性高度依赖具体变体、模型类型及数据分布，凸显其内在多样性。
原文摘要 · Abstract (English)
Recent studies have examined the computational complexity of computing Shapley additive explanations (also known as SHAP) across various models and distributions, revealing their tractability or intractability in different settings. However, these studies primarily focused on a specific variant called Conditional SHAP, though many other variants exist and address different limitations. In this work, we analyze the complexity of computing a much broader range of such variants, including Conditional, Interventional, and Baseline SHAP, while exploring both local and global computations. We show that both local and global Interventional and Baseline SHAP can be computed in polynomial time for various ML models under Hidden Markov Model distributions, extending popular algorithms such as TreeSHAP beyond empirical distributions. On the downside, we prove intractability results for these variants over a wide range of neural networks and tree ensembles. We believe that our results emphasize the intricate diversity of computing Shapley values, demonstrating how their complexity is substantially shaped by both the specific SHAP variant, the model type, and the distribution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。