AF: Small: Algorithms and Information Theory for Causal Inference

California Institute Of Technology, Pasadena CA

Investigators

Abstract

This project is concerned, firstly, with algorithmic and information-theoretic aspects of Causal Inference. With the exception of some scientific data that is gathered purely for knowledge, most data is gathered for the purpose of potential intervention: this holds for medicine, public health, environmental regulations, market research, legal remedies for discrimination, and in many other domains. A decision-maker cannot take advantage of correlations and other structural characterizations that are discovered in data without knowing about causal relationships between variables. Historically, causality has been teased apart from correlation through controlled experiments. However there are several good reasons that one must often make do with passive observation: ethical reasons; governance constraints; and uniqueness of the system and the inability to re-run history. Absent experiments, we are without the principal arsenal of the scientific method. Yet there is a special class of systems in which it is possible to perform causality inference purely from passive observation of the statistics. For a system to fall in this class one must be able to establish on physical grounds that certain observable variables are statistically independent of certain others, conditional on a third set being held fixed; the formalism for this is ``semi-Markovian graphical models". It is known which semi-Markovian models fall in this class, subject to the assumption of perfect statistics. From this starting point there remain significant theoretical challenges before these ideas can have the greatest possible impact on practice. Some of the challenges to be addressed include: (1) The PI will aim to quantify how the stability (condition number) of causal identification depends on the various sources of uncertainty (statistical error; numerical error; model error) and as a function of the structure of the graphical model. The purpose is both to understand what inference is justifiable from existing data, and to impact study design so that data with the greatest leverage is collected. For the former objective, in particular, the PI seeks an efficient algorithm to compute the condition number of a given semi-Markovian model at the specific observed statistics. For the last objective the PI seeks an efficient algorithm to compute the worst-case condition number of a given semi-Markovian model. (2) Existing causal identification algorithms, applied to data inconsistent with the model (which is unavoidable due to statistical error, and normally also due to model error), will yield an inference inconsistent with the model. The project will help to understand if projection onto the model may improve stability. (3) One of the obstacles to use of existing methods is that they require sample size exponential in the size of the graphical model. The project aims to determine when it is possible to infer causality using only the marginal distributions over small subsets of the observable variables; this will reduce sample size and likely improve condition number. (4) In the majority of semi-Markovian models, causality is not identifiable. This leaves open however the possibility of determining (or giving a nontrivial outer bound for) the feasible interval of causal effects. No effective algorithm is currently known for this problem, and we wish to provide one. Such an algorithm could be used to show that an intervention is favorable despite the effect not being fully identifiable. (5) The project aims to lift the causal-inference algorithm to time series, as well as study the connections with the distinct techniques (Granger causality and Massey's directed information) normally used in this setting. Secondary emphases of the project include broader research in theoretical computer science. In particular, studying connections between ``boosting" or ``multiplicative weights" methods used in algorithms and machine learning, and their variants which arise out of selection or self-interest in the system dynamics of ecosystems (``weak selection") and economic marketplaces (``tatonnement"). Inseparably from the research effort, the PI will train students and postdocs in these and related areas of the theory of computation.