Class Boss
- All Implemented Interfaces:
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:
- Start with an arbitrary ordering.
- Run the permutation search to find a better ordering.
- Project this ordering to a CPDAG.
- Optionally, Run BES this CPDAG.
- 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 Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptiongetBics()
The map from nodes to parents resulting from the search.getScore()
The score being used.getTimes()
The list of all variables, in order.void
searchSuborder
(List<Node> prefix, List<Node> suborder, Map<Node, GrowShrinkTree> gsts) Searches the suborder.void
setKnowledge
(Knowledge knowledge) The knowledge being used.void
setNumStarts
(int numStarts) Sets the number of random starts to use.void
setNumThreads
(int numThreads) void
setResetAfterBM
(boolean reset) void
setResetAfterRS
(boolean reset) void
setUseBes
(boolean use) Sets up BOSS to use the BES algorithm to render BOSS correct under the faithfulness assumption.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.void
setVerbose
(boolean verbose)
-
Constructor Details
-
Boss
This algorithm will work with an arbitrary BIC score.- Parameters:
score
- The Score to use.
-
-
Method Details
-
searchSuborder
Description copied from interface:SuborderSearch
Searches the suborder.- Specified by:
searchSuborder
in interfaceSuborderSearch
- 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
Description copied from interface:SuborderSearch
The knowledge being used.- Specified by:
setKnowledge
in interfaceSuborderSearch
- 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) -
setResetAfterRS
public void setResetAfterRS(boolean reset) -
setVerbose
public void setVerbose(boolean verbose) -
setNumThreads
public void setNumThreads(int numThreads) -
getVariables
Description copied from interface:SuborderSearch
The list of all variables, in order. They should satisfy the suborder requirements.- Specified by:
getVariables
in interfaceSuborderSearch
- Returns:
- This list.
- See Also:
-
getParents
Description copied from interface:SuborderSearch
The map from nodes to parents resulting from the search.- Specified by:
getParents
in interfaceSuborderSearch
- Returns:
- This map.
-
getScore
Description copied from interface:SuborderSearch
The score being used.- Specified by:
getScore
in interfaceSuborderSearch
- Returns:
- This score.
- See Also:
-
getBics
-
getTimes
-
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
-