When using the PC algorithm a pattern is generated. I wish to build a DAG from this automatically, but i am not sure which technique(s) is(are) used to build the pattern. Could somebody explain how the algorithm determines the direction of the arcs that are directed in the generated pattern.
Kind regards,
Lydia
pattern when using PC algorithm
Re: pattern when using PC algorithm
The algorithm is described in the book "Causation, Prediction, and Search" by Spirtes, Glymour, and Scheines (Page 84 of the second edition), and it's also mentioned in a few of their papers.
Basically, the PC algorithm works as following
We start with a fully connected, undirected graph
We perform conditional independence tests on the edges, pruning them if they are found to be independent
Next we try to find 'v-structures', triples of vertices X,Y,Z where X,Y and Y,Z are adjacent and X,Z is not. if another, specific condition, we orient the undirected edges so that we get X -> Y <- Z
After this is finished we iteratively try to orient the remaining undirected using a set of rules.
The algorithm terminates when the rules no longer can make any changes to the edges.
You will find that in the result returned by GeNIe and SMILE you will find three different types of edges
1) Directed edges, edges for which an orientation was found
2) undirected edges, edges for which the algorithm was unable to determine an orientation
3) bidirected edges, here the algorithm also was unable to determine an orientation, but it is suspected that there his a hidden common cause present (i.e. some variable not present in the data set, but that seems to be influencing both)
GeNIe allows to randomly assign directed arcs to the problem cases to get a DAG. This is a pretty standard thing to do.
You could use a similar approach in SMILE.
Another option is to play with the input parameters (significance level, adjancency size), although it is quite unlikely that you will end up with a DAG.
Martijn
Basically, the PC algorithm works as following
We start with a fully connected, undirected graph
We perform conditional independence tests on the edges, pruning them if they are found to be independent
Next we try to find 'v-structures', triples of vertices X,Y,Z where X,Y and Y,Z are adjacent and X,Z is not. if another, specific condition, we orient the undirected edges so that we get X -> Y <- Z
After this is finished we iteratively try to orient the remaining undirected using a set of rules.
The algorithm terminates when the rules no longer can make any changes to the edges.
You will find that in the result returned by GeNIe and SMILE you will find three different types of edges
1) Directed edges, edges for which an orientation was found
2) undirected edges, edges for which the algorithm was unable to determine an orientation
3) bidirected edges, here the algorithm also was unable to determine an orientation, but it is suspected that there his a hidden common cause present (i.e. some variable not present in the data set, but that seems to be influencing both)
GeNIe allows to randomly assign directed arcs to the problem cases to get a DAG. This is a pretty standard thing to do.
You could use a similar approach in SMILE.
Another option is to play with the input parameters (significance level, adjancency size), although it is quite unlikely that you will end up with a DAG.
Martijn