Parameter Identification in a Class of Linear Structural Equation Models

1 Introduction

Linear causal models known as structural equation models (SEMs) are widely used for causal reasoning in the social sciences, economics, and artificial intelligence (AI) [Bollen, 1989; Pearl, 2000; Spirtes et al., 2001]. In a SEM, the causal relationships among a set of variables are assumed to be linear and expressed by linear equations. As an example, consider the following model from [Pearl, 2000] that concerns with the relations between smoking (X) and lung cancer (Y ), mediated by the amount of tar (Z) deposited in a person's lungs:

The model makes the causal assumptions that the amount of tar Z deposited in the lungs depends on the level of smoking X (and external factors omitted from the model represented by ϵi assumed to have normal distribution) and that the production of lung cancer Y depends on the amount of tar in the lungs but smoking has no effect on lung cancer except as mediated through tar deposits. The external factors that have influence on smoking and cancer may be correlated (covariances Cov(ϵ1, ϵ3) ̸= 0). The parameters a and b quantify the strength of linear cause-effect relationships.

SEMs are typically used for confirmatory data analysis in the social sciences and economics, consisting of four steps [Kenny et al., 1998]: (1) hypothesizing a model, (2) identification analysis - to decide if there is a unique valuation for the parameters that make the model compatible with the observed data, (3) parameter estimation, and (4) evaluation of fit - to see how well the proposed model fits the data. In this paper, we will focus on the identification problem.

The identification problem has been under extensive study by econometricians and social scientists [Fisher, 1966; Bowden and Turkington, 1984; Bekker et al., 1994; Rigdon, 1995]. In recent years the problem has been addressed using the graphical models techniques in the AI community [Pearl, 1998; Spirtes et al., 1998; Tian, 2004]. A number of sufficient graphical criteria for identification have been developed, in [Brito and Pearl, 2002c; 2002b; 2002a; 2006] based on Wright's equations [Wright, 1934], and in [Tian, 2007a] using partial regression equations [Tian, 2005]. Most of these results are sufficient criteria which are applicable only when certain conditions are met.

Despite all this effort, the problem still remains open. In other words, we do not have a necessary and sufficient criterion for identification in arbitrary SEMs. One advancement in this direction is a necessary and sufficient procedure for identification in a special class of SEMs presented in [Tian, 2007b]. In this paper, we solve the identifiability problem in a class of SEMs strictly larger than those in [Tian, 2007b]. We present a procedure that will systematically determine whether each parameter in the model is identifiable or not and, if the answer is positive, the procedure will express the parameter in terms of observed covariances.

We begin with a formal introduction to SEMs and the identification problem, and introduce the partial regression equations method in [Tian, 2005] before presenting our results. For space reasons, the proofs are not included which can be found in the extended version of the paper.

2 Linear SEMs and Identification

A linear SEM over a set of random variables V = {V1, . . . , Vn} is given by a set of structural equations of the form

where the summation is over the variables in V judged to be immediate causes of Vj . cji, called a path coefficient, quantifies the direct causal influence of Vi on Vj . ϵj's represent "error" terms and are assumed to have normal distribution. In this paper we consider recursive models and assume that the summation in Eq. (1) is for i < j, that is, cji = 0 for i ≥ j. The set of variables (and the corresponding structural equations) are considered to be ordered as V1 < V2 < . . . < Vn. We denote the covariances between observed variables σij = Cov(Vi, Vj), and between error terms ψij = Cov(ϵi, ϵj). We denote the following matrices, Σ = [σij ], Ψ = [ψij ], and C = [cij ]. Without loss of generality, the model is assumed to be standardized such that each variable Vj has zero mean and variance 1.

The structural assumptions encoded in a model are the zero path coefficients cji and zero error covariances ψij. The model structure can be represented by a directed acyclic graph (DAG) G with (dashed) bidirected edges, called a causal diagram (or path diagram), as follows: the nodes of G are the variables V1, . . . , Vn; there is a directed edge from Vi to Vj in G if Vi appears in the structural equation for Vj, that is, cji ̸= 0; there is a bidirected edge between Vi and Vj if the error terms ϵi and ϵj have non-zero correlation (ψij ̸= 0). For example, the smoking-and-lung-cancer SEM is represented by the causal diagram in Figure 1, in which each directed edge is annotated by the corresponding path coefficient.

