Package edu.cmu.tetrad.search

Class PcMax

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

Modifies the PC algorithm to use the Max P rule for orienting ushielded colliders. The reference is this:

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

Max-P triple orientation is a method for orienting unshielded triples X*=-*Y*-*Z as one of the following: (a) Collider, X->Yinvalid input: '<'-Z, or (b) Noncollider, X-->Y-->Z, or Xinvalid input: '<'-Yinvalid input: '<'-Z, or Xinvalid input: '<'-Y->Z. One does this by conditioning on subsets of adj(X) or adj(Z). One first checks conditional independence of X and Z conditional on each of these subsets, and lists the p-values for each test. Then, one chooses the conditioning set out of all of these that maximizes the p-value. If this conditioning set contains Y, then the triple is judged to be a noncollider; otherwise, it is judged to be a collider.

All unshielded triples in the graph supplied by FAS are oriented using this procedure, and then the Meek orientation rules are applied to generate the final CPDAG.

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

Author:
josephramsey.
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    PcMax(IndependenceTest independenceTest)
    Constructs a CPC algorithm that uses the given independence test as oracle.

  • Method Summary

    Modifier and Type
    Method
    Description
    Set<Edge>
    getAdjacencies()
    Returns the edges in the search graph as a set of undirected edges.
    Set<Triple>
    getAmbiguousTriples()
    Returns the set of ambiguous triples found during the most recent run of the algorithm.
    int
    getDepth()
    Returns the depth of the search--that is, the maximum number of variables conditioned on in any conditional independence test.
    long
    getElapsedTime()
    Returns the elapsed time of search in milliseconds, after search() has been run.
    Graph
    getGraph()
    The graph that's constructed during the search.
    IndependenceTest
    getIndependenceTest()
    Rreturn the independence test used in the search, set in the constructor.
    Knowledge
    getKnowledge()
    Returns the knowledge specification used in the search.
    SepsetMap
    getSepsets()
    Returns a map for x _||_ y | z1,..,zn from {x, y} to {z1,...,zn}.
    boolean
    isAggressivelyPreventCycles()
    Returns true just in case edges will not be added if they would create cycles.
    Graph
    search()
    Runs CPC starting with a fully connected graph over all the variables in the domain of the independence test.
    void
    setAggressivelyPreventCycles(boolean aggressivelyPreventCycles)
    Sets to true just in case edges will not be added if they would create cycles.
    void
    setDepth(int depth)
    Sets the maximum number of variables conditioned on in any conditional independence test.
    void
    setKnowledge(Knowledge knowledge)
    Sets the knowledge specification used in the search.
    void
    setMaxPPathLength(int maxPPathLength)
    Sets the max path length for the max p heuristic.
    void
    setStable(boolean stable)
    Sets whether the stable FAS search should be used.
    void
    setUseHeuristic(boolean useHeuristic)
    Sets whether the heuristic should be used for max p.
    void
    setVerbose(boolean verbose)
    Sets whether verbose output should be printed.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • PcMax

      public PcMax(IndependenceTest independenceTest)
      Constructs a CPC algorithm that uses the given independence test as oracle. This does not make a copy of the independence test, for fear of duplicating the data set!
      Parameters:
      independenceTest - The test to user for oracle conditional independence information.

  • Method Details

    • isAggressivelyPreventCycles

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

    • setAggressivelyPreventCycles

      public void setAggressivelyPreventCycles(boolean aggressivelyPreventCycles)
      Sets to true just in case edges will not be added if they would create cycles.
      Parameters:
      aggressivelyPreventCycles - True if so.

    • setDepth

      public void setDepth(int depth)
      Sets the maximum number of variables conditioned on in any conditional independence test. If set to -1, the value of 1000 will be used. May not be set to Integer.MAX_VALUE, due to a Java bug on multicore systems.
      Parameters:
      depth - This maximum.

    • getElapsedTime

      public long getElapsedTime()
      Returns the elapsed time of search in milliseconds, after search() has been run.
      Returns:
      This time.

    • 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 used in the search. Non-null.
      Parameters:
      knowledge - This knowledge.

    • getIndependenceTest

      public IndependenceTest getIndependenceTest()
      Rreturn the independence test used in the search, set in the constructor.
      Returns:
      This.

    • getDepth

      public int getDepth()
      Returns the depth of the search--that is, the maximum number of variables conditioned on in any conditional independence test.
      Returns:
      This.

    • getAmbiguousTriples

      public Set<Triple> getAmbiguousTriples()
      Returns the set of ambiguous triples found during the most recent run of the algorithm. Non-null after a call to search().
      Returns:
      This set.

    • getAdjacencies

      public Set<Edge> getAdjacencies()
      Returns the edges in the search graph as a set of undirected edges.
      Returns:
      These edges.

    • search

      public Graph search()
      Runs CPC starting with a fully connected graph over all the variables in the domain of the independence test. See PC for caveats. The number of possible cycles and bidirected edges is far less with CPC than with PC.
      Specified by:
      search in interface IGraphSearch
      Returns:
      The e-pattern for the search, which is a graphical representation of a set of possible CPDAGs.

    • getSepsets

      public SepsetMap getSepsets()
      Returns a map for x _||_ y | z1,..,zn from {x, y} to {z1,...,zn}.
      Returns:
      This map.

    • getGraph

      public Graph getGraph()
      The graph that's constructed during the search.
      Returns:
      This graph.

    • setVerbose

      public void setVerbose(boolean verbose)
      Sets whether verbose output should be printed.
      Parameters:
      verbose - True if so.

    • setStable

      public void setStable(boolean stable)
      Sets whether the stable FAS search should be used.
      Parameters:
      stable - True if so.

    • setUseHeuristic

      public void setUseHeuristic(boolean useHeuristic)
      Sets whether the heuristic should be used for max p.
      Parameters:
      useHeuristic - True if so.

    • setMaxPPathLength

      public void setMaxPPathLength(int maxPPathLength)
      Sets the max path length for the max p heuristic.
      Parameters:
      maxPPathLength - This length.