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.

Projekt-Veröffentlichungen

2018

  • Benito van der Zander, Maciej Liskiewicz, Johannes Textor:
    Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework.
    Technischer Bericht arXiv:1803.00116 (2018), arXiv preprint, 2018.
    PDF anzeigen

2017

  • Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
    Learning Residual Alternating Automata.
    Electronic Colloquium on Computational Complexity (ECCC), 24(46)2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
    Learning Residual Alternating Automata.
    Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), S. 1749-1755. AAAI Press, 2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
    Proper Learning of k-term DNF Formulas from Satisfying Assignments.
    Electronic Colloquium on Computational Complexity (ECCC), 24(114)2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Martin R. Schuster, Maciej Liskiewicz:
    New Abilities and Limitations of Spectral Graph Bisection.
    Technischer Bericht 1701.01337, arXiv, 2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Martin R. Schuster, Maciej Liskiewicz:
    New Abilities and Limitations of Spectral Graph Bisection.
    In 25th Annual European Symposium on Algorithms, (ESA) 2017, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.

2016

  • Johannes Textor, Benito van der Zander, Mark S. Gilthorpe, Maciej Liskiewicz, George T.H. Ellison:
    Robust causal inference using Directed Acyclic Graphs: the R package ’dagitty’.
    International Journal of Epidemiology, 6(45):1887-1894, 2016.
    Website anzeigen
  • Benito Van der Zander, Maciej Liskiewicz:
    On Searching for Generalized Instrumental Variables.
    In Proceedings of the The 19th International Conference on Artificial Intelligence and Statistics (AISTATS'16), S. 1214-1222. JMLR Proceedings, 2016.
    Website anzeigen
  • Benito van der Zander, Maciej Liskiewicz:
    Separators and Adjustment Sets in Markov Equivalent DAGs.
    In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI'16), Phoenix, Arizona USA, S. 3315-3321. AAAI Press, 2016.
    Website anzeigen

2015

  • Johannes Textor, Alexander Idelberger, Maciej Liskiewicz:
    On the Faithful DAGs of a Dependency Graph.
    In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI'15), S. 882-891. AUAI Press, 2015.
    PDF anzeigen
  • Benito van der Zander, Johannes Textor, Maciej Liskiewicz:
    Efficiently Finding Conditional Instruments for Causal Inference.
    In (IJCAI'15), Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, July 25-31, 2015, S. 3243-3249. AAAI Press / International Joint Conferences on Artificial Intelligence, 2015.
    PDF anzeigen

Projekt-Entwicklungen

Im Rahmen des Projektes wurde die folgende Softwarebilbiothek entwickelt
DAGitty tool