BACKSHIFT: Learning causal cyclic graphs from unknown shift interventions
We propose a simple method to learn linear causal cyclic models in the presence of latent variables. The method relies on equilibrium data of the model recorded under a specific kind of interventions ("shift interventions"). The location and strength of these interventions do not have to be known and can be estimated from the data. Our method, called BACKSHIFT, only uses second moments of the data and performs simple joint matrix diagonalization, applied to differences between covariance matrices. We give a sufficient and necessary condition for identifiability of the system, which is fulfilled almost surely under some quite general assumptions if and only if there are at least three distinct experimental settings, one of which can be pure observational data. We demonstrate the performance on some simulated data and applications in flow cytometry and financial time series.
%%%%%%%%%%%%%%%%%%%%%%%%%%% Update after authors response: I thank the authors for taking the time to clearly and honestly respond to my (our) questions. I am even more convinced that the work is worth presenting at NIPS. Probably my lack of understanding (or me being too lazy to read the appendices) but would really like to see the step-by-step explanation on the link between Assumption C and the ability of the algorithm to identify situations where the permutation (1 step only? Other remark: possible since you only have few nodes as well right otherwise the permutation space simply can't be explored?) which makes CP < 1.%%%%%%%%%%%%%%%%%%%%%%%%%%% The manuscript introduces linear causal dependencies in a complex system as measured by x's. The originality is that the location of the intervened variables is unknown. The authors present assumptions (section 2.3) under which they derive theoretical results in terms of model identifiability (section 3), in both an ideal setting where the sample size is infinite (algorithm presented in section 2.4) and when it isn't (algorithm presented in section 2.5). A good aprt of the paper is devoted to much appreciated numerical experiments on both simulated (ground truth known) and real data networks.I quite appreciated reading this paper and found the problem well motivated and nicely tackled. The only nuance is that it is not a huge breakthrough, rather a nice and useful increment from existing theory.Comments to the authors:- l36, def of "equilibrium data" is never clear.- l44, "solutions to (1)": mind that (1) is only a model. I guess you mean solutions of an optimisation problem related to Eqn (1) by a score function; this is detailed in sections 2.4 and 2.5 I know so merely a language issue here.- l61: "surgical" used here and defined later.- l62: iterations? Haven't talked about an algorithm yet- l64: interactionS (typo)- l84: unknown location of interventions; OK why not but in fields like modern Molecular Biology, this is fully determined, e.g. gene KO. Or on the contrary there would be way too many interventions at the same time (e.g. genetical genomics data sets where tiny interventions are performed at each node at the same time, see Mooij et al NIPS 2015 or Vignes et al. PLoS ONE 2011)- l102-103 is intriguing, could you clarify?- section 2.3: the 3 assumptions are in fact 3 (coherent?) sets of assumptions? Sentences in each item are not always equivalent. Moreover I-B invertible roughly forbids considering high-dimensional or even moderate dimension scenarii. So you don't really compare to many approaches you quote? With nice implementations like Kalisch and Buhlmann JMLR 2007 or their pcalg R package. In the same vein, see also Rau et al. BMC Syst. Biol. 2013.- l177: can you expand why Eqn (7) motivates the estimator in Eqn (10)? Rational for the loss defined by L as well?- l204, can you quickly explain how FFDiag [23] ( I mean how it works, reads like the difficult part in your computational work) allows you to solve problem (11)?- l207: (a) permuting -> looks like a permutations of potentially many edges? Can be harsh at the end or do I understand incorrectly? For permutation effect on columns of an adjacency matrix, see Champion et al. http://arxiv.org/abs/1507.02018- l212, variant of LAP -> any guarantee of an acceptable solution at this step?- l268: producing the code is VERY appreciated!