提出可高效计算特征重要性方法的判定条件，拓展了SHAP等经典方法的适用范围。
When is the Computation of a Feature Attribution Method Tractable?
- 通过合作博弈中的权力指数，建立特征贡献度计算的复杂性判据
- 发现伯努利型权力指数仅需常数次期望值评估即可求解
- 揭示特征组合重要性计算与单个特征的复杂度一致
特征归因方法已成为解释机器学习模型的关键工具。许多流行方法（如SHAP和Banzhaf值）基于合作博弈论中的权力指数，用于衡量特征对模型预测的贡献。本文研究了超出SHAP的权力指数的计算复杂性，确定了保证其计算可在多项式时间内完成的简单条件，该条件使计算复杂度等价于评估期望值。我们引入伯努利型权力指数，证明其计算可简化为常数次期望值评估。此外，我们探讨了量化特征子集重要性的交互权力指数，证明其计算复杂度与单个特征相同。
原文摘要 · Abstract (English)
Feature attribution methods have become essential for explaining machine learning models. Many popular approaches, such as SHAP and Banzhaf values, are grounded in power indices from cooperative game theory, which measure the contribution of features to model predictions. This work studies the computational complexity of power indices beyond SHAP, addressing the conditions under which they can be computed efficiently. We identify a simple condition on power indices that ensures that computation is polynomially equivalent to evaluating expected values, extending known results for SHAP. We also introduce Bernoulli power indices, showing that their computation can be simplified to a constant number of expected value evaluations. Furthermore, we explore interaction power indices that quantify the importance of feature subsets, proving that their computation complexity mirrors that of individual features.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。