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.

Version:
$Id: $Id
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()
      Performs a search to discover all adjacencies in the graph. The procedure is to remove edges in the graph which connect pairs of variables that are independent, conditional on some other set of variables in the graph (the "sepset"). These edges 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.
      Specified by:
      search in interface IGraphSearch
      Returns:
      An undirected graph that summarizes the conditional independencies that obtain in the data.

    • 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 maximum depth for the search.
      Specified by:
      setDepth in interface IFas
      Parameters:
      depth - The maximum depth to set.
      Throws:
      IllegalArgumentException - if the depth is less than -1.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge for this object.
      Specified by:
      setKnowledge in interface IFas
      Parameters:
      knowledge - The knowledge object to set.

    • 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 the verbose mode.
      Specified by:
      setVerbose in interface IFas
      Parameters:
      verbose - true if verbose mode is enabled, false otherwise.

    • 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()
      Retrieves the list of nodes in the graph.
      Specified by:
      getNodes in interface IFas
      Returns:
      A List of Node objects representing the nodes in the graph.

    • getAmbiguousTriples

      public List<Triple> getAmbiguousTriples(Node node)
      Retrieves the list of ambiguous triples involving the given node.
      Specified by:
      getAmbiguousTriples in interface IFas
      Parameters:
      node - The node for which to retrieve the ambiguous triples.
      Returns:
      A list of Triple objects representing the ambiguous triples involving the node.
      See Also:

    • setOut

      public void setOut(PrintStream out)
      Sets the PrintStream to be used for output.
      Specified by:
      setOut in interface IFas
      Parameters:
      out - the PrintStream to be used for output

    • setPcHeuristicType

      public void setPcHeuristicType(PcCommon.PcHeuristicType pcHeuristic)
      Sets the type of heuristic to be used in the PC algorithm.
      Parameters:
      pcHeuristic - The type of heuristic to be used.

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