Package edu.cmu.tetrad.search

Class Fas

java.lang.Object
edu.cmu.tetrad.search.Fas
All Implemented Interfaces:
IFas, IGraphSearch
public class Fas extends Object implements IFas

Implements the Fast Adjacency Search (FAS), which is the adjacency search of the PC algorithm (see). This is a useful algorithm in many contexts, including as the first step of FCI (see).

The idea of FAS is that at a given stage of the search, an edge X*-*Y is removed from the graph if X _||_ Y | S, where S is a subset of size d either of adj(X) or of adj(Y), where d is the depth of the search. The fast adjacency search performs this procedure for each pair of adjacent edges in the graph and for each depth d = 0, 1, 2, ..., d1, where d1 is either the maximum depth or else the first such depth at which no edges can be removed. The interpretation of this adjacency search is different for different algorithm, depending on the assumptions of the algorithm. A mapping from {x, y} to S({x, y}) is returned for edges x *-* y that have been removed.

FAS may optionally use a heuristic from Causation, Prediction and Search, which (like PC-Stable) renders the output invariant to the order of the input variables.

This algorithm was described in the earlier edition of this book:

Spirtes, P., Glymour, C. N., Scheines, R., & Heckerman, D. (2000). Causation, prediction, and search. MIT press.

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

Author:
peterspirtes, clarkglymour, josephramsey.
See Also:

  • Constructor Details

    • Fas

      public Fas(IndependenceTest test)
      Constructor.
      Parameters:
      test - The test to use for oracle conditional independence test results.

  • Method Details

    • search

      public Graph search()
      Runs the search and returns the resulting (undirected) graph.
      Specified by:
      search in interface IGraphSearch
      Returns:
      This graph.

    • search

      public Graph search(List<Node> nodes)
      Discovers all adjacencies in data. The procedure is to remove edges in the graph which connect pairs of variables which are independent, conditional on some other set of variables in the graph (the "sepset"). These are removed in tiers. First, edges which are independent conditional on zero other variables are removed, then edges which are independent conditional on one other variable are removed, then two, then three, and so on, until no more edges can be removed from the graph. The edges which remain in the graph after this procedure are the adjacencies in the data.
      Parameters:
      nodes - A list of nodes to search over.
      Returns:
      An undirected graph that summarizes the conditional independencies that obtain in the data.

    • setDepth

      public void setDepth(int depth)
      Sets the depth of the search, which is the maximum number of variables that ben be conditioned on in any conditional independence test.
      Specified by:
      setDepth in interface IFas
      Parameters:
      depth - This maximum.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge to be used in the search.
      Specified by:
      setKnowledge in interface IFas
      Parameters:
      knowledge - This knowledge.
      See Also:

    • getNumIndependenceTests

      public int getNumIndependenceTests()
      Returns the number of independence tests that were done.
      Specified by:
      getNumIndependenceTests in interface IFas
      Returns:
      This number.

    • getSepsets

      public SepsetMap getSepsets()
      Returns the sepsets that were discovered in the search. A 'sepset' for test X _||_ Y | Z1,...,Zm would be {Z1,...,Zm}
      Specified by:
      getSepsets in interface IFas
      Returns:
      A map of these sepsets indexed by {X, Y}.

    • setVerbose

      public void setVerbose(boolean verbose)
      Sets whether verbose output should be printed.
      Specified by:
      setVerbose in interface IFas
      Parameters:
      verbose - True iff the case.

    • getElapsedTime

      public long getElapsedTime()
      Returns the elapsed time of the search.
      Specified by:
      getElapsedTime in interface IFas
      Returns:
      This elapsed time.

    • getNodes

      public List<Node> getNodes()
      Returns the nodes from the test.
      Specified by:
      getNodes in interface IFas
      Returns:
      These nodes.

    • getAmbiguousTriples

      public List<Triple> getAmbiguousTriples(Node node)
      There are no ambiguous triples for this search, for any nodes.
      Specified by:
      getAmbiguousTriples in interface IFas
      Parameters:
      node - The nodes in question.
      Returns:
      An empty list.
      See Also:

    • setOut

      public void setOut(PrintStream out)
      Description copied from interface: IFas
      sets the print stream to send text to.
      Specified by:
      setOut in interface IFas
      Parameters:
      out - This print stream.

    • setPcHeuristicType

      public void setPcHeuristicType(PcCommon.PcHeuristicType pcHeuristic)
      Parameters:
      pcHeuristic - Which PC heuristic to use (see Causation, Prediction and Search). Default is PcHeuristicType.NONE.
      See Also:

    • setStable

      public void setStable(boolean stable)

      Sets whether the stable adjacency search should be used. Default is false. Default is false. See the following reference for this:

      Colombo, D., & Maathuis, M. H. (2014). Order-independent constraint-based causal structure learning. J. Mach. Learn. Res., 15(1), 3741-3782.

      Parameters:
      stable - True iff the case.