The parameters of the model are the non-zero entries in the matrices C and Ψ. Fixing the model structure and given parameters C and Ψ, the covariance matrix Σ is given by (see, for example, [Bollen, 1989])

where "t" represents transpose. Conversely, in the identification problem, given the structure of a model, one attempts to solve for C in terms of the given observed covariance matrix Σ. If Eq. (2) gives a unique solution to some path coefficient cji, independent of the (unobserved) error correlations Ψ, the path coefficient cji is said to be identified; otherwise, cji is said to be nonidentifiable. In other words, the identification problem is that whether a path coefficient is determined uniquely from the covariance matrix Σ given the causal diagram. If every parameter of the model is identified, then the model is identified. Note that the identifiability conditions we seek involve the structure of the model alone, not particular numerical values of parameters, that is, we insist on having identification almost everywhere, allowing for pathological exceptions (see, for example, [Brito and Pearl, 2002a] for formal definition of identification almost everywhere).

3 Partial Regression Equations

In this paper, we will solve the identification problem using the partial regression equations method presented in [Tian, 2005] which will be introduced next.

For a set S ⊆ V , let βij.S denote the partial regression coefficient which represents the coefficient of Vj in the linear regression of Vi on Vj and S. Note that partial regression coefficients can be expressed in terms of the covariance matrix Σ and that the order of the subscripts in βij.S is essential. Let Sjk denote a setSjk = {V1, . . . , Vj-1} \ {Vk}. (3)

[Tian, 2005] derived an expression for the partial regression coefficient βjk.Sjk , for each pair of variables Vk < Vj, in terms of the model parameters (path coefficients and error covariances) given by

where αjk's are defined recursively in terms of the error covariances as

where

and

For convenience, we will often use the shorthand notation βjk. to denote βjk.Sjk .

The set of equations given by (4) are called the partial regression equations. As an example, the partial regression equations for the model shown in Figure 1 are given by

We immediately obtain that the path coefficients a and b are identified.

In general, given the model structure (represented by zero path coefficients and zero error correlations), some of the cjk and αjk will be set to zero in Eq. (4), and we can solve the identifiability problem by solving Eq. (4) for cjk in terms of the partial regression coefficients. This provides a principled method for solving the identifiability problem. A path coefficient cij is identified if and only if the set of partial regression equations (4) give a unique solution to cij , independent of error correlations.

The partial regression equations are linear with respect to cjk's and αjk's, but may not be linear with respect to ψij's. The main difficulty in solving these equations lies in that αjk's are nonlinear functions of ψij's and may not be independent with each other. In this paper, we will study a class of SEMs in which we can treat αjk's as independent free parameters and thus for this class of SEMs the partial regression equations become linear equations.

(a) A ρ-structure.

(b)A ρ-structure-free model.

Figure 2: Different structures of SEMs.

4 ρ-structure-free SEMs

[Tian, 2007b] studied so-called P-structure-free models which require that for any i < k < j the two bidirected edges Vj ↔ Vi and Vk ↔ Vi can not both appear in the causal diagram (Fig. 2(a) and (b) both contain P-structures). In this paper, we relax this restriction and allow the simultaneous appearances of the two bidirected edges Vj ↔ Vi and Vk ↔ Vi as far as there also exists a bidirected edge between Vj and Vk .

Definition 1 (ρ-structure) We will say that a SEM (or causal diagram) contains a ρ-structure if for some i < k < j, there is a bidirected edge between Vj and Vi, and a bidirected edge between Vi and Vk, but there is no bidirected edge between Vj and Vk (see Fig. 2a). Equivalently, in terms of model parameters, we say that a SEM contains a ρ-structure if for some i < k < j, ψji ̸= 0 and ψki ̸= 0 but ψjk = 0.

We will say that a SEM (or causal diagram) is ρ-structurefree if it does not contain any ρ-structures. It is clear that P-structure-free SEMs are a strict subset of ρ-structure-free SEMs as any P-structure-free SEM is also ρ-structure-free but there exist models such as the one in Fig. 2(b) that is ρstructure-free but is not P-structure-free.

