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
Residuality plays an essential role for learning finite automata.
While residual deterministic and nondeterministic
automata have been understood quite well, fundamental
questions concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman have initiated
a systematic study of residual AFAs and proposed an algorithm called AL*
-an extension of the popular L* algorithm - to learn AFAs.
Based on computer experiments they conjectured
that AL* produces residual AFAs, but have not been able to give a proof.
In this paper we disprove this conjecture by constructing a counterexample.
As our main positive result we design an efficient
learning algorithm, named AL**, and give a proof
that it outputs residual AFAs only.
In addition, we investigate the succinctness of these different FA types in more detail.
- 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
Residuality plays an essential role for learning finite automata.
While residual deterministic and non-deterministic
automata have been understood quite well, fundamental questions
concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman (2015) have initiated
a systematic study of residual AFAs and proposed an
algorithm called AL* – an extension of the popular L* algorithm
– to learn AFAs. Based on computer experiments
they have conjectured that AL* produces residual AFAs, but
have not been able to give a proof. In this paper we disprove
this conjecture by constructing a counterexample. As
our main positive result we design an efficient learning algorithm,
named AL**, and give a proof that it outputs residual
AFAs only. In addition, we investigate the succinctness of
these different FA types in more detail.
- 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
In
certain applications there may only be positive samples available to to
learn concepts of a class of interest, and this has to be done
properly, i.e. the hypothesis space has to coincide with the concept
class, and without false positives, i.e. the hypothesis always has be a
subset of the real concept (one-sided error). For the well studied class
of k-term DNF formulas it has been known that learning is difficult.
Unless RP = NP, it is not feasible to learn k-term DNF formulas properly
in a distribution-free sense even if both positive and negative samples
are available and even if false positives are allowed.
This paper constructs an efficient algorithm that for arbitrary fixed k,
if samples are drawn from distributions like uniform or q-bounded ones,
properly learns the class of k-term DNFs without false positives from
positive samples alone with arbitrarily small relative error.
- Martin R. Schuster, Maciej Liskiewicz:
New Abilities and Limitations of Spectral Graph Bisection.
Technischer Bericht 1701.01337,
arXiv,
2017.
Website anzeigen | Zusammenfassung anzeigen
Spectral
based heuristics belong to well-known commonly used methods which
determines provably minimal graph bisection or outputs "fail" when the
optimality cannot be certified. In this paper we focus on Boppana's
algorithm which belongs to one of the most prominent methods of this
type. It is well known that the algorithm works well in the random
\emph{planted bisection model} -- the standard class of graphs for
analysis minimum bisection and relevant problems. In 2001 Feige and
Kilian posed the question if Boppana's algorithm works well in the
semirandom model by Blum and Spencer. In our paper we answer this
question affirmatively. We show also that the algorithm achieves similar
performance on graph classes which extend the semirandom model.
Since the behavior of Boppana's algorithm on the semirandom graphs
remained unknown, Feige and Kilian proposed a new semidefinite
programming (SDP) based approach and proved that it works on this model.
The relationship between the performance of the SDP based algorithm and
Boppana's approach was left as an open problem. In this paper we solve
the problem in a complete way by proving that the bisection algorithm of
Feige and Kilian provides exactly the same results as Boppana's
algorithm. As a consequence we get that Boppana's algorithm achieves the
optimal threshold for exact cluster recovery in the \emph{stochastic
block model}. On the other hand we prove some limitations of Boppana's
approach: we show that if the density difference on the parameters of
the planted bisection model is too small then the algorithm fails with
high probability in the model.
- 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
