发现因果效应估算可高效计算，关键在估计算式结构的复杂度。
Graph-based Complexity for Causal Effect by Empirical Plug-in
- 基于图结构分析估计算式复杂度，用超图宽度衡量
- 计算时间可线性于数据量，取决于估计算式的超树宽
- 适用于高维因果推断，对算法设计有指导意义
本文研究在给定因果图和观测数据下，因果效应查询的实证插补估计的计算复杂度。任何可识别的因果查询均可表示为可观测变量的表达式（即估计算式），再通过从数据中经验性估计概率来评估该表达式。与通常认为高维概率函数会导致指数级计算时间的直觉相反，本文证明：计算可在多项式时间内完成，甚至可能在数据规模上线性展开，具体取决于估计算式的超图结构。特别地，估计算式的树宽与超树宽均能约束插补估计的评估复杂度，类似于它们在图模型概率推断中的作用。通常，由于经验分布具有稀疏性，超树宽能提供更有效的上界。
原文摘要 · Abstract (English)
This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom, which assumes that high dimensional probabilistic functions will lead to exponential evaluation time of the estimand. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph. In particular, we show that both the treewidth and hypertree width of the estimand's structure bound the evaluation complexity of the plug-in estimands, analogous to their role in the complexity of probabilistic inference in graphical models. Often, the hypertree width provides a more effective bound, since the empirical distributions are sparse.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。