[Statlist] Next talk: Friday, February 28, 2014 with Tom Claassen, Radboud University Nijmegen, The Netherlands

[Rey-Lutz Cecilia]

E-mail from the  Statlist at stat.ch  mailing list
_________________________________________________
ETH and University of Zurich

Organisers:
Profs. P. Bühlmann - R. Furrer - L. Held - T. Hothorn - H.R. Kuensch - M. Maathuis -
N. Meinshausen - S. van de Geer - M. Wolf

*****************************************************************************************

We are glad to announce the following talk

Friday, February 28, 2014 at 15.15h  ETH Zurich HG G 19.1
with Tom Claassen, Radboud University Nijmegen, The Netherlands
*****************************************************************************************

Title:
FCI+ or Why learning sparse causal models is not NP-hard.

Abstract:
Causal discovery lies at the heart of most scientific research today. It is the science of identifying presence or absence of cause-effect relations between certain variables in a model. Building up such a causal model from (purely) observational data can be hard, especially when latent confounders (unobserved common causes) may be present. For example, it is well-known that learning a minimal Bayesian network (BN) model over a (sub)set of variables from an underlying causal DAG is NP-hard, even for sparse networks with node degree bounded by k. Given that finding a minimal causal model is more complicated than finding a minimal DAG it was often tacitly assumed that causal discovery in general was NP-hard as well. Indeed the famous FCI algorithm, long the only provably sound and complete algorithm in the presence of latent confounders and selection bias, has worst-case running time that is exponential in the number of nodes N, even for sparse graphs.
Perhaps surprisingly then it turns out that we can exploit the structure in the problem to reconstruct the correct causal model in worst case N^(2k+4) independence tests, i.e. polynomial in the number of nodes. In this talk I will present the FCI+ algorithm as the first sound and complete causal discovery algorithm that implements this approach. It does not solve an NP-hard problem, and does not contradict any known hardness results: it just shows that causal discovery is perhaps more complicated, but not as hard as learning a minimal BN. In practice the running time remains close to the PC limit (without latent confounders, order k*N^(k+2), similar to RFCI). Current research aims to tighten complexity bounds and further optimize the algorithm.

*******************************************************************************************************
This abstract is also to be found under the following link: http://stat.ethz.ch/events/research_seminar
*******************************************************************************************************

Statlist mailing list
Statlist at stat.ch
https://stat.ethz.ch/mailman/listinfo/statlist