Learning Hidden Causes from Empirical Data

LEARNING HIDDEN CAUSES FROM EMPIRICAL DATA ·

Judea Pearl

Computer Science Department, Univenity of California at Los Angeles

ABSTRACT

Models of complex phenomena often consist of hypothetical entities called "hidden causes", which cannot be observed directly and yet play a major role in under­ standing, communicating, and predicting the dynamics of those phenomena. This paper examines the cognitive and computational roles of these constructs, and addresses the question of whether they can be disoovered from em­ pirical observations.

Causal models are treated as trees of binary ran­ dom variables where the leaves are accessible to direct observation, and the internal nodes--representing hidden causes--account for inter-leaf dependencies. In proba­ bilistic terms, every two leaves are conditionally indepen­ dent given the value of some internal node between them.

We show that if the mechanism which drives the visible variables is indeed tree-structured, then it is possi­ ble to uncover the topology of the tree uniquely by ~ serving pair-wise dependencies among the leaves. The entire tree structure, including the strengths of all inter­ nal relationships, can be reconstructed in time propor­ tional to nlogn, where n is the number of leaves.

I. INTRODUCTION: CAUSALITY, CONDITIONAL INDEPENDENCE AND TREES

This study is motivated by the observation that human beings, facing complex phenomena, exhibit an al­ most obsessive urge to conceptually mold these phenome­ na into structures of cause-and-effect relationships. This tendency is, in fact, so compulsive that it sometimes comes at the expense of precision and often requires the invention of hypothetical, unobservable entities such as "ego", "elementary particles", and "supreme beings" to make theories fit the mold of causal schema. When we try to explain the actions of another person, for example, we invariably invoke abstract notions of mental states, social attitudes, beliefs, goals, plans and intentions. Med­ ical knowledge, likewise, is organized into causal hierarchies of invading organisms, physical disorden, compli­ cations, pathological states, and only finally, the visible symptoms.

*This work was supported in part by the National Science Foundation, Grant #DSR 83-13875

This paper takes the position that human obses­ sion with causation is computationally motivated. Causal models are only attractive because they provide effective data-structures for representing empirical knowledge, and their effectiveness is a result of the high degree of decomposition they induce. More specifically, causes are viewed as names given to auxiliary variables which en­ code a summary of the interaction between the visible variables and, once calculated, would permit us to treat visible variables as if they were mutually independent.

The dual summarizing-decomposing role of a causal variable is analogous to that of an orchestra con­ ductor; it achieves coordinated behavior through central communication and thereby relieves the players from having to communicate directly with each other. Such coordination is characteristic of tree structures and draws its effectiveness from the local nature of the data flow to­ pology. In a management hierarchy, for example, where employees can only communicate with each other through their immediate superiors, the passage of infor­ mation is swift, economical, conflict-free, and highly parallel. These computational attributes, we postulate, give rise to the satisfying sensation called "in-depth understanding", which people experience when they dis­ cover causal models consistent with observations.

Cast in probabilistic terms, central decomposition is embodied by the relation of conditional iNkpelllkrrce, which we claim constitutes the most univenal and dis­ tinctive characteristic featured by the notion of causality. (See also (6] and [7].) In medical diagnosis, for example, a group of co-occurring symptoms often become indepen­ dent of each other once we know the disease that caused them. When some of the symptoms directly influence each other, the medical profession invents a name for that interaction (e.g., complication, pathological state, etc.) and treats it as a new auxiliary variable which again assumes the decompositional role characteristic of causal agents. Knowing the exact state of the auxiliary variable renders the interacting symptoms independent of each other. Causes invoked to explain human behavior, such as motives and intentions, also induce conditional independence. For example, once a murder suspect confesses to having wished the death of the victim, tes­ timonies proving that he expressed such wishes in public or that he stood to gain from the victim's death are per­ ceived to be irrelevant; they shed no further light on whether he actually performed the murder.

Based on these observations we chose to represent causal models as trees of binary random variables, where the leaves are directly aa:essible to empirical observa­ tions and the internal nodes represent hidden causes; any two leaves become conditionally independent once we know the value of some internal variable on the path connecting them. The propagation of updated probabili­ ties in such trees was analyzed by Pearl [6] and Kim and Pearl [3). It was shown that the propagation can be ac­ complished by a network of parallel processors working autonomously, and that the impact of new information can be imparted to all variables in time proportional to the longest path in the tree.

Given that tree-dependence captures the main feature of causation and that it provides a convenient computational medium for performing updating and predictions, we now ask whether the internal structure of the tree can be determined from observations made sole­ ly on the leaves. If it can, then the structure found would constitute an operational definition for_ the hidden causes. Additionally, if we take the view that "learning" entails the acquisition of computationally effective representa­ tions for nature's regularities, then the procedure of con­ figuring the tree may reflect an important component of human learning.

A related structuring task was treated by Chow and Liu [1], who also used tree-dependent random vari­ ables to approximate an arbitrary joint distribution. However, whereas in Chow's trees all nodes denote ob­ served variables, the internal nodes in our trees denote dummy variables, artificially concocted to make the representation tree-like. The problem of configuring probabilistic models using auxiliary variables is men­ tioned by Hinton et al. [2) as one of the tasks that a Boltzmann machine should be able to solve. However, no performance results have been reported and it is not clear whether the relaxation techniques employed by the Boltzmann machine can easily handle the restriction that the resulting structure be a tree.

This paper is organized as follows: Section 2 presents nomenclature and precise definitions for the no­ tions of star-decomposability and tree-decomposability. In section 3 we treat triplets of random variables and ask under what conditions one is justified in attributing the observed dependencies to one central cause. We show that these conditions are readily testable and, when the conditions are satisfied, that the parameters specify­ ing the relations between the visible variables and the central cause can be determined uniquely. In section 4

we extend these results to the case of a tree with 11

leaves. We show that if a joint distribution of 11 variables has a tree-dependent representation, then the uniqueness of the triplets' decomposition enables us to configure that tree from pair-wise dependencies among the variables. Moreover, the configuration procedure takes only 0(11logn) steps. In Section 5 we evaluate the merits of this method and address the difficult issues of estimation and approximations.

II. PROBLEM DEFINITION AND NOMENCLATURE

