DISENTANGLE CAUSAL MECHANISMS
Year: 2020

Abstract:
We propose to use a meta-learning objective that maximizes the speed of transfer on a modified distribution to learn how to modularize acquired knowledge and discover causal dependencies. In particular, we focus on how to factor a joint distribution into appropriate conditionals, consistent with the causal directions. To replace the assumption that the test cases are of the same distribution as the training examples, this method exploits the assumption that the changes in distributions are localized (e.g. to one of the marginals, for example due to an intervention on a cause). We prove that under this assumption of localized changes in causal mechanisms, the correct causal graph will tend to have only a few of its parameters with non-zero gradient, i.e. that need to be adapted (those of the modified variables). We argue and observe experimentally that this leads to faster adaptation, and use this property to define a meta-learning surrogate score which, in addition to a continuous parametrization of graphs, would favour correct causal graphs, making it possible to discover causal structure by gradient-based methods. Finally, motivated by the AI agent point of view (e.g. of a robot discovering its environment autonomously), we consider how the same objective can discover the causal variables themselves, as a transformation of observed low-level variables with no causal meaning. Experiments in the two-variable case validate the proposed ideas and theoretical results.

heading: 1 INTRODUCTION
text: The data used to train our models is often assumed to be independent and identically distributed (iid.), according to some unknown distribution. Likewise, the performance of a machine learning model is typically evaluated using test samples from the same distribution, assumed to be representative of the learned system’s usage. While these assumptions are well analyzed from a statistical point of view, they are rarely satisfied in many real-world applications. For example, an accident on a major highway could completely perturb the trajectories of cars, and a driving policy trained in a static way might not be robust to such changes. Ideally, we would like our models to generalize well and adapt quickly to out-of-distribution data.
However, this comes at a price – in order to successfully transfer to a novel distribution, one might need additional information about these distributions. In this paper, we are not considering assumptions on the data distribution itself, but rather on how it changes (e.g., when going from a training distribution to a transfer distribution, possibly resulting from some agent’s actions). We focus on the assumption that the changes are sparse when the knowledge is represented in an appropriately modularized way, with only one or a few of the modules having changed. This is especially relevant when the distributional change is due to actions by one or more agents, because agents intervene at a particular place and time, and this is reflected in the form of the interventions discussed in the causality literature (Pearl, 2009; Peters et al., 2016), where a single causal variable is clamped to a particular value or a random variable. In general, it is difficult for agents to influence many underlying causal variables at a time, and although this paper is not about agent learning as such, this is a property of the world that we propose to exploit here, to help discovering these variables
1 Université de Montréal, 2 CIFAR Senior Fellow, 3 École Polytechnique Montréal, 4 Max-Planck Institute for Intelligent Systems, Tübingen, 5 Canada CIFAR AI Chair
and how they are causally related to each other. In this context, the causal graph is a powerful tool because it tells us how perturbations in the distribution of intervened variables will propagate to all other variables and affect their distributions.
As expected, it is often the case that the causal structure is not known in advance. The problem of causal discovery then entails obtaining the causal graph, a feat which is in general achievable only with strong assumptions. One such assumption is that a learner that has learned to capture the correct structure of the true underlying data-generating process should still generalize to the case where the structure has been perturbed in a certain, restrictive way. This can be illustrated by considering the example of temperature and altitude from Peters et al. (2017): a learner that has learned to capture the mechanisms of atmospheric physics by learning that it makes more sense to predict temperature from the altitude (rather than vice versa) given training data from (say) Switzerland, will still remain valid when tested on out-of-distribution data from a less mountainous country like (say) the Netherlands. It has therefore been suggested that the out-of-distribution robustness of predictive models can be used to guide the inference of the true causal structure (Peters et al., 2016; 2017).
How can we exploit the assumption of localized change? As we explain theoretically and verify experimentally here, if we have the right knowledge representation, then we should get fast adaptation to the transfer distribution when starting from a model that is well trained on the training distribution. This arises because of our assumption that the ground truth data generative process is obtained as the composition of independent mechanisms, and that very few ground truth mechanisms and parameters need to change when going from the training distribution to the transfer distribution. A model capturing a corresponding factorization of knowledge would thus require just a few updates, a few examples, for this adaptation to the transfer distribution. As shown below, the expected gradient on the unchanged parameters would be near 0 (if the model was already well trained on the training distribution), so the effective search space during adaptation to the transfer distribution would be greatly reduced, which tends to produce faster adaptation, as found experimentally. Thus, based on the assumption of small change in the right knowledge representation space, we can define a meta-learning objective that measures the speed of online adaptation in order to optimize the way in which knowledge should be represented, factorized and structured. This is the core idea presented in this paper.
Returning to the example of temperature and altitude: when presented with out-of-distribution data from the Netherlands, we expect the correct model to adapt faster given a few transfer samples of actual weather data collected in the Netherlands. Analogous to the case of robustness, the adaptation speed can then be used to guide the inference of the true causal structure of the problem at hand, possibly along with other sources of signal about causal structure.
Contributions. We first verify on synthetic data that the model that correctly captures the underlying causal structure adapts faster when presented with data sampled after a performing certain interventions on the true two-variable causal graph (which is unknown to the learner). This suggests that the adaptation speed can indeed function as a score to assess how well the learner fits the underlying causal graph. We then use a smooth parameterization of the considered causal graph to directly optimize this score in an end-to-end gradient-based manner. Finally, we show in a simple setting that the score can be exploited to disentangle the correct causal variables given an unknown mixture of the said variables.

heading: 2 WHICH IS CAUSE AND WHICH IS EFFECT?
text: As an illustrative example of the proposed ideas, let us consider two discrete random variables A and B, each taking N possible values. We assume that A and B are correlated, without any hidden confounder. Our goal is to determine whether the underlying causal graph is A→ B (A causes B), or B → A. Note that this underlying causal graph cannot be identified from observational data from a single (training) distribution p only, since both graphs are Markov equivalent for p (Verma & Pearl, 1991); see Appendix A. In order to disambiguate between these two hypotheses, we will use samples from some transfer distribution p̃ in addition to our original samples from the training distribution p.

heading: 2.1 THE ADVANTAGE OF THE CORRECT CAUSAL MODEL
text: Without loss of generality, we can fix the true causal graph to be A → B, which is unknown to the learner. Moreover, to make the case stronger, we will consider a setting called covariate shift (Rojas-Carulla et al., 2018; Quionero-Candela et al., 2009), where we assume that the change (again,
whose nature is unknown to the learner) between the training and transfer distributions occurs after an intervention on the cause A. In other words, the marginal of A changes, while the conditional p(B | A) does not, i.e. p(B | A) = p̃(B | A). Changes on the cause will be most informative, since they will have direct effects on B. This is sufficient to fully identify the causal graph (Hauser & Bühlmann, 2012).
In order to demonstrate the advantage of choosing the causal model A → B over the anti-causal B → A, we can compare how fast the two models can adapt to samples from the transfer distribution p̃. We quantify the speed of adaptation as the log-likelihood after multiple steps of fine-tuning via (stochastic) gradient ascent, starting with both models trained on a large amount of data from the training distribution. In Figure 1 (see Section 3.3 for the experimental setup), we can see that the model corresponding to the underlying causal model adapts faster. Moreover, the difference is more significant when adapting on a small amount of data, of the order of 10 to 30 samples from the transfer distribution. We will make use of this property as a noisy signal to infer the direction of causality, which here is equivalent to choosing how to modularize the joint distribution.

