Search Algorithms: FCI



FCI  is intended to search for causal explanations of observational or mixed observational and experimental data when there may be unrecorded common causes of recorded variables, or sample selection bias. Sample selection bias occurs when the values of two or more recorded variables influence the probability that a unit is sampled.. With continuous variables, the statistical tests used in  FCI  assume linearity and a Normal distribution.

FCI is operated by the user exactly as is PC. The differences are in the interpretation of the output. The output of FCI is a partial ancestral graph. It gives partial information about which variables are or are not drect or indirect causes and effects of other variables.

An edge between two variables in the output, however the ends of the edge are marked, indicates that there is a causal pathway--a direct cause in one direction or the other or a common cause--connecting the two variables, that does not contain any other observed variable. It does not necessarily mean that in the true causal graph, the connected variables have a direct causal connection.  An edge of any kind between two measured variables implies that the variables are not independent conditional on any set of measured variables.


If there is a edge from X to Y that is unmarked--a tail of an arrow-- then X is a cause of Y.  X may not, however, be a direct cause of Y.

If there is an edge from X to Y that has an arrowhead directed into Y, then Y is not a cause--not an ancestor--of X.

If there is an edge with two arrowheads connecting X and Y, then there is an unrecorded common cause of X and Y

If an edge end  is marked with an "o" the algorithm cannot determine whether there should or should not be an arrowhead at that edge end.


Here is pseudocode for the implementation of the FCI algorithm used in Tetrad:

Given: Independence test I over variables v1,...,vn.


Step A:


Form new empty PAG G with variables from I. Fully connect G using 
unoriented (o-o) edges.


Step B:


Run a Fast Adjacency Search on G using I.


Step C:


Orient colliders in G, as follows:

For all nodes B:
 For each pair of nodes A,C adjacent to B:
   If A and C are not adjacent:
      If A and C are d-connected conditional on B:
         Orient A-->B<--C as a collider.

Step D:

Form a Sepset matrix using a possible d-sep search.
Then reorient all edges as unoriented.

Step CI C:

Orient unshielded triples, as follows:

For all nodes B:
 For each pair of nodes A,C adjacent to B:
    If A and C are not adjacent:
       If A and C are d-connected conditional on B:
          Orient A-->B<--C as a collider.
       Else:
         Do nothing (effectively marking A---B---C as a noncollider)

Step CI D:

Apply orientation rules until no more orientations are possible.

Rules to use: double triangle, discriminating paths, away from collider, away 
from ancestor, away from cycle.

Definitions of Orientation Rules:

Double triangle rule:

If D*-oB, A*->B<-**C and A**-**D**-**C is a noncollider, then D**->B.

For all nodes B:
 possible A: nodes into B with arrow
 possible C: nodes into B with arrow
 possible D: nodes into B with circle

 For all possible D:
    For all possible A:
       For all possible C:
          If A != C and required conditions hold:
             Orient D*->B.


Discriminating paths rule:

The triangles that must be oriented this way (won't be done by another rule) 
all look like the ones below, where the dots are a collider path from L to A 
with each modelNode on the path (except L) a parent of C.

             B

            xo           x is either an arrowhead or a circle

           /  \

          v    v
    L....A --> C



For all nodes B
 possible A: nodes out from B with arrow and into B with arrow or circle.
 possible C: nodes out from B with arrow and into B with circle.

 For all possible A:
    For all possible C:
       If A is a parent of C:
          Find a collider path back from A.
          If path found and if path endpoint is d-sep from C conditional on B:
             Set C<--B.
          else,
             Set A<->B and B<->C.


Away from collider rule:

If A*->Bo-oC and not A*-**C, then orient A**->B-->C. (Orient either circle 
if present, don't need both.)


Away from ancestor rule:

If A*-oC and either A-->B*->C or A*->B-->C, then orient A*->C.


Away from cycle rule:

If Ao->C and A-->B-->C, then orient A-->C.


Pseudocode for FCI:

Given: Independence test I over variables v1,...,vn.

Step A:

Form new empty PAG G with variables from I. Fully connect G using 
unoriented (o-o) edges.

Step B:

Run a Fast Adjacency Search on G using I.

Step C:

Orient colliders in G, as follows:

For all nodes B:
 For each pair of nodes A,C adjacent to B:
   If A and C are not adjacent:
      If A and C are d-connected conditional on B:
         Orient A-->B<--C as a collider.

Step D:

Form a Sepset matrix using a possible d-sep search.
Then reorient all edges as unoriented.

Step CI C:

Orient unshielded triples, as follows:

For all nodes B:
 For each pair of nodes A,C adjacent to B:
    If A and C are not adjacent:
       If A and C are d-connected conditional on B:
          Orient A-->B<--C as a collider.
       Else:
         Do nothing (effectively marking A---B---C as a noncollider)

Step CI D:

Apply orientation rules until no more orientations are possible.

Rules to use: double triangle, discriminating paths, away from collider, 
away from ancestor, away from cycle.


Definitions of Orientation Rules:

Double triangle rule:

If D*-oB, A*->B<-**C and A**-**D**-**C is a noncollider, then D**->B.

For all nodes B:
 possible A: nodes into B with arrow
 possible C: nodes into B with arrow
 possible D: nodes into B with circle

 For all possible D:
    For all possible A:
       For all possible C:
          If A != C and required conditions hold:
             Orient D*->B.


Discriminating paths rule:

The triangles that must be oriented this way (won't be done by another rule) all 
look like the ones below, where the dots are a collider path from L to A with each 
modelNode on the path (except L) a parent of C.

             B

            xo           x is either an arrowhead or a circle

           /  \

          v    v

    L....A --> C



For all nodes B
 possible A: nodes out from B with arrow and into B with arrow or circle.
 possible C: nodes out from B with arrow and into B with circle.

 For all possible A:
    For all possible C:
       If A is a parent of C:
          Find a collider path back from A.
          If path found and if path endpoint is d-sep from C conditional on B:
             Set C<--B.
          else,
             Set A<->B and B<->C.


Away from collider rule:

If A*->Bo-oC and not A*-**C, then orient A**->B-->C. (Orient either circle if 
present, don't need both.)

Away from ancestor rule:

If A*-oC and either A-->B*->C or A*->B-->C, then orient A*->C.

Away from cycle rule:

If Ao->C and A-->B-->C, then orient A-->C.