Package edu.cmu.tetrad.search

Class Boss

java.lang.Object
edu.cmu.tetrad.search.Boss
All Implemented Interfaces:
SuborderSearch
public class Boss extends Object implements SuborderSearch
Implements Best Order Score Search (BOSS). The reference is this:

Andrews, B., Ramsey, J., Sanchez Romero, R., Camchong, J., & Kummerfeld, E. (2024). Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score Search and Grow Shrink Trees. Advances in Neural Information Processing Systems, 36.

The BOSS algorithm is based on the idea that implied DAGs for permutations are most optimal in their BIC scores when the variables in the permutations are ordered so that that causes in the models come before effects for some DAG in the true Markov equivalence class.

This algorithm is implemented as a "plugin-in" algorithm to a PermutationSearch object (see), which deals with certain details of knowledge handling that are common to different permutation searches.

BOSS, like GRaSP (see), is characterized by high adjacency and orientation precision (especially) and recall for moderate sample sizes.

The algorithm works as follows:

  1. Start with an arbitrary ordering.
  2. Run the permutation search to find a better ordering.
  3. Project this ordering to a CPDAG.
  4. Optionally, Run BES this CPDAG.
  5. Return this CPDAG.

The optional BES step is needed for correctness, though with large models this has very little effect on the output, since nearly all edges are already oriented, so a parameter is included to turn that step off.

Knowledge can be used with this search. If tiered knowledge is used, then the procedure is carried out for each tier separately, given the variables preceding that tier, which allows the Boss algorithm to address tiered (e.g., time series) problems with larger numbers of variables. However, knowledge of required and forbidden edges is correctly implemented for arbitrary such knowledge.

A parameter is included to restart the search a certain number of times. The idea is that the goal is to optimize a BIC score, so if several runs are done of the algorithm for the same data, the model with the highest BIC score should be returned and the others ignored.

Version:
$Id: $Id
Author:
bryanandrews, josephramsey
See Also:

  • Constructor Details

    • Boss

      public Boss(Score score)
      This algorithm will work with an arbitrary BIC score.
      Parameters:
      score - The Score to use.

  • Method Details

    • searchSuborder

      public void searchSuborder(List<Node> prefix, List<Node> suborder, Map<Node,GrowShrinkTree> gsts)
      Searches a suborder of the variables. The prefix is the set of variables that must precede the suborder. The suborder is the set of variables to be ordered. The gsts is a map from variables to GrowShrinkTrees, which are used to cache scores for the variables. The searchSuborder method will update the suborder to be the best ordering found.
      Specified by:
      searchSuborder in interface SuborderSearch
      Parameters:
      prefix - The prefix of the suborder.
      suborder - The suborder.
      gsts - The GrowShrinkTree being used to do caching of scores.
      See Also:

    • setUseBes

      public void setUseBes(boolean use)
      Sets up BOSS to use the BES algorithm to render BOSS correct under the faithfulness assumption.
      Parameters:
      use - True if BES should be used.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge to be used for the search.
      Specified by:
      setKnowledge in interface SuborderSearch
      Parameters:
      knowledge - This knowledge.
      See Also:

    • setNumStarts

      public void setNumStarts(int numStarts)
      Sets the number of random starts to use. The model with the best score from these restarts will be reported.
      Parameters:
      numStarts - The number of random starts to use.

    • setResetAfterBM

      public void setResetAfterBM(boolean reset)
      Sets whether the grow-shrink trees should be reset after each best-mutation step.
      Parameters:
      reset - True if so.

    • setResetAfterRS

      public void setResetAfterRS(boolean reset)
      Sets whether the grow-shrink trees should be reset after each restart.
      Parameters:
      reset - True if so.

    • setVerbose

      public void setVerbose(boolean verbose)
      Sets whether verbose output should be printed.
      Parameters:
      verbose - True if so.

    • setNumThreads

      public void setNumThreads(int numThreads)
      Sets the number of threads to use.
      Parameters:
      numThreads - The number of threads to use. Must be at least 1.

    • getVariables

      public List<Node> getVariables()
      Returns the variables.
      Specified by:
      getVariables in interface SuborderSearch
      Returns:
      This list.
      See Also:

    • getParents

      public Map<Node,Set<Node>> getParents()
      Returns the map from nodes to the sets of their parents.
      Specified by:
      getParents in interface SuborderSearch
      Returns:
      This map.

    • getScore

      public Score getScore()
      Returns the score being used for the search.
      Specified by:
      getScore in interface SuborderSearch
      Returns:
      This score.
      See Also:

    • getBics

      public List<Double> getBics()
      Returns the BIC scores.
      Returns:
      This list.

    • getTimes

      public List<Double> getTimes()
      Returns the times.
      Returns:
      This list.

    • setUseDataOrder

      public void setUseDataOrder(boolean useDataOrder)
      True if the order of the variables in the data should be used for an initial best-order search, false if a random permutation should be used. (Subsequence automatic best order runs will use random permutations.) This is included so that the algorithm will be capable of outputting the same results with the same data without any randomness.
      Parameters:
      useDataOrder - True if so