heading: 2.2 PARAMETER COUNTING ARGUMENT
text: A simple parameter counting argument can help us understand what we are observing in Figure 1. Since we are using gradient ascent for the adaptation, let’s first inspect how the gradients of the log-likelihood wrt. each module behave under the transfer distribution. Proposition 1. Let G be a causal graph, and p a (training) distribution that factorizes according to G, with parameters θ. Let p̃ be a second (transfer) distribution that also factorizes according to G. If the training and transfer distributions have the same conditional probability distributions for all Vi but a subset C (e.g. the transfer distribution is the result of an intervention on the nodes in C):
p(Vi | PaG(Vi)) d= p̃(Vi | PaG(Vi)) ∀Vi /∈ C (1) then the expected gradient w.r.t. the parameters θi such that Vi /∈ C of the log-likelihood under the transfer distribution will be zero
∀Vi /∈ C, EV∼p̃ [ ∂ log p(V )
∂θi
] = 0. (2)
Proposition 1 (see proof in Appendix B.1) suggests that if both distributions factorize according to the correct causal graph, then only the parameters of the mechanisms that changed between the training and transfer distributions need to be updated. This effectively reduces the number of parameters that need to be adapted compared to any other factorization over a different graph. It also affects the number of examples necessary for the adaptation, since the sample complexity of a model grows approximately linearly with the VC-dimension (Ehrenfeucht et al., 1989; Vapnik & Chervonenkis, 1971), which itself also grows approximately linearly with the number of parameters (for linear
models and neural networks; Shalev-Shwartz & Ben-David, 2014). Therefore we argue that the performance on the transfer distribution (in terms of log-likelihood) will tend to improve faster if it factorizes according to the correct causal graph, an assertion which may not be true for every graph but that we can test by simulations.
Recall that in our example on two discrete random variables (each taking say N values), we assumed that the underlying causal model isA→ B, and the transfer distribution is the result of an intervention on the cause A. If the model we learn on the training distribution factorizes according to the correct graph, then only N − 1 free parameters should be updated to adapt to the shifted distribution, accounting for the change in the marginal distribution p̃(A), since the conditional p̃(B | A) = p(B | A) stays invariant. On the other hand, if the model factorizes according to the anti-causal graph B → A, then the parameters for both the marginal p̃(B) and the conditional p̃(A | B) must be adapted. Assuming there is a linear relationship between sample complexity and the number of free parameters, the sample complexity would be O(N2) for the anti-causal graph, compared to only O(N) for the true underlying causal graph A→ B.

heading: 3 THE META-TRANSFER OBJECTIVE
text: Since the speed of adaptation to some transfer distribution is closely related to the right modularization of knowledge, we propose to use it as a noisy signal to iteratively improve inference of the causal structure from data. Moreover, we saw in Figure 1 that the gap between correct and incorrect models is largest with a small amount of transfer data. In order to compare how fast some models adapt to a change in distribution, we can quantify the speed of adaptation based on their accumulated online performance after fine-tuning with gradient ascent on few examples from the transfer distribution. More precisely, given a small “intervention” datasetDint = {xt}Tt=1 from p̃, we can define the online likelihood as
LG(Dint) = T∏
t=1
p(xt ; θ (t) G , G)
θ (1) G = θ̂ ML G (Dobs)
θ (t+1) G = θ (t) G + α∇θ log p(xt ; θ (t) G , G),
(3)
where θ(t)G aggregates all the modules’ parameters in G after t steps of fine-tuning with gradient ascent, with learning rate α, starting from the maximum-likelihood estimate θ̂MLG (Dobs) on a large amount of data Dobs from the training distribution p. Note that, in addition to its contribution to the update of the parameters, each data point xt is also used to evaluate the performance of our model so far; this is called a prequential analysis (Dawid, 1984), also corresponding to sequential cross-validation (Gingras et al., 1999). From a structure learning perspective, the online likelihood (or, equivalently, its logarithm) can be interpreted as a score we would like to maximize, in order to recover the correct causal graph.

heading: 3.1 CONNECTION TO THE BAYESIAN SCORE
text: We can draw an interesting connection between the online log-likelihood, and a widely used score in structure learning called the Bayesian score (Heckerman et al., 1995; Geiger & Heckerman, 1994). The idea behind this score is to treat the problem of learning the structure from a fully Bayesian perspective. If we define a prior over graphs p(G) and a prior p(θG | G) over the parameters of each graph G, the Bayesian score is defined as scoreB(G ; Dint) = log p(Dint | G) + log p(G), where p(Dint | G) is the marginal likelihood
p(Dint | G) = T∏
t=1
p(xt | x1, . . . ,xt−1, G) = T∏
t=1
[ ∫
ΘG
p(xt | θG, G)p(θG | x1:t−1, G) dθG ] .
(4) In the online likelihood, the adapted parameters θ(t)G act as a summary of past data x1:t−1. Eq. (3) can be seen as an approximation of the marginal likelihood in Eq. (4), where the posteriors over the parameters p(θG | x1:t−1, G) is approximated by the point estimate θ(t)G . Therefore, the online log-likelihood provides a simple way to approximate the Bayesian score, which is often intractable.

heading: 3.2 A SMOOTH PARAMETRIZATION OF THE CAUSAL STRUCTURE
text: Due to the super-exponential number of possible Directed Acyclic Graphs (DAGs) over n nodes, the problem of searching for a causal structure that maximizes some score is, in general, NP-hard
(Chickering, 2002a). However, we can parametrize our belief about causal graphs by keeping track of the probability for each directed edge to be present. This provides a smooth parametrization of graphs, which hinges on gradually changing our belief in individual binary decisions associated with each edge of the causal graph. This allows us to define a fully differentiable meta-learning objective, with all the beliefs being updated at the same time by gradient descent.
In this section, we study the simplest version of this idea, applied to our example on two random variables from Section 2. Recall that here, we only have two hypotheses to choose from: either A→ B or B → A. We represent our belief of having an edge connecting A to B with a structural parameter γ such that p(A→ B) = σ(γ), where σ(γ) = 1/(1 + exp(−γ)) is the sigmoid function. We propose, as a meta-transfer objective, the negative log-likelihoodR (a form of regret) over the mixture of these two models, where the mixture parameter is given by σ(γ):
R(Dint) = − log [σ(γ)LA→B(Dint) + (1− σ(γ))LB→A(Dint)] (5) This meta-learning mixture combines the online adaptation likelihoods of each model over one meta-example or episode (specified by a Dint ∼ p̃), rather than considering and linearly mixing the per-example likelihoods as in ordinary mixtures.
In the experiments below, after each episode involving T examplesDint from the transfer distribution p̃, we update γ by doing one step of gradient descent, to reduce the regretR. Therefore, in order to update our belief about the edge A→ B, the quantity of interest is the gradient of the objectiveR with respect to the structural parameter, ∂R/∂γ. This gradient is pushing σ(γ) towards the posterior probability that the correct model is A→ B, given the evidence from the transfer data: Proposition 2. The gradient of the negative log-likelihood of the transfer data Dint in Equation (5) wrt. the structural parameter γ is given by
∂R ∂γ = p(A→ B)− p(A→ B | Dint), (6)
where p(A→ B | Dint) is the posterior probability of the hypothesis A→ B (when the alternative is B → A). Furthermore, this can be equivalently written as
∂R ∂γ = σ(γ)− σ(γ + ∆), (7)
where ∆ = logLA→B(Dint)− logLB→A(Dint) is the difference between the online log-likelihoods of the two hypotheses on the transfer data Dint. The proof is given in Appendix B.2. Note how the posterior probability is basically measuring which hypothesis is better explaining the transfer data Dint overall, along the adaptation trajectory. This posterior depends on the difference in online log-likelihoods ∆, showing the close relation between minimizing the regretR and maximizing the online log-likelihood score. The sign and magnitude of ∆ have a direct effect on the convergence of the meta-transfer objective. We can show that the meta-transfer objective is guaranteed to converge to one of the two hypotheses. Proposition 3. With stochastic gradient descent (and an appropriately decreasing learning rate) on EDint [R(Dint)], where the gradient steps are given by Proposition 2, the structural parameter converges towards
σ(γ)→ 1 if EDint [LA→B(Dint)] > EDint [LB→A(Dint)] or σ(γ)→ 0 otherwise (8)
This proposition (proved in Appendix B.3) shows that optimizing γ is equivalent to picking the hypothesis that has the smallest regret (or fastest convergence), measured as the accumulated loglikelihood of the transfer dataset Dint during adaptation. The distribution over datasets Dint is similar to a distribution over tasks in meta-learning. This analogy with meta-learning also appears in our gradient-based adaptation procedure, which is linked to existing methods like the first-order approximation of MAML (Finn et al., 2017), and its related algorithms (Grant et al., 2018; Kim et al., 2018; Finn et al., 2018). The pseudo-code for the proposed algorithm is given in Algorithm 1.
This smooth parametrization of the causal graph, along with the definition of the meta-transfer objective in Equation (5), can be extended to graphs with more than 2 variables. This general formulation builds on the bivariate case, where decisions are binary for each individual edge of the graph. See Appendix E for details and a generalization of Proposition 2; the structure of Algorithm 1 remains unchanged. Experimentally, this generalization of the meta-transfer objective proved to be effective on larger graphs (Ke et al., 2019), in work following the initial release of this paper.
Algorithm 1 Meta-learning algorithm for learning the structural parameter Require: Two graph candidates G = A→ B and G = B → A Require: A training distribution p that factorizes over the correct causal graph
1: Set the initial structural parameter γ = 0 . equal belief for both hypotheses 2: Sample a large dataset Dobs from the training distribution p 3: Pretrain the parameters of both models with maximum likelihood on Dobs 4: for each episode do 5: Draw a transfer distribution p̃ (via an intervention) 6: Sample a (small) transfer dataset Dint = {xt}Tt=1 from p̃ 7: for t = 1, . . . , T do 8: Accumulate the online log-likelihood for both models LA→B and LB→A as they adapt 9: Do one step of gradient ascent for both models: θ(t+1)G = θ (t) G + α∇θ log p(xt ; θ (t) G , G)
10: Compute the regretR(Dint) 11: Compute the gradient of the regret wrt. γ (see Proposition 2) 12: Do one step of gradient descent on the regret w.r.t. γ 13: Reset the models’ parameters to the maximum likelihood estimate on Dobs

