Please use this identifier to cite or link to this item: doi:10.22028/D291-32952
Title: Causal inference on discrete data
Author(s): Budhathoki, Kailash
Language: English
Year of Publication: 2020
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
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.
Link to this record: urn:nbn:de:bsz:291--ds-329528
hdl:20.500.11880/30501
http://dx.doi.org/10.22028/D291-32952
Advisor: Vreeken, Jilles
Date of oral examination: 6-Jul-2020
Date of registration: 1-Feb-2021
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Professorship: MI - Keiner Professur zugeordnet
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
thesis.pdf764,27 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.