Establishing cause-effect relationships is a fundamental goal of empirical science, and finding the
causes of diseases, economic crises, or other complex phenomena is of great importance for policy-making.
Such causal inference typically requires combining observed and interventional data with existing knowledge.
The structural approach to causal inference, developed over the past decades by Judea Pearl and others, allows
researchers to model complex causal relationships, reason about their implications, and estimate causal effects of
interest. In this approach, causal knowledge is encoded using directed or partially directed graphs, which is an
intuitive representation that is readable by non-specialists.
The graphical causal modeling approach currently receives substantial attention in Epidemiology, Sociology and
other disciplines, but is not yet widely applied. An important barrier to its application is of algorithmic nature:
Several key results of structural causality are either not general, i.e. do not apply for certain types of inputs,
or are proved non-constructively, such that efficient algorithms to find solutions are lacking. In collaboration
with scientists from application areas, we have identified several problems of real-world importance that require
more general and/or more efficient solutions. The goal of this proposal is to study those problems from an algorithmic
and computational complexity perspective.
Our main focus will be on questions concerning identification and estimation of causal effects, with a secondary
focus on learning possible causal structures from data. The graphical language used in structural causal modeling
allows us to apply discrete- and graph-algorithmic techniques as well as advanced methods of computational complexity
theory. While we expect to obtain some negative outcomes like NP-hardness results, the main goal is to provide effective
algorithms, and with our collaborators we aim to feed our positive algorithmic results back into the application areas
in the form of working software packages.
Project-Publications
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
Project-Development
In the context of this project the following software library was developed
DAGitty tool
