観測データにおける潜在混淆因子の下での因果効果の同定可能性を決定するための効率的な記号計算

arXiv:2604.20516v1 Announce Type: cross 要約: 潜在的混淆因子の下で観測データから因果効果の同定可能性を決定することは、因果推論における中心的な課題です。線形構造的因果モデルの文脈では、因果効果の同定可能性は記号計算を通じて決定可能です。しかし、グロベーナー系 (Gröbner bases) に基づく標準的なアプローチは、二重指数関数的複雑さを持つため、小さな規模を除き計算上で実現不可能になっています。本研究では、有理的な同定可能性を決定するための記号計算をどのように実用的に適用するかを探究しています。具体的には、最低度の同定公式を証明として発見する効率的なアルゴリズムを提案します。関心のある因果効果について、指定された最大度数の同定公式が存在する場合は、そのアルゴリズムが準多項式時間でそのような公式を帰還します。

arXiv:2604.20516v1 Announce Type: cross Abstract: Determining identifiability of causal effects from observational data under latent confounding is a central challenge in causal inference. For linear structural causal models, identifiability of causal effects is decidable through symbolic computation. However, standard approaches based on Gr\"obner bases become computationally infeasible beyond small settings due to their doubly exponential complexity. In this work, we study how to practically use symbolic computation for deciding rational identifiability. In particular, we present an efficient algorithm that provably finds the lowest degree identifying formulas. For a causal effect of interest, if there exists an identification formula of a prespecified maximal degree, our algorithm returns such a formula in quasi-polynomial time.