Package edu.cmu.tetrad.search

Class Cpc

java.lang.Object

edu.cmu.tetrad.search.Cpc

All Implemented Interfaces:

IGraphSearch

public final class Cpc
extends Object
implements IGraphSearch

Implements a convervative version of PC, in which the Markov condition is assumed but faithfulness is tested locally. The reference is here:

Ramsey, J., Zhang, J., & Spirtes, P. L. (2012). Adjacency-faithfulness and conservative causal inference. arXiv preprint arXiv:1206.6843.

Conservative triple orientation is a method for orienting unshielded triples X*-*Y*-*Z as one of the following: (a) Collider, X->Y<-Z, (b) Noncollider, X-->Y-->Z, or X<-Y<-Z, or X<-Y->Z, (c) ambiguous between (a) or (b). 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, then lists all of these subsets conditional on which X and Z are *independent*, then looks thoough this list to see if Y is in them. If Y is in all of these subset, the triple is judged to be a noncollider; if it is in none of these subsets, the triple is judged to be a collider, and if it is in some of these subsets and not in others of the subsets, then it is judged to be ambiguous.

Ambiguous triple are marked in the final graph using an underline, and the final graph is called an "e-pattern", and represents a collection of CPDAGs. To find an element of this collection, one first needs to choose for each ambiguous triple whether it should be a collider or a noncollider and then run the Meek rules given the result of these decisions.

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:

josephramsey (this version).

See Also:

• Pc
• Knowledge
• MeekRules

Constructor Summary

Constructors

Constructor	Description
Cpc(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}.
Graph	search()	Runs CPC starting with a fully connected graph over all the variables in the domain of the independence test.
void	setConflictRule(PcCommon.ConflictRule conflictRule)	Sets which conflict rule to use for resolving collider orientation conflicts.
void	setDepth(int depth)	Sets the maximum number of variables conditioned on in any conditional independence test.
void	setGuaranteeCpdag(boolean guaranteeCpdag)	Sets to true just in case the algorithm should guarantee that the output is consistent with a CPDAG, i.e., no bidirected edges and no actual or implied cycles.
void	setKnowledge(Knowledge knowledge)	Sets the knowledge specification 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	setVerbose(boolean verbose)	Sets whether verbose output should be printed.

Methods inherited from class java.lang.Object

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

Constructor Details

Cpc

public Cpc(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

search

public Graph search()
             throws InterruptedException

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.

Throws:

InterruptedException - if any.

setGuaranteeCpdag

public void setGuaranteeCpdag(boolean guaranteeCpdag)

Sets to true just in case the algorithm should guarantee that the output is consistent with a CPDAG, i.e., no bidirected edges and no actual or implied cycles.

Parameters:

guaranteeCpdag - True, if so.

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.

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.

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.

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

Parameters:

conflictRule - The rule.

See Also:

• PcCommon.ConflictRule

setPcHeuristicType

public void setPcHeuristicType(PcCommon.PcHeuristicType pcHeuristicType)

Sets the PC heuristic type. Default = NONE.

Parameters:

pcHeuristicType - The type.

See Also:

• PcCommon.PcHeuristicType