Variable Complexity in the Univariate and Multivariate Structural Causal Model
Authors: Tomer Galanti
Ofir Nabati
Lior Wolf
Venue:  (2020)

Abstract: We show that by comparing the individual complexities of univariante cause and effect in the Structural Causal Model, one can identify the cause and the effect, without considering their interaction at all. The entropy of each variable is ineffective in measuring the complexity, and we propose to capture it by an autoencoder that operates on the list of sorted samples. Comparing the reconstruction errors of the two autoencoders, one for each variable, is shown to perform well on the accepted benchmarks of the field.

In the multivariate case, where one can ensure that the complexities of the cause and effect are balanced, we propose a new method that mimics the disentangled structure of the causal model. We extend the results of~\cite{Zhang:2009:IPC:1795114.1795190} to the multidimensional case, showing that such modeling is only likely in the direction of causality. Furthermore, the learned model is shown theoretically to perform the separation to the causal component and to the residual  (noise) component. Our multidimensional method obtains a significantly higher accuracy than the literature methods.

Under review as a conference paper at ICLR 2020
VARIABLE COMPLEXITY IN THE UNIVARIATE AND MULTIVARIATE STRUCTURAL CAUSAL MODEL
Anonymous authors Paper under double-blind review
ABSTRACT
We provide a critical view of the univariate Structural Causal Model. We show that by comparing the individual complexities of univariate cause and effect, the Saneeettral--assete Modell one can identify the cause and the effect, without considering their interaction at all. Thee-entrop--oe enef-eehheeee is measuring the complexity, and We propose We suggest to capture it the complex- ity by the reconstruction error an autoencoder that operates on the list-of sorted samples the percentiles of the distribution. Comparing the reconstruction errors of the two autoencoders, one for each variable, is shown to perform well on the accepted benchmarks of the field. Hence, the decision to which of the two is the cause and which the effect may not be based on causality but on complexity.
In the multivariate case, where one can ensure that the complexities of the cause and effect are balanced, we propose a new adversarial training method that mimics the disentangled structure the causal model. We extend the results of /Zhag & Hyvrinen (010)) the multidimensional case, showing that such modeling is only likely in the direction causality. Furthermore, the learned model shown theoretically to perform the separation to the causal component and to the residual (noise) component. Our multidimensional method obtains a significantly higher accuracy than the literature methods.
INTRODUCTION
A long standing debate in the causality literature, is whether causality be inferred without in- tervention (Pearl 2009; Spirtes et al.] 2000). The Structural Causal Model (SCM) (Spirtes et al. 2000) is simple causative model for which many results demonstrate the possibility of such infer- ence (Stegle et al. 2010 Bloebaum et al. 2018 Goudet et al.) [2018] Lopez-Paz et al., 2017 2015). In this model, the effect (Y) is function of the cause (X) and some independent random noise (E).
In this work, we take a critical perspective of the univariate SCM. We demonstrate empirically that for the ID univariate case, which is the dominant case in the existing literature, the SCM medel leads to an effect that has a lower complexity than the cause. Therefore, one can identify the cause and the effect by measuring their individual complexities, with no need to make the inference based on both variables simultancously. Thus, the decision as to which of the two is the cause and which the effect may not be based on causality but on complexity.
Since we are dealing with unordered +D univariate random variables, the complexity measure has to be based on the probability distribution function. As we show empirically, comparing the entropies of the distribution two random variables is ineffective for inferring the causal direction. We, there- fore, consider the quantiles, i.e, fixed sized vectors that are obtained as sub-sequences of the sorted sampled values of the variable.
We consider suitable complexity scores for these vectors. our analysis, we show that the recon- struction error of an autoencoder of a multivariate random variable is valid complexity measure. In addition, we link the reconstruction error based complexity, in the case of variational autoencoders, to the differential entropy of the input random variable. Hence, by computing the reconstruction errors of trained autocncoders on these vectors we estimate the entropies of the quantile vectors of X and Y.

---

