A Study of Causal Discovery With Weak Links and Small Samples

1 Introduction

Our research on automating causal discovery aims at developing methods of reliably recovering the structure (and parameters) of causal models from sample data. Given such a method, several factors will affect the cor­ rectness of the discovered model, including the quality of the available data, the size of the sample obtained and the strength of the causal links to be discovered .

Having developed methods which, given large sam­ ples, discover causal models that are generally as good as or better than those discovered by TETRAD II [Wal­ lace,Korb and Dai . 1996], we report here initial results on the robustness of the two methods when u,;ing small samples and in discovering weak links. In Section :2 , we describe the sample size and weak link discovery prob­ lems. In Section 3, we give a brief analysis of the relationship between sample size, link strength and the discov­ ery of causal links . Section 4 presents the test strategies. Section 5 provides the experimental results of the causal model discovery algorithms across a range of sample sizes and with various small path coefficients. In particular we compare the results of the MML induction system MML­ CI (the MML Causal Inducer) [Wallace,Korb and Dai, 1996) with that of TETRAD II [Glymour et al, 1987; Scheines, 1994; Spirtes et al, 1993) .

2 Robustness of Causal Discovery

Let V = {Vi 1 ::; i ::; n} (corresponding to ran­ dom variables) be a set of nodes and E C V x V be a set of links , a causal model M is a directed acyclic graph (DAG) < V, E > together with numerical param­ eters reporting the strength of the connections, where < Xi,Xj >E E means that Xi is a direct cause of Xj rela­ tive to V. Such directed acyclic graphs that are used to represent causal theories are variously called causal mod­ els, causal graphs, causal networks and belief networks [Cooper and Herskovits, 1991) and [Russel and Norvig, 1995). A causal network gives a concise specification of the joint probability distribution [Pearl, 1988). Each node in the causal network has a conditional probabil­ ity table that quantifies the effects that the parents have on the node; linear causal networks (e.g., [Wright, 1934)) provide the same information under the assumption that each effect variable is a linear function of its parents, al­ lowing the numerical parameters to be attached to causal links independently.

Recently, causal models (especially in the form of Bayesian nets) have been widely employed for the rep­ resentation of the knowledge with uncertainty, including use in expert systems [Shafer, 1 996). In consequence, interest has grown in the learning of causal models as well. Various learning strategies have been developed. These methods include Spirtes et a!. 's TETJtAD I and II based upon significance tests for partial correlations, Pearl and Verma's approach [Pearl, 1988) and [Pearl and Verma, 1991) using conditional independencies, Heckerman 's Bayesian approach [Beckerman, 1995] and [Beck­ erman et al, 1995]. In 1995, Madigan and York intro­ duced Markov Chain Monte Carlo Model Composition (MC 3 ) [Mdigan et al, 1995] for approximate Bayesian model averaging (BMA) and recently further developed the G'ibbs MC 3 and the Augmented MC 3 algorithms [Mdigan et al, 1995] for the selection of Bayesian mod­ els. More recently Wallace et al developed the MML-CI [Wallace,Korb and Dai, 1996] based on MML induction, a Bayesian minimum encoding technique and Suzuki pro­ posed a MDL (Minimum Description Length) principle based Bayesian Network learning algorithm using the branch and bound technique [Suzuki , 1996] .

Here we examine the particular problem of the ro­ bustness of the two causal discovery algorithms which have been developed for inducing linear causal models, namely MML-CI and TETRAD II. In particular, we compare the models these algorithms produce when pre­ sented with varying sample sizes and samples generated from original causal structures with varying strengths of causal relationship. The robustness of the discov­ ery technique in dealing with small samples is an im­ portant issue for machine learning, since autonomous, resource-constrained agents must be prepared to learn interactively with environments that will not tolerate un­ bounded sampling. We need to estimate the reliability of a derived model. Also, although we do not here report on large causal models, we would expect that problems with robustness with small samples for small models will man­ ifest themselves also with large samples for large models , suggesting difficulty in scaling up a learning algorithm to cope with realistic examples of causal discovery. Here, the large model refers to the model with large number of links .

3 The Influence of Sample Size and Link Strength

For any learning technique which converges ·on the un­ derlying probability distribution in a prediction task, the predictive accuracy will be sensitive to sample size, model complexity and the strength of the correlation be­ tween measured variables. In general, predictive accu­ racy of a recovered model will be a function of sample size, quality of the data and the abi lity of the learner [Dai, 1994]. In the discovery of causal models verisimil­ itude of the model discovered relative to the original model (and the probability distribution implied) will also be affected by sample size, model complexity and the strength of causal association between measured vari­ ables. For practical purposes , starting from similar prior domain information, better learning ability will reveal itself in faster convergence upon the underlying model, or, to put it theother way around , in the robustness of discovery given smaller sample sizes. Here we examine such robustness in MML-CI and TETRAD II .

