Causal discovery with ancestral graphs

Thesis

Graphical models serve as a visual representation that captures the underlying conditional independence relationships within distributions, employing either directed or undirected graphs. In this thesis, we explore maximal ancestral graphs (MAGs), which is an extension to the conventionaldirected acyclic graphs (DAGs). While DAGs excel in illustrating causal relationships, they fail to capture all the conditional independences on the margin in the absence of latent confounders and selection bias. MAGs provide a more comprehensive depiction of complex dependencies by encompassing both direct causal connections and indirect influences stemming from latent variables and selection bias.

The scalability and accuracy of MAG learning algorithms have been some problems due to the complexity of the space of Markov equivalence classes (MECs) of MAGs and instability of scoring criteria. We first use the concept of heads, tails and parametrizing sets to characterize Markov equivalent MAGs. Then we study imsets of MAGs to address the above issues.

The framework of imsets (Studeny, 2006) is an algebraic approach to represent conditional independences. Given the remarkable success of standard imsets within DAGs, where they efficiently represent MECs and offer reliable scoring criteria, we endeavor to extend this framework to MAGs. Through an exploration of 0-1 imsets defined by parametrizing sets, we show under which conditions does this extended `standard imset' of MAGs define the correct model. Consequently, we refine the ordered local Markov property of MAGs (Richardson, 2003), demonstrating that the newly proposed refined Markov property can be constructed in polynomial time if we bound maximal head size.

Finally, we apply the above results to develop novel score-based learning algorithms for MAGs. To efficiently traverse between MECs of MAGs, we identify some important graphical features within MAGs whose independence models are subsets of others. Leveraging the imsets derived from the refined Markov property, we establish a consistent scoring criterion, offering an alternative to BIC by relying solely on estimates of entropy over subsets of variables. Empirical experiments show promising results when compared to state-of-the-art algorithms.

Authors: Hu, Z

• DOI: 10.5287/ora-9oyxx44gv
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: maximal ancestral graphs; causal discovery; graphical model
• Subjects: Statistic