In this paper we will study ρ-structure-free SEMs and show how to identify this class of models. First we show that in a ρstructure-free SEM, αjk's can be treated as independent free parameters of the model.

Lemma 1 In a ρ-structure-free SEM if ψjk = 0 then αjk = 0. Graphically speaking, if there is no bidirected edge between Vj and Vk, then αjk = 0.

It is straightforward to show that αjk's can be treated as independent parameters in place of ψjk's. Therefore, in ρstructure-free SEMs, the set of partial regression equations (4) become linear in terms of the variables cjk and αjk. And the identification problem is reduced to that of solving (4) for cjk in terms of the partial regression coefficients βjk., which leads to the following proposition.

Proposition 1 In a ρ-structure-free SEM, a path coefficient cjk is identified if and only if the set of linear equations (4) give a unique solution to cjk that is independent of αjk's.

Figure 3: Two possible types of effective paths from Vk to Vj .

The difficulty of solving these linear equations lies in that the coefficients of these equations, the partial regression coefficients, are not independent parameters. The partial regression coefficients are related to each other in a complicated way, and it is difficult to decide the rank of the set of linear equations since it is not easy to determine whether certain expressions of partial regression coefficients will cancel out each other and become identically zero. To overcome this difficulty, next we show that the partial regression coefficients that appear in (4) can be expressed in terms of the free parameters cjk and αjk. First, we define some graphical notations.

A path between two nodes X and Y in a causal diagram consists of a sequence of consecutive edges of any type (directed or bidirected). A non-endpoint node Z on a path is called a collider if two arrowheads on the path meet at Z, i.e. → Z ←, ↔ Z ↔, ↔ Z ←, → Z ↔; all other non-endpoint nodes on a path are non-colliders, i.e. ← Z →, ← Z ←, → Z →, ↔ Z →, ← Z ↔.

Definition 2 (Effective Path) Let k < j. A path (Vk, Vi1 , . . . , Vil , Vj) from Vk to Vj is said to be an effective path if every intermediate node on the path is a collider, and k < i1 < . . . < il < j (see Figure 3).

We assume that the edges in the causal diagram are associated with the model parameters as follows:

• each directed edge Vj ← Vk is associated with the path coefficient cjk.
• each bidirected edge Vj ↔ Vk where k < j is associated with the parameter αjk.

For a path p, let T(p) represent the product of the parameters along path p. For example, let p be the path V1 → V2 → V3 ↔ V5 in Figure 4(b). Then T (p) = c21c32α53.

Lemma 2 In a ρ-structure-free SEM,

in which the summation is over all the effective paths from Vk to Vj and |p| represents the number of edges on p.

As a corollary of Lemma 2 we have that βjk. = 0 if there is no effective paths from Vk to Vj .

Next, we show how to solve the set of partial regression equations (4) in a ρ-structure-free SEM.

5 Identifying ρ-structure-free SEMs

According to Eq. (4), to decide the identifiability of a path coefficient cjk, we need to solve the j -1 equations in (4) for k = 1, . . . , j -1 simultaneously with cjl and αjl for l < j as variables. And cjk is identified if and only if the set of j -1

equations give a unique solution to cjk in terms of βil.'s. For convenience, we will name the equation for βjk. after Vk (for a fixed j) as follows:

Assuming that there is a directed edge Vk → Vj in the causal diagram, the path coefficient cjk only appears once in this j -1 equations, that is, in the equation (Vk). Let PAj be the set of parents of Vj (that is, the set of variables Vk such that cjk ̸= 0). Let E(S) denote the set of equations (Vk) such that Vk ∈ S. Each equation (Vk) in E(PAj) can be solved for the path coefficient cjk by simply rewriting the equation to obtain

Therefore cjk is identifiable if none of the αji appears in this equation or all the αji appearing in the equation are identifiable. The problem of identifying cjk is reduced to the problem of identifying αji's.

Let V < j = {V1, . . . , Vj-1} denote the set of variables ordered ahead of Vj . Let PAj = V < j \ PAj . To identify αji's we need to solve the set of equations in E(PAj) with αji's as unknowns, rewritten in the following:

