Package edu.cmu.tetrad.search

Class Pc

java.lang.Object
edu.cmu.tetrad.search.Pc
All Implemented Interfaces:
IGraphSearch
public class Pc extends Object implements IGraphSearch

Implements the PC (Peter and Clark) algorithm, which uses conditional independence testing as an oracle to first of all remove extraneous edges from a complete graph, then to orient the unshielded colliders in the graph, and finally to make any additional orientations that are capable of avoiding additional unshielded colliders in the graph. An version of this algorithm was proposed earlier than this, but the standard reference for the algorithm is in Chapter 6 of the following book:

Spirtes, P., Glymour, C. N., Scheines, R., & Heckerman, D. (2000). Causation, prediction, and search. MIT press.

A modified rule set capable of dealing effectively with knowledge of required and forbidden edges is due to Chris Meek, with this reference:

Meek, C. (1995), "Causal inference and causal explanation with background knowledge."

This class is configured to respect knowledge of forbidden and required edges, including knowledge of temporal tiers.

Author:
peterspirtes, chrismeek, clarkglymour, josephramsey
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    Pc(IndependenceTest independenceTest)
    Constructs a new PC search using the given independence test as oracle.

  • Method Summary

    Modifier and Type
    Method
    Description
    Set<Edge>
    getAdjacencies()
    Returns The edges of the searched graph.
    int
    getDepth()
    Returns the current depth of search--that is, the maximum number of conditioning nodes for any conditional independence checked.
    long
    getElapsedTime()
    Returns the elapsed time of the search, in milliseconds.
    IndependenceTest
    getIndependenceTest()
    Returns the independence test being used in the search.
    Knowledge
    getKnowledge()
    Returns the knowledge specification used in the search.
    List<Node>
    getNodes()
    Returns the nodes of the search graph.
    Set<Edge>
    getNonadjacencies()
    Returns the non-adjacencies of the searched graph.
    int
    getNumIndependenceTests()
    Returns the number of independence tests performed in the search.
    SepsetMap
    getSepsets()
    Returns the sepset map from the most recent search.
    boolean
    isAggressivelyPreventCycles()
    Returns true iff edges will not be added if they would create cycles.
    Graph
    search()
    Runs PC starting with a complete graph over all nodes of the given conditional independence test, using the given independence test and knowledge and returns the resultant graph.
    Graph
    search(IFas fas, List<Node> nodes)
    Runs the search using a particular implementation of the fast adjacency search (FAS), over the given sublist of nodes.
    Graph
    search(List<Node> nodes)
    Runs PC starting with a commplete graph over the given list of nodes, using the given independence test and knowledge and returns the resultant graph.
    void
    setAggressivelyPreventCycles(boolean aggressivelyPreventCycles)
    Sets whether cycles should be aggressively checked.
    void
    setDepth(int depth)
    Sets the depth of the search--that is, the maximum number of conditioning nodes for any conditional independence checked.
    void
    setKnowledge(Knowledge knowledge)
    Sets the knowledge specification to be used in the search.
    void
    setMaxPPathLength(int maxPPathLength)
    Sets the maximum path length for the PC heuristic.
    void
    setStable(boolean stable)
    Sets whether the stable adjacency search should be used.
    void
    setUseMaxP(boolean useMaxP)
    Sets whether the max p method should be used in the adjacency searc h.
    void
    setVerbose(boolean verbose)
    Sets whether verbose output should be given.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Pc

      public Pc(IndependenceTest independenceTest)
      Constructs a new PC search using the given independence test as oracle.
      Parameters:
      independenceTest - The oracle for conditional independence facts. This does not make a copy of the independence test, for fear of duplicating the data set!

  • Method Details

    • isAggressivelyPreventCycles

      public boolean isAggressivelyPreventCycles()
      Returns true iff edges will not be added if they would create cycles.
      Returns:
      True if so.

    • setAggressivelyPreventCycles

      public void setAggressivelyPreventCycles(boolean aggressivelyPreventCycles)
      Sets whether cycles should be aggressively checked.
      Parameters:
      aggressivelyPreventCycles - Set to true just in case edges will not be addeds if they would create cycles.

    • getIndependenceTest

      public IndependenceTest getIndependenceTest()
      Returns the independence test being used in the search.
      Returns:
      this test.

    • getKnowledge

      public Knowledge getKnowledge()
      Returns the knowledge specification used in the search. Non-null.
      Returns:
      This knowledge.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge specification to be used in the search. May not be null.
      Parameters:
      knowledge - The knowledge.

    • getSepsets

      public SepsetMap getSepsets()
      Returns the sepset map from the most recent search. Non-null after the first call to search().
      Returns:
      This map.

    • getDepth

      public int getDepth()
      Returns the current depth of search--that is, the maximum number of conditioning nodes for any conditional independence checked.
      Returns:
      This depth.

    • setDepth

      public void setDepth(int depth)
      Sets the depth of the search--that is, the maximum number of conditioning nodes for any conditional independence checked.
      Parameters:
      depth - The depth of the search. The default is 1000. A value of -1 may be used to indicate that the depth should be high (1000). A value of Integer.MAX_VALUE may not be used, due to a bug on multi-core machines.

    • search

      public Graph search()
      Runs PC starting with a complete graph over all nodes of the given conditional independence test, using the given independence test and knowledge and returns the resultant graph. The returned graph will be a CPDAG if the independence information is consistent with the hypothesis that there are no latent common causes. It may, however, contain cycles or bidirected edges if this assumption is not born out, either due to the actual presence of latent common causes, or due to statistical errors in conditional independence judgments.
      Specified by:
      search in interface IGraphSearch
      Returns:
      The found CPDAG. In some cases there may be some errant bidirected edges or cycles, depending on the settings and whether the faithfulness assumption holds. If the faithfulness assumption holds, bidirected edges will indicate the existence of latent variables, so a latent variable search like FCI should be run.
      See Also:

    • search

      public Graph search(List<Node> nodes)
      Runs PC starting with a commplete graph over the given list of nodes, using the given independence test and knowledge and returns the resultant graph. The returned graph will be a CPDAG if the independence information is consistent with the hypothesis that there are no latent common causes. It may, however, contain cycles or bidirected edges if this assumption is not born out, either due to the actual presence of latent common causes, or due to statistical errors in conditional independence judgments.

      All the given nodes must be in the domatein of the given conditional independence test.

      Parameters:
      nodes - The sublist of nodes to search over.
      Returns:
      The search graph.
      See Also:

    • search

      public Graph search(IFas fas, List<Node> nodes)
      Runs the search using a particular implementation of the fast adjacency search (FAS), over the given sublist of nodes.
      Parameters:
      fas - The fast adjacency search to use.
      nodes - The sublist of nodes.
      Returns:
      The result graph
      See Also:

    • getElapsedTime

      public long getElapsedTime()
      Returns the elapsed time of the search, in milliseconds.
      Returns:
      this time.

    • getAdjacencies

      public Set<Edge> getAdjacencies()
      Returns The edges of the searched graph.
      Returns:
      This set.

    • getNonadjacencies

      public Set<Edge> getNonadjacencies()
      Returns the non-adjacencies of the searched graph.
      Returns:
      This set.

    • getNumIndependenceTests

      public int getNumIndependenceTests()
      Returns the number of independence tests performed in the search.
      Returns:
      This number.

    • getNodes

      public List<Node> getNodes()
      Returns the nodes of the search graph.
      Returns:
      This list.

    • setVerbose

      public void setVerbose(boolean verbose)
      Sets whether verbose output should be given.
      Parameters:
      verbose - True iff the case.

    • setStable

      public void setStable(boolean stable)
      Sets whether the stable adjacency search should be used.
      Parameters:
      stable - True iff the case.

    • setUseMaxP

      public void setUseMaxP(boolean useMaxP)
      Sets whether the max p method should be used in the adjacency searc h.
      Parameters:
      useMaxP - iff the case.

    • setMaxPPathLength

      public void setMaxPPathLength(int maxPPathLength)
      Sets the maximum path length for the PC heuristic.
      Parameters:
      maxPPathLength - this length.