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 following references are relevant:

Lam, W. Y., Andrews, B., & Ramsey, J. (2022, August). Greedy relaxations of the sparsest permutation algorithm. In Uncertainty in Artificial Intelligence (pp. 1052-1062). PMLR.

Teyssier, M., & Koller, D. (2012). Ordering-based search: A simple and effective algorithm for learning Bayesian networks. arXiv preprint arXiv:1207.1429.

Solus, L., Wang, Y., & Uhler, C. (2021). Consistency guarantees for greedy permutation-based causal inference algorithms. Biometrika, 108(4), 795-814.

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 causally--that is, so that that causes in the models come before effects in a topological order.

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. BOSS scales up currently further than GRaSP to larger variable sets and denser graphs and so is currently preferable from a practical standpoint, though performance is essentially identical.

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 is 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 time. 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.

This class is meant to be used in the context of the PermutationSearch class (see).

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)
      Description copied from interface: SuborderSearch
      Searches the suborder.
      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)
      Description copied from interface: SuborderSearch
      The knowledge being used.
      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.

    • getVariables

      public List<Node> getVariables()
      Description copied from interface: SuborderSearch
      The list of all variables, in order. They should satisfy the suborder requirements.
      Specified by:
      getVariables in interface SuborderSearch
      Returns:
      This list.
      See Also:

    • getParents

      public Map<Node,Set<Node>> getParents()
      Description copied from interface: SuborderSearch
      The map from nodes to parents resulting from the search.
      Specified by:
      getParents in interface SuborderSearch
      Returns:
      This map.

    • getScore

      public Score getScore()
      Description copied from interface: SuborderSearch
      The score being used.
      Specified by:
      getScore in interface SuborderSearch
      Returns:
      This score.
      See Also:

    • setAllowInternalRandomness

      public void setAllowInternalRandomness(boolean allowInternalRandomness)
      Sets whether to allow internal randomness in the algorithm. Some steps in the algorithm do shuffling of variables if this is set to true, to help avoid local optima. However, this randomness can lead to different results on different runs of the algorithm, which may be undesirable.
      Parameters:
      allowInternalRandomness - True if internal randomness should be allowed, false otherwise. This is false by default.