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:

• Fci
• Knowledge

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.
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	setGuaranteeCpdag(boolean guaranteeCpdag)	Sets whether cycles should be checked.
void	setKnowledge(Knowledge knowledge)	Sets the knowledge specification to be used in the search.
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()
             throws InterruptedException

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.

Throws:

InterruptedException - if any.

See Also:

• Fci

search

public Graph search(Set<Node> nodes)
             throws InterruptedException

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.

Throws:

InterruptedException

See Also:

• search()

search

public Graph search(IFas fas,
 Set<Node> nodes)
             throws InterruptedException

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

Throws:

InterruptedException

See Also:

• search()
• IFas

setGuaranteeCpdag

public void setGuaranteeCpdag(boolean guaranteeCpdag)

Sets whether cycles should be checked.

Parameters:

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

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:

• PcCommon.ConflictRule

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:

• PcCommon.PcHeuristicType