Causal Combinatorics

QC 2023-05-22

Abstract

Explaining data in a concise and efficient manner has become increasingly important in today's society. This thesis pertains to the problem of finding causal links within data, and how that can be done from a mathematical perspective. Using the framework of graphical models has several advantages, from interpretability to efficiency. One of the most commonly used graphical model are directed acyclic graphs (DAGs), that has been used to model complex problems within a plethora of areas. Usually, the model in question is either assumed or based on experiments, both of which are methods that have different drawbacks. Inferring a DAG from data alone is however a hard problem and a central question within causal discovery. Due to the combinatorial explosion of the number of DAGs, we cannot do this by hand and therefore we need to design algorithms specifically for this task; several algorithms already exists within this area: PC, GES, MMHC, and Greedy SP, to name but a few. Studený proposed an alternative viewpoint using integer valued multi-set functions (imsets). This in turn allows us to see DAG discovery as a linear optimization problem. Specifically we consider the characteristic imset polytope, $\CIM_n$, whose vertices correspond to Markov equivalence classes of DAGs. A central theme of this thesis is understanding the edge structure and how this can be used in algorithms. 

Many of the best performing algorithms use a fixed set of moves to greedily transform one DAG to another optimizing a score function. In this thesis we show that the most commonly used moves has a polyhedral interpretation as an edge-walk along $\CIM_n$, thus provide a geometric perspective on these algorithms. This in turn allow us to design algorithms that expand upon earlier algorithms and discuss how certain faces of $\CIM_n$ can be efficiently used to improve on state of the art. Of specific importance are the faces of $\CIM_n$ with clear graphical interpretation, for example $\CIM_G$, the convex hull of all imsets encoding for DAGs with a fixed skeleton $G$.  Via introducing a algorithm skeletal greedy CIM, that use conditional independence test to find $G$, and then proceeds in a greedy fashion, we show that these are not only interesting from a theoretical standpoint, but are directly applicable to real data. 

In general very little is known about the edge structure of $\CIM_n$, especially in terms of the DAGs. However, if we assume that $G$ is a tree, we can in fact give a complete description of all edges of $\CIM_G$. This allow us to give several connections to other well-studied polytopes. Moreover this gives a natural generalization of skeletal greedy CIM, for learning directed trees, sometimes referred to as polytrees.The additional edges, or moves, turns out to be especially useful when we do not have a lot of data. 

An important measure on the complexity of an edge-walk is the diameter of a polytope. We prove low-degree polynomial bounds, in the number of nodes of the DAGs, of the diameter of $\CIM_n$, $\CIM_G$, and other characteristic imset polytopes. This is surprising as the dimension grows exponentially.

As a final method of understanding the edge structure of the characteristic imset polytopes we define the rhombus criterion.It is a simple sufficient condition to determine when two vertices can not form an edge.  For several characteristic imset polytopes, the rhombus criterion is both necessary and sufficient, and hence characterize all edges. Therefore we raise the question when this is true for characteristic imset polytopes. We show that almost all pair of vertices of the chordal graph polytope fulfill the rhombus criterion and conjecture it holds for every pair. Using this criterion we also provide a way to compute the edge structure of some $0/1$-polytopes that scales better with dimension.Thus we can computationally show that the rhombus criterion describes the edge structure of $\CIM_n$ for $n\leq 5$ and the edge structure for the chordal graph polytope when $n\leq 6$.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-327056