heading: 3.3 EXPERIMENTAL RESULTS
text: To illustrate the convergence result from Proposition 3, we experiment with learning the structural parameter γ in a bivariate model. Following the setting presented in Section 2.1, we assume in all our experiments that A and B are two correlated random variables, and the underlying causal model (unknown to the algorithm) is fixed to A→ B. Recall that both variables are observed, and there is no hidden confounding factor. Since the correct causal model is A → B, the structural parameter should converge correctly, with σ(γ)→ 1. The details of the experimental setups, as well as details about the models, can be found in Appendix C.
We first experiment with the case where both A and B are discrete random variables, taking N possible values. In this setting, we explored how two different parametrizations of the conditional probability distributions (CPDs) might influence the convergence of the structural parameter. In the first experiment, we parametrized the CPDs as multinomial logistic CPDs (Koller & Friedman, 2009), maintaining a tabular representation of the conditional probabilities. For example, the conditional distribution p(B | A) is represented as
p(B = j | A = i ; θ) = exp(θij)∑ k exp(θik) , (9)
where the parameter θ is an N ×N matrix. We used a similar representation for the other marginal and conditional distributions p(A), p(B) and p(A | B). In a second experiment, we used structured CPDs, parametrized with multi-layer perceptrons (MLPs) with a softmax nonlinearity at the output layer. The advantage over a tabular representation is the ability to share parameters for similar contexts, and reduces the overall number of parameters required for each module. This would be crucial if either the number of categories N , or the number of variables, increased significantly.
In Figure 2, we show the evolution of σ(γ), which is the model’s belief of A→ B being the correct causal model, as the number of episodes increases, for different values of N . As expected, the structural parameter converges correctly to σ(γ)→ 1, within a few hundreds episodes. This observation is consistent in both experiments, regardless of the parametrization of the CPDs. Interestingly, the structural parameter tends to converge faster with a larger value of N and a tabular representation, illustrating the effect of the parameter counting argument described in Section 2.2, which is stronger as N increases. Precisely when generalization is more difficult (too many parameters and too few examples), we get a stronger signal about the better modularization.
We also experimented with A and B being continuous random variables, where they follow either multimodal distributions, or they are linear-Gaussian. Similar to Figure 2, we found that the structural parameter σ(γ) consistently converges to the correct causal model as well. See Appendix C.3 and Appendix C.4 for details about these experiments.

heading: 4 REPRESENTATION LEARNING
text: So far, we have assumed that all the variables in the causal graph are fully observed. However, in many realistic scenarios for learning agents, the learner might only have access to low-level observations (e.g. sensory-level data, like pixels or acoustic samples), which are very unlikely to be individually meaningful as causal variables. In that case, our assumption that the changes in distributions are localized might not hold at this level of observed data. To tackle this, we propose to follow the deep learning objective of disentangling the underlying causal variables (Bengio et al., 2013), and learn a representation in which the variables can be meaningfully cause or effect of each other. Our approach is to jointly learn this representation, as well as the causal graph over the latent variables.
We consider the simplest setting where the learner maps raw observations to a hidden representation space with two causal variables, via an encoder E . The encoder is trained such that this latent space helps to optimize the meta-transfer objective described in Section 3. We consider the parameters of the encoder, as well as γ (see Section 3.2), as part of the set of structural meta-parameters to be optimized. We assume that we have two raw observed variables (X,Y ), generated from the true causal variables (A,B) via the action of a ground truth decoder D (or generator network), that the learner is not aware of. This allows us to still have the ability to intervene on the underlying causal variables (e.g. to shift from training to transfer distributions) for the purpose of conducting experiments, while the learner only sees data from (X,Y ).
In this experiment, we only want to validate the proposed meta-objective as a way to recover a good encoder, and we assume that both the decoder D and the encoder E are rotations, whose angles are θD and θE respectively. The encoder maps the raw observed variables (X,Y ) to the latent variables (U, V ), over which we want to infer the causal graph. Similar to our experiments in Section 3.3, we assume that the underlying causal graph is A→ B, and the transfer distribution p̃ (now over (X,Y )) is the result of an intervention over A. Therefore, the encoder should ideally recover the structure U → V in the learned latent space, along with the angle of the encoder θE = −θD. However, since the encoder is not uniquely defined, V → U might also be a valid solution, if the encoder is θE = −π/2 − θD. Details about the experimental setup are provided in Appendix D. In Figure 4,
we consider that the learner succeeds, since both structural parameters converge to one of the two options. This shows how minimizing the meta-transfer objective can disentangle (here in a very simple setting) the ground-truth variables.

heading: 5 RELATED WORK
text: As stated already by Bengio et al. (2013), and clearly demonstrated by Locatello et al. (2019), assumptions, priors, or inductive biases are necessary to identify the underlying explanatory variables. The latter paper (Locatello et al., 2019) also reviews and evaluates recent work on disentangling, and discusses different metrics that have been proposed. Chalupka et al. (2015; 2017) recognize the potential and the challenges underlying causal representation learning. Closely related to our efforts is (Chalupka et al., 2017), which places a strong focus on the coalescence of low (e.g. sensory) level observations (microvariables) to higher level causal variables (macrovariables), albeit in a more observational setting.
There also exists an extensive literature on learning the structure of Bayesian networks from (observational) data, via score-based methods (Koller & Friedman, 2009). Heckerman et al. (1995); Daly et al. (2011) provide a comprehensive review of these methods. Many of these algorithms are based on greedy-search with local changes to the graphs (Chickering, 2002b), whereas we propose a continuous and fully-differentiable alternative. While most of these approaches only rely on observational data, it is sometimes possible to extend the definition of these scores to interventional data (Hauser & Bühlmann, 2012). The online-likelihood score presented here supports interventional data as its main feature.
Some identifiability results exist for causal models with purely observational data though (Peters et al., 2017), based on specific assumptions on the underlying causal graph. However, causal discovery is more natural under local changes in distributions (Tian & Pearl, 2001), similar to the setting used in this paper. Pearl’s seminal work on do-calculus (Pearl, 1995; 2009; Bareinboim & Pearl, 2016) lays the foundation for expressing the impact of interventions on causal graphical models. Here we are proposing a meta-learning objective function for learning the causal structure (without hidden variables), requiring mild assumptions such as localized changes in distributions and faithfulness of the causal graph, in contrast to the stronger assumptions necessary for these identifiability results.
Our work is also related to other recent advances in causation, domain adaptation, and transfer learning. Magliacane et al. (2018) have sought to identify a subset of features that leads to the best predictions for a variable of interest in a source domain, such that the conditional distribution of that variable given these features is the same in the target domain. Zhang et al. (2017) also examine non-stationarity and find that it makes causal discovery easier. Our adaptation procedure, using gradient ascent, is also closely related to gradient-based methods in meta-learning (Finn et al., 2017; Finn, 2018). Alet et al. (2018) proposed a meta-learning algorithm to recover a set of specialized modules, but did not establish any connections to causal mechanisms. More recently, Dasgupta et al. (2019) adopted a meta-learning approach to perform causal inference on purely observational data.

heading: 6 DISCUSSION & FUTURE WORK
text: We have established, in very simple bivariate settings, that the rate at which a learner adapts to sparse changes in the distribution of observed data can be exploited to infer the causal structure, and disentangle the causal variables. This relies on the assumption that with the correct causal structure, those distributional changes are localized. We have demonstrated these ideas through some theoretical results, as well as experimental validation. The source code for the experiments is available here: https://bit.ly/2M6X1al.
This work is only a first step in the direction of causal structure learning based on the speed of adaptation to modified distributions. On the experimental side, many settings other than those studied here should be considered, with different kinds of parametrizations, richer and larger causal graphs (see already Ke et al. (2019), based on a first version of this paper), or different kinds of optimization procedures. On the theoretical side, much more needs to be done to formally link the locality of interventions to faster adaptation, to clarify the conditions for this to work. Also, more work needs to be done in exploring how the proposed ideas can be used to learn good representations in which the causal variables are disentangled. Scaling up these ideas would permit their application towards improving the way learning agents deal with non-stationarities, and thus improving sample complexity and robustness of these agents.
An extreme view of disentangling is that the explanatory variables should be marginally independent, and many deep generative models (Goodfellow et al., 2016), and Independent Component Analysis models (Hyvärinen et al., 2001; Hyvärinen et al., 2018), are built on this assumption. However, the kinds of high-level variables that we manipulate with natural language are not marginally independent: they are related to each other through statements that are usually expressed in sentences (e.g. a sentence in natural language, or a classical symbolic AI fact or rule), involving only a few concepts at a time. This kind of assumption has been proposed to help discover relevant high-level representations from raw observations, such as the consciousness prior (Bengio, 2017), with the idea that humans focus at any particular time on just a few concepts that are present to our consciousness. The work presented here could provide an interesting meta-learning approach to help learn such encoders outputting causal variables, as well as figure out how the resulting variables are related to each other. In that case, one should distinguish two important assumptions: the first one is that the causal graph is sparse, which a common assumption in structure learning (Schmidt et al., 2007); the second is that the changes in distributions are sparse, which is the focus of this work.

heading: A RESULTS ON NON-IDENTIFIABILITY OF THE CAUSAL STRUCTURE
text: Suppose that A and B are two discrete random variables, each taking N possible values. We show here that the maximum likelihood estimation of both models A→ B and B → A yields the same estimated distribution over A and B. The joint likelihood on the training distribution is not sufficient to distinguish the causal model between the two hypotheses. If p is the training distribution, let
θi = p(A = i) θj|i = p(B = j | A = i) (10) ηj = p(B = j) ηi|j = p(A = i | B = j) (11)
Let Dobs be a training dataset. If N (A)i is the number of samples in Dobs where A = i, N (B) j the number of samples where B = j, and Nij the number of samples where A = i and B = j, then the maximum likelihood estimator for each parameter is
θ̂i = N (A) i /N θ̂j|i = Nij/N (A) i (12)
η̂j = N (B) j /N η̂i|j = Nij/N (B) j . (13)
The estimated distributions for each model A → B and B → A, under the maximum likelihood estimator, will be equal:
p̂(A = i, B = j ; A→ B) = θ̂iθ̂j|i = Nij/N (14) p̂(A = i, B = j ; B → A) = η̂j η̂i|j = Nij/N (15)
To illustrate this result, we also experiment with maximizing the likelihood for each modules for both models A → B and B → A with SGD. In Figure A.1, we show the difference in log-likelihoods between these two models, evaluated on training and test data sampled from the same distribution, during training. We can see that while the model A → B fits the data faster than the other model (corresponding to a positive difference in the figure), both models achieve the same log-likelihoods at convergence. This shows that the two models are indistinguishable, in the limit, based on data sampled from the same distribution, even on test data.

heading: B PROOFS

heading: B.1 ZERO-GRADIENT UNDER MECHANISM CHANGE
text: Let us restate Proposition 1 here for convenience: Proposition 1. Let G be a causal graph, and p a (training) distribution that factorizes according to G, with parameters θ. Let p̃ be a second (transfer) distribution that also factorizes according to G. If the training and transfer distributions have the same conditional probability distributions for all Vi but a subset C (e.g. the transfer distribution is the result of an intervention on the nodes in C):
p(Vi | PaG(Vi)) d= p̃(Vi | PaG(Vi)) ∀Vi /∈ C (16)
then the expected gradient w.r.t. the parameters θi such that Vi /∈ C of the log-likelihood under the transfer distribution will be zero
∀Vi /∈ C, EV∼p̃ [ ∂ log p(V )
∂θi
] = 0. (17)
Proof. For Vi /∈ C, we can simplify the expected gradient as follows:
EV∼p̃ [ ∂ log p(V )
∂θi
] = EV∼p̃ [ n∑
j=1
∂
∂θi log p(Vj | PaG(Vj) ; θj)
] (18)
= EV∼p̃ [ ∂
∂θi log p(Vi | PaG(Vi) ; θi)
] (19)
= EV∼p̃ [ ∂
∂θi log p̃(Vi | PaG(Vi) ; θi)
] (20)
= EV∼p̃ [ n∑
j=1
∂
∂θi log p̃(Vj | PaG(Vj) ; θj)
] (21)
= EV∼p̃ [ ∂ log p̃(V )
∂θi
] = 0 (22)
where Equation (20) arises from our assumption that the conditional distribution of Vi given its parents in G does not change between the training distribution p and the transfer distribution p̃. Moreover, the last equality arises from the marginalization
∑
v
p̃(v) = 1 (23)

