50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Kausalität: algorithmischer Ansatz und komplexitätstheoretische Perspektive


Projektbeschreibung

Projektname
Kausalität: algorithmischer Ansatz und komplexitätstheoretische Perspektive
Leitung
Prof. Dr. Maciej Liskiewicz
Laufzeit und Drittmittelgeber
Beginn 2016, voraussichtliches Ende 2020. Förderung durch die DFG.
Projektmitarbeiter
Benito Bela van der Zander,
Kooperationspartner
Dr. Johannes Textor
Zusammenfassung

Die Erforschung kausaler Zusammenhänge ist ein Hauptanliegen empirischer Wissenschaften. Auch gesellschaftlich sind die Ursachen von Krankheiten, Wirtschaftskrisen und anderen komplexen Phänomenen von großem Interesse. Kausale Inferenz erfordert meist die Kombination von Vorwissen mit experimentellen Daten oder Beobachtungen. Die in den letzten Jahrzehnten maßgeblich von Judea Pearl entwickelte Kausalitätstheorie ermöglicht eine intuitive, mathematisch fundierte Modellierung kausaler Zusammenhänge als gerichtete oder teilweise gerichtete Graphen. Aus solchen grafischen Modellen lassen sich Formeln ableiten, mit denen unter bestimmten Annahmen kausale Effekte identifiziert werden können.

Der grafische Modellierungsansatz erregt zur Zeit besonders in der Epidemiologie, aber auch in der Soziologie und anderen Wissenschaften erhebliches Interesse. Bei der Anwendung in der Praxis ergeben sich allerdings noch teils erhebliche algorithmische Schwierigkeiten. So gibt es für einige wichtige Theoreme der Kausalitätstheorie noch keine konstruktiven Beweise, aus denen sich effiziente Konstruktionsverfahren ableiten lassen würden, während andere Theoreme nur für eingeschränkte Klassen von Graphen anwendbar sind. In Zusammenarbeit mit empirischen Wissenschaftlern haben wir Probleme zusammengetragen, für die aktuell allgemeinere und/oder effizientere Lösungen benötigt werden. Ziel unseres Projekts ist es, diese Probleme aus algorithmischer und komplexitätstheoretischer Sicht genauer zu untersuchen.

Unser Hauptfokus liegt hierbei auf der Identifikation und Schätzung kausaler Effekte, wobei wir auch auf das Lernen möglicher Kausalstrukturen anhand beobachteter Daten eingehen. Durch die grafische Basis der Kausalitätstheorie können wir uns hier fortgeschrittene Techniken aus dem Bereich der Graphalgorithmen und der Komplexitätstheorie zu Nutzen machen. Neben negativen Ergebnissen wie NP-Härtebeweisen hoffen wir hierdurch insbesondere praktisch nutzbare Algorithmen zu erhalten. Dieses Projekt ist in eine Kollaborationsstruktur eingebettet, die es uns ermöglicht, unsere Ergebnisse direkt in die von empirischen Wissenschaftlern genutzte Software einfließen zu lassen.