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:

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