Package edu.cmu.tetrad.search

Class Sp

java.lang.Object
edu.cmu.tetrad.search.Sp
All Implemented Interfaces:
SuborderSearch
public class Sp extends Object implements SuborderSearch
Implements the SP (Sparsest Permutation) algorithm. This procedure goes through every permutation of the variables (so can be slow for more than 11 variables with no knowledge) looking for a permutation such that when a DAG is built it has the fewest number of edges (i.e., is a most 'frugal' or a 'sparsest' DAG). The procedure can in principle return all such sparsest permutations and their corresponding DAGs, but in this version it return one of them, and converts the result into a CPDAG.

Note that SP considers all permutations of the algorithm, which is exponential in the number of variables. So SP without knowledge is limited to about 10 variables per knowledge tier.

However, notably, tiered 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 more than 11 variables.

This class is meant to be used in the context of the PermutationSearch class (see). the proper use is PermutationSearch search = new PermutationSearch(new Sp(score));

Raskutti, G., & Uhler, C. (2018). Learning directed acyclic graph models based on sparsest permutations. Stat, 7(1), e183.

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:

  • Constructor Details

    • Sp

      public Sp(Score score)
      This algorithm will work with an arbitrary score.
      Parameters:
      score - The Score to use.

  • Method Details

    • searchSuborder

      public void searchSuborder(List<Node> prefix, List<Node> suborder, Map<Node,GrowShrinkTree> gsts)
      Searches for the best suborder of nodes given a prefix and a 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:

    • getVariables

      public List<Node> getVariables()
      Returns the list of variables associated with this object.
      Specified by:
      getVariables in interface SuborderSearch
      Returns:
      the list of variables.
      See Also:

    • getParents

      public Map<Node,Set<Node>> getParents()
      Retrieves a mapping of nodes to their parent nodes.
      Specified by:
      getParents in interface SuborderSearch
      Returns:
      the mapping of nodes to their parent nodes.

    • getScore

      public Score getScore()
      Retrieves the score associated with this object.
      Specified by:
      getScore in interface SuborderSearch
      Returns:
      the score
      See Also:

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge associated with this object.
      Specified by:
      setKnowledge in interface SuborderSearch
      Parameters:
      knowledge - The knowledge to set.
      See Also: