Package edu.cmu.tetrad.search

Class FgesMb

java.lang.Object

edu.cmu.tetrad.search.FgesMb

All Implemented Interfaces:

DagScorer

public final class FgesMb
extends Object
implements DagScorer

Implements the Fast Greedy Equivalence Search (FGES) algorithm. This is an implementation of the Greedy Equivalence Search algorithm, originally due to Chris Meek but developed significantly by Max Chickering. FGES uses with some optimizations that allow it to scale accurately to thousands of variables accurately for the sparse case. The reference for FGES is this:

Ramsey, J., Glymour, M., Sanchez-Romero, R., & Glymour, C. (2017). A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images. International journal of data science and analytics, 3, 121-129.

The reference for Chickering's GES is this:

Chickering (2002) "Optimal structure identification with greedy search" Journal of Machine Learning Research.

FGES works for the continuous case, the discrete case, and the mixed continuous/discrete case, so long as a BIC score is available for the type of data in question.

To speed things up, it has been assumed that variables X and Y with zero correlation do not correspond to edges in the graph. This is a restricted form of the heuristic speedup assumption, something GES does not assume. This heuristic speedup assumption needs to be explicitly turned on using setHeuristicSpeedup(true).

Also, edges to be added or remove from the graph in the forward or backward phase, respectively are cached, together with the ancillary information needed to do the additions or removals, to reduce rescoring.

A number of other optimizations were also. See code for details.

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

Version:

$Id: $Id

Author:

Ricardo Silva, josephramsey

See Also:

• Grasp
• Boss
• Sp
• Knowledge

Constructor Summary

Constructors

Constructor	Description
FgesMb(Score score)	Constructor.

Method Summary

Modifier and Type	Method	Description
long	getElapsedTime()	Returns the elapsed time of the search.
Knowledge	getKnowledge()	Returns the background knowledge.
int	getMaxDegree()	The maximum of parents any nodes can have in the output pattern.
double	getModelScore()	Returns the score of the final search model.
PrintStream	getOut()	Returns the output stream associated with this object.
double	scoreDag(Graph dag)	Scores the given directed acyclic graph (DAG).
Graph	search(List<Node> targets)	Greedy equivalence search: Start from the empty graph, add edges till the model is significant.
void	setBoundGraph(Graph boundGraph)	If non-null, edges not adjacent in this graph will not be added.
void	setFaithfulnessAssumed(boolean faithfulnessAssumed)	Sets whether one-edge faithfulness should be assumed.
void	setInitialGraph(Graph initialGraph)	Sets the initial graph for the software.
void	setKnowledge(Knowledge knowledge)	Sets the background knowledge.
void	setMaxDegree(int maxDegree)	The maximum of parents any nodes can have in the output pattern.
void	setNumExpansions(int numExpansions)	Sets the number of expansions for a given object.
void	setOut(PrintStream out)	Sets the output stream that output (except for log output) should be sent to.
void	setParallelized(boolean parallelized)	Sets the parallelized flag of the object.
void	setSymmetricFirstStep(boolean symmetricFirstStep)	Sets whether the first step of the procedure will score both X->Y and Y->X and prefer the higher score (for adding X--Y to the graph).
void	setTrimmingStyle(int trimmingStyle)	Sets the trimming style for the algorithm.
void	setVerbose(boolean verbose)	Sets whether verbose output should be produced.

Methods inherited from class java.lang.Object

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

Constructor Details

FgesMb

public FgesMb(Score score)

Constructor. Construct a Score and pass it in here. The totalScore should return a positive value in case of conditional dependence and a negative values in case of conditional independence. See Chickering (2002), locally consistent scoring criterion. This by default uses all the processors on the machine.

Parameters:

score - The score to use. The score should yield better scores for more correct local models. The algorithm as given by Chickering assumes the score will be a BIC score of some sort.

Method Details

setTrimmingStyle

public void setTrimmingStyle(int trimmingStyle)

Sets the trimming style for the algorithm.

Parameters:

trimmingStyle - The trimming style to be set. It represents how edges are trimmed during the search. The valid values are: - 0: No trimming. All edges are considered during the search. - 1: Forward trimming. Edges are trimmed only during the forward search phase. - 2: Backward trimming. Edges are trimmed only during the backward search phase.

search

public Graph search(List<Node> targets)
             throws InterruptedException

Greedy equivalence search: Start from the empty graph, add edges till the model is significant. Then start deleting edges till a minimum is achieved.

Parameters:

targets - a List object

Returns:

the resulting Pattern.

Throws:

InterruptedException

setFaithfulnessAssumed

public void setFaithfulnessAssumed(boolean faithfulnessAssumed)

Sets whether one-edge faithfulness should be assumed. This assumption is that if X and Y are unconditionally dependent, then there is an edge between X and Y in the graph. This could in principle be false, as for a path cancellation whether one path is A->B->C->D and the other path is A->D.

Parameters:

faithfulnessAssumed - True, if so.

getKnowledge

public Knowledge getKnowledge()

Returns the background knowledge.

Returns:

This knowledge

setKnowledge

public void setKnowledge(Knowledge knowledge)

Sets the background knowledge.

Parameters:

knowledge - the knowledge object, specifying forbidden and required edges.

getElapsedTime

public long getElapsedTime()

Returns the elapsed time of the search.

Returns:

This elapsed time.

scoreDag

public double scoreDag(Graph dag)

Scores the given directed acyclic graph (DAG).

Specified by:

scoreDag in interface DagScorer

Parameters:

dag - The directed acyclic graph to be scored. Must be of type Graph.

Returns:

The score of the DAG.

setVerbose

public void setVerbose(boolean verbose)

Sets whether verbose output should be produced. Verbose output generated by the Meek rules is treated separately.

Parameters:

verbose - True iff the case.

getOut

public PrintStream getOut()

Returns the output stream associated with this object.

Returns:

the output stream

setOut

public void setOut(PrintStream out)

Sets the output stream that output (except for log output) should be sent to. By default System.out.

Parameters:

out - This print stream.

setBoundGraph

public void setBoundGraph(Graph boundGraph)

If non-null, edges not adjacent in this graph will not be added.

Parameters:

boundGraph - This bound graph.

getMaxDegree

public int getMaxDegree()

The maximum of parents any nodes can have in the output pattern.

Returns:

-1 for unlimited.

setMaxDegree

public void setMaxDegree(int maxDegree)

The maximum of parents any nodes can have in the output pattern.

Parameters:

maxDegree - -1 for unlimited.

setSymmetricFirstStep

public void setSymmetricFirstStep(boolean symmetricFirstStep)

Sets whether the first step of the procedure will score both X->Y and Y->X and prefer the higher score (for adding X--Y to the graph).

Parameters:

symmetricFirstStep - True iff the case.

getModelScore

public double getModelScore()

Returns the score of the final search model.

Returns:

This score.

setParallelized

public void setParallelized(boolean parallelized)

Sets the parallelized flag of the object.

Parameters:

parallelized - the value indicating whether the object should be parallelized

setInitialGraph

public void setInitialGraph(Graph initialGraph)

Sets the initial graph for the software.

Parameters:

initialGraph - the initial graph to be set

setNumExpansions

public void setNumExpansions(int numExpansions)

Sets the number of expansions for a given object.

Parameters:

numExpansions - the number of expansions to set. Must be at least 1.

Throws:

IllegalArgumentException - if the number of expansions is less than 1.