Package edu.cmu.tetrad.search

Class GrowShrink

java.lang.Object
edu.cmu.tetrad.search.GrowShrink
All Implemented Interfaces:
IMbSearch
public class GrowShrink extends Object implements IMbSearch

Implements the Grow-Shrink algorithm of Margaritis and Thrun, a simple yet correct and useful Markov blanket search.

Margaritis, D., & Thrun, S. (1999). Bayesian network induction via local neighborhoods. Advances in neural information processing systems, 12.

Grow-Shrink learns the Markov blanket of a node, given a conditional independence test over a list of possible nodes. The Markov blanket is a set of nodes (or, in this case a list of distinct nodes), conditional on which every other node in the set is independent of X. In this case, a minimal Markov blanket is learned, which is to say, a Markov boundary of X.

Graphically, in a DAG, the Markov blanket of X is the set of parents, children, and parents of children of X; GrowShrink will, for a faithful test, learn this set for X. However, a graph over the nodes together with X is not learned; other algorithms are available to do that (see, e.g., FgesMb, PcMb).

We include GrowShrink in our algorithm suite mainly because it is a CMU algorithm (see the above reference). Markov blanket search has been explored in some detail in the literature and several algorithms are available. See for instance the BNLEARN package in R:

https://www.bnlearn.com

This class is not configured to respect knowledge of forbidden and required edges.

Author:
josephramsey
See Also:

  • Constructor Details

    • GrowShrink

      public GrowShrink(IndependenceTest test)
      Constructs a new search.
      Parameters:
      test - The test used for this search.

  • Method Details

    • findMb

      public Set<Node> findMb(Node target)
      Finds the Markov blanket of the given target.
      Specified by:
      findMb in interface IMbSearch
      Parameters:
      target - the target
      Returns:
      the set of node in the Markov blanket.

    • getAlgorithmName

      public String getAlgorithmName()
      Returns "Grow Shrink".
      Specified by:
      getAlgorithmName in interface IMbSearch
      Returns:
      This string.

    • getNumIndependenceTests

      public int getNumIndependenceTests()
      Description copied from interface: IMbSearch
      Number of independent tests.
      Specified by:
      getNumIndependenceTests in interface IMbSearch
      Throws:
      UnsupportedOperationException - Since independence tests are not counted.