The probability of discovering from sample data the existence of a particular causal link depends, in part, upon the strength of that causal link . In the case of a single causal path between two nodes being a single, direct causal link (in standardized models) the path co­ efficient is identical to the correlation between the two nodes, making the relation between sample size and de­ tectability of the link plain. TETRAD II is sensitive to the strength of the causal relation quite directly: it determines whether a link is present or not by apply­ ing significance tests potentially to all orders of partial correlation, removing the effects of all subsets of V ex­ cluding the nodes under consideration. In consequence, ordinary concerns about the robustness of significance testing apply to TETRAD II - and for each link these concerns will apply not to a single significance test, but to a battery of significance tests 1 Things are worse than ordinary for TETRAD II , however: because a high-order partial correlation estimate depends upon estimates of the marginal correlations for each pair of variables in­ volved, the uncertainties associated with each estimate will accumulate, which results in high standard errors (variance) for high-order partial correlation estimates and in the need for very large samples to get significant results. The reliance on significance tests for high-order partial correlations suggests that TETRAD II will be unlikely recover the structure of a larger model without quite large samples available. In other words, the larger the order of such a significance test, the greater the sam­ ple size must be for an effect of constant strength to be detected. As a result, as the authors admit [Scheines, 1994], TETRAD II has a tendency to omit arcs for larger models even with fairly large sample sizes.

MML-CI does not depend upon a test as rigid as sig­ nificance tests at a fixed level: it reports an arc whenever the presence of such an arc leads to a reduction in the message length for a joint encoding of the causal model and the sample data [Wallace,Korb and Dai, 1996]. That is , given a sample with m instances over n variables, the message length is calculated according to the following formulas:

This involves a trade-off between greater simplicity of the model (and commensurately higher prior probability) and greater accuracy in accommodating the given sample data (and so a higher likelihood for the model) via Shannon's definition of information.

In detail, the MML encoding of causal models and data is given in the following equations (see [Wal­ lace,Korb and Dai , 1996] for a detailed explanation) . We start by dividing the code for the model into two parts. corresponding to the causal structure and the numerical parameters:

1 This is true even though TETRAD I I takes steps to re­ duce the number of significance tests required per pair of nodes, in its "PC algorithm" [Scheines, 1994].

We use

which provides an efficient encoding for a directed acyclic graph, when M is a count of the linear extensions of the dag.

where: n; is the number of arcs incident on the vari­ able x;; a; is a hyper-parameter reflecting the expected strength of the causal links to node i (set to 1 in all ex­ periments reported here); 0'; is the variance; a;j are the parameters; and A = ( x; · x j) is the n x n data matrix. To encode the data requires a message of size:

where r; · is deviation of the data from the linear pre­ diction. J

In MML-CI's discovery the relation between sam­ ple size and. the strength of causal links remains, of course; but the possibility of MML-CI finding weaker links sooner seems intuitively more likely, because such links will be reported as soon as the improv·ement they afford in encoding the data overcomes the increased cost of reporting a somewhat more complex model.

4 Testing Strategy

To examine the influence of sample size on the discov­ ery of causal models experimentally we chose six mod­ els varying in complexity: models 1 through 6 in Fig­ ure 1. We used these models to generate sets of sample data of various sizes stochastically, which in turn were given as input to MML-CI and TETRAD II to deter­ mine what causal models would be discovered. In the case of TETRAD II default values were employed exclu­ sively; no prior information about the temporal order of variables was provided to either algorithm.

The first model is simplest, having only one link and two variables. In this case, the path coefficient is ex­ actly equal to the correlation between the two variables. This makes the existence of the causal link extremely easy to find (although not its direction). Model six is the most complex model, having five variables and seven arcs. Three of the models contain weak links with coef­ ficients Jess than 0.1, namely models 3, 5 and 6. These six artificial models were manually designed for the fol­ lowing testing purposes: (1) The learning difficulties as­ sociated with model complexity in terms of the number of variables; (2) The learning difficulties associated with model complexity in terms of the number of arcs; (3) The learning difficulties associated with the strength of the links. In each case we generated data sets with 10, 50, 100, 200 , 500 , 1000, 2000 and 5000 instances. Then we ran both MML-CI and TETRAD II using all eight data sets for each of the six models.

In a second experiment we looked at the effect of link strength on the recovered model. In this case we used model6 (above) with the strength of the causal arc b-+ c varied between 0.08 and 0.16, in each case generating the same range of sample sizes as above .

5 Experimental Results and Analysis

