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 Peter/Clark (PC) 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. A 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."

See setter methods for "knobs" you can turn to control the output of PC and their defaults.

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

Version:
$Id: $Id
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.
    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.
    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, Set<Node> nodes)
    Runs the search using a particular implementation of the fast adjacency search (FAS), over the given sublist of nodes.
    Graph
    search(Set<Node> nodes)
    Runs PC starting with a complete graph over the given list of nodes, using the given independence test and knowledge and returns the resultant graph.
    void
    setConflictRule(PcCommon.ConflictRule conflictRule)
    Sets which conflict-rule to use for resolving collider orientation conflicts.
    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
    setMeekPreventCycles(boolean meekPreventCycles)
    Sets whether cycles should be checked.
    void
    setPcHeuristicType(PcCommon.PcHeuristicType pcHeuristicType)
    Sets the PC heuristic type.
    void
    setStable(boolean stable)
    Sets whether the stable adjacency search should be used.
    void
    setUseMaxPHeuristic(boolean useMaxPHeuristic)
    Sets whether the max-p heuristic should be used for collider discovery.
    void
    setVerbose(boolean verbose)
    Sets whether verbose output should be given.

    Methods inherited from class java.lang.Object

    equals, 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

    • 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 discovered graph.
      See Also:

    • search

      public Graph search(Set<Node> nodes)
      Runs PC starting with a complete 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 domain 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, Set<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:

    • setMeekPreventCycles

      public void setMeekPreventCycles(boolean meekPreventCycles)
      Sets whether cycles should be checked.
      Parameters:
      meekPreventCycles - Set to true just in case edges will not be added if they 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. Default is 1000.
      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 multicore machines.

    • 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.

    • setVerbose

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

    • setStable

      public void setStable(boolean stable)
      Sets whether the stable adjacency search should be used. Default is false. Default is false. See the following reference for this:

      Colombo, D., & Maathuis, M. H. (2014). Order-independent constraint-based causal structure learning. J. Mach. Learn. Res., 15(1), 3741-3782.

      Parameters:
      stable - True iff the case.

    • setConflictRule

      public void setConflictRule(PcCommon.ConflictRule conflictRule)
      Sets which conflict-rule to use for resolving collider orientation conflicts. Default is ConflictRule.PRIORITIZE_EXISTING.
      Parameters:
      conflictRule - The rule.
      See Also:

    • setUseMaxPHeuristic

      public void setUseMaxPHeuristic(boolean useMaxPHeuristic)
      Sets whether the max-p heuristic should be used for collider discovery. Default is true. See the following reference for this:

      Ramsey, J. (2016). Improving the accuracy and scalability of the pc algorithm by maximizing p-value. arXiv preprint arXiv:1610.00378.

      Parameters:
      useMaxPHeuristic - True, if so.

    • setPcHeuristicType

      public void setPcHeuristicType(PcCommon.PcHeuristicType pcHeuristicType)
      Sets the PC heuristic type. Default = PcHeuristicType.NONE.
      Parameters:
      pcHeuristicType - The type.
      See Also: