We study one of the simplest causal prediction algorithms that uses only conditional independences estimated from purely observational data. A specific pattern of four conditional independence relations amongst a quadruple of random variables already implies that one of these variables causes another one without any confounding. As a consequence, it is possible to predict what would happen under an intervention on that variable without actually performing the intervention. Although the method is asymptotically consistent and works well in settings with only few (latent) variables, we find that its prediction accuracy can be worse than simple (inconsistent) baselines when many (latent) variables are present. Our findings illustrate that violations of strong faithfulness become increasingly likely in the presence of many latent variables, and this can significantly deterioriate the accuracy of constraint-based causal prediction algorithms that assume faithfulness.
One of the central tasks in causal inference is to predict the
changes resulting from interventions [
However, the causal structure of the system is often not
known. Estimating the full causal structure from data is
typically not possible without making strong assumptions.
However, it is possible under weaker assumptions to
estimate the Markov equivalence class from purely
observational data, i.e., the set of all causal structures that are
compatible with the observed conditional independences in
the data. This can be done for instance using
constraintbased causal discovery algorithms, like the
A brute-force approach to causal prediction would then
consist of enumerating all possible causal graphs in the
estimated Markov equivalence class, and estimating the causal
effects for each of these graphs, thereby yielding a set of
causal effects that are compatible with the data. Smarter
a
In this work, we investigate a simple alternative method for predicting causal effects that is sound and consistent (also in the presence of confounders). The method effectively avoids estimating the (equivalence class of the) complete causal structure of all observed variables and focusses on small subsets of four variables instead. In this way, it minimizes the number of conditional independence tests necessary to reach a nontrivial causal prediction, thereby hopefully improving the accuracy of that particular prediction, as there is less possibility for statistical errors to accumulate. The main motivations behind our approach are (i) we would like to trade completeness for reliability, and (ii) focussing on a simple algorithm makes it easier to analyse its statistical properties.
We first sketch a general approach to causal reasoning, and
then focus on a simple special case with four variables
that leads to nontrivial conclusions. That special case is
closely related to an existing method to detect so-called
Ystructures [Man
Given a set of random variables1 V , we can express their direct causal relationships by means of a causal graph, which has a directed edge X ! Y if and only if X 2 V is a direct cause of Y 2 V . A directed path (sequence of head-to-tail directed edges) corresponds to an indirect causal relationship, or ancestral relation. We denote the set of all indirect causes (ancestors) of a variable X 2 V according to causal graph G by AnG (X) (we adopt here the convention that this includes X itself). For a set of variables X V , we define AnG (X) = SX2X AnG (X). Therefore, X 2 AnG (Y ) means that X is an (indirect) cause of some Y 2 Y according to the causal graph G, and X 62 AnG (Y ) means that X is not an (indirect) cause of any Y 2 Y according to the causal graph G. In addition to directed edges, the causal graph G may contain bidirected edges to denote confounders, i.e., latent common causes. From now on, we assume that there is a causally sufficient set of variables V = O [_L, of which we observe only the variables in O, the variables in L being latent, and that the causal graph on O [L is a directed acyclic graph (DAG). In particular, this means that we assume that there is no causal feedback and that there are no confounders of the variables O [ L. Note that when considering only the observed variables O, the latent variables in L may act as confounders for variables in O, so we do not assume that the variables in O are causally sufficient on their own. Furthermore, we assume that there is no selection bias, i.e., we are not implicitly conditioning on (common effects of) the variables in O [ L. Finally, an important assumption is faithfulness, i.e., each conditional independence X ?? Y j Z in the joint distribution of the random variables O [ L corresponds to a d-separation X ??G Y j Z in the DAG G. In other words, conditional independences in the distribution reflect properties of the causal structure rather than accidental cancellations due to very specific choices of the parameters of the causal model.
The approach we study here is a straightforward
combination of two ingredients: causal discovery rules by Claassen
and Heskes [2011] and a causal predi
Claassen and Heskes [2011] pointed out a correspondence between what they call minimal conditional (in)dependences and ancestral relations. We adopt the same notation for these minimal conditional (in)dependences here. Claassen and Heskes [2011] define a minimal con
ditional independence by: The square brackets express that the variables in Z are necessary to obtain the (in)dependence, in the context of W . The minimal conditional (in)dependences relate directly to ancestral relations in the DAG G, as shown by Claassen and Heskes [2011]. In particular, they give the following inference rules: Lemma 1 For disjoint sets fXg; fY g; fZg; W O: 1. X ?? Y j W [ [Z] =)
Z 2 AnG (fX; Y g [ W ) 2. X ?6? Y j W [ [Z] =)
Z 62 AnG (fX; Y g [ W ).
In addition, the following obvious rules for ancestral relations in a DAG G hold: Lemma 2 For X; Y; Z 2 O: 1. X 2 AnG (Y ) ^ Y 2 AnG (Z) =) X 2 AnG (Z); 2. X 2 AnG (Y ) ^ Y 2 AnG (X) =) X = Y .
These rules express the transitivity and acyclicity of indirect causal relations. 2.2
Under the same assumptions that we made above, Entner et al. [2013] show that: Lemma 3 For disjoint sets fXg; fY g; fZg; W : if 8Y 62 AnG (fXg [ W [ fZg) > <
X 62 AnG (W [ fZg) >:Z ?? Y j W [ [X] then W is sufficient for adjustment of X on Y , i.e.,
Z p(Y j do(X = x)) =
p(Y jX = x; W )p(W ) dW :
Here, p(Y j do(X = x)) denotes the interventional
distribution of Y under a perfect intervention on X that sets X to
the value x [
The causal discovery rules by Claassen and Heskes [2011]
allow to derive ancestral relations from conditional
independence relations, and the causal predi
In our context, one of the simplest combinations of conditional independences that yields nontrivial causal predictions on four variables is the following: Proposition 1 For a quadruple hX; Y; Z; U i 2 O4 of different observed variables, if (
Z ?? Y j [X] Z ?6? U j [X] (1) then X 2 AnG (Y ) and p(Y j do(X)) = p(Y j X). Proof. From Z ?6? U j [X] and Lemma 1.2 it follows that X 2= AnG (fZ; U g), and therefore X 2= AnG (Z). From Z ?? Y j [X] and Lemma 1.1 it follows that X 2 AnG (fZ; Y g). Combining these two results, we conclude that X 2 AnG (Y ). By acyclicity, this implies Y 2= AnG (X). Further, Y 2 AnG (Z) would lead to X 2 AnG (Z) by transitivity, which contradicts X 2= AnG (Z). Applying Lemma 3 with W = ; immediately gives that p(Y j do(X)) = p(Y j X).
In this simple context where W = ;, the causal predi
Y “Extended Y-structure” X
Y “Y-structure” two cases: U and Y are nonadjacent (“Y-structure”) and U and Y are adjacent (“Extended Y-structure”). In both cases, three arrowheads follow from the ancestral relations Y 2= AnG (X), X 2= AnG (U ), X 2= AnG (Z), and one tail follows from X 2 AnG (Y ), Note that if there is an edge between U and Y , then U must be a collider. Indeed, the path Z X U Y must be blocked when conditioning on X. But then the edge between U and Y must have an arrowhead at Y , otherwise X would be ancestor of U . It is easy to check that each of the six MAGs corresponding with the two PAGs is compatible with the constraints (1). We can obtain symmetry between U and Z by adding another minimal conditional independence test (only satisfied by the Y-structures): 8 > < > :
Z ?? Y j [X] U ?? Y j [X] Z ?6? U j [X] (2) As we assume faithfulness, all other conditional independence relations on fX; Y; Z; U g can now be read off from the PAGs.
Corollary 1 Under faithfulness, the only conditional independences that hold in an Extended Y-structure are the two in (1), i.e., Z ?? Y j X and Z ?? U . The only conditional independences that hold in a Y-structure are the three in (2), i.e., Z ?? Y j X, Z ?? U and U ?? Y j X, and in addition U ?? Y j fX; Zg and Y ?? Z j fU; Xg.
Y-structures have been stud
O
set of observed variables D i.i.d. sample of p(O)
L set of Extended Y-structures;
L ; for all hX; Y; Z; U i 2 O4 do if #fX; Y; Z; U g = 4 then if Z ?6?D Y and Z ??D Y j X and Z ??D U and Z ?6?D U j X then
L L [ fhX; Y; Z; U ig end if end if end for
8hX; Y; Z; U i 2 L : p(Y j do(X)) = p(Y j X) 2.4
One of the simplest algorithms that makes nontrivial causal predictions from purely observational data using the ideas above is given in Algorithm 1. It is a brute-force search over all quadruples in O that satisfy the Extended Ystructure conditional independences in (1). Any conditional independence test can be used when testing for conditional independences of the form X ??D Y j Z in the data D. For each of the quadruples hX; Y; Z; U i output by the algorithm, the causal prediction is that p(Y j do(X = x)) = p(Y j X = x) for all x. In words: the interventional distribution of Y when setting X to the value x coincides with the conditional distribution of Y given X = x. It follows directly from Proposition 1 that Algorithm 1 is sound. When using consistent conditional independence tests, it is also consistent: as the number of samples in D grows, the probability for an erroneous conclusion converges to 0. This directly follows from the consistency of the independence tests. However, the algorithm is not uniformly consistent. In practice, we do not know a priori how many samples we need to be confident about the correctness of the result [Robins et al., 2003]. Intuitively, as a dependence can be arbitrarily weak, we may need an arbitrarily high number of data points to be able to distinguish it from an independence. Furthermore, Cornia and Mooij [2014] showed that for LCD in a linear-Gaussian setting, it is impossible to derive a confidence interval on the causal prediction error without making strong assumptions. Their result also applies to Algorithm 1, as it makes a similar causal prediction as LCD does. Summarizing: Proposition 3 Algorithm 1 is sound and consistent when using consistent independence tests. However, it is not uniformly consistent and it is impossible to derive a confidence interval on the prediction error without making additional assumptions in the linear-Gaussian setting.
We have spelled out Algorithm 1 for clarity, even though it is a special case of the more general Algorithm 2 that performs a brute-force search for certain conditional independence patterns by testing whether all relations in the pattern simultaneously hold in the data. For example, using the following pattern for testing an Extended Y-structure in Algorithm 2 we recover Algorithm 1:
extY(hX; Y; Z; U i) = Z ?? Y j [X] ^ Z ?6? U j [X]: In the next section, we will study also the following patterns on quadruples of variables:
Y(hX; Y; Z; U i) = extY(hX; Y; Z; U i) ^ U ?? Y j [X]: Y1(hX; Y; Z; U i) = Y(hX; Y; Z; U i) Y2(hX; Y; Z; U i) = Y1(hX; Y; Z; U i) ^ Z ?6? X ^ X ?6? Y ^ X ?6? U ^ Y ?6? U ^ X ?6? U j Y ^ X ?6? Z j Y ^ U ?6? Z j Y ^ X ?6? Y j U ^ X ?6? Z j U ^ Y ?6? Z j U ^ X ?6? Y j Z ^ X ?6? U j Z ^ U ?6? Y j Z: ^ U ?6? Z j fX; Y g ^ U ?6? X j fZ; Y g ^ Z ?6? X j fU; Y g ^ X ?6? Y j fU; Zg ^ U ?? Y j fX; Zg ^ Z ?? Y j fX; U g: The patterns Y, Y1 and Y2 all test for a Y-structure. Y uses the minimal number of tests, Y1 also tests for all (asymptotically redundant) tests up to conditioning set size 1, and Y2 adds all (asymptotically redundant) tests up to conditioning set size 2. 3
For the simulations, we created random causal DAGs G with p = jV j variables.2 For i = 1; : : : ; p, we chose the parents pa(i) f1; : : : ; i 1g for variable Xi randomly (using 0,1,2,3 parents with probability 1=8; 1=2; 1=4; 1=8, respectively). In this way, the random graph is guaranteed to be a DAG. After generating the random causal graph, we drew random weights B~ji N (0; 1) independently from a standard normal distribution for constructing linear structural equations
Xi =
X j2pa(i)
B~jiXj + ~i with i.i.d. error terms ~i N (0; 2) having a normal distribution with standard deviation = 0:1. After sampling all weights in this way, we applied rescaling transformations to all structural equations (of the form (B~ji; ~i) 7! (Bji; i) = ( iB~ji; i~i)) sequentially for i = 1; : : : ; p such that Var(Xi) = 1 for all i = 1; : : : ; p. Without the rescaling, variances could easily diverge and Var(Xi) could depend strongly on i, thereby already revealing the causal order.
We sampled N = 3000 samples from p(X) to simulate the observational data D. We also simulated perfect interventions on different targets as follows. For each intervention, we chose its target i uniformly from f1; : : : ; pg. Under the intervention do(Xi = i), the structural equation for Xi is changed into Xi = i, while the other structural equations and the distribution of the noise terms remain invariant under this intervention. We used a constant value i = 2 throughout. We then generated one sample from the intervened structural causal model. In this way, we generated 1000 interventional data points, each one corresponding to an intervention on a particular randomly chosen target variable. We used this interventional data to validate the causal predictions.
We considered four settings for the number of variables, p = 10, p = 30, p = 50 and p = 70.
Because we simulated linear-Gaussian data, for the (conditional) independence tests we simply calculate the (partial) correlations and their p-values by using a Student’s t distribution for a transformation of the (partial) correlation. Small p-values indicate strong evidence against the null hypothesis of independence. On the other hand, for large pvalues it is not clear whether there is a weak dependence or an independence. Nevertheless, following common practice in the field, we will use large p-values as evidence in We performed simulation experiments to study the performance of Algorithms 1 and 2.
2In our simulations, we used V = O, i.e., all variables are observed. favor of independence. We use two thresholds on the pvalue p to distinguish three possible independence test results: lo p < lo =) dependence; p p > hi =) unknown; hi =) independence: We used fixed values lo = 10 4 and hi = 10 1 throughout the experiments. When testing for combinations (conjunctions) of (in)dependences, we use a three-valued (false, unknown, true) logic when combining conditional independence test results with logical operators. 3.3
We studied the performance of Algorithm (1) and Algorithm (2) with patterns Y, Y1 and Y2 on simulated data. In addition, we studied the performance of some of their building blocks: pairwise (in)dependence tests, conditional (in)dependence tests when conditioning on a single variable, and minimal conditional (in)dependence tests when conditioning on a single variable. The ground truth is provided by testing the patterns directly in the causal graph by using the Bayes Ball algorithm [Shachter, 1998] as an independence oracle.
T P T P precision = ; recall =
T P + F P T P + F N + P U where T P are true positives, F P are false positives, F N are false negatives and P U are unknowns that are positives according to ground truth. Here, we are more interested in high precision than high recall, because being able to predict with high confidence a few strong causal effects would already be of great practical interest in applications. The results are reported in Table 1 for p = 10 and p = 50 variables. First, note that the recall of the conditional and pairwise independence test is at 1 hi as it should be. Also, note that the precision of the conditional and pairwise dependence tests are very close to 1, reflecting that it is easy to recognize a strong (conditional) dependence as such. The elementary tests are not perfect, but precision and recall are within a reasonable range. However, when combining two elementary tests into a minimal test, precision may drop significantly. When combining two minimal tests into an extended Y-structure test, the precision drops even further. On the other hand, when adding another minimal conditional independence test to test for a Y-structure, precision increases. Adding more tests (patterns Y1 and Y2) does not make much of a difference. To put everything into perspective, the precisions should be compared with the baseline of random guessing (indicated in angular brackets). The pattern search algorithm outperforms random guessing considerably, achieving precisions that are a few orders of magnitude higher. 0.8 We conclude that for the task of detecting (Extended) Ystructures, the pattern search algorithm performs much better than random guessing. Furthermore, we observed that errors of elementary tests combine in unexpected ways into errors of compound tests. Sometimes the probability of an error of a compound test is much higher than the probability of error of its constituent tests, in other cases errors seem to cancel out and combining multiple tests results in “error correction”. The reasons for this behavior of the precision are unclear. Recall has a more consistent behavior: the more tests are combined, the lower the recall. The evaluation measure used in the previous subsection is rather strict: the precision reflects how accurately a specific pattern can be detected from observational data. When we are only interested in using the (Extended) Y-structure patterns as a causal discovery method, i.e., as a way to detect whether X 2 AnG (Y ) (X is an indirect cause of Y ), the picture changes considerably. For this task, we define the “positives” to be the hX; Y i pairs that are contained in a quadruple hX; Y; Z; U i that satisfies the pattern of interest. The results are reported in Table 2 for p = 10 and p = 50. In both cases, the pattern search algorithms still outperform the baseline of random guessing, but not as much as for the task considered in the previous subsection. Precision again decreases as the number of variables increases. Figure 2 illustrates how the precisions depend on p, the number of (latent) variables.
We conclude that according to this performance measure, the simple causal discovery algorithm that searches for (Extended) Y-structures can outperform random guessing when used to find (indirect) causal relations. Detecting Y-structures works significantly better than detecting Extended Y-structures in this setting. However, precision decreases as the number of (latent) variables increases. The evaluation measure used in the previous subsection is a natural one when simulating data, but when using real data, it is often not known whether a variable is an indirect cause of another. Instead, interventional data may be available. In that context, we may be more interested in how accurately we predict the effects of interventions. When detecting an (Extended) Y-structure pattern for a quadruple hX; Y; Z; U i, we can conclude that p(Y j do(X = x)) = p(Y j X = x). Using linear regression of Y on X we estimate E(Y j X = x) and use this as our prediction for the value of Y under the intervention X = x. In our setting, a natural measure for the causal prediction error of Y under an intervention do(X = x) is jE(Y j X = x)
E(Y j do(X = x))j : We report the average error (`1 error) over all (X; Y ) pairs in patterns found by the algorithm, all simulated interventions and all models. In addition, we report the corresponding root-mean-square error (`2 error).
For comparison, we also report results of two simple baselines. The first baseline predicts p(Y j do(X = x)) = p(Y ) for all pairs X 6= Y (i.e., complete absence of causal effects). The second baseline predicts p(Y j do(X = x)) = p(Y j X = x) for all pairs X 6= Y (i.e., no difference between correlation and causation). Note that these baselines are provably inconsistent.
The results for these evaluation measures are reported in Table 3, for p = 10 and p = 50. Figure 3 shows how the `1 error depends on p, the number of (latent) variables. For p = 10 variables, most methods outperform the simple baselines. Unfortunately, that does not hold for p = 50 variables: in that case the simple baseline that always predicts that nothing will change due to an intervention outperforms all causal prediction methods. The reason is that even though the pattern search algorithm obtains a low error on the true positives (as expected), this is compensated by an error that is considerably higher than average on the false positives. 4
We have studied a simple causal discovery and prediction method that focusses on quadruples of variables and only makes a prediction when it detects a certain pattern of conditional independences amongst those variables. The method is sound and consistent, and works well if the number of variables is not too large. However, like most constraint-based methods that rely only on conditional independences and the faithfulness assumption, it is not uniformly consistent [Robins et al., 2003]. Our empirical observations show that the accuracy of causal predictions deteriorates as more (latent) variables are present. This man1.5 r o r 1 r e 1 l 0 0 20 40
60 p 80 100 ifests itself quite clearly already in rather low-dimensional settings (50 variables, 3000 observations), where the simple causal prediction method does not even outperform na¨ıve (inconsistent) baselines in terms of prediction error in our simulations.
Even though in our simulations the distribution on all
variables V = O [ L is faithful to the DAG, when only
looking at a small subset of variables Q = fX; Y; Z; U g, the
marginal distribution on Q can become close-to-unfaithful
to its PAG on Q. One explanation for this might be that the
more (latent) paths between the variables in Q there are,
the higher the probability that these paths will cancel each
other in some way when the edge weights are chosen
randomly. This may then lead to near-faithfulness violations
on Q, and hence to to false-positive detections of the
(Extended) Y-structure algorithms. However, the problem is
not necessarily related to cancellation of paths, as we
observe qualitatively similar behavior when we restrict all the
edge weights to be positive (not reported here).
Note that the observed bad prediction performance occurs
even though individual tests have relatively low probability
of making an error in our simulation setting, and we only
combine a few of these individual tests. In other words,
there are strong dependences between test results that
cannot be ignored. Adding more tests and thereby restricting
the pattern to Y-structures helped to improve performance.
On the other hand, adding more “redundant” tests did not
significantly change accuracy. Thus, the original idea that
minimizing the number of conditional independence tests
would maximize accuracy turns out to be overly simplistic.
Problems with the faithfulness assumption have been
pointed out before. Robins et al. [2003] showed that it is
possible to create a sequence of faithful distributions that
comes arbitrarily close to an unfaithful distribution. One
possible way out would be to make a stronger assumption,
like strong faithfulness [Zhang and Spirtes, 2003] for the
linear-Gaussian case, requiring that nonzero partial
correlations are bounded away from zero, and in that way obtain
uniform consisten
We conclude that faithfulness violations can be very problematic for causal inference, even when individual independence tests have a low probability of error and we only combine a few of them to draw causal conclusions. The severity of this effect surprised us: one would probably need enormous amounts of observations for strong faithfulness to hold. Indeed, already for p = 50 variables, N = 3000 observations is not enough to outperform inconsistent noncausal baselines. In addition, we observed that prediction accuracy deteriorates as p becomes larger. A related pattern search amongst quadruples of variables was proposed recently by Tsamardinos et al. [2012]. They search for a pattern amongst quadruples of variables that allows one to conclude that two of the four variables are dependent. To make this more interesting, they consider the situation that one has two datasets, each containing observations regarding only 3 out of 4 variables, and the two variables that are predicted to be dependent have not been simultaneously observed within a single dataset. Interestingly, that particular pattern search performs very well, also on high-dimensional real-world data, as reported by Tsamardinos et al. [2012]. This raises the question why certain patterns apparently lead to reliable predictions, whereas for other (superficially similar) patterns, the predictions turn out to be unreliable in high dimensions because of faithfulness violations. We leave this question for future research.
JM was supported by NWO (VIDI grant 639.072.410). We thank Oliver Stegle, Barbara Rakitsch, Tom Claassen and Ioannis Tsamardinos for helpful discussions. We thank Philip Versteeg for proofreading the manuscript.