Package edu.cmu.tetrad.search

Class FgesOrienter

java.lang.Object
edu.cmu.tetrad.search.FgesOrienter
All Implemented Interfaces:
GraphScorer, GraphSearch, Reorienter
public final class FgesOrienter extends Object implements GraphSearch, GraphScorer, Reorienter
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 faithfulness assumption, something GES does not assume. This faithfulness 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

This Orients a given undirected graph such that the edges in the graph are a superset of the edges in the oriented graph, AJ Sedgewick, 5/2015

  • Constructor Details

    • FgesOrienter

      public FgesOrienter(DataSet dataSet)
      The data set must either be all continuous or all discrete.

  • Method Details

    • orient

      public void orient(Graph graph)
      Description copied from interface: Reorienter
      Globally reorients the graph.
      Specified by:
      orient in interface Reorienter

    • setFaithfulnessAssumed

      public void setFaithfulnessAssumed(boolean faithfulness)
      Set to true if it is assumed that all path pairs with one length 1 path do not cancelAll.

    • isFaithfulnessAssumed

      public boolean isFaithfulnessAssumed()
      Returns:
      true if it is assumed that all path pairs with one length 1 path do not cancelAll.

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

    • getKnowledge

      public Knowledge getKnowledge()
      Returns:
      the background knowledge.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the background knowledge.
      Specified by:
      setKnowledge in interface Reorienter
      Parameters:
      knowledge - the knowledge object, specifying forbidden and required edges.

    • setStructurePrior

      public void setStructurePrior(double structurePrior)
      For BDeu score for discrete search; see Chickering (2002).

    • setSamplePrior

      public void setSamplePrior(double samplePrior)
      For BDeu score for discrete search; see Chickering (2002).

    • getElapsedTime

      public long getElapsedTime()

    • getPenaltyDiscount

      public double getPenaltyDiscount()
      For BIC score, a multiplier on the penalty term. For continuous searches.

    • setPenaltyDiscount

      public void setPenaltyDiscount(double penaltyDiscount)
      For BIC score, a multiplier on the penalty term. For continuous searches.

    • setTrueGraph

      public void setTrueGraph(Graph trueGraph)
      If the true graph is set, askterisks will be printed in log output for the true edges.

    • getScore

      public double getScore(Graph dag)
      Returns:
      the score of the given DAG, up to a constant.

    • getTopGraphs

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

    • getnumCPDAGsToStore

      public int getnumCPDAGsToStore()
      Returns:
      the number of CPDAGs to store.

    • getDiscreteScore

      public LocalDiscreteScore getDiscreteScore()
      Returns:
      the discrete scoring function being used. By default, BDeu.

    • setDiscreteScore

      public void setDiscreteScore(LocalDiscreteScore discreteScore)
      Sets the discrete scoring function to use.

    • isLog

      public boolean isLog()
      True iff log output should be produced.

    • setLog

      public void setLog(boolean log)
      Sets whether log output should be produced. Set to false a faster search.

    • getExternalGraph

      public Graph getExternalGraph()
      Returns:
      the initial graph for the search. The search is initialized to this graph and proceeds from there.

    • setExternalGraph

      public void setExternalGraph(Graph externalGraph)
      Sets the initial graph.

    • setVerbose

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

    • setOut

      public void setOut(PrintStream out)
      Sets the output stream that output (except for log output) should be sent to. By detault System.out.

    • getOut

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

    • getAdjacencies

      public Graph getAdjacencies()
      Returns:
      the set of preset adjacenies for the algorithm; edges not in this adjacencies graph will not be added.

    • setAdjacencies

      public void setAdjacencies(Graph adjacencies)
      Sets the set of preset adjacenies for the algorithm; edges not in this adjacencies graph will not be added.

    • getDepth

      public int getDepth()
      Returns:
      the depth for the forward reevaluation step.

    • setDepth

      public void setDepth(int depth)
      -1 for unlimited depth, otherwise a number >= 0. In the forward reevaluation step, subsets of neighbors up to depth in size are considered. Limiting depth can speed up the algorithm.

    • scoreDag

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