heading: B.2 GRADIENT OF THE STRUCTURAL PARAMETER
text: Let us restate Proposition 2 here for convenience:
Proposition 2. The gradient of the negative log-likelihood of the transfer data Dint in Equation (5) wrt. the structural parameter γ is given by
∂R ∂γ = p(A→ B)− p(A→ B | Dint), (24)
where p(A→ B | Dint) is the posterior probability of the hypothesis A→ B (when the alternative is B → A). Furthermore, this can be equivalently written as
∂R ∂γ = σ(γ)− σ(γ + ∆), (25)
where ∆ = logLA→B(Dint)− logLB→A(Dint) is the difference between the online log-likelihoods of the two hypotheses on the transfer data Dint.
Proof. First note that, using Bayes rule,
p(A→ B | Dint) = p(Dint | A→ B)p(A→ B)
p(Dint | A→ B)p(A→ B) + p(Dint | B → A)p(B → A) (26)
= LA→B(Dint)σ(γ)
LA→B(Dint)σ(γ) + LB→A(Dint)(1− σ(γ)) (27)
= LA→B(Dint)σ(γ)
M (28)
where M = LA→B(Dint)σ(γ) + LB→A(Dint)(1 − σ(γ)) is the online likelihood of the transfer data under the mixture, so that the regret is R(Dint) = − logM . For Equation (27), note that if Dint = {at, bt}Tt=1,
p(Dint | A→ B) = T∏
t=1
p(at, bt | A→ B, {as, bs}t−1s=1) (29)
=
T∏
t=1
p(at, bt | A→ B ; θ(t)A→B) = LA→B(Dint) (30)
where θ(t)A→B encapsulates the information about the previous datapoints {as, bs}t−1s=1 in the graph A → B, through some adaptation procedure. Since we only consider the two hypotheses A → B and B → A, we also have
p(B → A | Dint) = 1− p(A→ B | Dint) = LB→A(Dint)(1− σ(γ))
M (31)
Therefore, the gradient of the regret wrt. the structural parameter γ is ∂R ∂γ = − 1 M [σ(γ)(1− σ(γ))LA→B(Dint)− σ(γ)(1− σ(γ))LB→A(Dint)] (32)
= σ(γ)p(B → A | Dint)− (1− σ(γ))p(A→ B | Dint) (33) = σ(γ)− σ(γ)p(B → A | Dint)− p(A→ B | Dint) + σ(γ)p(A→ B | Dint) (34) = σ(γ)− p(A→ B | Dint) (35) = p(A→ B)− p(A→ B | Dint) (36)
which concludes the first part of the proof. Moreover, given Equation (35), it is sufficient to show that p(A→ B | Dint) = σ(γ + ∆) to prove the equivalent formulation in Equation (25). Using the logit function σ−1(z) = log z1−z , and the expression in Equation (28), we have
σ−1(p(A→ B | Dint)) = log σ(γ)LA→B(Dint)
M − σ(γ)LA→B(Dint) (37)
= log σ(γ)LA→B(Dint)
(1− σ(γ))LB→A(Dint) (38)
= log σ(γ)
1− σ(γ)︸ ︷︷ ︸ = γ
+ logLA→B(Dint)− logLB→A(Dint)︸ ︷︷ ︸ = ∆
(39)
= γ + ∆. (40)

