论文标题
关于反事实推理的复杂性
On the Complexity of Counterfactual Reasoning
论文作者
论文摘要
我们研究了反事实推理的计算复杂性，与结构因果模型（SCMS）的联想和介入推理的复杂性有关。我们表明，在两个计算框架的背景下，反事实推理并不比完全指定的SCM上的关联或介入推理要难。第一个框架是基于树宽的概念，包括经典变量消除和加入树算法。第二个框架是基于因果树宽的最新和精致的概念，该框架针对具有功能依赖性的模型，例如SCM。我们的结果是建设性的，基于双网络的（因果）树宽度（用于标准的反事实推理中，这些推理都将两个世界（真实和虚构的世界）带到基础SCM结构的（因果关系）宽度。特别是，我们表明后者（因果）宽度不超过前者的两倍。因此，如果可以在完全指定的SCM上进行关联或介入推理，则反事实推理也是可行的。我们将结果扩展到一般性的反事实推理，要求考虑两个以上的世界，并讨论结果的应用，以与部分指定的SCM与数据相结合，以与数据相反。我们最终提出了经验结果，以衡量反事实推理的复杂性与随机SCM上的关联/介入推理之间的差距。
We study the computational complexity of counterfactual reasoning in relation to the complexity of associational and interventional reasoning on structural causal models (SCMs). We show that counterfactual reasoning is no harder than associational or interventional reasoning on fully specified SCMs in the context of two computational frameworks. The first framework is based on the notion of treewidth and includes the classical variable elimination and jointree algorithms. The second framework is based on the more recent and refined notion of causal treewidth which is directed towards models with functional dependencies such as SCMs. Our results are constructive and based on bounding the (causal) treewidth of twin networks -- used in standard counterfactual reasoning that contemplates two worlds, real and imaginary -- to the (causal) treewidth of the underlying SCM structure. In particular, we show that the latter (causal) treewidth is no more than twice the former plus one. Hence, if associational or interventional reasoning is tractable on a fully specified SCM then counterfactual reasoning is tractable too. We extend our results to general counterfactual reasoning that requires contemplating more than two worlds and discuss applications of our results to counterfactual reasoning with a partially specified SCM that is coupled with data. We finally present empirical results that measure the gap between the complexities of counterfactual reasoning and associational/interventional reasoning on random SCMs.
