揭示因果推理中高阶问题所需信息量的指数级增长
The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy
- 用描述复杂度衡量因果层级间的信息差
- 观测到干预答案需额外Θ(n²)比特，实现二次分离
- 结果对模型结构敏感，适合因果推断研究者
Pearl的因果层级表明，观察、干预和反事实查询在性质上是不同的。本文提出量化问题：一旦知道低层级答案，要指定高层级因果答案还需多少额外比特？通过查询类描述长度（即由结构因果模型生成的答案预言机的柯尔莫哥洛夫复杂度）形式化该问题。主要构造展示了二元无环因果模型：其观测分布的描述长度为常数，而单变量干预答案预言机的描述长度为Θ(n²)。一个关于门限敏感的上界表明，最大入度为d的有限门结构因果模型，其观测-干预差距最多为O(nd log(en/d) + n log n)，使得二次构造在密集情形下达到阶次最优，树状结构在有界入度时也阶次最优。该二次分离在任意固定ε < 1/4的总变差ε-近似描述下依然成立。在下一层级，完整干预预言机仍可能留下Θ(n)的反事实描述差距。一般性的模糊性-比特定理与香农类比表明，这些差距等于残余高层级模糊性的对数，忽略低阶项。
原文摘要 · Abstract (English)
Pearl's causal hierarchy shows that observational, interventional, and counterfactual queries are qualitatively distinct. We ask a quantitative version of this question: how many additional bits are needed to specify higher-rung causal answers once lower-rung answers are known? We formalize this via query-class description length, the Kolmogorov complexity of the answer oracle induced by an SCM for a class of queries. Our main construction gives binary acyclic SCMs whose observational distribution has constant description length, while the single-variable interventional answer oracle has description length $Θ(n^2)$. A degree-sensitive upper bound shows that finite-gate-schema SCMs of indegree $d$ have observational-interventional gap at most $O(nd \log(en/d) + n \log n)$, making the quadratic construction order-optimal in the dense regime and a rooted-tree construction order-optimal for bounded indegree. The quadratic separation persists under $\varepsilon$-accurate total-variation descriptions for every fixed $\varepsilon < 1/4$. At the next rung, the full hard-do interventional oracle can still leave a $Θ(n)$ counterfactual description gap. A general ambiguity-to-bits theorem and Shannon analogue show that these gaps equal the logarithm of residual higher-rung ambiguity up to lower-order terms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。