heading: B.3 CONVERGENCE POINT OF GRADIENT DESCENT ON THE STRUCTURAL PARAMETER
text: Let us restate Proposition 3 here for convenience: Proposition 3. With stochastic gradient descent (and an appropriately decreasing learning rate) on EDint [R(Dint)], where the gradient steps are given by Proposition 2, the structural parameter converges towards
σ(γ)→ 1 if EDint [LA→B(Dint)] > EDint [LB→A(Dint)] or σ(γ)→ 0 otherwise (41)
Proof. We are going to consider the fixed point of gradient descent (a point where the gradient is zero), since we already know that SGD converges with an appropriately decreasing learning rate. Let us introduce some notations to simplify the algebra: let p = σ(γ), M = pLA→B(Dint) + (1− p)LB→A(Dint), so that the regret is R(Dint) = − logM . We define P1 and P2 as (see also the proof in Appendix B.2)
P1 = pLA→B(Dint)
M = p(A→ B | Dint) P2 = (1− p)LB→A(Dint) M = 1− P1 (42)
Framing the stationary point in terms of p rather than γ gives us a constrained optimization problem, with inequality constraints −p ≤ 0 and p− 1 ≤ 0, and no equality constraint.
min p
EDint [R(Dint)] (43)
s.t. −p ≤ 0 (44) p− 1 ≤ 0 (45)
Applying the KKT conditions to this problem, with constraint functions −p and p− 1, gives us
EDint [ ∂R ∂p ] = −µ1 + µ2 (46)
µi ≥ 0 for i = 1, 2 (47) µ1p = 0 (48)
µ2(p− 1) = 0 (49) We already see from equations (48) & (49) that if p ∈ (0, 1) (i.e. excluding 0 and 1), we must have µ1 = µ2 = 0, that is
EDint [ ∂R ∂p ] = 0. (50)
Let us study that case first, and show that it leads to an inconsistent set of equations (thus, forcing the solution to be either p = 0 or p = 1). Let us rewrite the gradient to highlight p in it (using Proposition 2):
∂R ∂p = 1 p(1− p) (p− p(A→ B | Dint)) (51)
= 1
p(1− p)
[ p− pLA→B(Dint)
M
] (52)
= 1 p(1− p) p(pLA→B(Dint) + (1− p)LB→A(Dint))− pLA→B(Dint) M (53)
= LB→A(Dint)− LA→B(Dint)
M (54)
This derivation is valid since we assume that p ∈ (0, 1). Suppose that p 6= 0; multiplying both sides of Equation (50) by p gives
0 = EDint [ p(LB→A(Dint)− LA→B(Dint))
M
] (55)
= EDint [ pLB→A(Dint)
M − P1
] (56)
= EDint [LB→A(Dint)
M − P2 − P1
] (57)
= EDint [LB→A(Dint) M − 1 ]
(58)
For this equation to be satisfied, we need LB→A = M almost surely, since LB→A(Dint) ≤M by construction. This would, however, correspond to p = 0, which contradicts our assumption. Similarly, assuming that p 6= 1, we can also multiply both sides of Equation (50) by 1− p and get
0 = EDint [
(1− p)(LB→A(Dint)− LA→B(Dint) M
] (59)
= EDint [ P2 −
(1− p)LA→B(Dint) M
] (60)
= EDint [ P2 + P1 −
LA→B(Dint) M
] (61)
= EDint [ 1− LA→B(Dint)
M
] (62)
Again, this can only be true if LA→B = M almost surely, meaning that p = 1, contradicting our assumption. We conclude that the solutions p ∈ (0, 1) are not possible because they would lead to inconsistent conclusions, which leaves only p = 0 or p = 1.

heading: C RESULTS ON LEARNING WHICH IS CAUSE AND WHICH IS EFFECT
text: In order to assess the performance of our meta-learning algorithm, we applied it on generated data from three different domains: discrete random variables, multimodal continuous random variables and multivariate Gaussian-distributed variables. In this section, we describe the setups for all three experiments, along with additional results to complement the results descrbed in Section 3.3. Note that in all these experiments, we fix the ground-truth structure as A→ B, and only perform interventions on the cause A.

heading: C.1 DISCRETE VARIABLES WITH TABULAR REPRESENTATION
text: We consider a bivariate model, where both random variables are sampled from a categorical distribution. The underlying ground-truth model can be described as
A ∼ Categorical(πA) (63) B | A = a ∼ Categorical(πB|a), (64)
with πA a probability vector of size N , and πB|a a probability vector of size N , which depends on the value of the variable A. In our experiment, each random variable can take one of N = 10 or N = 100 values. Since we are working with only two variables, the only two possible models are:
• Model A→ B: p(A,B) = p(A)p(B | A) • Model B → A: p(A,B) = p(B)p(A | B)
We build 4 different modules, corresponding to every possible marginal and conditional distributions. Here, we use multinomial logistic Conditional Probability Distributions (Koller & Friedman, 2009). The modules’ definition, and their corresponding parameters, are shown in Table C.1.
In order to get a set of initial parameters, we first train all 4 modules on a training distribution (p in the main text). This distribution corresponds to a fixed choice of π(1)A and πB|a (for all N possible values of a). The superscript in π(1)A emphasizes the fact that this defines the distribution prior to an intervention, with the mechanism p(B | A) being unchanged by the intervention. These probability vectors are sampled randomly from a uniform Dirichlet distribution:
π (1) A ∼ Dirichlet(1N ) (65)
πB|a ∼ Dirichlet(1N ) ∀a ∈ [1, N ]. (66) Given this training distribution, we can sample a large dataset of samples Dobs = {ai, bi}mi=1 for the ground truth model, using ancestral sampling. Using Dobs, we can train all 4 modules using gradient ascent on the log-likelihood (or any other advanced first-order optimizer, like RMSprop). The parameters θA, θB|A, θB & θA|B of the maximum likelihood estimate will be used as the initial parameters for the adaptation on the new transfer distribution.
Similar to the way we defined the training distribution, we can define a transfer distribution (p̃ in the main text) as an intervention on the random variable A. In this experiment, this accounts for changing the distribution of A, that is with a new probability vector π(2)A , also sampled from a uniform Dirichlet distribution
π (2) A ∼ Dirichlet(1N ). (67)
To perform adaptation on the transfer distribution, we also sample a smaller transfer dataset Dint = {at, bt}Tt=1, with T m. In our experiment, we used T = 20 datapoints, following the observation from Section 2.1.

heading: C.2 DISCRETE VARIABLES WITH MLP PARAMETRIZATION
text: We consider a bivariate model, similar to the one defined in Appendix C.1, where each random variable is sampled from a categorical distribution. Instead of expressing the CPDs in tabular form, we use structured CPDs, parametrized with multi-layer perceptrons (MLPs). In our experiment, all the MLPs have only one hidden layer with H = 8 hidden units, with a ReLU non-linearity, and the output layer has a softmax non-linearity. To avoid any modeling bias, we assume that the ground-truth model is also parametrized by MLPs, such that
A ∼ Categorical(MLP(0 ; WA)) (68) B | A = a ∼ Categorical(MLP(1[a] ; WB)) (69)
where 0 is a vector of size N will all zeros, and 1[a] is a one-hot vector of size N . WA and WB summarize the parameters of the ground truth model, with the weights and biases for the 2 layers. Similar to the tabular representation, we define 4 different modules, this time using MLPs. Their definition, as well as their corresponding parameters, are shown in Table C.2.
Again, to define the training distribution, we first fix the parameters W (1)A and WB . We use randomly initialized networks for the training distribution, with the parameters sampled using the He initialization. We train all the modules using maximum likelihood on a large dataset of training samples Dobs, to get the initial set of parameters for the adaptation on the transfer distribution.
We also define a transfer distribution as the result of an intervention on A. In this experiment, this means sampling a new set of parameters W (2)A , still as a randomly initialized network. We sample a transfer dataset Dint = {at, bt}Tt=1, with T = 20 datapoints.

heading: C.3 CONTINUOUS MULTIMODAL VARIABLES
text: Consider a family of joint distributions pµ(A,B) over the causal variables A and B, defined by the following structural causal model (SCM):
A ∼ pµ(A) = N (µ, σ2 = 4) (70) B := f(A) +NB NB ∼ N (0, 1), (71)
where f is a randomly generated spline, and the noise NB is sampled iid. from the unit Gaussian distribution. To obtain the spline, we sample K points {xk}Kk=1 uniformly spaced from the interval [−8, 8], and another K points {yk}Kk=1 uniformly randomly from the interval [−8, 8]. This yields K
pairs {xk, yk}Kk=1, which make the knots of a second-order spline. We choose K = 8 points in our experiments.
The conditional distributions p(B | A) and p(A | B) are parametrized as 2-layer Mixture Density Networks (MDNs; Bishop, 1994), with 32 hidden units and 10 components. The marginal distributions p(A) and p(B) are parametrized as Gaussian Mixture Models (GMMs), also with 10 components. The definition of the different modules, as well as their corresponding parameters, are shown in Table C.3.
We select p0(A,B) as the training distribution, from which we sample a large dataset Dobs using ancestral sampling. Similar to the earlier experiments, this dataset is used to get the initial set of parameters for the adaptation on the transfer distribution. The MDNs are fitted with gradient descent, while the GMMs are learned via Expectation Maximization. The transfer distribution is the result of an intervention on A, where we shift the distribution pµ(A) with µ sampled uniformly in [−1, 1]. In Figure C.1, we plot samples from the training distribution (µ = 0), as well as two transfer distributions (µ = ±4).
The structural regret R(γ) is now minimized with respect to γ for 500 iterations (updates of γ). In the notation of Algorithm 1, these are the iterations over the number of episodes. Figure C.2 shows the evolution of σ(γ) as training progresses. This is expected, given that we expect the causal model to perform better on the transfer distributions, i.e. we expect LA→B > LB→A in expectation. Consequently, assigning a larger weight to LA→B optimizes the objective (see Proposition 3). Finally as a sanity check, we test the experimental set-up described above on a linear SCM with additive Gaussian noise. In this setting, it is well known that the causal structure cannot be discovered from observations alone Peters et al. (2017) and one must rely on the transfer distribution tell cause from effect.
To that end, we repeat the experiment in Figure C.2 with the following amendments: (a) we replace the non-linear spline with a linear curve (Figure C.3), and (b) in addition to training the structural
parameter by adapting the A→ B and B → A models to multiple interventional distributions, we train it by “adapting" the said model to the train distribution, where the latter serves as a baseline.
Figure C.4 shows that using multiple transfer (i.e. interventional) distributions (“With Interventions") enables causal discovery, as opposed to the model trained with a single observational distribution. This confirms that our method indeed relies on the interventional distributions to discover the causal structure.

heading: C.4 LINEAR GAUSSIAN MODEL
text: In this experiment, the two variablesA andB are vector-valued, taking values in Rd. The ground-truth causal model is given by
A ∼ N (µ,Σ) (72) B := β1A+ β0 +NB NB ∼ N (0, Σ̃), (73)
where µ ∈ Rd, β0 ∈ Rd and β1 ∈ Rd×d. Σ and Σ̃ are two d × d covariance matrices. In our experiment, d = 100. Once again, we want to identify the correct causal direction between A and B.
To do so, we consider two models A → B and B → A parametrized with Gaussian distributions. The details of the modules’ definitions, as well as their parameters, is given in Table C.4. Note that each covariance matrix is parametrized using the Cholesky decomposition.
To build the training distribution, we draw µ(1), β0 and β1 from a Gaussian distribution, and Σ(1) and Σ̃ from an inverse Wishart distribution. The transfer distribution is the result of an intervention on A, meaning that the marginal p̃(A) changes. To do so, we sample new parameters µ(2) from a Gaussian distribution, and Σ(2) from an inverse Wishart distribution as well.
Unlike the previous experiments, we are not conduction any pre-training on actual data from the training distribution. Instead, we fix the parameters of both models to their exact values, according to the ground truth distribution. For Model A → B, this can be done easily. For the Model B → A, we compute the exact parameters analytically using Bayes rule. This can be seen as the maximum likelihood estimate in the limit of infinite data. In Figure C.5, we show that, after 200 episodes, σ(γ) converges to 1, indicating the success of the method on this particular task.

heading: C.5 EXPERIMENTS WITH SOFT INTERVENTION
text: In this section, we describe an experimental setting where the conditional p(B | A) is perturbed while the distribution of the cause, p(A), is left unchanged. To that end, consider a set-up similar to that in Section C.3:
A ∼ pµ(A) = U(−8, 8) (74) B := f0(A) +NB NB ∼ N (0, 1), (75)
where f0 is a randomly generated spline and NB is sampled iid. from the unit Gaussian distribution and the cause variable A is sampled from the uniform distribution supported on [−8, 8]. To induce soft-interventions, we modify the SCM as follows. Consider the knots {ai, bi}5i=1 of the order 3 spline f0; we obtain a new spline fint by randomly perturbing the b-coordinate of the knots, where the perturbations are sampled from another uniform distribution1. Using the perturbed spline fint instead of f0 in Equation (74) results in a new SCM, from which we generate a single transfer distribution (i.e. for a single episode). In Figure C.6 we plot samples from three such transfer distributions.
The models used are identical to those detailed in Appendix C.3 and are trained on the training SCM (corresponding base-spline f0) with a large amount of samples (≈ 3,000k). The meta-training procedure differs in that (a) in every transfer episode, we create a new spline fint and sample a transfer distribution Dint from the corresponding SCM, and (b) we use the following measure of adaptation:
LG(Dint) = exp [log p(Dint | θ(T )G )− log p(Dint | θ (0) G )] (76)
where G is one of A→ B or B → A. The meta-transfer objective in Equation (5) remains the same. Figure C.7 shows the evolution of the σ(γ) as the training progresses, and we find that the structural parameter correctly converges to 1, representing the correct causal graph A→ B.
1The scale of the perturbation is 0.5 times that of the original knots.
Failure case In addition to the result above, we also observed that using soft interventions on the effect B instead on changes on the marginal p(A) was sometimes failing to recover the correct causal graph. Instead, the anti-causal graph (here B → A) was found, with high confidence. We describe here one such experiment where using the meta-transfer objective failed at recovering the correct causal graph.
Our experimental setting is similar to the one described in Appendix C.1. However instead of changing the marginal p(A), the conditional distribution p(B | A) changes and p(A) remains unchanged. Following the notations in Appendix C.1, we have
πA ∼ Dirichlet(1N ) (77) π
(1) B|a ∼ Dirichlet(1N ) & π (2) B|a ∼ Dirichlet(1N ) ∀a ∈ [1, N ], (78)
where π(1)B|a are the parameters of the conditional distribution before intervention, and π (2) B|a its parameters after intervention. We again sample data from both the training and transfer distributions to get datasets Dobs and Dint. The different modules and their corresponding parameters are defined in Table C.1.
In Figure C.8, we show the evolution of the structural parameter σ(γ), the model’s belief that A→ B is the correct causal model, as the number of episodes increases. Unlike our previous experiments in Section 3.3, the structural parameter now converges to σ(γ)→ 0, corresponding to a strong belief that the model is B → A. We are therefore unable to recover the correct causal graph here under the
assumption that p(B | A) changes. Note that here the parameter counting argument from Section 2.2 clearly does not hold anymore, since the modules all use a tabular representation, and both models require the same order O(N2) of updates to adapt to a transfer distribution.

heading: D RESULTS ON REPRESENTATION LEARNING
text: The true latent causal variables (A,B) are sampled from the distribution described in Appendix C.3 (Equations (74) & (75)). These variables are then mapped to observations (X,Y ) ∼ pµ(X,Y ) via a hidden (and unknown to the learner) decoder D = RθD , where Rθ is a rotation of angle θ. The observations are then mapped to the hidden state (U, V ) ∼ pµ(U, V ) via the encoder E = RθE ; in this experiment, the angle θE is the only additional meta-parameter, besides the structural parameter γ. The computational graph is depicted in Figure 3. In our experiment, θD = −π/4 is fixed for all our observation and intervention datasets. Interventional data is acquired by intervening on the latent variables (A,B), following the process described in Appendix C.3, and then mapping the data through the decoder D. Since the underlying latent causal variables (A,B) are unobserved, we need to define the online likelihood over the recovered variables (U, V ) instead. Analogous to how we defined the online likelihood in the fully observable case in Section 3, this is defined as
LG(Dint ; θE) = T∏
t=1
p(RθE (xt) ; θ (t) G , G)
θ (1) G = θ̂ ML G (RθE (Dobs))
θ (t+1) G = θ (t) G + α∇θ log p(RθE (xt) ; θ (t) G , G),
(79)
where RθE (Dobs) = {RθE (x) | x ∈ Dobs}. Note that here the online likelihood depends on the parameters of the encoder E (here, θE ). Using this definition of the online likelihood that takes into account the encoder, the meta-transfer objective is also similar to the one defined in Equation (5):
R(Dint ; γ, θE) = − log [σ(γ)LU→V (Dint ; θE) + (1− σ(γ))LV→U (Dint ; θE)] . (80) On the one hand, the gradient of R(Dint ; γ, θE) with respect to the structural parameter γ can be computed using Proposition 2, similar to the fully observable case. On the other hand, the gradient of the meta-transfer objective with respect to the meta-parameter θE is computed using backpropagation through the T updates of the parameters θG of the modules in Equation (79); this process is similar to backpropagation through time. In our experiment, we did not observe any degenerate behaviour like vanishing gradients, due to the limited amount of interventional data (T = 5).

heading: E MORE THAN TWO CAUSAL HYPOTHESES
text: In Section 3.2, we defined the meta-transfer objective only in the context of bivariate models. The challenge with learning the structure of graphs on n variables is that there is a super-exponential number of DAGs on n variables, making the problem of structure learning NP-hard (Chickering, 2002a). If we were to naively extend the meta-transfer objective to graphs on n > 2 variables, this would require adaptation of 2O(n 2) different models (hypotheses), which is intractable.
Instead, we can decouple the optimization of the graph from the acyclicity constraint, since causal graphs can have cycles (Peters et al., 2017). This constraint can be enforced as an extra penalty to the meta-transfer objective (Zheng et al., 2018). We consider the problem of optimization on the graph as O(n2) independent binary decisions on whether Vj is a parent (or direct cause) of Vi. Motivated by the mechanism independence assumption (Parascandolo et al., 2017), we propose a heuristic to learn the causal graph, in which we independently parametrize the binary probability pij that Vj is a parent of Vi. We can then define a distribution over graphs (or more precisely, their adjacency matrix B) as:
Bij ∼ Bernoulli(pij) (81) p(B) = ∏
i,j
p(Bij), (82)
where pij = σ(γij). We denote PaB(Vi) as the parent set of Vi in the graph defined by the adjacency matrix B (that is the nodes Vj such that Bij = 1). We can slightly rewrite the definition of the
online-likelihood as in Section 3 to show the dependence on B:
LB(Dint) = T∏
t=1
p(xt ; θ (t) B , B) =
n∏
i=1
T∏
t=1
p(x (t) i | x (t) PaB(Vi) ; θ (t) B,i), (83)
where the second equality uses the factorization of p in the graph defined by B. Note that since the graph defined by B can contain cycles, the definition in Equation (83) involves the pseudolikelihood instead of the joint likelihood (which is defined as the product of individual conditional distributions only if the graph is a DAG). The pseudolikelihood was shown to be a reasonable approximation of the true joint likelihood when maximizing the joint likelihood (which is performed here for adaptation; Koller & Friedman (2009)). Similar to the bivariate case, we want to consider a mixture over all possible graph structures, but where each component must explain the whole adaptation sequence. We can generalize our definition of the regret as
R(Dint) = − logEB [LB(Dint)]. (84) Note, however, that this expectation is over the O(2n 2
) possible values of B, which is intractable. We can rewrite the regret in a more convenient form: Proposition 4. The regretR(Dint) defined in Equation (84) can be decomposed as
R(Dint) = − n∑
i=1
logEBi [LBi(Dint)], (85)
where Bi is a row of the matrix B, and LBi(Dint) appears in the factorization of LB(Dint) in Equation (83):
LBi = T∏
t=1
p(x (t) i | x (t) PaB(Vi) ; θ (t) B,i) (86)
Proof. Recall that LB(Dint) = ∏ i LBi(Dint), so that we can rewrite the regret as follows:
R(Dint) = − logEB [LB(Dint)] (87) = − log ∑
B
p(B)LB(Dint) (88)
= − log ∑
B1
∑
B2
. . . ∑
Bn
[ n∏
i=1
p(Bi)LBi(Dint) ]
(89)
= − log n∏
i=1
[∑
Bi
p(Bi)LBi(Dint) ]
(90)
= − n∑
i=1
log ∑
Bi
p(Bi)LBi(Dint) (91)
= − n∑
i=1
logEBi [LBi(Dint)] (92)
The structural parameters, here, are the O(n2) scalars γij . Regardless of the intractability of the regret, we can still derive its gradient wrt. each γij . The following proposition provides a direct extension of Proposition 2 to the case of multiple variables: Proposition 5. The gradient of the regretR(Dint) wrt. the structural parameter γij is given by
∂R ∂γij = σ(γij)− σ(γij + ∆ij), (93)
where ∆ij is the difference in log-likelihoods of two mixture candidates, conditioning on the variable Vj
∆ij = log(EBi [LBi(Dint) | Vj ∈ PaB(Vi)])− log(EBi [LBi(Dint) | Vj /∈ PaB(Vi)]) (94)
Proof. To simplify the notation, we remove the explicit dependence on the transfer distribution Dint in this proof. Recall from Proposition 4 that the regret can be written as
R = − n∑
i=1
logEBi [LBi ]. (95)
Using a conditional expectation, it follows that for any i, j
EBi [LBi ] = ∑
Bi
p(Bi)LBi (96)
= p(Bij = 1) · ∑
Bi|Vj∈PaB(Vi)
p(Bi | Bij = 1)LBi + p(Bij = 0) · ∑
Bi|Vj /∈PaB(Vi)
p(Bi | Bij = 0)LBi
(97)
= σ(γij) · ∑
Bi|Vj∈PaB(Vi)
p(Bi | Bij = 1)LBi + (1− σ(γij)) · ∑
Bi|Vj /∈PaB(Vi)
p(Bi | Bij = 0)LBi (98)
To simplify the notation, let us define E(1)ij and E (0) ij the two conditional expectations of LBi , conditioned on whether or not Vj is a parent of Vi in B
E (0) ij =
∑
Bi|Vj /∈PaB(Vi)
p(Bi | Bij = 0)LBi = EBi [LBi | Vj /∈ PaB(Vi)] (99)
E (1) ij =
∑
Bi|Vj∈PaB(Vi)
p(Bi | Bij = 1)LBi = EBi [LBi | Vj ∈ PaB(Vi)], (100)
so that Equation (98) can be written as
EBi [LBi ] = σ(γij)E(1)ij + (1− σ(γij))E (0) ij . (101)
Note that neither E(0)ij nor E (1) ij depend on the structural parameter γij . Therefore we can now easily compute the gradient ofR wrt. γij only ∂R ∂γij = − ∂ ∂γij log ( σ(γij)E (1) ij + (1− σ(γij))E (0) ij ) (102)
= − 1 EBi [LBi ]
( σ(γij)(1− σ(γij)) [ E (1) ij − E (0) ij ]) (103)
If we substract σ(γij) from this expression gives us
σ(γij)− ∂R ∂γij = 1 EBi [LBi ] ( σ(γij) 2E (1) ij + σ(γij)(1− σ(γij))E (0) ij
+ σ(γij)(1− σ(γij)) [ E (1) ij − E (0) ij ] ) (104)
= σ(γij)
EBi [LBi ] E
(1) ij = x (105)
Denoting the previous expression as x, we can also easily compute 1− x:
1− x = 1− σ(γij) EBi [LBi ] E (0) ij (106)
Using the logit function σ−1(x) = log x1−x , we can conclude that
σ−1 ( σ(γij)−
∂R ∂γij
) = log
σ(γij)E (1) ij
(1− σ(γij))E(0)ij (107)
= log σ(γij)
1− σ(γij) + logE
(1) ij − logE (0) ij (108)
= γij + ∆ij (109)
While Proposition 5 gives an analytic form for the gradient of the regret wrt. the structural parameters, computing it is still intractable, due to ∆ij . However, we can still get an effecient stochastic gradient estimator from Proposition 4, which can be computed separately for each node of the graph (with samples arising only out of Bi, the incoming edges of Vi): Proposition 6. If we consider multiple samples ofB in parallel, a biased but asymptotically unbiased (as the number K of these samples B(k) increases to infinity) estimator of the gradient of the overall regret with respect to the meta parameters can be defined as:
gij =
∑ k(σ(γij)−B (k) ij )L
(k) Bi∑
k L (k) Bi
, (110)
where the index (k) indicates the values obtained for the k-th draw of B.
Proof. The gradient of the regret with respect to the meta-parameters γi of node i is
∂R ∂γi = − ∑ Bi p(Bi)LBi ∂ log p(Bi)∂γi∑ Bi P (Bi)LBi
= − EBi [LBi ∂ log p(Bi)∂γi ]
EBi [LBi ] (111)
Note that with the sigmoidal parametrization of p(Bi), log p(Bi) = Bij log σ(γij) + (1−Bij) log(1− σ(γij)) (112)
as in the cross-entropy loss. Its gradient can similarly be simplified to ∂ log p(Bij)
∂γij = Bij σ(γij) σ(γij)(1− σ(γij))− (1−Bij) (1− σ(γij)) σ(γij)(1− σ(γij)))
= Bij − σ(γij). (113) A biased, but asymptotically unbiased, estimator of ∂R/∂γij is thus obtained by sampling K graphs (over which the means below are run):
gij = ∑
k (σ(γij)−B(k)ij ) L(k)Bi∑ k′ L (k′) Bi
(114)
where index (k) indicates the k-th draw ofB, and we obtain a weighted sum of the individual binomial gradients weighted by the relative regret of each draw B(k)i of Bi, leading to Equation (110).
We can therefore adapt Algorithm 1 using the gradient estimate in Proposition 6 to update the structural parameters γij , without having to explicitly compute the full regretR(Dint). In addition to the gradient estimate provided by Proposition 6, we can also derive a Rao-Blackwellized (Rao, 1992; Blackwell, 1947) estimate of the gradient of the regret, based on the formulation derived in Proposition 5. Proposition 7. Let {B(k)}Kk=1 be K binary matrices (corresponding to sample graphs), sampled from independent Bernoulli distributions depending on the structural parameters γij
B (k) ij iid∼ Bernoulli(σ(γij)), (115) and their corresponding likelihoods L(k)Bi . A Monte-Carlo estimate of the log-likelihood difference ∆ij in Equation (94) is given by
∆̃ (K) ij = log
( 1
|K(1)ij | ∑
k∈K(1)ij
L(k)Bi
) − log ( 1
|K(0)ij | ∑
k∈K(0)ij
L(k)Bi
) , (116)
where K(0)ij = {k ; B (k) ij = 0} and K (1) ij = {k ; B (k) ij = 1} are (disjoint) sets of indices k, depending on the value of B(k)ij .
Based on this Monte-Carlo estimate of ∆ij , we can define an estimate of the gradient of the regretR wrt. the structural parameter γij by
∂̃R ∂γij = σ(γij)− σ(γij + ∆̃(K)ij ). (117)

heading: F THE EFFECT OF ADAPTATION ON THE ONLINE LIKELIHOOD
text: Since we are using the online likelihood defined in Equation (3) as a measure of adaptation in our meta-transfer objective, it is reasonable to know if this measure is sound. To validate this assumption, we are running an experiment similar to the one described in Section 2.1 and Figure 1, using the same experimental setup on discrete variables described in Section 3.3. However, instead of measuring the raw log likelihood on a validation set, we report the online likelihood LG(Dint) for both models in Figure F.1. The online likelihoods are scaled by the number of transfer examples seen for visualization. Similar to Figure 1, we can see that the difference in online likelihoods for both models is most significant on a small amount of data.
100 101 102 103 104
Number of examples
−5.50
−5.25
−5.00
−4.75
−4.50
−4.25
−4.00
−3.75
O n
li n
e L
ik el
ih o o d L · → ·( D
)
A→ B B → A
Figure F.1: Adaptation to the transfer distribution (online likelihood on transfer examples, vertical axis), as more transfer examples are seen by the learner (horizontal axis). The curves are the median over 20,000 runs, with their 25-75th quantiles intervals. The dotted line is the asymptotic online likelihood

Review summaries:
The paper first shows that, in a very simple two-variable task, the model with the correct underlying structure will adapt faster to a causal intervention than the model with the incorrect structure. This idea is used to develop a “meta-transfer” objective function for which gradient ascent on a continuous representation of the model structure allows learning of that structure. The paper shows that optimizing with respect to this objective with a simple model is guaranteed to converge to the correct structure, and also presents experimental results on toy problems to demonstrate.