Let SPj (the set of spouses of Vj) be the set of variables Vk that connects with Vj by a bidirected edge Vk ↔ Vj (that is, ψjk ̸= 0). Then the number of unknowns is given by the number of variables in SPj , denoted by |SPj |. In general we may have more equations than unknowns (|PAj| ≥ |SPj|), or more unknowns than equations (|PAj| ≤ |SPj|). And these equations may not be linearly independent with each other.

For example, assume that we are interested in identifying the path coefficients c53 and c54 in the model in Figure 4(a). The set of equations E(PAj) in (13) become

And the set of equations E(PAj) become

(V1) and (V2) may be solved simultaneously to identify α53 and α54 (almost everywhere), and therefore c53 and c54 are identified. On the other hand, in the model in Figure 4(b), the set of equations E(PAj) become

We obtain that α53 and α54 are not identified.

In general, to solve the set of linear equations E(PAj) in (14), we look for linearly independent equations. Next we show that this can be achieved by solving a maximum flow problem. We acknowledge that the idea of using the maximum flow technique was proposed by [Brito and Pearl, 2002b] and also used in [Tian, 2007a]. Still, constructing a relevant flow network poses a nontrivial problem.

5.1 Flow network

A flow network F = (V, E) is a directed graph in which each edge (u, v) ∈ E has a nonnegative capacity c(u, v) ≥ 0 (see, for example, [Cormen et al., 1990]). We distinguish two vertices in a flow network: a source s and a sink t. A flow in F is a real-valued function f : V × V → R that satisfies the capacity constraints f (u, v) ≤ c(u, v) and the flow conservation property (the amount of flow entering any vertex must be the same as the amount of flow leaving the vertex) among others. The value of a flow f is defined as |f| = ∑v∈V f(s, v), that is, the total net flow out of the source. In the maximum flow problem, we are given a flow network F, with source s and sink t, and we wish to find a flow of maximum value from s to t.

To facilitate identifying a set of linearly independent equations in E(PAj), we construct a flow network Fj as follows. The nodes of Fj consists of:

• for every node Vi < Vj , add two nodes V - i and V + i into Fj .
• a source node s.
• a sink node t.

The edges of Fj are:

• for every node Vi < Vj , add edge V - i →V + i .
• for every edge Vi → Vl, add edge V - i →V + l .
• for every edge Vi ↔Vl, i < l, add edge V + i →V + l .
• for every node Vi ∈ SPj (those with αVjVi ̸= 0), add edge V + i → t.
• for every node Vi ∈ PAj (those with cji = 0), add s → V - i .

We assign a capacity 1 to every edge in Fj . We also assign a node capacity of 1 to every node (except s and t) in Fj (this can be achieved by splitting every node into two and connecting them by an edge of capacity 1 [Even, 1979]). As an example, for the model shown in Figure 5(a), the flow network relative to V7 is given in Figure 5(b).

Assume that we have solved the maximum flow problem on the flow network Fj (using, for example, Ford-Fulkerson algorithm). Since every edge has a capacity 1 and every node has a capacity 1, the computed flow f represents a set of disjoint directed paths from s to t. Let the set of directed paths be

where k = |f|. From the network construction, we have that Zi ∈ PAj and Xi ∈ SPj. We will call the set of variables AC = {Z1, . . . , Zk} ⊆ PAj a contributory set relative to DC = {X1, . . . ,Xk} ⊆ SPj and Vj. For example, the flow network in Figure 5(b) shows a maximum flow solution, which identifies the set {V1, V2} as a contributory set relative to {V4, V5} and V7.

A contributory set plays a key role in solving the set of equations E(PAj). Using Lemma 2 and the properties of the maximum flow we obtain the following theorems.

Theorem 1 In a ρ-structure-free SEM, let AC ⊆ PAj be a contributory set relative to DC ⊆ SPj and Vj , then the set of linear equations E(AC) are linearly independent with respect to the set of unknowns α(DC) = {αVjXi |Xi ∈ DC}, that is, E(AC) can be solved with respect to unknowns in α(DC) (almost everywhere).

The rest of the equations in E(PAj) will be linearly dependent on the set of equations in E(AC).

Theorem 2 The number of linearly independent equations in E(PAj) (that is, the rank of the coefficient matrix of the equations) is equal to the maximum flow value |f|.

5.2 Solving the problem

