Package edu.cmu.tetrad.search

Class Grasp

java.lang.Object

edu.cmu.tetrad.search.Grasp

public class Grasp
extends Object

Implements the GRaSP algorithms, which uses a certain procedure to search in the space of permutations of variables for ones that imply CPDAGs that are especially close to the CPDAG of the true model. The reference is here:

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.

GRaSP can use either a score or an independence test; you can provide both, though if you do you need to use the parameters to choose which one will be used. The score option is more scalable and accurate, though the independence option is perhaps a little easier ot deal with theoretically and is useful for generating unit test results.

As shown the reference above, GRaSP generates results for the linear, Gaussian case for N = 1000 with precisions for adjacencies and arrowheads near 1 and recalls of about 0.85, when the linear, Gaussian BIC score is used with a penalty of 2. For N = 10,000 recalls also rise up to about 1, so it can be an extraordinarily accurate search for the linear, Gaussian case. But in principle, it can be used with any sort of data, so long as a BIC score is available for that data. So it can be used for the discrete case and for the mixed continuous/discrete case as well.

The version of GRaSP described in the above reference is limited to about 100 variables in execution time, after which it become impracticably slow. Recent optimizations allow it to scale further than that; hopefully these will be written up soon and made available.

Knowledge can be used with this search. If tiered knowledge is used, then the procedure is carried out for each tier separately, given the variable preceding that tier, which allows the SP algorithm to address tiered (e.g., time series) problems with larger numbers of variables.

This class is configured to respect knowledge of forbidden and required edges, including knowledge of temporal tiers.

Version:

$Id: $Id

Author:

bryanandrews, josephramsey

See Also:

• Fges
• Boss
• Sp
• Knowledge

Constructor Summary

Constructors

Constructor	Description
Grasp(@NotNull IndependenceTest test)	Constructor for a test.
Grasp(IndependenceTest test, Score score)	Constructor that takes both a test and a score; only one is used-- the parameter setting will decide which.
Grasp(@NotNull Score score)	Constructor for a score.

Method Summary

Modifier and Type	Method	Description
List<Node>	bestOrder(@NotNull List<Node> order)	Given an initial permutation, 'order,' of the variables, searches for a best permutation of the variables by rearranging the variables in 'order.'
@NotNull Graph	getGraph(boolean cpDag)	Returns the graph implied by the discovered permutation.
int	getNumEdges()	Returns the number of edges in the DAG implied by the discovered permutation.
List<Node>	getVariables()	Returns the variables.
void	setAllowInternalRandomness(boolean allowInternalRandomness)	Sets whether to allow internal randomness in the algorithm.
void	setDepth(int depth)	Sets the maximum depth of the depth-first search that GRaSP performs while searching for a weakly increasing tuck sequence that improves the score.
void	setKnowledge(Knowledge knowledge)	Sets the knowledge used in the search.
void	setNonSingularDepth(int nonSingularDepth)	Sets the maximum depth at which singular tucks can be performed within the depth-first search of GRaSP.
void	setNumStarts(int numStarts)	Sets the number of times the best order algorithm should be rerun with different starting permutations in search of a best BIC scoring permutation.
void	setOrdered(boolean ordered)	True if GRasP0 should be performed before GRaSP1 and GRaSP1 before GRaSP2.
void	setSeed(long seed)	Sets the seed for random number generation.
void	setUncoveredDepth(int uncoveredDepth)	Sets the maximum depth at which uncovered tucks can be performed within the depth-first search of GRaSP.
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	setUseRaskuttiUhler(boolean useRaskuttiUhler)	True if the Raskutti-Uhler method should be used, false if the Verma-Pearl method should be used.
void	setUseScore(boolean useScore)	True if the score should be used (if both a score and a test are provided), false if not.
void	setVerbose(boolean verbose)	Sets whether verbose output is printed.

Methods inherited from class java.lang.Object

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

Constructor Details

Grasp

public Grasp(@NotNull
 @NotNull Score score)

Constructor for a score.

Parameters:

score - The score to use.

Grasp

public Grasp(@NotNull
 @NotNull IndependenceTest test)

Constructor for a test.

Parameters:

test - The test to use.

Grasp

public Grasp(IndependenceTest test,
 Score score)

Constructor that takes both a test and a score; only one is used-- the parameter setting will decide which.

Parameters:

test - The test to use.

score - The score to use.

Method Details

bestOrder

public List<Node> bestOrder(@NotNull
 @NotNull List<Node> order)
                     throws InterruptedException

Given an initial permutation, 'order,' of the variables, searches for a best permutation of the variables by rearranging the variables in 'order.'

Parameters:

order - The initial permutation.

Returns:

The discovered permutation at the end of the procedure.

Throws:

InterruptedException

getNumEdges

public int getNumEdges()

Returns the number of edges in the DAG implied by the discovered permutation.

Returns:

This number.

getGraph

@NotNull
public @NotNull Graph getGraph(boolean cpDag)

Returns the graph implied by the discovered permutation.

Parameters:

cpDag - True if a CPDAG should be returned, false if a DAG should be returned.

Returns:

This graph.

setNumStarts

public void setNumStarts(int numStarts)

Sets the number of times the best order algorithm should be rerun with different starting permutations in search of a best BIC scoring permutation.

Parameters:

numStarts - This number, if 1, it is run just once with the given starting permutation, if 2 or higher, it is rerun subsequently with random initial permutations, and the best scoring discovered final permutation is reported.

See Also:

• setUseDataOrder(boolean)

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

getVariables

public List<Node> getVariables()

Returns the variables.

Returns:

This list.

setVerbose

public void setVerbose(boolean verbose)

Sets whether verbose output is printed.

Parameters:

verbose - True, if so.

setKnowledge

public void setKnowledge(Knowledge knowledge)

Sets the knowledge used in the search. The search is set up to honor all knowledge of forbidden or required directed edges, and tiered knowledge.

Parameters:

knowledge - This knowledge.

setDepth

public void setDepth(int depth)

Sets the maximum depth of the depth-first search that GRaSP performs while searching for a weakly increasing tuck sequence that improves the score.

Parameters:

depth - This depth.

setUncoveredDepth

public void setUncoveredDepth(int uncoveredDepth)

Sets the maximum depth at which uncovered tucks can be performed within the depth-first search of GRaSP.

Parameters:

uncoveredDepth - This depth.

setNonSingularDepth

public void setNonSingularDepth(int nonSingularDepth)

Sets the maximum depth at which singular tucks can be performed within the depth-first search of GRaSP.

Parameters:

nonSingularDepth - This depth.

setUseScore

public void setUseScore(boolean useScore)

True if the score should be used (if both a score and a test are provided), false if not.

Parameters:

useScore - True, if so.

setOrdered

public void setOrdered(boolean ordered)

True if GRasP0 should be performed before GRaSP1 and GRaSP1 before GRaSP2. False if this ordering should not be imposed.

Parameters:

ordered - True if the ordering should be imposed.

setUseRaskuttiUhler

public void setUseRaskuttiUhler(boolean useRaskuttiUhler)

True if the Raskutti-Uhler method should be used, false if the Verma-Pearl method should be used.

Parameters:

useRaskuttiUhler - True if RU, false if VP.

See Also:

• setNumStarts(int)

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.

setSeed

public void setSeed(long seed)

Sets the seed for random number generation.

Parameters:

seed - The seed to set.