Package edu.cmu.tetrad.search

Class Fges

java.lang.Object
edu.cmu.tetrad.search.Fges
All Implemented Interfaces:
GraphScorer, GraphSearch
public final class Fges extends Object implements GraphSearch, GraphScorer
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 for caching sufficient statistics, for instance.

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 heuristicSpeedup assumption, something GES does not assume. This 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 Details

    • Fges

      public Fges(Score 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. This by default uses all the processors on the machine.

  • Method Details

    • setFaithfulnessAssumed

      public void setFaithfulnessAssumed(boolean faithfulnessAssumed)

    • search

      public Graph search()
      Greedy equivalence search: Start from the empty graph, add edges till model is significant. Then start deleting edges till a minimum is achieved.
      Specified by:
      search in interface GraphSearch
      Returns:
      the resulting Pattern.

    • getKnowledge

      public Knowledge getKnowledge()
      Returns:
      the background 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()

    • scoreDag

      public double scoreDag(Graph dag)
      Specified by:
      scoreDag in interface GraphScorer
      Returns:
      the totalScore of the given DAG, up to a constant.

    • getTopGraphs

      public LinkedList<ScoredGraph> getTopGraphs()
      Returns:
      the list of top scoring graphs.

    • setInitialGraph

      public void setInitialGraph(Graph initialGraph)
      Sets the initial graph.

    • setVerbose

      public void setVerbose(boolean verbose)
      Sets whether verbose output should be produced.

    • setMeekVerbose

      public void setMeekVerbose(boolean meekVerbose)
      Sets whether verbose output should be produced.

    • 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 detault System.out.

    • setBoundGraph

      public void setBoundGraph(Graph boundGraph)
      If non-null, edges not adjacent in this graph will not be added.

    • getMaxDegree

      public int getMaxDegree()
      The maximum of parents any nodes can have in output pattern.
      Returns:
      -1 for unlimited.

    • setMaxDegree

      public void setMaxDegree(int maxDegree)
      The maximum of parents any nodes can have in output pattern.
      Parameters:
      maxDegree - -1 for unlimited.

    • setSymmetricFirstStep

      public void setSymmetricFirstStep(boolean symmetricFirstStep)

    • logEdgeBayesFactorsString

      public String logEdgeBayesFactorsString(Graph dag)

    • setParallelized

      public void setParallelized(boolean parallelized)