Under review as a conference paper at ICLR 2020
The challenges of measuring causality independently of complexity in the 1D case lead us sider the multidimensional case, where the complexity can be controlled by, e.g., manipulating the dimension of the noise signal in the SCM model. Note that unlike Goudet et al. (2018), we consider pairs of multivariate vectors and not many univariate variables in a graph structure. We demonstrate that for the multidimensional case, any method that is based comparing the complexity of the individual random variables X and Y fails to infer causality of random variables. Furthermore, we extend the result of Zhang & Hyvrinen (2010) to the multidimensional case and prove that an SCM is unlikely to hold in both directions X Y and Y + X for reasonable conditions.
Based on our observations. we propose new causality inference method for multidimensional cause and effect. The algorithm learns three networks in way that mimics the parts of the SCM model. The noise part is unknown and is replaced by a function that is constrained be independent of the cause, as captured by an adversarial loss. However, we show analytically and empirically that even without the explicit constraint, in several cases, such an independence emerges.
Our empirical results support our analysis and demonstrate that in the ID univariate case, assigning cause and effect based on complexity is competitive with the state of the art methods. In the mul- tidimensional case, we show that the proposed method outperforms existing and new extensions of the literature methods to the multidimensional case.
1.1 PROBLEM SETUP
We investigate the problem of causal inference from observational data. non- non-linear structural causal model (SCM for short) is generative process of the following form:
X ~ Px
E PE Y + {(())
The functions g : Rdd+d. + Rd and f: R + Rd are fixed and unknown. In general, g and f are non-linear. Here, X the input random variable and E is the environment random variable that is independent of X. We say that X causes Y if they satisfy generative process such as Eq. [
We present methods for inferring whether X causes Y (denoted by X - Y) or Y causes X, or neither. The algorithm is provided with i.i.d samples {( v:)] Pxyyy (the distribution of m i..d samples from the joint distribution ) from the generative process of Eq. In general, by (cf. Prop 4.8, (Peters et al. 2017)), for any joint distribution Px,y of two random variables X and Y, there is an SCM, Y g(((), E), where E is noise variable, such that, X_L and h is some (measurable) function. Therefore, in general, deciding whether X causes Y or vice versa is ill-posed when only provided with samples from the joint distribution. However, Khowever,ZZhang & Hyvrinen (210)) showed for the one dimensional case (i.e., X,Y E R) that under reasonable conditions, representation = (Xf x E¹) holds only in one direction. In Sec. 3.22 3.2. show that representation Y = g( [XX), E') holds only in one direction when and f are assumed to be neural networks and X, Y are multidimensional (we call such SCMs neural SCMs).
extend this theorem and
Throughout the paper, we denote by Pu[u] := PU < u] the cumulative distribution function of a uni/multi-varia variite real valued random variable U and IP is a standard Lebesgue measure. Additionally, we denote by (u) = d Pr [u] the probability density function of U (if exists, i.e., Per [M] is absolutely continuous), We denote by [f or by [f the expected value of f(u) for that is distributed by Pe [u]. depending on the context. The identity matrix of dimension n n is denoted by I,. We recall a few notations from information theory (Shannon, 1948 Cover & Epp log (Pr (u)]],
du
Thomas, 2006). The entropy of a random variable U, defined as h(U) := -E
where U is the domain of U. The mutual information between two random variables U and V is denoted by [(U; V) == Eppc,r log (, Sometimes, we will denote (U; V), to specify the PDF, of the variables (U, V).
1.2 RELATED WORK
In causal inference, the algorithm is provided with a dataset of matched samples (z, y) of two random variables X and Y and decides whether X causes y vice versa. The early wisdom
2

---

Under review as a conference paper at ICLR 2020
in this area asserted that this asymmetry of the data generating process (i.e., that Y is computed from X and not vice versa) is not apparent from looking at Px.y alone. That is, in general, provided with samples from the joint distribution P Fxyy of two variables X, Y does tell whether it has been induced by an SCM from X to Y or from Y to X.
In publications such (Pearl 2009 Spirtes et al., 2000) it is argued that in order to decide whether X causes Y or vice versa, one needs to observe the influence of interventions on the environment parameter. To avoid employing interventions, most publications assume prior knowledge on the generating process and/or independence between the cause and the mechanism.
Various methods for causal inference under the SCM model have been suggested. Many of these methods are based on independence testing, where the algorithm models the data as Y = g(f(X), (and vice versa) and decides upon the side that provides better fitting in terms of map- ping accuracy and independence between f(X) and E = r(X, Y). The LiNGAM (Shimizu et al., 2006) algorithm assumes that the SCM takes the form Y = |x + E, where X_ and |3 E IR and E is non-Gaussian. The algorithm learns 3, such that, X and Y - BX are independent by applying independent component analysis (ICA for short). The Direct-LiNGAM (Shimizu et al. 2011 ex- tends this method and replaces the mutual information minimization with a non-parametric kernel based loss (Bach & Jordan 2003 However, the computation of this loss is of order (mm²) in the the worst case (m is the number of samples).
The ANM approach (Hoyer et al., 2009) extends LiNGAM's modeling and assumes that Y = f(X) + E, where X E. In their modeling they employ a Gaussian process for the learned mech- anism between the two random variable. The function f is trained to map between X and Y (and vice versa) and the method then tests whether, X and f(X) Y are independent. The independence test is based on kernels (Gretton et al. 2005).
A different extension of LiNGAM is the PNL algorithm by Zhang & Hyvrinen 2010 This algo- rithm learns a mapping between X' and Y (and vice versa) of the form Y = (() + E),, where fX) and E' are restricted be independent. To do so, PNL trains two neural networks f and g to minimize the mutual information between f(X) and E' = g (Y) - f(X). The main disadvantage of this methods is the reliance on the minimization of the mutual information. It is often hard to measure and optimize the mutual information directly, especially in higher dimensions. In many cases, it requires having an explicit modeling of the density functions, because of the computation of expected tog-probability within the formulation of the entropy measure.
In our method, we take a similar approach to the above methods. However, our independence constraint is non-parametric and is applied on the observations rather on an explicit modeling of the density functions. In addition, we do not assume restrictive structural assumptions and treat the generic case where the effect is of the form Y 9(f(X), E). In addition, our method is computationally efficient.
Several other methods take different approaches. For example, the Information Geometric Causal Inference algorithm (IGCI) (Daniusis et al., 2012) approach determines the causal relationship in a deterministic setting Y = f(X) under independence assumption between the cause X and the
mechanism f. Cov(log (xxx),x))= 0.
The Conditional Distribution Similarity Statistic (CDS) (Fonollosa) 2016 measures the standard deviation of the values of Y (resp. X) after binning in the X (resp. Y) direction. The lower the standard deivation, the more likely the pair to be X Y. The CURE algorithm (Sgouritsa et al. 2015) compares between X + Y and Y - X directions in the following manner: is given as follows: if we can estimate Pxjy based on samples from py more accurately than pr|x based on samples from px, then X + Y is inferred.
The BivariateFit method learns a Gaussian process regressor in both directions and decides upon the side that had the lowest error. The RECI method (Bloebaum et al. 2018) trains a regression model in both directions, and returns the side that produced lower MSE loss. The utilized regression models were: logistic function, polynomial functions, support vector regression and neural networks. The CGNN algorithm (Goudet et al., 2018) uses the Maximum Mean Discrepancy (MMD) distance between the distribution produced by modeling Y as effect of X, (X,9(X, (X, E)) (and vice versa), and the ground truth distribution. The algorithm compares the two distances and returns the direction that led to smaller distance. The Gaussian Process Inference model (GPI) Stegle al. 2010)
3

---

Under review as a conference paper at ICLR 2020
builds two generative models, one for X - Y and one for + X. The distribution of the candidate cause variable is modelled as a Gaussian mixture model, and the mechanism f is a Gaussian process. The causal direction is determined from the generative model that best fits the data.
Finally, it is worth mentioning that several other methods, such as (Heinze- Deml et al. 2017 Zhang et al. T assume different type of SCM, where the algorithm provided with separate datasets that correspond to different environments, i.e. sampled i.i.d from Px,yJE- where the value of E fixed for all samples in the dataset. In these publications, different independence condition is assumed: Y is independent of E given X. This assumption typically fails in our setting, In our paper, we focus on a vanilla SCM, where the algorithm is only provided with observational samples of X and Y = g(f()), E) (i.idd samples). The samples are not divided into subsets that are invariant w.r.t
THE UNIVARIATE CASE
In this section, intend to show that the univariate case is bit simplistie. For this purpose, start by describing method for identifying the cause and the effect, which considers each of the two variables independently without considering the mapping between them. The method is based on the statistics of the quantiles of each of the two distributions. In Sec. [.2 we show that the reconstruction error of an autoencoder is directly linked the differential entropy of the distribution it models.
2.1 A METHOD FOR INFERRING DIRECTIONALITY
We hypothesize that due to the information processing inequality, the entropy of the cause (xX) in the SCM model is higher than the eniropy A(Y) of the efffet. However, estimating the entropy eaeh-randon variable from its sumples does not present consistent differrenee h(X) and and hYY).
entropiets
Our method, therefore, The proposed method computes an-ulternative complexity score for X and, independently. for Y. It then compares the scores and decides that the cause is the random variable that has the larger score among them.
Our scoring function has few stages. As first step, it converts the random variable at hand (say, X) into a multivariate random variable. This done by sorting the samples of the random variable, and then cutting the obtained list into fixed sized vectors of length k. We discard the largest measurements in the case where the number of samples is not a multiple of k. We denote the random variable obtained this way by U.
At the second stage, the method trains an autoencoder A IR + I& on these quantile vectors. Formally, A is trained to minimize the following objective:
Creco (A) := E.-uU ( (A(u), u)]
where É(a, b) is some loss function. In our implementation, we employ the L2-loss function, defined as E(a, b) ||a 1|a-b113. bllž- Finally, the method uses the value of Crcom (A), which we refer to as the AEQ score, as a proxy for the complexity of X (smaller loss means lower complexity). It decides that X or Y the cause, based on which side provides a higher AEQ.
2.2 RECONSTRUCTION ERROR AS AN ESTIMATOR OF THE ENTROPY
Next, we would like to provide better understanding of the AEQ method. Since we use the re- construction етто as a measure of complexity, we next link it to entropy, which an acceptable complexity measure. This will explain that the AEQ method estimates and compares the entropies of the percentiles of X and Y. This does not imply that the AEQ method compares between the entropies of X and Y.
The analysis This is done in the context a learned variational autoencoder (VAE) Kingma & Welling 2014), with fixed latent space dimension.
We are given a valluve
www.aaanndoambbbbbaa (not necessarily quantiles) with a PDF Pr. We recall the setting of VAEs and the analysis of /hao al. (2017). The VAE model employs
4

---

Under review as a conference paper at ICLR 2020
d dimensional latent variable (0 I2), and considers the family of the distribution pe (ul2) parameterized by 8 E @. The objective of this framework to select & that maximizes the likelihood of the samples of U within po(ul2) p(z).
B (og) = Bune Ure Po(ul2) p(z) de
(3)
-k/ the PDF of 2 and po(u) = pe (u]()) p(z). In typical situations, select po be the PDF of a normal distribution NV ([f(=)), of In), where Jo(z) F a learned neural network and of is a variance hyperparameter of the framework. We denote by P [p)(u]=))= IRd, 0 E )) the class of density functions over X'
where p(z) = exp(<11=13/2)- (2T)
To optimize this objective, it is required to evaluate Pe (u), which involves the computation of high dimensional integral. Even though this integral can be approximated by sampling, this is a costy process that has to be done for every sample To solve this problem, distribution that is responsible to model the latent codes that are most probable given a. This PDF normal distribution ((g((u), o2 Ia). Here, go(u) is
have second
denoted by (2(2|u) (z/u) and corresponds neural network with parameters & E 4.
Suppose we are given fixed inference distribution ys (z(z)u), which maps (probabilistically) inputs to features 2. We denote by (u, 2) := pu (u(u) (2((2lu) the joint distribution of u and 2, the marginal 9o (2) := J,, ( 2)du and the posterior (a(u)2) qs(2)u) (u)) (z))
The optimization criterion is redefined as follows, where for each we use member of a class of distributions, P, fit different 2 (u) 2) rather than the entire pc-
E:Egg(..:)) [log [o(u]2)]
(4)
The following lemma links the reconstruction loss and the entropy (all proofs are in the appendix) Lemma 1. In the setting of Sec. 2.2 Let 6 be the global optimum of Eq. forr sufficiently large F. Assume that P is sufficiently large, such that:
Vz 2,0 o go(u)2) E
(5)
M(U)- = 207 Enny [EeNN((,LLa) [Il (go + o² la l..
-112]] log (2mOat
Then,
(6)
+ Ennu [u))) + (o3 log(oz))
+ "
2
Therefore, from this lemma, we observe that ge learned, such that, the expected norm of encodings of u, Eesv [u)]( bounded, then, the differential entropy h(U) is proportional reconstruction error of the learned autoencoder. In particular, for two random variables U1 and U2. their entropies can be compared, by considering the reconstruction error of their autoencoders with the same hyperparameters (latent space dimension d, of, og. etc').
THE MULTIVARIATE CASE
For the univariate case, one consider the complexity of the X and Y variables of the SCM model and infer directionality. We propose the AEQ complexity for this case, since more conventional complexities ill-defined for unordered 1D data or, in the case of entropy, found to be ineffective.
In the multivariate case, one can consider the complexity of the random variables various ways. We focus the family of complexity measures C(X) that satisfy the assumption that when X and Y are independent
C(X,)) 2 max(C(X),
Sample complexity measures that satisfy this condition the Shannon Entropy and the Kol- mogorov Complexity. Lem. 3 in Appendix. B.2 shows that the complexity that is based on au- toencoder modeling is also in this family.
The next result shows that for any complexity measure C' this family, one cannot infer direction- ality in the multivariate SCM based on C.
5

---

Under review as a conference paper at ICLR 2020
Lemma 2. Let C be complexity measure of multivariate random variables (i.e, non-negative and satisfies Eq. 7p. Then, there triplets of random variables (X, E,Y) and E,E,, such that, Y yXx E), Y g' (X, E), C(X) C(Y) and C(X) > C(Y). Therefore, C cannot serve score for causal inference.
3.1 A METHOD FOR CAUSAL INFERENCE
The causality inference algorithm trains neural networks G, F, and D. The success of fitting these networks serves as the score for the causality test.
The function F models the function S. G models g and R(Y) aims to model the environment parameter E. In general, our method aims at solving the following objective:
min for CG,(G, F,R =- Σ (G((F(a) R(b.)) 1 G,F.R
(8)
S.t: AIL
where is either X or Y and B the other option, and a; = 22, Yi or a; = Y/s ys. I; accordingly. To decide whether X + Y or vice versa, we train different triplet G. F for each direction and see if we can minimize the translation error subject to independence. We decide upon specified direction if the loss can be minimized subject to independence. In general, searching within the space of functions that satisfy A A RBB) is an intractable problem. However, we can replace with loss term that is minimized when A R(B).
Independence loss We would like R(B) to capture the information encoded in E. Therefore, restrict IBB) and A to be independent in each other. We propose an adversarial loss for this purpose, which is a modified version of loss proposed by Brakel & Bengio (2017) and later analyzed by (Press et al. 2019).
This loss measures the discrepancy between the joint distribution PA,R(B) and the product of the marginal distributions PA PR(B)- Let dr (dr) be the dimension of F's output (R). To measure the discrepancy, we make use of discriminator Ru+da + [0, 1] from class C that maximizes the following term:
(D(D: = Σ E(D(a, R(b,),
Σ R(D)), R(b.)).
where D is a discriminator network, and 1(,, q) = - log(() + (1 9) log(1 - p)) is the binary cross entropy loss for E [0.1] and q E 10. In addition, {(ās, ) are i.i.d samples from PA Pn. To create such samples, independently and then arbitrarily match them into couples (ā,, 64).
simply generate samples from à; PA and b; Pn
To restrict that R(B) and A are independent, we train At to fool the discriminator D and to convince it that the two of samples are from the same distribution,
Lindep Rt D)
1 m m
Σ ((D(as R(b)), 1)
1
Σ ((((a, R(o)).)
m
(10)
m
Full objective The full objective of our method is then translated into the following program:
min Ler(G, G, F, R) Àι Lindep Rt D)
G.F.R
(11)
min LD(D:R)
Where A is some positive constant. The discriminator D minimizes the loss Lp (D; R) concur- rently with the other networks. We denote by Geal the percentage of samples (a,, b,) that the dis- criminator classifies as and by Ctake the percentage of samples (ā,, b.) that are classified as O. We note that when Graal Clake distributions, i.e., is wrong in classifying half the samples.
the discriminator is unable discriminate between the two
Our method decides if X causes Y vice versa by comparing the score (G, F, R). A lower error means a better fit. The full description of the architecture employed for the encoders, generator and discriminator is given in Appendix.

---

Under review as a conference paper at ICLR 2020
3.2 ANALYSIS
In this section, we analyze the proposed method. In Thm. I we show that if X and Y admit a SCM in one direction, then it admits SCM in the opposite direction only if the involved functions satisfy a specific partial differential equation.
Theorem (Identifiability of neural SCMs). Let x,y admit a neural SCM from X to Y in Eq. such that px, and the activation functions of J and are three-times difserentiable. Then it admils a neural SCM from Y X only if px. f. 9 satisfy Eq. 34 the Appendix.
This result generalizes the one-dimensional case presented in (Zhang & Hyvrinen, 2010), where a one-dimensional version of this differential equation is shown to hold in the analog case.
In the following theorem, we show that minimizing the proposed losses is sufficient to recover the different components, i.e., F(X) x f(X) and R(Y) E, where A x B means that A = ((B) for some invertible function f.
Theorem 2 (Uniqueness of Representation). Let Pxy admit nonlinear model from X Y in Eq. [ i.e., Y = g( F.) for some random variable F.LX.. Assume that f and are invertible. Let G. F and R be functions, such that, Lent == (X.))) (x),, R(y)) y and G and F invertible functions and X JL ILY(.). Then, F(X) x f(X) and R(Y) x E.
Here, Ler = ((z,g))(X,) Y) [IG
- yll8 is the mapping error proposed in Eq. 8 In addition, the assumption X Il ILR(Y) sufficed by the independence loss. In Lem. Glin Appendix we extend this lemma to the case where the mapping loss is not necessarily zero and get rid of the assumption that invertible. this case, instead of showing that R(Y) x E, we provide an upper bound on the reconstruction of E out of R(Y) (and vice versa) that improves as Lee decreases.
B.3
We note that when the entropy of R(Y is smaller than the entropy of E, then, the independence X XIL)((Y) follows, even without the discriminator. Typically, when R has a limited capacity (i.e., small number of layers or output dimension), then, the entropy of R(Y) is limited as well.
Theorem 3 (Emergence of independent representations). Let Pxx admits nonlinear model from X to Y as in Eq. [ i.e.. Y = ((f B) for some random variable E.L... As- sume that X and Y are discrete random variables. Let G, F and R be functions, such that, fen = (x.)))(X..
R(y)) yllă = 0 and G is an invertible function. Assume that MR(()) S h(E) and that g is invertible. Then, we have: F(X)LL((Y), F(X) x S(X) and R(Y) E.
To conclude this section, by Thm. | under reasonable assumptions, if X and Y admit multivariate SCM in direction X > Y, then, there is no such representation in the other direction. By Thm. 2 by training our method in both directions, one is able to capture the causal model in the correct direction. This is something that is impossible to do in the other direction by Thm. [ By Thm. we show that in cases where (((())) S h( h(E),, J,,,,. the independence between F (X) and R(Y emerges implicitly. This is the typical case, when R's capacity is limited.
4 EXPERIMENTS
This section is divided into two parts. The first, is devoted to showing that causal inference in the one-dimensional case highly depends on the complexities of the distributions of X and Y. In the second part of this section, we show that our multivariate causal inference method outperforms existing baselines. Most of the baseline implementations were taken from the Causality Discovery Toolbox of Kalainathan & Goudet (2019). The experiments with PNL (Zhang & Hyvrinen] 2010)). LiNGAM (Shimizu et al. (0066) and GPI (Seggle et al. 2010 are based on their original matlab code.
4.1 ONE-DIMENSIONALL DATA
We compared the autoencoder method on several well-known one dimensional cause-effect pairs datasets. Each dataset consists of list of pairs of real valued random variables (X, Y) with their direction 1 or depending on X + Y or Y + X (resp.). For each pair, we have a dataset of samples ((x;, )=))

---

Under review as a conference paper at ICLR 2020
Five cause-effect inference datasets, covering wide range of associations, are used. CE- Net (Goudet et al., 2018) contains 300 artificial cause-effect pairs generated using random distribu- tions as causes, and neural networks as causal mechanisms. CE-Gauss contains 300 artificial cause- effect pairs as generated by Mooij et al. (016)) using random mixtures of Gaussians as causes, and Gaussian process priors causal mechanisms. CE-Multi (Goudet al. 2018) contains 300 artifi- cial cause-effect pairs built with random linear and polynomial causal mechanisms. In this dataset, simulated additive or multiplicative noise applied before or after the causal mechanism.
The real-world datasets include the diabetes dataset by Frank & Asuncion (2010), where causality from Insulin + Glucose. Glucose curves and Insulin dose were analysed for 69 patients, each serves as a separate dataset. To match the literature protocols, the pairs are taken in an orderless manner, ignoring the time series aspect of the problem. Finally, the Tübingen cause-effect pairs dataset by MMoii et al. (2016) is employed. This dataset is a collection of 100 heterogeneous, hand- collected, real-world cause-effect samples.
The autoencoder employed in our method is fully-connected 5-layered neural network with 3 layers for the encoder and 2 layers for the decoder. The hyperparameters of this algorithm are the sizes of each layer, the activation function and the input dimension, i.e., length of sorted cuts (denoted by in Sec. ( Throughout the experiments, we noticed that the hyperparameter that has the highest influence is the input dimension. For all datasets results are stable in the range of 200 I l: 300, and we therefore use k = 250 throughout the experiments. For all dataset we employed the ReLU activation function, except the Tübingen dataset, where the sigmoid activation function produced better results (results are also reasonable with ReLU, but not state of the art).
In addition to our method, also employ the entropy of each individual variable complexity method. This is done by binning the values of the variables into 50 bins. Other numbers of bins produce similar results.
Tab. presents the mean AUC for each literature benchmark. As can be seen, the AEQ complexity measure produces reasonable results in comparison to the state of the art methods, indicating that the ID SCM model can be overcome by comparing per-variable scores. On the popular Tübingen dataset, the ene-sided AEQ computation outperforms all literature methods.
Tab. presents accuracy rates for various methods on the Tübingen dataset, where such results are often reported in the literature. As can be seen, our simple method outperforms almost all other methods, including methods that employ supervised learning of the cause-effect relation.
4.2 MULTIVARIATE DATA
We compared our method on several synthetic datasets. Each dataset consists of list of pairs of real multivariate random variables (X, Y) with their direction 1 or O, depending on X - Y or Y X (resp.). For each pair, we have a dataset of samples (( y)))
We employ five datasets, covering multiple associations. Each dataset contains 300 artificial cause- effect pairs. The cause random variable is of the form X h(z), where h is some function and z ~ (O, of In). The effect is of the form Y = uu X, E)), where E ~ NN0 oz In) is independent of X, u a fixed function that combined the cause X and the noise term E and g is the causal mechanism. For each dataset, the functions h and are taken from the same family of causal mechanisms H. Each pair of random variables is specified by randomly selected functions and g.
MCE-Poly is generated element- wise polynomials composed on linear transformations as mech- anisms and E) X + E. MCE-Net pairs are generated using neural networks as causal mechanisms and is the concatenation operator. The mechanism in MCF-SigMix consists of linear transformation followed by element wise application of (a.b.e()) == ab(ā + c)/1 + bb (# + c)}, where a, 6, are random real valued numbers, which are sampled for each pair and ă te, where e is the environment random variable. this case, ul X, E') X E.
In order to create each one of the synthetic datasets we took the standard synthetic data generators of Kalainathan & Goudet (019)) and extended them to produce multivariate causal pairs. We noticed that a priori, the produced datasets are imbalanced in way that the reconstruction error of a standard autoencoder on each random variable can be employed as a score that predicts the cause variable with high accuracy. Therefore, in order to create balanced datasets, varied the amount of noise
8

---

Under review as a conference paper at ICLR 2020
Table 1:
Mean AUC rates of various baselines different dimensional cause-effect pairs datasets. Our simple AEQ algorithm achieves competitive results on most datasets.
Dataset
Method
CE-Net
CE-Gauss
CE-Multi
Tübingen
Diabetes
BivariateFit
77.6
36.3
55.4
58.4
0.0
LiNGAM (Shimizu et al.
2006
43.7
66.5
59.3
39.7
100.0
CDS Fonoolosa
2016
89.5
84.3
37.2
59.8
12.0
IGCI Dannusis et al. 2012)
57.2
33.2
80.7
62.2
100.0
ANM (Hoyer et al. 2009
85.1
88.9
35.5
53.7
22.2
PNL Zhang & Hyvrinen
2010)
75.5
83.0
49.0
68.1
28.1
GPI Stegle et al. | (010))
88.4
89.1
65.8
66.4
92.9
RECI [Bloebaum et al.
2018
60.0
64.2
85.3
62.6
95.4
CGNN (Goudet et al. 2018)
89.6
82.9
96.6
79.8
34.1
Entropy complexity measure
49.6
49.7
50.8
54.5
53.4
Our AEQ comparison
62.5
71.0
96.0
82.8
95.0
Table 2:
Accuracy rates various baselines on the CE-Tüb dataset. Our simple algorithm AEQ
achieves almost SOTA accuracy.
Method
Supervised
Acc
LiNGAM (hhmiiuu et al. 2006
44.3%
BivariateFit
44.9%
Entropy as complexity measure
52.5%
IGCI (Daniusis et al. 2012)
62.6%
CDS Fonollosa
2016)
65.5%
ANM (Hoyer al. 2009
59.5%
CURE (Sgouritsa et al. 2015)
60.0%
GPI Stegee et al. 201O
62.6%
PNL [Zhang & Hyvrinen
2010
66.2%
CGNN (Goudet ct al. 2018
74.4%
RECI (Bloebaum
2018
77.5%
SLOPE (Marx & Vreeken
2017
81.0%
Our AEQ comparison
80.0%
Jarfo
Fonollosa,
2016
+ 59.5%
RCC
Lopez- Paz et al.
2015
+ 75.0%
NCC
(Lopez-Paz et al.
2017
+
79.0%
"The accuracy of CURE is reported on version 0.8 of the dataset in (Sgouritsa et al. 2015) as 75%. In Bloe- baum et al. (2018) they reran this algorithm and achieved an accuracy rate around 60%.
"The accuracy scores reported (Lopez-Per Paz et al. 2015) are version 0.8 of the dataset, (Lopez-Pal al. 2017) they reran RCC (Lopez-Paz et al. 2015) on version 1.0 of the dataset.
dimensions and their intensity until the autoencoder reconstruction error of both X and Y became similar. Note that for these multivariate variables, we do not use quantiles and use the variables themsevles. the AutoEncoder reconstruction results in Tab. show, in the MCF--SgMix dataset balancing was only partly successful.
Tab. we also compare our method to BivariateFit and ANM (Hoyer et al. 2009 algorithms on these datasets and present favorable performance. The other literature methods are designed for the univariate case and therefore, we were unable to extend them. The only baseline methods that are extendable to multi dimensions are PNL (Zhang & Hyvrinen 2010), CGNN (Goudet al. 2018) and RECI (Bloebaum et al.) 2018). However, their runtime becomes toe-let-eee long. Specifieally; However, RECT's runtime of order O where is the input dimension.

---

Under review as a conference paper at ICLR 2020
Table 3: Mean AUC rates of various baselines on different multidimensional dimensional cause- effect pairs datasets. The datasets are designed and balanced, such that an autoencoder method would fail. Our method achieves SOTA results.
Method
MCE-Poly
MCE-Net
MCE-SigMix
MOUS-MEG
BivariateFit
54.7
48.4
48.2
44.2
ANM (Hoyer et al., 2009
52.2
51.1
46.4
52.4
PNL hann & Hyvrinen 2010
76.4
54.7
16.8
56.3
CGNN (Goudtt et al. 2018
47.8
67.8
58.8
40.9
AE reconstruction
57.2
42.4
22.3
41.2
Our method
95.3
70.0
98.5
87.6
In addition to the synthetic dataset, we also employ the MOUS-MEG real world dataset, provided
to us by the authors of (Anonymous) 2020). This dataset is part of Mother Of Unification Studies (MOUS) dataset (Schoffelen al. 2019). This dataset contains eegnntt-cnccehallgrrpyy (MEG) recordings 102 healthy dutch dutch-speaking subjects performing reading task (9 of them were ex- cluded due to corrupted data). Each subject was asked to read 120 sentences in Dutch, both in the right order and randomly mixed order, which adds up to a total of over 1000 words. Each word was presented on the computer screen for 351ms on average and was separated from the next word by 3-4 seconds. Each time step consists of 301 MEG readings of the magnetometers, attached to different parts of the head. For more information X is the interval [-1.5s, 0.5ss relative to the word onset concatenated with the word embedding (using the spaCy python module with Dutch language model), this presents the subject in his "rest" state (i.e. the cause). Y is the interval [0, 1.0s] relative to the word onset, which presents the subject in his "active" state (i.e. the effect). The results, also given in Tab. 3 show a clear advantage over the literature methods.
(Schoffelen et al. 2019). For each pair (X, Y).
To validate the soundness of the dataset, we ran made few experiments on variations of the dataset and report the results in Tab. 4 As can be seen, a dataset where the cause consists of the word embedding and the effect consists of the subject's "active" state highly imbalanced. This rea- sonable since the word embedding and the MEG readings are encoded differently and are of different dimensions. In addition, when the cause selected to be the "rest" state and the effect the "active" state, the various algorithms are unable to infer which side is the cause and which one is the effect since the word is missing.
Emergence of independence To check the importance of our adversarial loss in identifying the direction of causality and capturing the implicit independent representation f(X) and E, we applied method without training R against the discriminator. Therefore, in this case, the discriminator only serves as test whether X and R(Y) are independent or not. Recall that our analysis shows that the discriminator not necessary under reasonable conditions. As can be seen in Tab. S the adversarial loss improves the results when there is no implicit emergence of independence, however, in cases where there is emergence of independence, the results are similar. This is verified in Tab which shows similar performance with and without the discriminator.
As mentioned in Sec. 3.T. the distance between Geal + Ctke to indicates the amount of dependence between X and R(Y). We denote by Ind C the mean values of Creal + Crake - 1 over all pairs of random variables, epochs and samples when training our method the causal direction. The same mean score when training in the anti-causal direction is denoted Ind E. As is evident from Tab. 5 the independence is similar between the two directions, emphasizing the importance of the reconstruction error in the score.
We noticed that the values of Ind C and Ind E are smaller for the full method. However, in MCE-Poly and MCE-SigMix they still very small, and therefore, there is implicit emergence of indepen- dence between X and R(Y), even without explicitly training R(Y) ) to be independent of X. This explain the fact that the drop in the AUC is significant but not drastic.
10

---

Under review as a conference paper at ICLR 2020
Table 4: Results of various methods different variations of the MOUS-MEG dataset.
Dataset
Method
Rest, Word - Active
Rest - Active
Word + Active
BivariateFit
44.2
58.1
0.0
ANM (Hoyer et al. 2009)
52.4
49.3
0.0
AE reconstruction Our method
41.2
51.7
98.6
87.6
44.4
0.0
Table 5: Emergence of independence. Ind C (Ind E) is the mean of |Creal Cfake - 1| over all pairs of random variables, epochs and samples, when training the method from to (vice versa). w/o backprop means without backpropagating gradients from D to R.
Full method
w/o backprop
Dataset
AUC
Ind C
Ind E
AUC
Ind C
Ind E
MCE-Poly
95.3
0.06
0.05
95.1
0.10
0.10
MCE-Net
70.0
0.16
0.20
65.1
0.55
0.55
MCE-SigMix
98.5
0.05
0.06
98.8
0.16
0.20
MOUS-MER
87.6
0.61
0.61
80.7
0.74
0.75
SUMMARY
We identify an inbalance in the complexities of cause and effect in the unidimensional SCM medel and suggest a method to exploit it. Since the method does not consider the interactions between the variables, its success in predicting cause and effect indicates inherent bias the unidimensional datasets. Turning our attention to the multivariate case, where the complexity can be actively bal- anced, we propose a new method in which the learned networks models the underlying SCM model itself. Since the noise term E is unknown, we replace it by function of Y that is enforced to be independent X. We also show that under reasonable conditions, the independence emerges even without explicitly enforeing it.
REFERENCES
Anonymous. Measuring causal influence with back-to-back regression: the linear case. In Submitted to International Conference on Learning Representations, 2020. URL https:
//openzeview wostt//ooummddBBBe...
B11KD1HtWKS under review.
Francis R. Bach and Michael I. Jordan. Kernel independent component analysis. J. Mach. Learn. Res., 3:1-48, March 2003. ISSN 1532-4435. doi: 10. 10.11222553243376666660 URL https:
Patrick Bloebaum, Dominik Janzing, Takashi Washio, Shohei Shimizu, and Bernhard Schoelkopf. Cause-effect inference by comparing regression errors. In Amos Storkey and Fernando Perez- Cruz (eds.), Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 900-909, Playa Blanca, Lanzarote, Canary Islands, 09-11 Apr 2018. PMLR.
Philemon Brakel and Y Bengio. Learning independent features with adversarial nets for non-linear ica. 2017.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series Telecom- munications and Signal Processing). Wiley--nterscience,, New York, NY, USA, 2006. ISBN 0471241954.
Povilas Daniusis, Dominik Janzing, Joris M. Mooij, Jakob Zscheischler, Bastian Steudel, Kun Zhang, and Bernhard Schölkopf. Inferring deterministic causal relations. CoRR, 2012.
11

---

Under review as a conference paper at ICLR 2020
M. Feder and N. Merhav. Relations between entropy and error probability. IEEE Transactions Information Theory, 40(1):259- 2600 Jan 1994.
José A. R. Fonollosa. Conditional distribution variability measures for causality detection. ArXiv,
(bbs/100.06680, 2016.
A. Frank and A. Asuncion. UCI machine learning repository, 2010. http://archive.ic.u....d...
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, David Lopez-Paz, Isabelle Guyon, and Michèle Sebag. Learning functional causal models with generative neural networks. In Ex- plainable and Interpretable Models in Computer Vision and Machine Learning, Springer Series Challenges in Machine Learning. Springer International Publishing. 2018
Arthur Gretton, Ralf Herbrich, Alexander Smola, Olivier Bousquet, and Bernhard Schölkopf. Kernel methods for measuring independence. J. Mach. Learn. Res., 6:2075-2129, December 2005. ISSN 1532-4435. URL http:://// //dt:::/dd...
acm www.e.oooo.o..ooooo.ooooooooo.oe weiiiaaiiiooo cfm ? id= 04 6920. 1 94914
Christina Heinze-Deml, Jonas Peters, and Nicolai Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6, 2017.
Patrik O. Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlin- ear causal discovery with additive noise models. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou (eds.), Advances in Neural Information Processing Systems 21, pp. 689-696. Curran Associates, Inc., 2009.
Diviyan Kalainathan and Olivier Goudet. Causal discovery toolbox: Uncover causal relationships in python, 2019.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
D. Lopez-Paz, R. Nishihara, S. Chintala, B. Schölkopf. and L. Bottou. Discovering causal signals in images. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2017, pp. 58-66, 66, Piscataway, NJ, USA, July 2017. IEEE
David Lopez-Paz, Krikamol Muandet, Bernhard Schikopf, and Iliya Tolstikhin. Towards learning theory of cause-effect inference. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 1452-1461, Lille, France, 07-09 Jul 2015. PMLR.
A. Marx and J. Vreeken. Telling cause from effect using mdl-based local and global regression. In 2017 IEEE International Conference Data Mining (ICDM), pp. 307-316, Nov 2017.
Joris M. Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Bernhard Schölkopf. Dis- tinguishing cause from effect using observational data: Methods and benchmarks. Journal of Machine Learning Research, 17(32):1-102, 2016.
Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2009. ISBN 852189560X, 9780521895606
J. Peters, D. Janzing, and B. Schölkopf. Elements of Causal Inference Foundations and Learning Algorithms. Adaptive Computation and Machine Learning Series. The MIT Press, Cambridge, MA, USA, 2017.
Ori Press, Tomer Galanti, Sagie Benaim, and Lior Wolf. Emerging disentanglement auto-encoder based unsupervised image content transfer. In International Conference on Learning Representa- tions, 2019.
Jan-Mathijs Schoffelen, Robert Oostenveld, Nietzsche HL Lam, Julia Uddén, Annika Hultén, and Peter Hagoort. A 204-subject multimodal neuroimaging dataset to study language processing. Scientific data, 6(1):17, 2019.
12

---

Under review as a conference paper at ICLR 2020
Eleni Sgouritsa, Dominik Janzing, Philipp Hennig, and Bernhard Schlkopf. Inference of Cause and Effect with Unsupervised Inverse Regression. In Guy Lebanon and S. N. Vishwanathan (eds.), Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pp. 847-855, San Diego, California, USA, 09-12 May 2015. PMLR.
Claude Elwood Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379-475 423, 7 1948. doi: 10. 151.:)111188777.18888.... leeexplore. fees. org/ www.cmmen//77300000
URL https://
Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. linear non-gaussian acyclic model for causal discovery. J. Mach. Learn. Res., 7:2003- 2030, December 2006. ISSN 1532-4435.
Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvärinen, Yoshinobu Kawahara, Takashi Washio, Patrik O. Hoyer, and Kenneth Bollen. Directlingam: direct method for learn- ing linear non gaussaassin structural equation model. J. Mach. Learn. Res., 12:1225 1248, July 2011. ISSN 1532-4435. URL http:: aww.acm.roo.o wcm.org/citation. em? wwwffmiid-99mm
2021 1 040
John R. Silvester. Determinants of block matrices. The Mathematical Gazetle, pp. 2000, 1999.
P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT press, 2nd edition, 2000.
Oliver Stegle, Dominik Janzing, Kun Zhang, Joris M Mooij, and Bernhard Schölkopf. Probabilistic latent variable models for distinguishing between cause and effect. In J. D. Lafferty, K. Williams, J. Shhawe-Tayoor, R. S. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems 23, pp. 1687-1695. Curran Associates, Inc., 2010.
Kun Zhang and Aapo Hyvrinen. Distinguishing causes from effects using nonlinear acyclic causal models. In Isabelle Guyon, Dominik Janzing, and Bernhard Schlkopf (eds.), Proceedings of Workshop on Causality: Objectives and Assessment at NIPS 2008, volume of Proceedings of Machine Learning Research, pp. 157-164, Whistler, Canada, 12 Dec 2010. PMLR
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI'1,, pp. 804-813, Arlington, Virginia, United States, 2011. AUAI Press. ISBN 978-0-974903997-2. URL http: //tp: acm. org/ 3020661
citation.ccfsi
Shengjia Zhao, Jiaming Song, and Stefano Ermon. Towards deeper understanding of variational autoencoding models. ArXiv, abs/ 702.08865, 2017.
13

---

Under review as a conference paper at ICLR 2020
A ARCHITECTURE
The function G, F, R and the multivariate method in Sec are fully connected neural networks
and their architectures are follows: F is 2-layered network with dimensions 100 - 60 50, Rt is 3-layered network with dimensions 100 + 50 - 50 + 20, G is a 2-layers neural network with dimensions 50 + 20 80 100 (the input has 50 dimensions for F(X) and 20 for R(Y)) The discriminator is a 3-layers network with dimensions 100 + 20 - 60 - 50 + 2 (the input is X and R(Y)). The activation function in all networks is the sigmoid function except the discriminator that applies the leaky ReLU activation. For all networks, the activation is not applied at the output layer.
B ANALYSIS
B. TERMINOLOGY AND NOTATIONS
We recall some relevant notations and terminology. The identity matrix of dimension n is denoted by In. For vector z (æI...., :nn) E IR" we denote | == V 2i=1 . the Euclidean norm of x. For a differentiable function f IRm > IR" and x E RT,, we denote by
05i OG
I((())
(x)
(12)
iE(m],j[(m]
the Jacobian matrix of f in x. For twice differentiable function
IR. :R
IR, we denote by
8
H(f(=))
ac,OC, (x)
(13)
(.jE(m]
the Hessian matrix of f x. Additionally, for a twice differentiable function f Ihm + R
f(x) = (/.) (x))) we denote the Hessian of / by H(f(z)) == (H(fi (x:),.... (=))))))).
For scalar function f IR + R instead of using the Jacobian notation, the gradient notation will be employed, v(f()) (()())).
B.2 AUTOENCODER AS COMPLEXITY MEASURE
Let F = { be a family of classes of autoencoders A Rd - Rdd Assume that the family F is closed to fixations, i.e., for any autoencoder E Hdi+dz and any fixed vector y" E RR (x" E Ed1,, we have: A(x, y "²").dd 1:d; Hdt (A(x", 4)di+1idz Hd)). Here, Uag = (U,...., U.)) We consider that this is the typical situation when considering neural networks with biases.
Let X be random variable. Let X be multivariate random variable dimension d. We define the autoencoding complexity of X as follows:
C(X:F) = min E (x),))
(14)
A'EE"
Let (Hd)00 be a family of classes of autoencoders that is closed to fixations. The function C(;FF) is a complexity measure according to Sec.
Lemma 3.
Proof. First, since {(a, b) 2 0 for all a, b E R this function is non-negative. Next, we would like to show that (x(X, () Z max(C((),, C(Y)). Let A be the minimizer of E [f(A*(x)) x)] within Hdl t-d We consider that there is vector y", such that,
B(x,))((X)) [e(A(z v), (2, y))] 2 Eywy [e(A(r, y), (w,y)))
E [[(A(x,)) y") (x,y"))
(15)
2 Erax [[(A(z, v "1.l,, x))]
We note that A(x, y² 2ndd Hdh Therefore, (x [((A(z: y), (x,0))
min E = ArEnds
(16)
By similar considerations, C(XY;;F) Y)F).
14

---

Under review as a conference paper at ICLR 2020
B.3 PROOFS FOR THE RESULTS
In this section we provide the proofs of the main results in the paper.
Lemma 1. In the setting of Sec. 2.2 Let 6 be the global optinum of Eq. for sufficiently large F. Assume that sufficiemtly large, such that:
V2 2,E, o go(uz)) EP
(5)
1 M(U)
2 EuNu (EeNN((Ona)) [llfo- (g)(u) + t Ia cc [a]]]]
Then,
(6)
+ 2 Ean [u)g) + d (o2 1 - log (gg())))
+ log (og((
2
Proof.
This a corollary the analysis of Zhao et al. 2017). By their analysis, we have:
M(U) 1 (2; u)
Egg [logPa- Pa- (u|=)]
(17)
Since we selected pa- (u|z) be the PDF of a normal distribution WN (2), In), we have:
log Pe- (ulz) || (z) u1
loogo222 log((
(18)
20
Therefore, since distributed by (z(z)u) can be represented as z/u go(u) + to la where (o)
1
(u,)) [logPur po (u|=)]
(u)))) [llfo (2) uu|@] + log log(2xTo})
20
1
EnNU [eo() [llfo- (2) = + 2 log (2TTO
207
(19)
1
EEwu [BenN(odda [[lfo- (go(u) (u) + og la t) - -112]
20
+
log(2TT²))
In addition, we have:
190 (z; = Euwu DKL (2(l(((2)))llppee
Enwu DKL ( (o)
EnwU
(d [d [1 + dloo(oo))
(20)
2
d (oz - 1 log(oz))
1 Bu (1))
2
2
Therefore, we obtained the desired equation.
Lemma 2. Let C be a complexity measure of multivariate random variables (i.e, non-negative and satisfies Eq. 7). Then, there are triplets of random variables (X, E, Y) and (X, F, Y), such that, Y == =X(,, E), Y = score for causal inference.
= g'(,, C(X) < C(Y) and C(²) > C(Y). Therefore, C cannot serve
Proof. Let X be a random variable and E.LX,, such that, = g(X, E). Assume that C(X) < C(Y). Then, let X' be random variable independent of X, such that, C(X') C(Y). Then, have: C(X,')) C(Y) and we have: Y = (X, X',B) E), for g' (a b, g(a,c).
The following lemma is an extension of Thm. in (Zhang Hyvrinen 2010 to real valued random variables of dimension 1.
15

---

Under review as a conference paper at ICLR 2020
Lemma 4. Assume that (X,Y) can be described by both:
Y = (x) + E1), s.t. X E and 91 is invertible
(21)
and
= 92 (x2 + E2), s.t. Y E2 and 92 invertible Assume that 91 and 92 are invertible and let:
(22)
Ti : 91 (Y) and h1 == f2 91
(23)
T2 92 (X) and h2 = fi 92
Assume that the involved densities pT,, PE, and nonlinear functions f1.g. and f2, 92 third order differentiable. We then have the following equations for all (X,Y) satisfying:
H(mi(t2) (()r(tz)) - H((z(e))) ((h2(t2))
+ H(n((e)) ((h2((2)) -
(24)
- v(n((e)) H(hh((()) (()((t)))
where (12) = Pr, (12) and (2(e1) == Po (e)).
Proof. The proof is an extension of the proof of Thm. in (Zhang & Hyvrinen 2010). We define:
Ti 91 (Y) and h1 == fz 91
(25)
T2 = 92 (X) and h2 f 92
Since 92 is invertible, the independence between X and Ej is equivalent the independence be- tween 722 and Ej. Similarly, the independence between Y and Eg is equivalent to the independence between Ti and Eg. Consider the transformation F (E2, Ti) T2):
E Ti fi Ti- fi (g2((T2) T- = J2(Y) Eg = (1:111(7))) + Eg
(26)
The Jacobian matrix of this transformation is given by:
: I=F((F(2,tt)) = ((h2(t2))) 1 ((h2(t2)) (())
(27)
(())
Since commutes with any matrix, by Thm. in (Silvester) 1999). we have:
de((I((((2)TTT)) det (-J(h2(Tb)) ((h) 1- ( (((])
=1
(28)
Therefore, we have: (t,) PE, (E1) = (t,,x((1,e2))) Jet]
(t),e.)
Hence,
log(pr,.e, (t1, m (t2) (2(())) and we have:
i log(pr log(p,,,,,th,.) (11, (m)(t2 Vnz(er) I(hg(tz))
(29)
de2
Therefore,
0 (E,T,,,,,,,1, e2))
=H(n (t2)) ((h)(ti)) H(m)()))) (I- J(he(ta)) ((hr(t)))) J(h2(tz))
Ōez0t,
v(n((e))) ((()((t)))J((((()))
=H(m(tz)) (())())))))))))))))))))))))))))) (((hh(((())))((((t)))))
+H(r)(e)) ((a -(a)))((((((((t)))) ((h2(tz))
((z((e)) H(ha(t2)) ((h)
(30)
The independence between Ti and Eg implies that for every possible (11,02), have:
8 log pr (f1.22)
0.
De20t1
16

---

Under review as a conference paper at ICLR 2020
Lemma 5 (Reduction to post-linear models). Let f(z 01 (Waz)) and g(u, 02(U,... ... ((]](()))) be two neural networks. Then, if = g(f(X); E) for some E,I,,, we can represent Y = (x) + for some N N.X.X
Proof. Let f(x) di (Wa... ... (Wix) and g(u, 2) 0z 02 ... (2U1(u))) be neural networks. Here, (u, v) is the concatenation of the vectors u and c. We consider that (x)),,
U1((X)+ + UP F. We define noise variable N := -UPh E. and have: X N. In addition, let f(x) Ul and Ø(z) 02(Uk ... (2(20o.(2)(2)))) We consider that: Y ((f(X) N) desired.
neural SCMs), Let x.y admit a neural SCM from X to Y as in Eq. such that px, and the activation functions of f and three-times differentiable. Then it admis a neural SCM from Y to X only if px, f. satisfy Eq. 34 in the Appendix.
Theorem (Identifiability
Proof. Let f1(=) oW 01 (W,,1²) and gs (u, v) = 02(UER ... 02 (U (u, v))) (where i 1, be pairs of neural networks, such that, on and 02 are three-times differentiable. Assume that:
Y ==((((x), E1) and X g(f(),, Ez)
(31)
for some E1 IL and EL By Lem. 5
we can represent
Y= (f Ni).
(32)
where N1 = Ei, f = (X) and 91(2) = o2 =.((Uis...o(iiooo(())
and also,
X = (2((f(YY) + N2).
(33)
where N2 = E2, f2 = f2(X) and 02(2) = (U2, (((
From the proof of Lem. 5 is evident that the constructed ÿ1 f and Ô fa are three-times differ- entiable whenever d and 02 are. Therefore, by Thm. [ the following differential equation holds:
((2))))) ((h1(tt)) ((n)()1)) ((h2(t2))
+ H(n)(m))) ((he(t2)) (()) ((h2(tz)) ((n((m)) H(h2((2)) ((b)(t)) =
(34)
where
Ti = 01 (Y) and hi = f2 أ1 T2 = 92 (X) and h2 = f 92
(35)
and m (12) = log.r, (12) and n/2 (n))= == log pN, (n1).
Theorem 2 (Uniqueness of Representation). Let Px, admit nonlinear model from X Y in Eq. 7 i.e., Y = g(f(X), for some random variable E.L... Assume that f and are invertible. Let G, F and R be functions, such that, Lerr == (llll R(w) E and G and F invertible functions and X ILY)). Then, F(X) f(X) and R(Y) E.
Proof. Since F and f are invertible, one can represent: F(X) = f(F-1 (F(X)). Similarly, since G and are invertible, also have: (F(X),((Y)) (f(X),)) E). Since (F(X), x (f(X), and F(X) x f(X), we have: R(Y) Q(F(X), E). However, R(Y)LF((X) and therefore, versa.
and f(X) =
represent R(Y) = P(E) and vice
Theorem 3 (Emergence of independent representations). Let Px, admits nonlinear model from to Y as in Eq. ! ie.., Y = ((((),, E) for some random variable F.I.X. As- sume that X and are discrete random variables. Let G, F and R be functions, such that, R(y)) vil 0 and G is an invertible function. Assume that h(R(Y)) < h(E) and that g is invertible. Then, we have: F(X) R(Y), F(X) x f(X) and
Len := (xxe)=(xxxx)I]G[[(((a
R(Y) x E.
17

---

Under review as a conference paper at ICLR 2020
Proof. Since g and f are invertible, have: h(Y) h(f(X)) h(E) h(X) + M In addition, we have: h(R(Y) & h(E). Therefore, since G invertible, = - S + S h(X) + h(E) h(Y). Hence, F(X) and R(Y) are independent.
In the following three lemmas we extend Thms. 2 and
Lemma 6. Let Px, admit a nonlinear model from X to Y as in Eq. 7 Le., Y = =x{((X); E), for some random variable E.L.X. Assume that f and g are invertible. Assume that X and Y are discrete and Y is over set y, such that, Vy + y2 E Y, F and R be functions, such that, Den == ((x,)))(X.))) [llv - G(F(2), R())) < A/2 and F is invertible. Then, F(X) f(X) and ((R(Y): 2 (1
have, |1y1 1/2 ll2 > A > 0. Let G,
( h(()) V Lar.
Proof. First, since both F and / are invertible, F(X) ((X). By the proof of Lem. 10 in Press et al. 2019), there is a function r, such that:
Ler A
P(.)))(xx))(F(())) R(v)) = 2
2 0.5
(36)
Since g is invertible, there is function u(Y) E. In particular,
P ((a.))-(x., R(y))) = u(v)) 2 (1
Ler
N 0.5
(37)
A
Therefore, by Lem. 6 in Press et al. 2019). we have:
Ler
Ler
(()()) 2
-h(E) - h
(38)
A
A
By the analysis in the proof of Lem. 10 in (Press et al. 2019), derive that:
Len
Len
I(F(X), 2
1
h(E)
(39)
A
A
Finally, since F(X) is a function of X which independent of E, we obtain the desired inequality:
I()(Y); (1-2(112))
Let
-h(E)
-V
1
Een
(40)
A
We mention that in Lem. 6. the function R(Y) can hold all of the information present in Y. There- fore, in order to suffice that R[Y)) holds only the information present in E, one can restrict that I(R(Y)) < I(E)= e as will be shown in the next lemma. We note that under the conditions of Lem. 6 h( (R(()) < h(E) + e1 is equivalent to (F(X;; R(Y)) I Eg for e1, 62 that are functions of each other.
Lemma 7. In the setting of Lem. Assume that h(R(Y)) & h(E) + e, for some constant E > O. Then, T(F(X); R(Y)) < f h(Y) +
+ e. In addition, there are functions T T2, such that, A
Plr() # E] < 2 Car A(E)/A Eaul
(41)
and
Pir((E) + R(Y) < 1 hom) -mm ///0///AA-CC///// Ae
(42)
Proof. By Lem. 10 in Press et al. 2019), we have:
M(F(X) MF(()), (())) R(Y)Y)
1
Lex
-((Y)
VA
V
Car
(43)
A
18

---

Under review as a conference paper at ICLR 2020
In addition, by the data processing inequality and the assumption h(R(Y) & h(E) + c, have: T(F(X); R()) z M(F(X)) + A(R(Y) - (FF(X), R(Y))
(1- A
Ler
Lew
- ((X) + +(V) -
M(Y)
A
(1- A
Lee
Lee
(44)
I <hYY) c
h(Y)
A
$ Lun h(Y +
Len
te
A
Finally, by Feder & Merhav 1994). there is a function 71, such that,
PIr)(R(Y)) * E S 1 (
(45)
2 ho) E
In addition, there is a function r2, such that,
Pir2(E) R(Y) s - (R())))))))))
< 1 -(())
(46)
S 1 - 2 - M(B/A Fea/A-
as desired.
19


Reviews:
[{"review_id": "rJgH6p3pFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update:\n\nThe authors have successfully justified my concerns. Therefore, I have increased my score to 6.\n\nOriginal comments:\n\nIn this paper, the authors consider learning causal directions from observational data from both univariate case and multi-dimensional case. In the univariate case, the authors propose a new method to learn causal directions by exploiting the complexities of cause and effect variables. In the multi-dimensional case, where the complexity can be balanced, the authors proposed a method that learns causal direction based on independence loss.\n\n1. The independence loss part looks confusing to me. Standard results in SCM yields that the error term E is a function of both the outcome Y and X. How can you learn the term E just from Y itself? In other words, I am not sure if the conditions required in Theorem 2 is feasible. The authors need to provide some examples to justify that the conditions in Theorem 2 are feasible conditions.\n\n2. In fact, the novel idea of learning causal directions based on independence test has been extensively studied in the previous literature. I regret that this has not been mentioned in the current manuscript. Examples include:\n\nhttp://www.jmlr.org/papers/v12/shimizu11a.html\n\nIn conclusion, since the idea of using independence relations for learning the causal directions is not a very new idea and a lot of discussion of the theoretical analysis is still missing. I regret that this work seems not strong enough to be accepted by ICLR.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SyxF49zXjS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Edit after author rebuttal and author additions:\n\nI have updated my score from a weak reject (3) to a weak accept (6).\n\nJustification:\n\n1. The authors have pointed out that I misunderstood one of their contributions: pointing out that they are demonstrating that the univariate case is an insufficient setting to test causal discovery methods because it can be done without even looking at the conditional distributions (just the marginals). This contribution seems important to orient future work. They have made this more clear in their recent upload and would likely make it even more clear in a camera-ready version.\n\n2. The authors have made their contribution to the multivariate setting more substantial by adding evaluation on the MOUS-MEG real-world dataset and have better positioned their work relative to others by adding comparisions to multivariate extensions of PNL and CGNN.\n\n====================================================================================================\n\nOriginal Review:\n\nSummary: The authors focus on the problem of inferring whether the causal structure X —> Y or Y —> X. They first consider the case where both X and Y are scalar (univariate) random variables and then consider the case where X and Y are vector-valued (multivariate) random variables. In the scalar case, motivated by the idea that the effect could be less entropic than the cause (due to data processing inequality), they introduce a method based on comparing reconstruction losses of X and Y and show competitive results in Tables 1 and 2. They establish that this method is not sufficient for the multivariate case in Lemma 2 and move to a new method for the multivariate case. They prove identifiability for this new method in for the multivariate case in Section 4.2 and claim state-of-the-art (SOTA) results in Table 3. \n\nMain contributions:\n- Presents a causal discovery technique for the univariate cases that only examines the marginal distributions of X and Y and seems fairly competitive (Tables 1 and 2)\n- Extends the post-nonlinear identifiability analysis of Zhang & Hyv¨arinen (2009) from scalars to vectors and proved that their method will actually identify the correct causal direction\n- Demonstrates competitive experimental results for both their univariate method\n- Claims SOTA results for their multivariate method\n\nDecision: I lean toward rejecting this paper because 1) I have several questions about the univariate case (see below) that would need to be resolved before I lean toward accept, 2) although I am not too familiar with the literature, I believe that this paper may be missing key related work that also uses independence testing for causal discovery (see, e.g., Heinze-Deml et al. (2017)’s Invariant Causal Prediction for Nonlinear Models), and 3) I am not yet convinced that the comparison done in Table 3 is fair and exhaustive.  \n\nSufficient reason to accept: If the theorems in Section 4.2 are found to checkout, and the SOTA results in Table 3 are found to be fair, exhaustive comparisons to the previous SOTA, their contribution to the multivariate case would seem to be sufficient for acceptance. I believe more discussion between the authors and reviewers is necessary here.\n\n Questions about univariate case:\n\n 1. The motivation for the first method (entropy decreasing along a Markov chain due the data processing inequality) seems to only be valid when Y := f(X), but not necessarily when Y := f(X) + E. For example, let f be the identity function and E be independent to X. How did you resolve this argument against the intuition? \n\n2. Also, I thought the data processing inequality relates mutual information between variables, not necessarily their entropies. Can you make this connection more clear? \n\nContext for questions 3 and 4: In Section 3.1, you write, “estimating the entropy of each random variable from its samples does not present a consistent difference between the entropies h(X)  and h(Y). Our method, therefore, computes an alternative complexity score for X and, independently, for Y.” You then go on to link the entropy to the reconstruction error (your method) in Lemma 1 and show competitive results in Tables 1 and 2.\n\n3. Why do you want to link the reconstruction error to entropy if you found a purely entropy-based method did not work?\n\n4. Why did the purely entropy-based method not work while your method worked if the two are linked?\n\nQuestions about multivariate case:\n\n5. Are you certain that BivariateFit and ANM are the only models that you should be comparing against for this multivariate setting?\n\n6. What is CGNN’s runtime? Would you be able to compare against CGNN in time for a potential camera-ready version of this paper?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Skx3i1gMqr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use the autoencoder to measure the complexity for identifying the cause and effect in the univariate case. For the multivariate case, this paper extends the PNL model and use GAN for enforcing the independence between cause and noise.\n\n- However, my main concerns are regarding the assumption of this work, seeing that the assumption h(X)>h(Y) in the univariate case is easy to violate. For example, let Y=f(X)+N (a special case of PNL) with some high entropy N, then h(Y) could higher than the h(X). \n\n- In the multivariate case, it can be seen as incremental for PNL but does not offer new insights.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The author response and revisions to the manuscript motivated two reviewers to increase their scores to weak accept. While these revisions increased the quality of the work, the overall assessment is just shy of the threshold for inclusion.
Decision: Reject