Jump to content

User:AaronSw/PC algorithm

From Wikipedia, the free encyclopedia

IC Algorithm (Inductive Causality)

[edit]

Input: , a stable distribution on a set V of variables
Output: a patter compatible with .

  1. For each pair of variables a and b in V, search for a set Sab such that (a || b | Sab) holds in -- in other words, a and b should be independent in P-hat, conditioned on Sab. Construct an undirected graph G such that vertices a and b are connected with an edg if and only if no set Sab can be found.
  1. For each pair of nonadjacient variables a and b with a common neighbor c, check if c e Sab.
    • If it is, then continue.
    • If it is not, then add arrowheads pointing at c (i.e., a->c <- b).
  1. In the partially directed graph that results, orient as many of the undirected edges as possible subject to two conditions: (i) the orientation should not create a new v-structure; and (ii) the orientation should not create a directed cycle.