Class RecursiveDiscriminatingPathRule

java.lang.Object
edu.cmu.tetrad.search.RecursiveDiscriminatingPathRule
public class RecursiveDiscriminatingPathRule extends Object
Finds separating sets for the discriminating path rule (R4 of the final FCI orientation rules, Zhang 2008) by recursive path blocking rather than by searching over subsets of adjacents.

R4 needs, for a discriminating path from x to y through v, a set that renders x and y independent; whether that set contains v then decides v's orientation. The difficulty is that some nodes on the candidate paths have circle endpoints and so might be colliders (which must not be followed when blocking) or non-colliders (which may be). This class handles that by first running RecursiveBlocking.blockPathsRecursively(Graph, Node, Node, Set, Set, int, int, int, int, boolean) with nothing excluded to obtain a pool of "ambiguous" nodes (those in the blocking set with a circle endpoint on some incident edge; or, if the unconstrained pass fails, the v-nodes of the discriminating paths from x to y), and then enumerating subsets of that pool as the not-followed set, re-blocking for each and testing the resulting set for independence. The first passing set is returned, or, under the max-p option, the passing set with the strongest evidence of independence.

All methods are static; the class is not instantiable.

Author:
josephramsey
See Also:

  • Method Details

    • findDdpSepsetRecursive

      public static Set<Node> findDdpSepsetRecursive(IndependenceTest test, Graph pag, Node x, Node y, int recursiveDepth, int maxDdpPathLength, int depth, PreserveMarkov preserveMarkovHelper, long timeout) throws InterruptedException
      Finds a separating set for the non-adjacent nodes x and y by recursive blocking over discriminating paths, returning the first passing candidate, with no independence-check counter and the given timeout. See findDdpSepsetRecursive(IndependenceTest, Graph, Node, Node, int, int, int, PreserveMarkov, IndependenceCheckCounter, long, boolean) for the algorithm and the meaning of the parameters.
      Parameters:
      test - the independence test used to check candidate separating sets.
      pag - the partially oriented graph being oriented.
      x - one endpoint; must not be adjacent to y.
      y - the other endpoint.
      recursiveDepth - the maximum recursion depth of the path-blocking search (-1 for unlimited).
      maxDdpPathLength - the maximum length of discriminating paths considered when the ambiguous pool has to be built from the paths themselves (-1 for unlimited).
      depth - the maximum size of a candidate separating set (-1 for unlimited).
      preserveMarkovHelper - if non-null, candidates are checked through this helper instead of the test, so that its running Markov bookkeeping is respected; may be null.
      timeout - the maximum time allowed, in milliseconds; a negative value means no timeout.
      Returns:
      a separating set for x and y, or null if none was found within the limits.
      Throws:
      InterruptedException - if the thread is interrupted.
      IllegalArgumentException - if x and y are adjacent in the graph.

    • findDdpSepsetRecursive

      public static Set<Node> findDdpSepsetRecursive(IndependenceTest test, Graph pag, Node x, Node y, int recursiveDepth, int maxDdpPathLength, int depth, PreserveMarkov preserveMarkovHelper, IndependenceCheckCounter counter) throws InterruptedException
      Finds a separating set for the non-adjacent nodes x and y by recursive blocking over discriminating paths, returning the first passing candidate, with an independence-check counter and no timeout. See findDdpSepsetRecursive(IndependenceTest, Graph, Node, Node, int, int, int, PreserveMarkov, IndependenceCheckCounter, long, boolean) for the algorithm and the meaning of the parameters.
      Parameters:
      test - the independence test used to check candidate separating sets.
      pag - the partially oriented graph being oriented.
      x - one endpoint; must not be adjacent to y.
      y - the other endpoint.
      recursiveDepth - the maximum recursion depth of the path-blocking search (-1 for unlimited).
      maxDdpPathLength - the maximum length of discriminating paths considered when the ambiguous pool has to be built from the paths themselves (-1 for unlimited).
      depth - the maximum size of a candidate separating set (-1 for unlimited).
      preserveMarkovHelper - if non-null, candidates are checked through this helper instead of the test, so that its running Markov bookkeeping is respected; may be null.
      counter - a counter incremented once per independence check performed; may be null.
      Returns:
      a separating set for x and y, or null if none was found within the limits.
      Throws:
      InterruptedException - if the thread is interrupted.
      IllegalArgumentException - if x and y are adjacent in the graph.

    • findDdpSepsetRecursive

      public static Set<Node> findDdpSepsetRecursive(IndependenceTest test, Graph pag, Node x, Node y, int recursiveDepth, int maxDdpPathLength, int depth, PreserveMarkov preserveMarkovHelper, IndependenceCheckCounter counter, long timeout) throws InterruptedException
      Finds a separating set for the non-adjacent nodes x and y by recursive blocking over discriminating paths, returning the first passing candidate. See findDdpSepsetRecursive(IndependenceTest, Graph, Node, Node, int, int, int, PreserveMarkov, IndependenceCheckCounter, long, boolean) for the algorithm and the meaning of the parameters; this overload fixes useMaxP to false.
      Parameters:
      test - the independence test used to check candidate separating sets.
      pag - the partially oriented graph being oriented.
      x - one endpoint; must not be adjacent to y.
      y - the other endpoint.
      recursiveDepth - the maximum recursion depth of the path-blocking search (-1 for unlimited).
      maxDdpPathLength - the maximum length of discriminating paths considered when the ambiguous pool has to be built from the paths themselves (-1 for unlimited).
      depth - the maximum size of a candidate separating set (-1 for unlimited).
      preserveMarkovHelper - if non-null, candidates are checked through this helper instead of the test, so that its running Markov bookkeeping is respected; may be null.
      counter - a counter incremented once per independence check performed; may be null.
      timeout - the maximum time allowed, in milliseconds; a negative value means no timeout.
      Returns:
      a separating set for x and y, or null if none was found within the limits.
      Throws:
      InterruptedException - if the thread is interrupted.
      IllegalArgumentException - if x and y are adjacent in the graph.

    • findDdpSepsetRecursive

      public static Set<Node> findDdpSepsetRecursive(IndependenceTest test, Graph pag, Node x, Node y, int recursiveDepth, int maxDdpPathLength, int depth, PreserveMarkov preserveMarkovHelper, IndependenceCheckCounter counter, long timeout, boolean useMaxP) throws InterruptedException
      Finds a separating set for the non-adjacent nodes x and y by recursive blocking over discriminating paths, with control over how the set is chosen when more than one candidate renders x and y independent.

      The algorithm: (1) run RecursiveBlocking.blockPathsRecursively(Graph, Node, Node, Set, Set, int, int, int, int, boolean) from x to y with nothing excluded; (2) take as the ambiguous pool those nodes of the resulting blocking set that have a circle endpoint on some incident edge, or, if that pass found no blocking set or timed out, the v-nodes of the discriminating paths from x to y of length at most maxDdpPathLength; (3) for each subset of the pool, re-run the blocking with that subset marked not-followed (treating those nodes as colliders), add back any pool node the blocking itself placed in the set, and check the resulting set for independence, skipping sets already checked.

      With useMaxP false the FIRST passing candidate is returned, so the result depends on the order in which SublistGenerator enumerates the subsets. With it true, every candidate is checked and the one with the STRONGEST evidence of independence is returned (largest p-value for a p-value test, smallest score for a score wrapped as a test), which removes that order dependence. The choice matters: R4 reads the returned set twice, once to check that it contains the collider path and once to decide (by whether it contains V) whether V is a collider on the discriminating path, and the set is recorded in the caller's sepset map.

      Two caveats. First, max-p forces the full enumeration on every call rather than exiting at the first hit; the enumeration is over subsets of the ambiguous pool, so the cost is bounded by the same worst case the greedy rule already faces, but the average case is worse. If the timeout cuts the enumeration short, the strongest candidate seen so far is returned, whereas the greedy rule returns null on timeout unless a hit was already found. Second, when a PreserveMarkov helper is supplied the greedy rule is used regardless of this flag: that helper's accept path mutates its running p-value bookkeeping, so evaluating every candidate would fold rejected candidates' updates into the state that later calls depend on. That restriction can be lifted if PreserveMarkov grows a side-effect-free query.

      Parameters:
      test - the independence test used to check candidate separating sets, and, under max-p, to rank them.
      pag - the partially oriented graph being oriented.
      x - one endpoint; must not be adjacent to y.
      y - the other endpoint.
      recursiveDepth - the maximum recursion depth of the path-blocking search (-1 for unlimited).
      maxDdpPathLength - the maximum length of discriminating paths considered when the ambiguous pool has to be built from the paths themselves (-1 for unlimited).
      depth - the maximum size of a candidate separating set (-1 for unlimited).
      preserveMarkovHelper - if non-null, candidates are checked through this helper instead of the test, so that its running Markov bookkeeping is respected, and the greedy rule is used regardless of useMaxP; may be null.
      counter - a counter incremented once per independence check performed; may be null.
      timeout - the maximum time allowed, in milliseconds, shared by the blocking passes and the enumeration; a negative value means no timeout.
      useMaxP - whether to return the passing candidate with the strongest evidence of independence rather than the first one found.
      Returns:
      a separating set for x and y, or null if none was found within the limits.
      Throws:
      InterruptedException - if the thread is interrupted.
      IllegalArgumentException - if x and y are adjacent in the graph.