Package edu.cmu.tetrad.search

Class TsFges2

java.lang.Object
edu.cmu.tetrad.search.TsFges2
All Implemented Interfaces:
GraphScorer, GraphSearch
public final class TsFges2 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, Daniel Malinsky

  • Constructor Details

    • TsFges2

      public TsFges2(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.

  • Method Details

    • setFaithfulnessAssumed

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

    • isFaithfulnessAssumed

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

    • 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.
      Parameters:
      knowledge - the knowledge object, specifying forbidden and required edges.

    • getElapsedTime

      public long getElapsedTime()

    • 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 totalScore of the given DAG, up to a constant.

    • getTopGraphs

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

    • getnumCPDAGsToStore

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

    • setNumCPDAGsToStore

      public void setNumCPDAGsToStore(int numCPDAGsToStore)
      Sets the number of patterns to store. This should be set to zero for fast 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.

    • getCycleBound

      public int getCycleBound()
      A bound on cycle length.

    • setCycleBound

      public void setCycleBound(int cycleBound)
      A bound on cycle length.
      Parameters:
      cycleBound - The bound, >= 1, or -1 for unlimited.

    • setParallelism

      public void setParallelism(int numProcessors)
      Creates a new processors pool with the specified number of threads.

    • setBoundGraph

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

    • getPenaltyDiscount

      public double getPenaltyDiscount()
      Deprecated.
      Use the getters on the individual scores instead.
      For BIC totalScore, a multiplier on the penalty term. For continuous searches.

    • setSamplePrior

      public void setSamplePrior(double samplePrior)
      Deprecated.
      Use the setters on the individual scores instead.

    • setStructurePrior

      public void setStructurePrior(double expectedNumParents)
      Deprecated.
      Use the setters on the individual scores instead.

    • setPenaltyDiscount

      public void setPenaltyDiscount(double penaltyDiscount)
      Deprecated.
      Use the setters on the individual scores instead.
      For BIC totalScore, a multiplier on the penalty term. For continuous searches.

    • getMaxIndegree

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

    • setMaxIndegree

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

    • getMinChunk

      public int getMinChunk(int n)

    • getModelScore

      public double getModelScore()

    • scoreDag

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

    • logEdgeBayesFactorsString

      public String logEdgeBayesFactorsString(Graph dag)

    • logEdgeBayesFactors

      public Map<Edge,Double> logEdgeBayesFactors(Graph dag)

    • getNameNoLag

      public String getNameNoLag(Object obj)

    • addSimilarEdges

      public void addSimilarEdges(Node x, Node y)

    • removeSimilarEdges

      public void removeSimilarEdges(Node x, Node y)