提出高效计算非对称谢尔普利值的方法，可融入因果知识并加速计算。
Beyond Shapley: Efficient Computation of Asymmetric Shapley Values
- 基于因果图定义非对称谢尔普利值，利用等价类减少计算量。
- 在根树结构下，可在多项式时间内精确计算，突破传统方法的#P难限制。
- 适用于需要因果解释的机器学习场景，如医疗、金融建模。
我们通过特征归因方法解决机器学习模型的可解释性问题。特别关注一种称为非对称谢尔普利值（ASV）的变体，该方法通过因果图将因果知识融入模型无关的解释中。我们证明，在某些传统SHAP计算为#P难的情况下，ASV的精确计算可在多项式时间内完成。为进一步拓展此算法结果，我们引入了因果图拓扑排序的等价类概念，有效降低计算时间。尤其当因果图为有根有向树时，提出了基于等价类数量的多项式时间算法。此外，针对任意因果有向无环图（DAG），我们设计了一种近似算法，依赖于均匀随机采样拓扑排序的过程，结合已知算法与简化方案实现采样。实验表明，该方法在真实因果结构中具有实际可行性。
原文摘要 · Abstract (English)
We address the problem of explainability in machine learning models through feature attribution methods. In particular, we consider a variant of Shapley values known as Asymmetric Shapley Values (ASV), which enables the incorporation of causal knowledge into model-agnostic explanations through the use of a causal graph. We show that in certain contexts in which the computation of SHAP is $\#P$-hard, the exact computation of ASV can be done in polynomial time. To extend this algorithmic result, we introduce a notion of equivalence classes over the topological orderings of the underlying causal graph, which is useful to reduce the time to compute ASV. In particular, we present a polynomial-time algorithm (in the number of equivalence classes) to compute it whenever the causal graph is a rooted directed tree. Finally, we develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random. To implement this sampling mechanism we leverage known algorithms as well as simpler alternatives. Our experimental results demonstrate the practical viability of the proposed approach in realistic causal structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。