Description Usage Arguments Details Value Author(s) References See Also Examples
These functions perform the last step in the PC algorithm:
Transform an object of the class
"pcAlgo"
containing a skeleton and corresponding
conditional independence information into a completed partially
directed acyclic graph (CPDAG). The functions first determine the
vstructures, and then apply the three orientation rules as described
in Sprirtes et al (2000) and Meek (1995) to orient as many of the
remaining edges as possible.
In the oracle version and when all assumptions hold, all three functions yield the same CPDAG. In the sample version, however, the resulting CPDAG may be invalid in the sense that one cannot extend it a DAG without additional unshielded colliders by orienting the undirecting edges. This can for example happen due to errors in the conditional indepedence tests or violations of the faithfulness assumption. The three functions deal with such conflicts in different ways, as described in Details.
1 2 3 4  udag2pdag (gInput, verbose)
udag2pdagRelaxed(gInput, verbose, unfVect=NULL, solve.confl=FALSE,
orientCollider = TRUE, rules = rep(TRUE, 3))
udag2pdagSpecial(gInput, verbose, n.max=100)

gInput 

verbose 
0: No output; 1: Details 
unfVect 
vector containing numbers that encode ambiguous
triples (as returned by 
solve.confl 
if 
n.max 
maximum number of tries for reorienting doubly visited
edges in 
orientCollider 
if 
rules 
Array of length 3 containing 
udag2pdag
:If there are edges that are part of more than one vstructure (i.e., the edge b  c in the vstructures a > b < c and b > c < d), earlier edge orientations are simply overwritten by later ones. Thus, if a > b < c is considered first, the edge b  c is first oriented as b < c and later overwritten by b > c. The vstructures are considered in lexicographical ordering.
If the resulting graph is extendable to a DAG without additional
vstructures, then the rules of Meek (1995) and Spirtes et al
(2000) are applied to obtain the corresponding CPDAG. Otherwise,
the edges are oriented randomly to obtain a DAG that fits on the
skeleton, discarding all information about the vstructures. The
resulting DAG is then transformed into its CPDAG. Note that the
output of udag2pdag
is random whenever the initial graph
was not extendable.
Although the output of udag2pdag
is always
extendable, it is not necessarily a valid CPDAG in the sense that
it describes a Markov equivalence class of DAGs. For example, two
vstructures a > b < c and b > c < d (considered in this
order) would yield the output a > b > c < d. This is
extendable to a DAG (it already is a DAG), but it does not
describe a Markov equivalence class of DAGs, since the DAG a < b
> c < d describes the same conditional independencies.
udag2pdagSpecial
:If the graph after orienting the vstructures as in
udag2pdag
is extendable to a DAG without additional
vstructures, then the rules of Meek (1995) and Spirtes et al
(2000) are applied to obtain the corresponding CPDAG. Otherwise,
the algorithm tries at most n.max
different random
orderings of the vstructures (hence overwriting orientations in
different orders), until it finds one that yields an extendable
CPDAG. If this fails, the edges are oriented randomly to obtain a
DAG that fits on the skeleton, discarding all information about
the vstructures. The resulting DAG is then transformed into its
CPDAG. Note that the output of udag2pdagSpecial
is random
whenever the initial graph was not extendable.
Although the output of udag2pdag
is always
extendable, it is not necessarily a valid CPDAG in the sense that
it describes a Markov equivalence class of DAGs. For example, two
vstructures a > b < c and b > c < d (considered in this
order) would yield the output a > b > c < d. This is
extendable to a DAG (it already IS a DAG), but it does not
describe a Markov equivalence class of DAGs, since the DAG a < b
> c < d describes the same conditional independencies.
udag2pdagRelaxed
:This is the default version in the PC/RFCI/FCI algorithm. It does not test whether the output is extendable to a DAG without additional vstructures.
If unfVect = NULL
(no ambiguous triples), the three
orientation rules are applied to each eligible structure until no
more edges can be oriented. Otherwise, unfVect
contains
the numbers of all ambiguous triples in the graph as determined by
pc.cons.intern
. Then the orientation rules take
this information into account. For example, if a > b  c and
<a,b,c> is an unambigous triple and a nonvstructure, then rule 1
implies b > c. On the other hand, if a > b  c but <a,b,c> is
an ambiguous triple, then the edge b  c is not oriented.
If solve.confl = FALSE
, earlier edge orientations are
overwritten by later ones as in udag2pdag
and
udag2pdagSpecial
.
If solv.confl = TRUE
, both the vstructures and the
orientation rules work with lists for the candidate edges and
allow bidirected edges if there are conflicting orientations. For
example, two vstructures a > b < c and b > c < d then yield a
> b <> c <d. This option can be used to get an
orderindependent version of the PC algorithm (see Colombo and
Maathuis (2014)).
We denote bidirected edges, for example between two variables i and j, in the adjacency matrix M of the graph as M[i,j]=2 and M[j,i]=2. Such edges should be interpreted as indications of conflicts in the algorithm, for example due to errors in the conditional independence tests or violations of the faithfulness assumption.
udag2pdag()
and udag2pdagRelaxed()
:oriented "pcAlgo"
object.
udag2pdagSpecial
:a list
with
components
An oriented "pcAlgo"
object.
Matrix counting the number of orientation attempts per edge
Logical indicating whether the original graph with vstructures is extendable.
Logical indicating whether the final graph with vstructures is extendable
Adjacency matrix of original graph with vstructures (type amat.cpdag) .
Adjacency matrix of final graph with vstructures after changing the ordering in which the vstructures are considered (type amat.cpdag) .
Integer code with values
Original try is extendable;
Reorienting double edge visits helps;
Original try is not extendable; reorienting double visits does not help; result is acyclic, has original vstructures, but perhaps additional vstructures.
Number of orderings of the vstructures until
success or n.max
.
Markus Kalisch ([email protected])
C. Meek (1995). Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI95), pp. 403411. Morgan Kaufmann Publishers, Inc.
P. Spirtes, C. Glymour and R. Scheines (2000) Causation, Prediction, and Search, 2nd edition, The MIT Press.
J. Pearl (2000), Causality, Cambridge University Press.
D. Colombo and M.H. Maathuis (2014).Orderindependent constraintbased causal structure learning. Journal of Machine Learning Research 15 37413782.
pc
, pdag2dag
,
dag2cpdag
, udag2pag
,
udag2apag
, dag2pag
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  ## simulate data
set.seed(123)
p < 10
myDAG < randomDAG(p, prob = 0.2)
trueCPDAG < dag2cpdag(myDAG)
n < 1000
d.mat < rmvDAG(n, myDAG, errDist = "normal")
## estimate skeleton
resU < skeleton(suffStat = list(C = cor(d.mat), n = n),
indepTest = gaussCItest, ## (partial correlations)
alpha = 0.05, p=p)
## orient edges using three different methods
resD1 < udag2pdagRelaxed(resU, verbose=0)
resD2 < udag2pdagSpecial(resU, verbose=0, n.max=100)
resD3 < udag2pdag (resU, verbose=0)

Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.