Package edu.cmu.tetrad.search.work_in_progress

Class ISFges

java.lang.Object

edu.cmu.tetrad.search.work_in_progress.ISFges

All Implemented Interfaces:

IGraphSearch

public final class ISFges
extends Object
implements IGraphSearch

GesSearch is an implementation of the GES algorithm, as specified in Chickering (2002) "Optimal structure identification with greedy search" Journal of Machine Learning Research. It works for both BayesNets and SEMs.

Some code optimization could be done for the scoring part of the graph for discrete models (method scoreGraphChange). Some of Andrew Moore's approaches to caching sufficient statistics, for instance.

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

A number of other optimizations were added 5/2015. See code for details.

Author:

Ricardo Silva, Summer 2003, Joseph Ramsey, Revisions 5/2015

Constructor Summary

Constructors

Constructor	Description
ISFges(ISScore score)	Construct a Score and pass it in here.

Method Summary

Modifier and Type	Method	Description
Graph	getAdjacencies()	Retrieves the preset adjacencies graph.
long	getElapsedTime()	Returns the elapsed time.
Knowledge	getKnowledge()	Retrieves the Knowledge instance associated with this object.
int	getMaxDegree()	The maximum of parents any nodes can have in an output pattern.
int	getMinChunk(int n)	Calculates the minimum chunk size for parallel processing.
PrintStream	getOut()	Retrieves the current PrintStream used for standard output.
double	getScore(Graph dag)	Calculates and returns the score of the provided Directed Acyclic Graph (DAG).
boolean	isFaithfulnessAssumed()	Returns the faithfulness assumption status for the current instance.
boolean	isSymmetricFirstStep()	Checks if the first step of the algorithm is symmetric.
double	scoreDag(Graph dag)	Computes the score of a given directed acyclic graph (DAG).
double	scoreDag(Graph dag, Graph pop)	Computes the score of a Directed Acyclic Graph (DAG) based on a given population graph.
Graph	search()	Greedy equivalence search: Start from the empty graph, add edges till the model is significant.
void	setAdjacencies(Graph adjacencies)	Sets the preset adjacency information for the graph.
void	setFaithfulnessAssumed(boolean faithfulnessAssumed)	Sets the faithfulness assumption status for the current instance.
void	setInitialGraph(Graph initialGraph)	Sets the initial graph, ensuring the graph's nodes match the expected variables.
void	setKnowledge(Knowledge knowledge)	Sets the background knowledge.
void	setMaxDegree(int maxDegree)	The maximum of parents any nodes can have in an output pattern.
void	setOut(PrintStream out)	Sets the output stream for this instance.
void	setParallelism(int numProcessors)	Sets the level of parallelism for the ForkJoinPool by specifying the number of processors to be used.
void	setPopulationGraph(Graph populationGraph)	Sets the population graph for the current instance.
void	setSymmetricFirstStep(boolean symmetricFirstStep)	Sets whether the first step of the algorithm should be symmetric.
void	setTrueGraph(Graph trueGraph)	Sets the true graph.
void	setVerbose(boolean verbose)	Sets the verbosity level for the application.

Methods inherited from class java.lang.Object

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

Constructor Details

ISFges

public ISFges(ISScore score)

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.

Parameters:

score - the ISScore object to be used for scoring

Method Details

isFaithfulnessAssumed

public boolean isFaithfulnessAssumed()

Returns the faithfulness assumption status for the current instance.

Returns:

true if it is assumed that all path pairs with one length 1 path do not cancel.

setFaithfulnessAssumed

public void setFaithfulnessAssumed(boolean faithfulnessAssumed)

Sets the faithfulness assumption status for the current instance.

Parameters:

faithfulnessAssumed - a boolean indicating whether faithfulness is assumed

search

public Graph search()

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.

getKnowledge

public Knowledge getKnowledge()

Retrieves the Knowledge instance associated with this object.

Returns:

the Knowledge instance associated with this object

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.

Returns:

the elapsed time in milliseconds.

setTrueGraph

public void setTrueGraph(Graph trueGraph)

Sets the true graph.

Parameters:

trueGraph - the Graph object to be set as the true graph

getScore

public double getScore(Graph dag)

Calculates and returns the score of the provided Directed Acyclic Graph (DAG).

Parameters:

dag - the DAG for which the score needs to be calculated

Returns:

the score of the given DAG

setInitialGraph

public void setInitialGraph(Graph initialGraph)

Sets the initial graph, ensuring the graph's nodes match the expected variables.

Parameters:

initialGraph - the initial graph to set. If null, does nothing. The method replaces the nodes of the graph with the expected variables and checks if they match.

Throws:

IllegalArgumentException - if the nodes of the initialGraph do not match the expected variables.

setPopulationGraph

public void setPopulationGraph(Graph populationGraph)

Sets the population graph for the current instance. The provided graph will replace the current population graph if it is not null. The method ensures that the nodes of the provided graph match the expected variables.

Parameters:

populationGraph - the graph to set as the population graph

Throws:

IllegalArgumentException - if the variables of the provided graph do not match the expected variables

setVerbose

public void setVerbose(boolean verbose)

Sets the verbosity level for the application.

Parameters:

verbose - a boolean indicating whether to enable verbose mode (true) or not (false)

getOut

public PrintStream getOut()

Retrieves the current PrintStream used for standard output.

Returns:

the PrintStream object representing the standard output stream.

setOut

public void setOut(PrintStream out)

Sets the output stream for this instance.

Parameters:

out - the PrintStream to be used for output

getAdjacencies

public Graph getAdjacencies()

Retrieves the preset adjacencies graph.

Returns:

the Graph of adjacencies.

setAdjacencies

public void setAdjacencies(Graph adjacencies)

Sets the preset adjacency information for the graph.

Parameters:

adjacencies - the graph representing adjacency relationships to be set

setParallelism

public void setParallelism(int numProcessors)

Sets the level of parallelism for the ForkJoinPool by specifying the number of processors to be used.

Parameters:

numProcessors - the number of processors to be used for parallel computations

getMaxDegree

public int getMaxDegree()

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

Returns:

-1 for unlimited.

setMaxDegree

public void setMaxDegree(int maxDegree)

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

Parameters:

maxDegree - -1 for unlimited.

isSymmetricFirstStep

public boolean isSymmetricFirstStep()

Checks if the first step of the algorithm is symmetric.

Returns:

true if the first step of the algorithm is symmetric, false otherwise.

setSymmetricFirstStep

public void setSymmetricFirstStep(boolean symmetricFirstStep)

Sets whether the first step of the algorithm should be symmetric.

Parameters:

symmetricFirstStep - true to make the first step symmetric, false otherwise.

getMinChunk

public int getMinChunk(int n)

Calculates the minimum chunk size for parallel processing.

Parameters:

n - the total number of tasks to be distributed

Returns:

the minimum chunk size which is either the result of dividing the total number of tasks by the parallelism of the pool or 100, whichever is larger

scoreDag

public double scoreDag(Graph dag)

Computes the score of a given directed acyclic graph (DAG).

Parameters:

dag - the directed acyclic graph to be scored

Returns:

the computed score of the DAG as a double

scoreDag

public double scoreDag(Graph dag,
 Graph pop)

Computes the score of a Directed Acyclic Graph (DAG) based on a given population graph. This method evaluates each node in the DAG, considering its parents and the corresponding nodes and structure in the population graph.

Parameters:

dag - The directed acyclic graph whose score is to be calculated.

pop - The population graph used as a reference for scoring the DAG.

Returns:

The cumulative score of the DAG based on the population graph.