Exactly Computing do-Shapley Values

Structural Causal Models (SCM) は、自然科学における複雑なダイナミックスを記述するための強力な枠組みです。SCM を解釈する、特にエレガントなアプローチが do-Shapley 方法です。これは、指数関数的に多くの介入において $d$ 変数の平均効果を量化するゲーム理論的な手法です。Shapley 値と同様に、do-Shapley 値を計算するには一般的に指数関数的な多くの項を評価する必要があります。本稿の基礎となるのは、底となる SCM の不可約集合（irreducible sets）に関する do-Shapley 値の再表現です。この洞察を利用することで、不可約集合の数 $r$ に比例する線形時間で do-Shapley 値を正確に計算することが可能です。$r$ の値は SCM のグラフ構造によって $d$ から $2^d$ までの範囲を取る可能性があります。$r$ が事前に分かっているとは限らないため、我々は一般的な Shapley 値推定量と同様に任意のクエリ予算（query budget）で実行可能な推定量を、正確なアルゴリズムを補完するように構築しました。クエリ予算が $r$ に近づくにつれ、我々の推定量は以前の手法よりも数桁精度高い估计を提供でき、予算が $r$ に至ると機械の精度レベルの Shapley 値を返すことができます。計算速度だけでなく、同定負荷の低減という点においても、我々は非パラメトリックな do-Shapley 値の同定は、すべてのクラス同定を必要とするのではなく、$d$ 単独coalition に対する介入効果の同定だけで十分であることを示しました。

arXiv:2602.07203v1 Announce Type: new Abstract: 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.