Causality: an algorithmic framework and a computational complexity perspective

建立因果关系是实证科学的基本目标，寻找疾病、经济危机或其他复杂现象的原因对决策具有重要意义。这种因果推理通常需要将观察到的和介入的数据与现有知识结合起来。在过去的几十年里，Judea Pearl和其他人发展了因果推理的结构方法，使研究人员能够对复杂的因果关系进行建模，对其含义进行推理，并估计感兴趣的因果效应。在这种方法中，因果知识使用有向图或部分有向图进行编码，这是一种非专业人员可读的直观表示。图形因果建模方法目前在流行病学、社会学等学科中得到了广泛关注，但尚未得到广泛应用。其应用的一个重要障碍是算法性质：结构因果关系的几个关键结果要么不是一般的，即不适用于某些类型的输入，要么被证明是非建设性的，因此缺乏有效的算法来寻找解决方案。通过与应用领域的科学家合作，我们已经确定了几个现实世界的重要问题，这些问题需要更通用和/或更有效的解决方案。本提案的目标是从算法和计算复杂性的角度来研究这些问题。我们的主要焦点将是关于因果效应的识别和估计的问题，其次是从数据中学习可能的因果结构。结构因果建模中使用的图形语言使我们能够应用离散和图形算法技术以及计算复杂性理论的先进方法。虽然我们期望获得一些负面结果，如np -硬度结果，但主要目标是提供有效的算法，并且与我们的合作者一起，我们的目标是将我们积极的算法结果以工作软件包的形式反馈到应用领域。

Establishing cause-effect relationships is a fundamental goal of empirical science, and finding the causes of diseases, economic crises, or other complex phenomena is of great importance for policy-making. Such causal inference typically requires combining observed and interventional data with existing knowledge. The structural approach to causal inference, developed over the past decades by Judea Pearl and others, allows researchers to model complex causal relationships, reason about their implications, and estimate causal effects of interest. In this approach, causal knowledge is encoded using directed or partially directed graphs, which is an intuitive representation that is readable by non-specialists.The graphical causal modeling approach currently receives substantial attention in Epidemiology, Sociology and other disciplines, but is not yet widely applied. An important barrier to its application is of algorithmic nature: Several key results of structural causality are either not general, i.e. do not apply for certain types of inputs, or are proved non-constructively, such that efficient algorithms to find solutions are lacking. In collaboration with scientists from application areas, we have identified several problems of real-world importance that require more general and/or more efficient solutions. The goal of this proposal is to study those problems from an algorithmic and computational complexity perspective.Our main focus will be on questions concerning identification and estimation of causal effects, with a secondary focus on learning possible causal structures from data. The graphical language used in structural causal modeling allows us to apply discrete- and graph-algorithmic techniques as well as advanced methods of computational complexity theory. While we expect to obtain some negative outcomes like NP-hardness results, the main goal is to provide effective algorithms, and with our collaborators we aim to feed our positive algorithmic results back into the application areas in the form of working software packages.