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 options is more scalable and accurate, though the independence option is perhaps a little easier ot deal with theoretically and are 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.

Author:
bryanandrews, josephramsey
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    Grasp(@NotNull IndependenceTest test)
    Constructor for a test.
    Grasp(@NotNull 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
    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

    clone, equals, finalize, 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(@NotNull @NotNull 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)
      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.

    • 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

      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:

    • 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.