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:

• PermutationSearch
• Grasp
• Knowledge

Constructor Summary

Constructors

Constructor	Description
Boss(Score score)	This algorithm will work with an arbitrary BIC score.

Method Summary

Modifier and Type	Method	Description
List<Double>	getBics()	Returns the BIC scores.
Map<Node,Set<Node>>	getParents()	Returns the map from nodes to the sets of their parents.
Score	getScore()	Returns the score being used for the search.
List<Double>	getTimes()	Returns the times.
List<Node>	getVariables()	Returns the variables.
void	searchSuborder(List<Node> prefix, List<Node> suborder, Map<Node,GrowShrinkTree> gsts)	Searches a suborder of the variables.
void	setKnowledge(Knowledge knowledge)	Sets the knowledge to be used for the search.
void	setNumStarts(int numStarts)	Sets the number of random starts to use.
void	setNumThreads(int numThreads)	Sets the number of threads to use.
void	setResetAfterBM(boolean reset)	Sets whether the grow-shrink trees should be reset after each best-mutation step.
void	setResetAfterRS(boolean reset)	Sets whether the grow-shrink trees should be reset after each restart.
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)	Sets whether verbose output should be printed.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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)
                    throws InterruptedException

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.

Throws:

InterruptedException

See Also:

• GrowShrinkTree

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:

• Knowledge

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:

• Node
• Variable

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:

• Score

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