This function is rather similar to fci. However, it does not
compute any Possible-D-SEP sets and thus does not make tests
conditioning on subsets of Possible-D-SEP. This makes RFCI much faster
than FCI. The orientation rules for v-structures and rule 4 were
modified in order to produce an RFCI-PAG which, in the oracle version,
is guaranteed to have the correct ancestral relationships.
The first part of the RFCI algorithm is analogous to the PC and FCI
algorithm. It starts with a complete undirected graph and estimates an
initial skeleton using the function skeleton, 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. The FCI algorithm performs
independence tests conditioning on subsets of Possible-D-SEP to remove
those edges. Since this procedure is computationally infeasible, the
RFCI algorithm uses a different approach to remove some of those
superfluous edges before orienting the v-structures and the
discriminating paths in orientation rule 4.
Before orienting the v-structures, we perform the following additional
conditional independence tests. For each unshielded triple a-b-c in
the initial skeleton, we check if both a and b and b and c are
conditionally dependent given the separating of a and c
(sepset(a,c)). These conditional dependencies may not have been
checked while estimating the initial skeleton, since sepset(a,c) does
not need to be a subset of the neighbors of a nor of the neighbors of
c. If both conditional dependencies hold and b is not in the
sepset(a,c), the triple is oriented as a v-structure a->b<-c. On the
other hand, if an additional conditional independence relationship may
be detected, say a is independent from b given the sepset(a,c), the
edge between a and c is removed from the graph and the set responsible
for that is saved in sepset(a,b). The removal of an edge can destroy
or create new unshielded triples in the graph. To solve this problem
we work with lists (for details see Colombo et al., 2012).
Before orienting discriminating paths, we perform the following additional
conditional independence tests. For each triple a <-* b o- *c with a
-> c, the algorithm searches for a discriminating path p = <d,
. . . , a,b,c> for b of minimal length, and checks that the vertices
in every consecutive pair (f1,f2) on p are conditionally dependent
given all subsets of sepset(d,c) \ f1,f2 . If we do not find any
conditional independence relationship, the path is oriented as in rule
(R4). If one or more conditional independence relationships are found,
the corresponding edges are removed, their minimal separating sets are
stored.
Conservative RFCI can be computed if the argument of conservative is
TRUE. After the final skeleton is computed and the
additional local tests on all unshielded triples, as described above,
have been done, 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 RFCI 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 RFCI 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).
The implementation uses the stabilized skeleton
skeleton, which produces an initial order-independent
skeleton. The final skeleton and edge orientations can still be
order-dependent, see Colombo and Maathuis (2014).