Class Sp
- All Implemented Interfaces:
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.
- Author:
- bryanandrews, josephramsey
- See Also:
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionThe map from nodes to parents resulting from the search.getScore()
The score being used.The list of all variables, in order.void
searchSuborder
(List<Node> prefix, List<Node> suborder, Map<Node, GrowShrinkTree> gsts) This is the method called by PermutationSearch per tier.void
setKnowledge
(Knowledge knowledge) The knowledge being used.
-
Constructor Details
-
Sp
This algorithm will work with an arbitrary score.- Parameters:
score
- The Score to use.
-
-
Method Details
-
searchSuborder
This is the method called by PermutationSearch per tier.- Specified by:
searchSuborder
in interfaceSuborderSearch
- Parameters:
prefix
- The variable preceding the suborder variables in the permutation, including all variables from previous tiers.suborder
- The suborder of the variable list beign searched over. Only the order of the variables in this suborder will be modified.gsts
- The GrowShrinkTree used for the search. This is an optimized score-caching class.- See Also:
-
setKnowledge
Description copied from interface:SuborderSearch
The knowledge being used.- Specified by:
setKnowledge
in interfaceSuborderSearch
- Parameters:
knowledge
- This knowledge.- See Also:
-
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:
-