Causal inference on discrete data

Abstract

Causal inference is one of the fundamental problems in science. To make absolute statements about cause and effect, carefully designed experiments are necessary, in which we consider representative populations, instrument the putative cause, and control for everything else. In practice, setting up such an experiment is often impossible, too expensive, or unethical. The only option then is to consider causal inference from observational studies where data has not been obtained in a controlled manner. A particularly interesting setting is to tell cause from effect between a pair of random variables X and Y given a sample from their joint distribution. For a long period of time, it was thought to be impossible to distinguish between causal structures X → Y and Y → X from observational data as the factorisation of the joint distribution is the same in both directions. In the past decade, researchers have made a long stride in this direction by exploiting sophisticated properties of the joint distribution. Most of the existing methods, however, are for continuous real-valued data. In the first part of the thesis, we consider bivariate causal inference on different discrete data settings—--univariate i.i.d., univariate non-i.i.d., and multivariate i.i.d. pairs. To this end, we build upon the principle of algorithmic independence of conditionals (AIC), which states that marginal distribution of the cause is algorithmically independent of conditional distribution of the effect given the cause. However, as Kolmogorov complexity is not computable, we approximate the AIC from above through the statistically sound Minimum Description Length (MDL) principle. On univariate i.i.d. and non-i.i.d. pairs, where causal mechanisms are simple, we use refined MDL codes that are minimax optimal w.r.t. a model class. We resort to crude MDL codes on a pair of multivariate i.i.d. variables. Although useful, saying that there exists a causal relationship from a set of variables towards a certain variable of interest does not always fully satisfy one's curiosity; for a domain expert it is of particular interest to know those conditions that are most effective, such as the combinations of drugs and their dosages that are most effective towards recovery. Motivated by this problem, in the second part of this thesis, we consider discovering statistically reliable causal rules from observational data. Overall, extensive evaluations show that methods proposed in this thesis are highly accurate, and discover meaningful causations from real-world data.

Kausale Inferenz ist eines der grundlegenden Probleme in der Wissenschaft. Um absolute Aussagen über Ursache und Wirkung zu treffen sind sorgfältig geplante Experimente notwendig, in denen wir repräsentative Populationen betrachten, die mutmaßliche Ursache messen und alle weiteren Umstände kontrollieren. In der Praxis ist die Einrichtung eines solches Experiments oft unmöglich, zu teuer oder unethisch. Die einzige Möglichkeit besteht dann darin kausale Schlussfolgerungen aus unkontrollierten Beobachtungsstudien zu ziehen. Ein Problem von besonderem Interesse ist die Unterscheidung zwishchen Ursache und Wirkung von einem Paar von Zufallsvariablen X and Y. Lange Zeit wurde angenommen dass es unmöglich ist zwischen den kausalen Strukturen X !Y und Y !X auf Grundlage von Beobachtungsdaten zu unterscheiden, da die Faktorisierung der gemeinsamen Verteilung in beide Richtungen die gleiche ist. Im letzten Jahrzehnt haben Forscher jedoch große Fortschritte in diesem Gebiet gemacht, indem Sie Komplexe Eigenschaften der gemeinsamen Verteilung geschickt ausnutzen. Die meisten bestehenden Methoden beziehen sich jedoch auf kontinuierliche, reellwertige Daten. Im ersten Teil der Arbeit, betrachten wir bivariate kausale Inferenz auf verschiedenen diskreten datenquellen—univariat i.i.d., univariat nicht-i.i.d. und multivariat i.i.d. Paare. Zu diesem Zweck bauen wir auf dem Prinzip der algorithmischen Unabhängigkeit von Konditionalen (AIC) auf, das besagt, dass die Randverteilung der Ursache algorithmisch unabhängig von der bedingten Verteilung der Wirkung gegeben der Ursache ist. Da die Kolmogorow-Komplexität jedoch nicht berechenbar ist, nähern wir uns der AIC mithilfe des statistisch soliden Minimum Description Length (MDL) Prinzips von oben an. Bei univariat i.i.d. und nicht i.i.d. Paaren, wo kausale Mechanismen einfach sind, verwenden wir “refined” MDL Kodierungen welche minimax optimal bzgl. einer Modellklasse sind. Wir greifen auf “crude” MDL Kodierungen für multivariat i.i.d. Variablen Paare zurück. Obwohl die Aussage, dass ein kausaler Zusammenhang von einer Menge von Variablen gegenüber einer bestimmten Variable existiert nützlich ist, erfüllt nicht es immer vollständig jedermanns Interesse. Für Experten in einem Bereich ist es von besonderem Interesse die effektivsten Bedingungen zu kennen, wie z.B. die Kombination und Dosierung von Medikamenten, die für die Genesung am effektivsten sind. Durch diese Problemstellung motiviert, betrachten wir im zweiten Teil dieser Arbeit die Entdeckung kausaler Regeln aus Beobachtungsdaten. Allgemein zeigen umfangreiche Evaluierungen dass die vorgestellten Methoden in dieser Arbeit sehr genau sind und sinnvolle Ursache- Wirkungsverhaltnisse gefunden werden.