From Theorems 1 and 2, after we have identified a contributory set AC relative to Vj we can determine the identifiability of the path coefficient cjk by solving the set of equations E(PAj) and E(AC). The following is a direct corollary of Theorems 1 and 2.

Theorem 3 In a ρ-structure-free SEM, a path coefficient cjk is identified if and only if the set of linearly independent equations E(PAj) and E(AC) give a unique solution to cjk that is independent of αjk's.

In general, we can first solve the set of linear equations E(AC) for unknown variables in α(DC) in terms of βjk.'s For j = 1, . . . , n,

1. Express cjk's in terms of parameter αjk's using the equations in E(PAj).
2. Construct the flow network for Vj.
3. Solve the maximum flow problem to obtain a contributory set ACj relative to DCj and Vj.
4. Solve E(ACj) with respect to the unknown variables {αjk|Vk ∈ DCj}.
5. Substitute the values of solved variables into the equations E(PAj ) to determine the identifiability of the path coefficients cjk's.

Figure 6: A procedure for systematically identifying the path coefficients in a ρ-structure-free SEM.

and possibly some αVjXi 's for Xi ̸∈ DC. Then we substitute the values of solved variables into the equations E(PAj ) given in (13) to determine the identifiability of the path coefficients cjk's.

In summary, a procedure for systematically identifying the path coefficients in a ρ-structure-free SEM is given in Figure 6. For j = 1, . . . , n, at each step, we attempt to identify parameters associated with the variable Vj . The procedure will tell which cjk's are identifiable, and which are not.

Notice that the equations in E(PAj \AC) are linearly dependent on the equations in E(AC) and therefore are not useful for determining the identifiability of parameters. If we substitute the values of solved variables in α(DC) into the equations in E(PAj \ AC), we will get a set of equations involving βil.'s. These equations represent the set of constraints on the covariance matrix implied by the model structure. They can be used for testing a hypothesized model against the observed data.

5.3 An example

We illustrate the identification procedure by an example. Consider the model in Figure 5(a). Assume that we want to identify the path coefficients associated with V7 (c74, c75, and c76). First we express the path coefficients in terms of α7i's as follows

Then we construct the flow network shown in Figure 5(b) and solve the maximum flow problem. Assume that the solution returns {V1, V2} as a contributory set relative to {V4, V5}. Then we solve the equations (V1) and (V2) given in the following

with α74 and α75 as unknown variables. We obtain

We conclude that α74 is identified, and that α75 and α76 are nonidentifiable. Finally, we substitute expressions for α74 and α75 into Eqs. (21)-(23), and we conclude that c74 is identified, and c75 and c76 are both nonidentifiable.

We notice that we have not used equation (V3) given below

which is indeed linearly dependent on the equations (V1) and (V2). In fact if we substitute into (V3) the solved value of α74 given in Eq. (26) we obtain

which represents a constraint on the covariance matrix imposed by the model structure.

6 Conclusion and Discussion

The identification problem has been a long standing problem in the applications of linear SEMs. Given a SEM, we would like to know which parameters in the model are uniquely determined by the observed covariances and which parameters are not, and we would like to know what constraints are implied by the model structure on the covariance matrix. In this paper, we provide a procedure for answering these questions in the class of ρ-structure-free SEMs.

In related work using graphical models methods, sufficient criteria for model identification have been developed in [Brito and Pearl, 2002c; 2002b; 2006], which established sufficient conditions for all the parameters in the model to be identified but can not be used to identify individual parameters if there exist nonidentifiable parameters in the model. A number of sufficient criteria for identifying individual parameters have been developed in [Pearl, 2000; Brito and Pearl, 2002a; Tian, 2007a]. Given a model, these methods may identify certain parameters but make no claims about other parameters.

The closest related work is a necessary and sufficient procedure for identifying P-structure-free SEMs [Tian, 2007b]. The ρ-structure-free SEMs we have solved in this paper contain P-structure-free models as a strict subset. The ultimate goal of this line of research is to provide a necessary and sufficient algorithm for identifying any possible models that may be hypothesized by researchers using SEMs. We believe this work is an important advance in this direction as there exist a large number of possible models containing the structure in Fig. 2(b) that are ρ-structure-free but not P-structure-free.

Acknowledgments

This research was partly supported by NSF grant IIS0347846.