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 adjacency search of the PC algorithm (see), which is a useful algorithm in many contexts, including as the first step of FCI (see). Se we call it the "Fast Adjacency Search" (FAS), to give it a name.

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.

Optionally uses Heuristic 3 from Causation, Prediction and Search, which (like FAS-Stable) renders the output invariant to the order of the input variables (See Tsagris).

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 independendencies 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 int the search.
      Specified by:
      setKnowledge in interface IFas
      Parameters:
      knowledge - This knoweldge.
      See Also:

    • getNumIndependenceTests

      public int getNumIndependenceTests()
      Returns the nubmer 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)
      This is not used here.
      Specified by:
      setOut in interface IFas
      Parameters:
      out - This print stream.

    • setHeuristic

      public void setHeuristic(int heuristic)
      Sets the heuristic to use to fix variable order (1, 2, 3, or 0 = none).
      Parameters:
      heuristic - This heuristic.

    • setStable

      public void setStable(boolean stable)
      Sets whether the stable algorithm shoudl be used.
      Parameters:
      stable - True iff the case.