Large Structures Seminar: Liam Solus

The focus of this talk will be an application of convex polytopes to causal inference. Graphical models based on directed acyclic graphs (DAGs), also known as Bayesian networks, are used to model complex cause-and-effect systems across a vast number of research areas including computational biology, epidemiology, sociology, and environmental management. A DAG model is family of joint probability distributions over the nodes of a DAG G that entail a set of conditional independence (CI) relations encoded by the nonedges of G. A fundamental problem in causality is to learn an unknown DAG G based only on a set of observed conditional independence relations. Since multiple DAGs can encode the same set of CI relations, a property termed Markov equivalence, the goal is to identify efficient algorithms that consistently recover a DAG within the correct Markov equivalence class. We will describe a pair of greedy algorithms for DAG model selection that operate via edge walks on a family of generalized permutohedra called DAG associahedra. We will present consistency guarantees for these algorithms, and compare them with the more classical approaches to Bayesian model selection in both efficiency and strength of satisfied identifiability assumptions. To better understand the efficiency of these new algorithms, we study two new generating functions associated to a graph which share rich connections with classic combinatorial structures.