Causality: an algorithmic framework and a computational complexity perspective

建立因果关系是实证科学的一个基本目标，找到疾病、经济危机或其他复杂现象的原因对政策制定至关重要。这种因果推断通常需要将观察到的和干预性的数据与现有的知识相结合。在过去的几十年里，Judea Pearl和其他人开发了因果推理的结构方法，使研究人员能够模拟复杂的因果关系，推理其含义，并估计利益的因果效应。在这种方法中，因果知识编码使用有向图或部分有向图，这是一个直观的表示，是可读的non-professional. Graphical因果建模方法目前收到大量的关注，在流行病学，社会学和其他学科，但尚未得到广泛应用。其应用的一个重要障碍是算法性质：结构因果关系的几个关键结果要么不通用，即不适用于某些类型的输入，要么被证明是非建设性的，这样就缺乏找到解决方案的有效算法。通过与应用领域的科学家合作，我们已经确定了几个具有现实意义的问题，这些问题需要更通用和/或更有效的解决方案。本提案的目标是从算法和计算复杂性的角度来研究这些问题。我们的主要重点将是关于因果效应的识别和估计的问题，其次重点是从数据中学习可能的因果结构。结构因果建模中使用的图形语言使我们能够应用离散和图形算法技术以及计算复杂性理论的先进方法。虽然我们希望获得一些负面的结果，如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.