arXiv:2602.07203cs.LGcs.AI2026-02被引 3

提出精确计算因果模型中变量贡献的新方法,速度远超传统方式。

Exactly Computing do-Shapley Values

  • 基于不可约集重构do-Shapley值,实现线性时间精确计算
  • 当查询预算达r时,精度比旧方法高数个数量级,可达机器精度
  • 只需识别d个单变量干预效应,降低因果识别负担

结构因果模型(SCM)是描述自然科学中复杂动态的强大框架。do-Shapley是一种博弈论方法,用于量化d个变量在指数级干预中的平均影响。与Shapley值类似,计算do-Shapley值通常需评估指数级项。本文通过将do-Shapley值重新表述为底层SCM的不可约集,实现了线性于不可约集数量r的精确计算,r范围从d到2^d,取决于图结构。由于r事先未知,我们还提出了一个估计器,可适应任意查询预算。当预算接近r时,估计精度比现有方法高数个数量级;达到r时,可返回机器精度下的精确值。此外,我们证明了非参数可识别性仅需识别d个单例联盟的干预效应,而非所有类别。

原文摘要 · Abstract (English)

Structural Causal Models (SCM) are a powerful framework for describing complicated dynamics across the natural sciences. A particularly elegant way of interpreting SCMs is do-Shapley, a game-theoretic method of quantifying the average effect of $d$ variables across exponentially many interventions. Like Shapley values, computing do-Shapley values generally requires evaluating exponentially many terms. The foundation of our work is a reformulation of do-Shapley values in terms of the irreducible sets of the underlying SCM. Leveraging this insight, we can exactly compute do-Shapley values in time linear in the number of irreducible sets $r$, which itself can range from $d$ to $2^d$ depending on the graph structure of the SCM. Since $r$ is unknown a priori, we complement the exact algorithm with an estimator that, like general Shapley value estimators, can be run with any query budget. As the query budget approaches $r$, our estimators can produce more accurate estimates than prior methods by several orders of magnitude, and, when the budget reaches $r$, return the Shapley values up to machine precision. Beyond computational speed, we also reduce the identification burden: we prove that non-parametric identifiability of do-Shapley values requires only the identification of interventional effects for the $d$ singleton coalitions, rather than all classes.

因果推断可解释性算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。