Consider a set of 11 binary-valued random vari­ ables ~1> · · · , ~n with a given probability mass function P(~1 · · · · , ~n>· We first address the problem of represent­ ing P as a marginal of an (11+l)-variable distribution Ps (~!, ... , ~n. w), that renders ~~. · · · , ~n conditionally in­ dependent given w, i.e.

The functions Ps (~1 I w), w=O, 1, i=l, ... , 11, can be viewed as 2x2 stochastic matrices relating each ~1 to the central hidden variable w (see Fig. 1a), hence we name Ps a star-distribution and call P star-decomposable. Each ma­ trix contains two independent parameters, fl and g1, where

and the central variable w is characterized by its prior probability P, (w=1) = a (see Figure 1b).

The advantages of having star-decomposable dis­ tributions are several. First, the product form of P, in (1) makes it extremely easy to compute the probability of any combination of variables. More importantly, it is also convenient for calculating the conditional probabili­ ties P(.x1 ~ 1 ), describing the impact of an observation .x1 on the probabilities of unobserved variables. The computa­ tion requires only two vector multiplications.

Unfortunately, when the number of variables exceeds 3 the conditions for star-decomposability become very stringent, and are not likely to be met in practice. Indeed, a star-decomposable distribution for ,. variables has 211+1 independent parameters, while the specification of a general distribution requires 2"-1 parameters. La­ zarfeld [ 4) considered star-decomposable distributions where the hidden variable w is permitted to range over ~ values, ~>2. Such an extension requires the solution of ~n+~-1 non-linear equations to fmd the values of the ~nH-1 independent parameters. In this paper, we pur­ sue a different approach, allowing a larger number of binary hidden variables, but insisting that they form a tree-like structure (see Figure 2), i.e., each triplet forms a star but the central variables may differ from triplet to triplet. Trees often portray meaningful conceptual hierarchies and, computationally, are almost as con­ venient as stars.

We shall say that a distribution P(.x1,x2, · · · , .x") is tree-fkcomposable if it is a marginal of a tree distribution

where wttw2, · · · , w,. correspond to the internal nodes of an unrooted tree T and x1, x2, · · · , x" to its leaves. Given a tree structure and an assignment of variables to its nodes, the form of the corresponding distribution can be written by inspection. We first choose an arbitrary node as a root. This, in tum, defmes a unique father F(y1) for each node y1 £ {.xtt · · · , .x"' Wto · · · , w"} in the tree, except the chosen root, y1· The joint distribution is simply given by the product form:

For example, if in Figure 2 we choose w2 as the root we obtain:

Throughout this discussion we shall assume that each w has at least three neighbors; otherwise it is super­ fluous. In other words, an internal node with two neigh­ bors can simply be replaced by an equivalent direct link between the two. Note that any two leaves are condition­ ally independent given the value of any internal node on the path connecting them.

If we are given Pr(x~o · · · .x", wto · · · w,.) then, clearly, we can obtain P(x~o · · · x") by summing over the w's. We now ask whether the inverse transformation is possible, i.e., given a tree-decomposable distribution P(xto · · · x")' can we recover its underlying extension Pr(x1 · · · x", w1 · · · w,.) 1 We shall show that: (1) the tree distribution Pr is unique, (2) it can be recovered from P using nlogn computations, and (3) the structure of T is uniquely determined by the second order probabili­ ties of P. The construction method depends on the analysis of star-decomposability for triplets which is presented next.

111. SI'AR-DECOMPOSABLE TRIPLETS

In order to test whether a given 3-variable distri­ bution P(.x1,x2,x3) is star-decomposable, we first solve Equation (2) and express the parameters aj,g1 as a func­ tion of the parameters specifying P (see Figure 1). This task was carried out by Lazarfeld [4) in terms of the seven joint-occurrence probabilities

and led to the following solution:

Defme the quantities

and let t be the solution of

The parameters aj1,g1 are given by:

Moreover, the differences /;-8; are independent of Puh

The conditions for star-decomposability are ob­ tained by requiring that the preceding solutions satisfy:

(a) S1 be real

(b) Osft:s1

(c) os8;s1

Using the variances

and the correlation coefficients

requirement (a) is equivalent to the condition that all three correlation coefficients are non-negative. (H two of them are negative, we can rename two variables by their complements; the newly defmed triplet will have all its pairs positively correlated.) We shall call triplets with this property positively co"elated.

This, together with requirements (b) and (c), gives (after some manipulations):

Theorem 1: A necessary and sufficient condition for three dichotomous random variables to be star­ decomposable is that they are positively correlated, and that the inequality:

is satisfied for all i£{1, 2, 3}. When this condition is satis­ fied, the parameters of the star-decomposed distribution can be determined uniquely, up to a complementation w-(1-w) of the central variable w (i.e., w -1-w, !1 +-+ 8;), a -1-a).

Obviously, in order to satisfy (17), the term (p11 - PuPUc) must be non-negative. This introduces a sim­ ple necessary condition for star-decomposability that may be used to quickly rule out many likely candidates.

Corollary -- A necessary condition for a distribution P(zh z2, z3) to be star-decomposable is that all correlation coefficients obey the triangle inequality:

(18) is satisfied with equality if w coincides with z;; i.e., when z 1 and z1 are independent given z1· Thus, an intuitive interpretation of this corollary is that the corre­ lation between any two variables must be stronger than that induced by their dependencies on the third variable; a mechanism accounting for direct dependencies must be present.

Having established the criterion for star­ decomposability we may address a related problem: Sup­ pose p is not star-decomposable, can it be approximated by a star-decomposable distribution P that has the same second-order probabilities 'l

The preceding analysis contains the a.nSwer to this question. Note that the 3rd order dependencies are represented only by the term PUh and this term is con­ fined by Eq. (17) to a region whose boundaries are determined by 2nd- order parameters. Thus, if we insist on keeping all 2nd-order dependencies of P in tact and are willing to choose Put so as to yield a star­ decomposable distribution, we can only do so if the re­ gion circumscribed by (17) is non-empty. This leads to the statement:

Theorem 2: A necessary and sufficient condition for the 2nd order dependencies among the triplet z1, z2, z3 to sup­ port a star-decomposable extension is that the six ine­ qualities:

possess a solution for z.

IV. A TREE-RECONSTRUCTION PROCEDURE

We are now ready to confront the central problem of this paper: Given a tree-decomposable distribution P(zl! . · · , z.), can we recover its underlying topology and the underlying tree-distribution

The construction method is based on the observa­ tion that any three leaves in a tree have one and only one internal node that can be considered their center, i.e., it lies on all the paths connecting the leaves to each other. H one removes the center, the three leaves become disconnected from each other. This means that if P is tree-decomposable then the joint distribution of any tri­ plet of variables z1,.r 1 ,.r1 is star-decomposable, i.e., P(z1, z 1 , zt) uniquely determines the parameters aJ;,8; as in Equations (11), (12), and (13), where a is the marginal probability of the central variable. Moreover, if we com­ pute the star decompositions of two triplets of leaves, both having the same central node w, the two distribu­ tions should have the same value for a= Pr(w=1). This provides us with a basic test for verifying whether two arbitrary triplets of leaves share a common center and a successive application of this test is sufficient for deter­ mining the structure of the entire tree.

Consider a 4-tuple z1o z2, z3, z4 of leaves in T. These leaves are interconnected through one of the four possible topologies shown in Figure 3. The topologies differ in the identity of the triplets which share a common center. For example, in the topology of Figure 3(a), the pair [(1,2,3), (1,2,4)] share a common center and so does the pair [(1,3,4), (2,3,4)]. In Figure 3(b), on the other hand, the sharing pairs are [(1,2,4), (2,4,3)] and [(1,3,4), (2,1,3)], and in Figure 3(d) all triplets share the same center. Thus, the basic test for center-sharing tri­ plets enables us to decide the topology of any 4-tuple and, eventually, to configure the entire tree.

We start with any three variables x1o x2, and x3, form their star decomposition, choose a fourth variable x4, and ask to which leg of the star should x4 be joined. We can answer this question easily by testing which pain of triplets share centers, decide on the appropriate topol­ ogy, and connect x4 accordingly. Similarly, if we already have a tree structure T, with i leaves, and wish to know where to join the (i+1) ... leaf, we can choose any triplet of leaves from T1 with central variable w, and test to which leg of w should xl+1 be joined. This, in tum, identifies a subtree T/ of T1 that should receive x1+1 and permits us to remove from further considerations the subtrees emanat­ ing from the unselected legs of w. Repeating this opera­ tion on the selected subtree T/ will eventually reduce it to a single branch, to which xl+1 is joined.

It is possible to show (8] that by choosing, in each state, a central variable that splits the available tree into subtrees of roughly equal-size, the joining branch of xl+1 can be identified in at most log · (i) tests, where k is the r-:1 maximal degree of the tree T1· This amounts to O(nlogn) tests for constructing an entire tree of n leaves.

So far we have shown that the structure of the tree T can be uncovered uniquely. Next we show that the distribution Pr, likewise, is uniquely determined from P, i.e., that we can determine all the functions P(x1 I w 1 ) and P(w1 I w~c) in (4), for i=1, · · · nand j, k=1, 2, · · · m. The functions P(x1 I w1) assigned to the peripheral branches of the tree are determined directly from the star decomposi­ tion of triplets involving adjacent leaves. In Figure 2, for example, the star decomposition of P(x1, x 2 , x 5 ) yields P(x1 I w1) and P(x2 I w1). The conditional probabilities P(w1 I w·) assigned to interior branches are determined by solving matrix equations. For example, P(x 1 1 w~ is ob­ tained from the star decomposition of (x11 x5, x1), and it is related to P(x1 I w1) via

This matrix equation has a solution for P(w1 1 w~ because P(x1 I w1) must be non-singular. It is only singular when !t=lt· i.e., when x1 is independent of w1 and therefore independent of all other variables. Hence, w~ can deter~ mine the parameters of the branches next to the peri­ phery, use those to determine more interior branches, and so on, until all the interior conditional probabilities P(w1 I w 1 ) are determined.

Next, we shall show that the tree structure can be recovered without resorting to 3rd order probabilities; correlations among pairs of leaves suffice. This feature stems from the observation that when two triplets of a 4-tuple are star-decomposable with respect to the same central variable w (e.g. 1,2,3 and 1,2,4 in Fig. 3(a)), then not only the values of a are the same but also the f and 1 parameters associated with the two common variables (e.g. 1 and 2 in Fig. 3(a)) must be the same. Whereas the value of a depends on a 3rd order probability, the difference !t-It depends only on 2nd order terms via Equation (14). Thus, requiripg that {1-11 in Fig. 3(a) obtains the same value in the star decomposition of (1,2,3) as in that of (1,2,4), leads to the equation:

and, using (6), this yields

An identical equality will be obtained for each { 1-11, i=1,2,3,4, relative to the topology of Figure 3(a). Similarly, the topology of Figure 3(b) dictates

and that of Figure 3(c):

Thus, we see that each of these three topologies is characterized by its own distinct equality, while the to­ pology of Figure 3( d) by having all three equalities hold simultaneously. This provides the necessary 2nd-order criterion for deciding the topology of any 4-tuple tested; if the equality PiJPid = PUcPJI holds for some permutation of the indices, we decide on the topology :>---< J, if it holds for two such permutations, the entire 4-tuple is star decomposable. Note that the equality PvPid = PUcPJI must hold for at least one permutation of the variables, or else the 4-tuple would not be tree-decomposable.

v. CONCLUSIONS AND OPEN QUESI'IONS

This paper provides an operational definition for entities called "hidden causes", which are not directly observable but facilitate the acquisition of effective causal models from empirical data. Hidden causes are viewed as dummy variables which, if held constant, induce pr~ babilistic independence between sets of visible variables. It is shown that if all variables are bi-valued and if the activities of the visible variables are governed by a tree­ decomposable probability distribution, then the topology of the tree can be uncovered uniquely from the observed correlations between pain of variables. Moreover, the structuring algorithm requires only nlogn steps.

The method introduced in this paper has two ma­ jor shortcomings: It requires precise knowledge of the correlation coefficients and it only works when the underlying model is tree-structured. In practice, we often have only sample estimates of the correlation coeffi­ cients, and it is therefore unlikely that criteria based on equalities (as in Eq. (21)) will ever be satisfied exactly. It is possible, of course, to relaJ: these criteria and make topological decisions on the basis of proximities rather than equalities. For example, instead of searching for an equality PuPkl = P~&PJio we can decide the 4-tuple topology on the basis of the permutation of indices that minimizes the difference PuPkl- P~&PJJ· Experiments show, however, that the structure which evolves by such a method is very sensitive to inaccuracies in the estimates Pu· because no mechanism is provided to retract erroneous decisions made in the early stages of the structuring process. Ideal­ ly, the topological membership of the (i+l) 111 leaf should be decided not merely by its relations to a single triplet of leaves chosen to represent an internal node w, but also by its relations to all previously structured triplets which share w as a center. This, of course, will substantially increase the complexity of the algorithm.

Similar difficulties plague the task of finding the best tree-structured approximatio11 to a distribution which is not tree-decomposable. Even though we argued that natural data which lend themselves to causal modeling should be representable as tree-decomposable distribu­ tions, these distributions may contain internal nodes with more than two values. The task of determining the parameten associated with such nodes is much more complicated and, in addition, rarely yields unique solu­ tions. Unique solutions, as shown in section 4, are essen­ tial for building large structures from smaller ones. We leave open the question of explaining how approximate causal modeling, an activity which humans seem to per­ form with relative ease, can be embodied in computation­ al procedures that are both sound and efficient.