Sample Size and Model Complexity In our experiments, we focus on linear models with Gaussian error and as­ sume no hidden variables. We use TETRAD II default settings with a significant level of 0.05. The PC al­ gorithm is the one applied on fully measured models with continuous variables. Figure 2 reports the models discovered by MML-CI from the 48 data sets, while Figure 3 reports those discovered by TETRAD II . The shading indicates for each model at what point the al­ gorithm discovered the original model or a model statis­ tically equivalent to the original. Statistically equivalent causaL models are those which can be used to specify the same class of probability distributions over the variables (perhaps using distinct parameterizations). [Verma and Pearl , 1990] report a simple graphical criterion of equiv­ alence which can be used to identify the statistically equivalent models in our figures : two causal models are statistically equivalent if and only if they have the same skeleton (undirected graph) and they have the same v­ structures (nodes that are the children of two parents which are themselves non-adjacent). Such models can­ not be distinguished on the basis of sample data alone [Chickering, 1995], so the discovery of one is as good as the discovery of another in this experiment .

1\ v~ ' r'swlnplc Si For TETRAD II , in Figure 3, undirected arcs reflect the fact that TETRAD was unable to determine an arc orientation; for these arcs , either orientation is allowed by TETRAD, so long as the resulting graph is acyclic and so long as no new v-structures are introduced by selecting such an orientation. We counted the resulting TETRAD graph as satisfactory (and so appears shaded) if no such selection of arc orientations results in a causal model that is not statistically equivalent to the original model.

Figure 4: Comparison of Edges Omitted

_\ v ' S11mpi1'Siz

Figure 5: Comparison of Arrows Omitted

Although in this study we have not performed sig­ nificance tests on the results (i.e., by generating large numbers of samples of each model for each sample size), the trend is fairly clear. For all of the models showing any complexity (i.e., for model 3 and above) MML-CI has found the correct model at smaller sample sizes than has TETRAD II. In the case of model 6 TETRAD II was unable to recover the weakest link even when supplied 5000 samples, while for model 3 TETRAD II found all the links but failed to discover the v-structure at node d.

Figures 4 and 5 compare MML-CI with TETRAD II in the manner used by Spirtes, et a!. [Scheines, 1994] . Figure 4 graphs the percentage of edges of the original model which MML-CI and TETRAD II have failed to recover, by sample size. Figure 5 graphs the percent­ age of arc orientations missed by each program (but not counting cases where a graph with an incorrect arc ori­ entation is statistically equivalent to the original model). Of course, both algorithms display the expected conver­ gence towards zero errors - expected because TETRAD II is , in effect , a classical estimation technique whereas MML-CI is, in effect, a Bayesian estimation technique, and so both fall under the general convergence results established for the respective classes of statistical infer­ ence procedures. It remains of interest, however , that in all of these measures MML-CI tends to display a more rapid convergence towards the true model - which is to say it appears to be more robust when dealing with smaller sample sizes.

Sample Size and Weak Link Discovery Figure 6 illus­ trates the experimental results for MML-CI on model 6 when the causal link from b Lo c Lakes varying degrees of strength, in particular coefficients ranging from 0.08 to 0.16. Unsurprisingly, the results clearly reveal the fact that the weaker the association the larger the sample required to discover it. With the weakest coefficient of 0.08 in Figure 6, MML-CI does not discover the link un­ til provided with 2000 samples. Whereas with a weakest link of 0.10 and 0.14, the system discovered the link once provided with a data set with the sample size of 500 and 100 respectively.

Figure 7 illustrates like experimental results for TETRAD II. These results again show the inverse rela­ tionship between strength of causal relationship and the sample size required to discover it. Given coefficients above our original 0.8 TETRAD II was able to discover the link between b and c that it had missed before. It remains clear in all of the test cases that MML-CI re­ covers the original causal model with fewer samples than TETRAD II. Figure 8 and Figure 9 report similar stories for the measures of arc omission and arrow omission.

6 Conclusions

The following conclusions appear to be supported by our experimental results. (1) The theoretical difficulties of significance testing with robustness appear to be mani­ fested in TETRAD II 's inferior robustness with respect to sample size. This shows up, for example, in TETRAD Il 's inability to recover the weaker links (with coefficients below 0.1) with smaller samples. (2) The problem of arc omission given small samples is particularly acute for TETRAD II (in comparison with MML-CI) as model complexity increases, as predicted by our analysis in §3 . From the experimental results we also find that MML-CI shows promise not just in finding causal models that are as good as those discovered by TETRAD II in general, but given the constraints imposed by small samples or by weak causal links the models discovered appear to be characteristically superior to those discovered using the significance testing methods of TETRAD. This is likely to be an especially important feature of causal discov­ ery when causal models become large, for TETRAD's method of examining partial correlations of all orders in such cases is both computationally expensive and lacking robustness .

Acknowledgement

This work was conducted with partial assistance from ARC grant A49330662.