Causal discovery and prediction: methods and algorithms

Abstract

(English) This thesis focuses on the discovery of causal relations and on the prediction of causal effects. Regarding causal discovery, this thesis introduces a novel and generic method to learn causal graphs by performing a sequence of interventions, where each intervention is applied on a single value of the intervened variables, while minimizing the overall cost of the sequence of intervened and observed variables during the discovery process. Regarding causal effect prediction, this thesis introduces a comprehensive causal reasoning method for models recurrent in time. In this thesis, all causal models are assumed to contain hidden confounders that have an influence on observed variables in the causal model, except when explicitly referring to causal models without hidden confounders as a sub-case. Also all variables are assumed to be in a finite domain.

Contributions to the Discovery of Causal Relations Our method for the discovery of causal relations introduces several novelties. Firstly, we use interventions on a single value of the intervened variables. All previous methods require interventions on several values of the intervened variables in order to measure correlation or conditional independence among variables. By seeing do-calculus as a tool to predict systematically and numerically the effect of all the interventions that are possible, without having to actually perform them, we have moved the search space out of the real world, and eliminated the need for systematic correlation and independence testing in the real world. We assume that computational cost is not a concern, if we compare it with the cost of actually experimenting in the real world. Secondly, we accept any set of candidate graphs as input to our method. Previous knowledge may or may not be in the form of an equivalence class of graphs, and the set of candidate graphs may or may not have any particular parametrical characteristic. Some candidate graphs may have been discarded previously based on analyzing the available observational data, however no algorithm based on observational data only can identify the true graph of a causal model. As such, our method accepts any set of causal graph candidates, with the only assumption that the true graph, the solution to the problem, is included in the set of candidates. Thirdly, all causal graphs are assumed to contain hidden confounders, whereas most previous work focused on causal graphs without hidden confounders.

Contributions to the Prediction of Causal Effects The second subject of this thesis is causal prediction. The thesis focus is on dynamic causal reasoning: given the formal description of a dynamic causal system and a set of assumptions, we propose methods to evaluate the modified trajectory of the system over time, after an experiment or intervention. We assume that the observation time-scale is sufficiently small compared to the system dynamics, and that the causal model includes both the non-equilibrium causal relations and those under equilibrium states. We assume that a stable set of causal dependencies exist which generate the system evolution along time. Our proposed algorithms take such models as an input and predict their evolution over time, after an intervention. We also introduce transportability algorithms in the dynamic setting, where causal knowledge in source time-recurrent domains may be used for prediction in target time-recurrent domains.

(Español) Esta tesis estudia el aprendizaje de relaciones causales y la predicción de efectos causales. En cuanto al aprendizaje de relaciones causales, esta tesis presenta un método novedoso y genérico para aprender grafos causales mediante la realización de una secuencia de intervenciones, donde cada intervención se aplica sobre un único valor de las variables intervenidas, minimizando el coste total de la secuencia de variables intervenidas y observadas durante el proceso de aprendizaje. En cuanto a la predicción de efectos causales, esta tesis introduce un método de razonamiento causal para modelos recurrentes en el tiempo. En esta tesis, asumimos que los modelos causales contienen variables ocultas que tienen influencia sobre las variables observadas del modelo, excepto cuando se hace referencia explícita a modelos causales sin variables ocultas como subcaso. También asumimos que todas las variables están en un dominio finito.

Contribución al aprendizaje de relaciones causales Nuestro método para el aprendizaje de relaciones causales introduce varias novedades. En primer lugar, utilizamos intervenciones sobre un único valor de las variables intervenidas. Todos los métodos anteriores requieren intervenciones sobre varios valores de las variables intervenidas para medir la correlación o la independencia condicional entre variables. Al utilizar el do-calculus como una herramienta para predecir sistemática y numéricamente el efecto de todas las intervenciones que son posibles, sin tener que realizarlas en la realidad, trasladamos el espacio de búsqueda fuera del mundo real y eliminamos la necesidad de correlación sistemática y pruebas de independencia condicional en el mundo real. Asumimos que disponemos de recursos computacionales ilimitados, y que disponer de ellos es preferible al costo de experimentar en el mundo real. En segundo lugar, aceptamos cualquier conjunto de grafos candidatos. El conocimiento previo de algunas partes del modelo puede tener o no la forma de una clase de grafos de equivalencia, y el conjunto de grafos candidatos puede tener o no alguna característica paramétrica particular. Es posible que algunos grafos candidatos se hayan descartado previamente en función del análisis de los datos observacionales disponibles; sin embargo, ningún algoritmo basado solo en datos observacionales puede identificar el grafo completo de un modelo causal. Como tal, nuestro método acepta cualquier conjunto de candidatos de gráfos causales, con la única suposición de que el grafo verdadero, la solución al problema, está incluido en el conjunto de candidatos. En tercer lugar, asumimos que todos los grafos causales contienen variables ocultas, mientras que la mayoría de los trabajos anteriores se centran en grafos causales sin variables ocultas.

Contribución a la predicción de efectos causales El segundo tema central de esta tesis es la predicción causal. El enfoque de la tesis es el razonamiento causal dinámico: dada la descripción formal de un sistema causal dinámico en el tiempo, proponemos métodos para evaluar la trayectoria modificada del sistema a lo largo del tiempo, después de un experimento o intervención. Suponemos que la escala de tiempo de observación es lo suficientemente pequeña en comparación con la dinámica del sistema, y que el modelo causal incluye tanto las relaciones causales de no equilibrio como aquellas en estados de equilibrio. Suponemos que existe un conjunto estable de dependencias causales que generan la evolución del sistema a lo largo del tiempo. Nuestros algoritmos se basan en estos modelos y predicen su evolución en el tiempo, después de una intervención. También presentamos algoritmos de transportabilidad en el entorno dinámico, donde el conocimiento experimental en dominios recurrentes en el tiempo se puede usar para la predicción en los otros dominios recurrentes en el tiempo que tengan las mismas relaciones causales.