| Directed graphical models are a powerful statistical method to compactly describe directional or causal relationships among the set of variables in large-scale data. However, a number of statistical and computational challenges arise that make learning directed graphical models often impossible for large-scale data. These issues include: (1) model identifiability; (2) computational guarantee; (3) sample size guarantee; and (4) combining interventional experiments with observational data.;In this thesis, we focus on learning directed graphical models by addressing the above four issues. In Chapter 3, we discuss learning Poisson DAG models for modeling large-scale multivariate count data problems where each node is a Poisson random variable conditioning on its parents. We address the question of (1) model identifiability and learning algorithms with (2) computational complexity and (3) sample complexity. We prove that Poisson DAG models are fully identifiable from observational data using the notion of overdispersion, and present a polynomial-time algorithm that learns the Poisson DAG model under suitable regularity conditions.;Chapter 4 focuses on learning a broader class of DAG models in large-scale settings. We address the issue of (1) model identifiability and learning algorithms with (2) computational complexity and (3) sample complexity. We introduce a new class of identifiable DAG models which include many interesting classes of distributions such as Poisson, Binomial, Geometric, Exponential, Gamma, and many more, and prove that this class of DAG models is fully identifiable using the idea of overdispersion. Furthermore, we develop statistically consistent and computationally tractable learning algorithms for the new class of identifiable DAG models in high-dimensional settings. Our algorithms exploits the sparsity of the graphs and overdispersion property.;Chapter 5 concerns learning general DAG models using a combination of observational and interventional (or experimental) data. Prior work has focused on algorithms using Markov equivalence class (MEC) for the DAG and then using do-calculus rules based on interventions to learn the additional directions. However it has been shown that existing passive and active learning strategies that rely on accurate recovery of the MEC do not scale well to large-scale graphs because recovering MEC for DAG models are not successful large-scale graphs. Hence, we prove (1) model identifiability using the notion of the moralized graphs, and develop passive and active learning algorithms (4) combining interventional experiments with observational data.;Lastly in Chapter 6, we concern learning directed cyclic graphical (DCG) models. We focus on (1) model identifiability for directed graphical models with feedback. We provide two new identifiability assumptions with respect to sparsity of a graph and the number of d-separation rules, and compare these new identifiability assumptions to the widely-held faithfulness and minimality assumptions. Furthermore we develop search algorithms for small-scale DCG models based on our new identifiability assumptions. |
