This function is a generalization of the PC algorithm (see
pc), in the sense that it allows arbitrarily many
latent and selection variables. Under the assumption that the data
are faithful to a DAG that includes all latent and selection variables,
the FCI algorithm (Fast Causal Inference algorithm) (Spirtes, Glymour
and Scheines, 2000) estimates the Markov equivalence class of MAGs
that describe the conditional independence relationships between the
observed variables. We estimate an equivalence class of maximal ancestral graphs (MAGs)
instead of DAGs, since DAGs are not closed under marginalization and
conditioning (Richardson and Spirtes, 2002).
An equivalence class of a MAG can be uniquely represented by a partial
ancestral graph (PAG). A PAG contains the following types of edges:
o-o, o-, o->, ->, <->, -. The bidirected edges come from hidden variables,
and the undirected edges come from selection variables. The edges have
the following interpretation: (i) there is an edge between x
and y if and only if variables x and y are conditionally dependent
given S for all sets S consisting of all selection variables
and a subset of the observed variables; (ii) a tail on an edge means
that this tail is present in all MAGs in the Markov equivalence class;
(iii) an arrowhead on an edge means that this arrowhead is present in
all MAGs in the Markov equivalence class; (iv) a o-edgemark means that
there is a at least one MAG in the Markov equivalence class where the
edgemark is a tail, and at least one where the edgemark is an
arrowhead. Information on the interpretation of edges in a MAG can be
found in the references given below.
The first part of the FCI algorithm is analogous to the PC algorithm. It
starts with a complete undirected graph and estimates an initial skeleton
using skeleton(*, method="stable") which produces an
initial order-independent skeleton, see skeleton for
more details. All edges of this skeleton are of
the form o-o. Due to the presence of hidden variables, it is no longer
sufficient to consider only subsets of the neighborhoods of nodes x
and y to decide whether the edge x o-o y should be removed.
Therefore, the initial skeleton may contain some superfluous edges.
These edges are removed in the next step of the algorithm which
requires some orientations. Therefore, the v-structures
are determined using the conservative method (see discussion on
conservative below).
After the v-structures have been oriented, Possible-D-SEP sets for each
node in the graph are computed at once. To decide whether edge
x o-o y should be removed, one performs conditional indepedence
tests of x and y given all possible subsets of Possible-D-SEP(x) and
of Possible-D-SEP(y). The edge is removed if a conditional
independence is found. This produces a fully order-independent final
skeleton as explained in Colombo and Maathuis (2014). Subsequently,
the v-structures are newly determined on the final skeleton (using
information in sepset). Finally, as many as possible undetermined edge
marks (o) are determined using (a subset of) the 10 orientation rules
given by Zhang (2009).
The “Anytime FCI” algorithm was introduced by Spirtes (2001). It
can be viewed as a modification of the FCI algorithm that only performs
conditional independence tests up to and including order m.max when
finding the initial skeleton, using the function skeleton, and
the final skeleton, using the function pdsep. Thus, Anytime FCI
performs fewer conditional independence tests than FCI. To use the
Anytime algorithm, one sets type = "anytime" and needs to
specify m.max, the maximum size of the conditioning sets.
The “Adaptive Anytime FCI” algorithm was introduced by Colombo
et. al (2012). The first part of the algorithm is identical to the normal
FCI described above. But in the second part when the final skeleton is
estimated using the function pdsep, the Adaptive Anytime
FCI algorithm only performs conditional independence tests up to and
including order m.max, where m.max is the maximum size of the
conditioning sets that were considered to determine the initial
skeleton using the function skeleton. Thus, m.max is chosen
adaptively and does not have to be specified by the user.
Conservative versions of FCI, Anytime FCI, and Adaptive Anytime FCI
are computed if conservative = TRUE is specified. After the
final skeleton is computed, all potential
v-structures a-b-c are checked in the following way. We test whether a
and c are independent conditioning on any subset of the neighbors of a
or any subset of the neighbors of c. When a subset makes a and c
conditionally independent, we call it a separating set. If b is in no
such separating set or in all such separating sets, no further action
is taken and the normal version of the FCI, Anytime FCI, or Adaptive
Anytime FCI algorithm is continued. If, however, b is in only some
separating sets, the triple a-b-c is marked ‘ambiguous’. If a is
independent of c given some S in the skeleton (i.e., the edge a-c
dropped out), but a and c remain dependent given all subsets of
neighbors of either a or c, we will call all triples a-b-c
‘unambiguous’. This is because in the FCI algorithm, the true separating set
might be outside the neighborhood of either a or c. An ambiguous
triple is not oriented as a v-structure. Furthermore, no further
orientation rule that needs to know whether a-b-c is a v-structure or
not is applied. Instead of using the conservative version, which is
quite strict towards the v-structures, Colombo and Maathuis (2014)
introduced a less strict version for the v-structures called majority
rule. This adaptation can be called using maj.rule = TRUE. In
this case, the triple a-b-c is marked as ‘ambiguous’ if and only if b
is in exactly 50 percent of such separating sets or no separating set
was found. If b is in less than 50 percent of the separating sets it
is set as a v-structure, and if in more than 50 percent it is set as a
non v-structure (for more details see Colombo and Maathuis,
2014). Colombo and Maathuis (2014) showed that with both these
modifications, the final skeleton and the decisions about the
v-structures of the FCI algorithm are fully order-independent.
Note that the order-dependence issues on the 10 orientation rules are
still present, see Colombo and Maathuis (2014) for more details.