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

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

Author:
Ricardo Silva, josephramsey
See Also:

  • 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()
      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.

    • 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)
      Specified by:
      scoreDag in interface DagScorer
      Returns:
      the score of the given DAG, up to a constant.

    • 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.
      See Also:

    • setMeekVerbose

      public void setMeekVerbose(boolean meekVerbose)
      Sets whether verbose output should be produced for the Meek rules.
      Parameters:
      meekVerbose - True iff the case.

    • getOut

      public PrintStream getOut()
      Returns:
      the output stream that output (except for log output) should be sent to.

    • 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)

    • setInitialGraph

      public void setInitialGraph(Graph initialGraph)