Package edu.cmu.tetrad.search

Class Fges

java.lang.Object

edu.cmu.tetrad.search.Fges

All Implemented Interfaces:

IGraphSearch, DagScorer

public final class Fges
extends Object
implements IGraphSearch, 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 de tails.

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
Fges(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 used for printing.
double	scoreDag(Graph dag)	Scores a Directed Acyclic Graph (DAG) based on its structure.
Graph	search()	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 application.
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	setNumThreads(int numThreads)	Sets the number of threads to use.
void	setOut(PrintStream out)	Sets the output stream that output (except for log output) should be sent to.
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	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

Fges

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

search

public Graph search()
             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.

Specified by:

search in interface IGraphSearch

Returns:

the resulting Pattern.

Throws:

InterruptedException - if any.

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 a Directed Acyclic Graph (DAG) based on its structure.

Specified by:

scoreDag in interface DagScorer

Parameters:

dag - The input DAG to be scored.

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 used for printing.

Returns:

the output stream used for printing.

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.

setNumThreads

public void setNumThreads(int numThreads)

Sets the number of threads to use. By default, the number of threads is 1.

Parameters:

numThreads - The number of threads to use. Must be at least 1.

setInitialGraph

public void setInitialGraph(Graph initialGraph)

Sets the initial graph for the application.

Parameters:

initialGraph - the initial graph to be set