Class FcitSlScoreCheck

java.lang.Object
edu.cmu.tetrad.search.FcitSlScoreCheck
All Implemented Interfaces:
IGraphSearch
public final class FcitSlScoreCheck extends Object implements IGraphSearch
FCIT-SL-SCORE-CHECK: FcitSl with a MAG SCORE CHECK on every candidate the search adjudicates.

FCIT-SL searches within (and, in escape mode, beyond) the Markov equivalence class for a representative MAG that can host a proposed deletion, and commits the first candidate that clears its structural gates. This class adds one further gate at exactly that point: a candidate is committed only if the MAG it yields does not DECREASE the RICF Gaussian BIC relative to the currently committed model.

WHY THIS IS A CLEAN PLACE FOR THE CHECK. The object being scored is a genuine MAG by construction: the gate has already verified isLegalMag() on the candidate, and the deletion cannot create an inducing path (removing an edge removes paths and removes ancestor relations, so it can introduce no inducing path between any pair, while the pair being separated is checked explicitly). A Gaussian MAG has a well-defined likelihood via RICF and a well-defined parameter count, so the BIC is meaningful for every candidate reaching the check -- unlike a score applied to an arbitrary PAG-shaped graph, where the implied "MAG" may not be a MAG at all and the number that comes back means nothing.

THE REFERENCE MODEL. The BIC of a Gaussian MAG is invariant across a Markov equivalence class -- equivalent MAGs impose the same constraints and carry the same number of parameters -- so it does not matter which representative the class walk has travelled to: the reference is simply the BIC of the currently committed model, computed once per commit and cached.

FAIL-SOFT. When the score cannot be computed (no covariance available, an undirected selection edge that RICF cannot fit, a singular covariance, a non-finite likelihood), the candidate is judged by the structural gates alone, exactly as in FcitSl. A missing score is never read as a rejection: doing so would silently disable all deletion on any dataset RICF cannot fit.

Author:
josephramsey
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    FcitSlScoreCheck.CommitGate
    Commit gate.
    static enum 
    FcitSlScoreCheck.START_WITH
    Enumeration representing different start options.

  • Constructor Summary

    Constructors
    Constructor
    Description
    FcitSlScoreCheck(IndependenceTest test, Score score)
    FCIT constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    String
    getFocusBasePag()
    Retrieves the value of the focusBasePag property.
    List<Set<String>>
    getFocusBatteryZ()
    Retrieves the focus battery data structured as a list of sets of strings.
    List<String>
    getFocusEnumerated()
    Retrieves the value of the focusEnumerated property.
    String
    getFocusInterimPag()
    Retrieves the value of the focusInterimPag property.
    List<String>
    getFocusSeedLog()
    Retrieves the log of focus seed activities.
    List<String>
    getFocusSepsetLog()
    Retrieves the log of focus separation sets.
    Map<String,Integer>
    getFocusTally()
    Retrieves the current focus tally, which is a mapping of keys to their corresponding integer values.
    int
    getRecursiveDepth()
    Retrieves the current depth of recursion.
    SepsetMap
    getSepsetMap()
    Returns the map of committed separating sets discovered during the search.
    IndependenceTest
    getTest()
    Returns the independence test used in this search.
    Graph
    search()
    Run the search and return a PAG.
    void
    setAllowClassEscape(boolean allowClassEscape)
    Sets whether pass 3 (certified out-of-class seeds) may run; see seedMags(Graph, Node, Node, Set, long, boolean).
    void
    setBatteryZMax(int batteryZMax)
    Sets the maximum conditioning-set size for the deleted-pair battery.
    void
    setClassWalkBestFirst(boolean classWalkBestFirst)
    Sets the class walk's ordering: true (default) for best-first on stamp deficit, false for plain breadth-first.
    void
    setClassWalkMaxCandidates(int classWalkMaxCandidates)
    Sets the per-deletion cap on class members the walk may emit; negative means uncapped.
    void
    setClosureAutoBudgetCap(int closureAutoBudgetCap)
    Sets the ceiling on the AUTO move budget; see maxCoverMoves.
    void
    setClosureFallbackToStaged(boolean closureFallbackToStaged)
    Sets whether a pair the closure-cover search cannot host is handed to the staged generator; see closureFallbackToStaged.
    void
    setClosureMaxPathLength(int closureMaxPathLength)
    Sets the bound (in nodes) on the skeleton paths the closure-cover search enumerates.
    void
    setClosureMaxPaths(int closureMaxPaths)
    Sets the bound on the number of skeleton paths the closure-cover search enumerates.
    void
    setCommitGate(FcitSlScoreCheck.CommitGate commitGate)
    Sets the commit gate; see FcitSlScoreCheck.CommitGate.
    void
    setCompleteRuleSetUsed(boolean completeRuleSetUsed)
    Sets whether the Zhang complete rule set should be used; false if only R1-R4 (the rule set of the original FCI) should be used.
    void
    setCovarianceMatrix(ICovarianceMatrix covarianceMatrix)
    Sets the covariance matrix used by the MAG score check explicitly.
    void
    setDepth(int depth)
    Sets the depth of search, which is the maximum number of variables conditioned on in any test.
    void
    setExcludeSelectionBias(boolean excludeSelectionBias)
    Sets whether selection bias should be excluded during the search process.
    void
    setFocusPair(Node a, Node b)
    Sets the focus pair by combining the names of the given nodes in a specific order.
    void
    setGraspUseRaskuttiUhler(boolean graspUseRaskuttiUhler)
    Sets whether GRaSP, when used as the starting algorithm, should use the Raskutti-Uhler test-based method instead of the score-based method.
    void
    setKnowledge(Knowledge knowledge)
    Sets the knowledge used in search.
    void
    setLvHeuristicOnly(boolean lvHeuristicOnly)
    A flag indicating whether the LV-Heuristic results should be returned.
    void
    setMaxBlockingSetAdditions(int maxBlockingSetAdditions)
    Sets the cap on common neighbours the sepset search may add to RB's blocking set; negative means unbounded.
    void
    setMaxBlockingSetRemovals(int maxBlockingSetRemovals)
    Sets the maximum number of nodes droppable from RB's blocking set during separator search.
    void
    setMaxCoverMoves(int maxCoverMoves)
    Sets the per-candidate move budget of the closure-cover search; the analog of maxForkFlips, but counting path-directed assignments.
    void
    setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)
    Sets the maximum length of the discriminating path.
    void
    setMaxForkFlips(int maxForkFlips)
    Sets the maximum number of fork nodes converted to colliders when building an out-of-class seed.
    void
    setNumStarts(int numStarts)
    Sets the number of starts for BOSS.
    void
    setOrientationBlindFallback(boolean orientationBlindFallback)
    Sets whether the sepset search retries with RB run against the skeleton after every oriented pass fails.
    void
    setRbRadius(int rbRadius)
    Sets the radius for the RB (Recursive Blocking) algorithm, which bounds the scope of the recursive path-blocking search.
    void
    setRecursiveDepth(int recursiveDepth)
    Sets the depth level for recursive operations.
    void
    setReplicatingGraph(boolean replicatingGraph)
    Sets the flag indicating whether the graph should be replicated during the search process.
    void
    setScoreCheckPenaltyDiscount(double scoreCheckPenaltyDiscount)
    Sets the penalty discount c used by the MAG score check, in bic = 2 * logLik - c * k * ln(n).
    void
    setStartWith(FcitSlScoreCheck.START_WITH startWith)
    Sets the algorithm to use to get the initial CPDAG.
    void
    setTimeout(long timeout)
    Sets the timeout for the search algorithm, or -1 for unlimited.
    void
    setUseBes(boolean useBes)
    Sets whether to use the BES (Backward Elimination Search) algorithm during the search.
    void
    setUseClassWalk(boolean useClassWalk)
    Sets whether the within-class candidate generator is the class walk (single mark changes over the Markov equivalence class) rather than the staged seeds/LEG/fork-flip search.
    void
    setUseClosureCoverSearch(boolean useClosureCoverSearch)
    Sets whether the closure-cover generator replaces the staged representative search; see useClosureCoverSearch.
    void
    setUseDataOrder(boolean useDataOrder)
    Sets the flag indicating whether to use data order.
    void
    setUseScoreCheck(boolean useScoreCheck)
    Sets whether the MAG score check is applied.
    void
    setVerbose(boolean verbose)
    True, just in case good and restored changes are printed.

    Methods inherited from class Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface IGraphSearch

    setTest

  • Constructor Details

    • FcitSlScoreCheck

      public FcitSlScoreCheck(IndependenceTest test, Score score)
      FCIT constructor. Initializes a new object of the FCIT search algorithm with the given IndependenceTest and Score object.

      In this constructor, we will use BOSS or GRaSP internally to infer an initial CPDAG and a valid order of the variables. This is the default behavior of the FCIT algorithm.

      Parameters:
      test - The IndependenceTest object to be used for testing independence between variables.
      score - The Score object to be used for scoring DAGs.
      Throws:
      NullPointerException - if the score is null.

  • Method Details

    • setFocusPair

      public void setFocusPair(Node a, Node b)
      Sets the focus pair by combining the names of the given nodes in a specific order. The names are concatenated with a null character separator, ensuring the names are ordered lexicographically.
      Parameters:
      a - the first node whose name will be used in determining the focus pair
      b - the second node whose name will be used in determining the focus pair

    • getFocusTally

      public Map<String,Integer> getFocusTally()
      Retrieves the current focus tally, which is a mapping of keys to their corresponding integer values.
      Returns:
      a map containing the focus tally, where the keys are strings and the values are integers.

    • getFocusBatteryZ

      public List<Set<String>> getFocusBatteryZ()
      Retrieves the focus battery data structured as a list of sets of strings.
      Returns:
      a list where each element is a set of strings representing focus battery information.

    • getFocusInterimPag

      public String getFocusInterimPag()
      Retrieves the value of the focusInterimPag property.
      Returns:
      the current value of the focusInterimPag as a String.

    • getFocusBasePag

      public String getFocusBasePag()
      Retrieves the value of the focusBasePag property.
      Returns:
      the current value of the focusBasePag as a String.

    • getFocusEnumerated

      public List<String> getFocusEnumerated()
      Retrieves the value of the focusEnumerated property.
      Returns:
      a list of strings representing the focus enumerated MAGs.

    • getFocusSeedLog

      public List<String> getFocusSeedLog()
      Retrieves the log of focus seed activities.
      Returns:
      a list of strings representing the focus seed log entries.

    • getFocusSepsetLog

      public List<String> getFocusSepsetLog()
      Retrieves the log of focus separation sets.
      Returns:
      A list of strings representing the focus separation set log.

    • getTest

      public IndependenceTest getTest()
      Returns the independence test used in this search.
      Specified by:
      getTest in interface IGraphSearch
      Returns:
      the independence test

    • search

      public Graph search() throws InterruptedException
      Run the search and return a PAG.
      Specified by:
      search in interface IGraphSearch
      Returns:
      The PAG.
      Throws:
      InterruptedException - if any

    • setUseScoreCheck

      public void setUseScoreCheck(boolean useScoreCheck)
      Sets whether the MAG score check is applied. With this false the class reproduces FcitSl exactly.
      Parameters:
      useScoreCheck - True to apply the check.

    • setScoreCheckPenaltyDiscount

      public void setScoreCheckPenaltyDiscount(double scoreCheckPenaltyDiscount)
      Sets the penalty discount c used by the MAG score check, in bic = 2 * logLik - c * k * ln(n). Default 1, the classical BIC comparison. Larger values make the check more willing to accept deletions (a deletion saves c * ln(n) of penalty); smaller values make it more conservative. Independent of the penalty discount inside the initializer score.
      Parameters:
      scoreCheckPenaltyDiscount - The penalty discount; must be positive.

    • setCovarianceMatrix

      public void setCovarianceMatrix(ICovarianceMatrix covarianceMatrix)
      Sets the covariance matrix used by the MAG score check explicitly. If not set, it is resolved from the test or the score.
      Parameters:
      covarianceMatrix - The covariance matrix.

    • setCommitGate

      public void setCommitGate(FcitSlScoreCheck.CommitGate commitGate)
      Sets the commit gate; see FcitSlScoreCheck.CommitGate.
      Parameters:
      commitGate - the gate.

    • setBatteryZMax

      public void setBatteryZMax(int batteryZMax)
      Sets the maximum conditioning-set size for the deleted-pair battery.
      Parameters:
      batteryZMax - the bound; PKE6 evidence supports 2 at the enumerated scope.

    • setMaxBlockingSetRemovals

      public void setMaxBlockingSetRemovals(int maxBlockingSetRemovals)
      Sets the maximum number of nodes droppable from RB's blocking set during separator search.
      Parameters:
      maxBlockingSetRemovals - the bound; -1 (default) for all subsets.

    • setUseClassWalk

      public void setUseClassWalk(boolean useClassWalk)
      Sets whether the within-class candidate generator is the class walk (single mark changes over the Markov equivalence class) rather than the staged seeds/LEG/fork-flip search. The commit gates are identical either way, so this changes which candidates are proposed and in what order, never what is accepted. See useClassWalk.
      Parameters:
      useClassWalk - true for the class walk (default), false for the legacy generator.

    • setClassWalkBestFirst

      public void setClassWalkBestFirst(boolean classWalkBestFirst)
      Sets the class walk's ordering: true (default) for best-first on stamp deficit, false for plain breadth-first. See classWalkBestFirst.
      Parameters:
      classWalkBestFirst - true for best-first ordering.

    • setClassWalkMaxCandidates

      public void setClassWalkMaxCandidates(int classWalkMaxCandidates)
      Sets the per-deletion cap on class members the walk may emit; negative means uncapped. Hitting the cap makes a failure to host INCONCLUSIVE -- see classWalkMaxCandidates.
      Parameters:
      classWalkMaxCandidates - the cap, or negative for uncapped.

    • setMaxBlockingSetAdditions

      public void setMaxBlockingSetAdditions(int maxBlockingSetAdditions)
      Sets the cap on common neighbours the sepset search may add to RB's blocking set; negative means unbounded. See maxBlockingSetAdditions.
      Parameters:
      maxBlockingSetAdditions - the cap, or negative for unbounded.

    • setOrientationBlindFallback

      public void setOrientationBlindFallback(boolean orientationBlindFallback)
      Sets whether the sepset search retries with RB run against the skeleton after every oriented pass fails. See orientationBlindFallback.
      Parameters:
      orientationBlindFallback - true to enable the fallback (default).

    • setMaxForkFlips

      public void setMaxForkFlips(int maxForkFlips)
      Sets the maximum number of fork nodes converted to colliders when building an out-of-class seed. Bounded low (1-2) for audit-scale models. Applies to the staged generator and to escape mode; the class walk does not use it. See seedMags(Graph, Node, Node, Set, long, boolean).
      Parameters:
      maxForkFlips - the bound.

    • setAllowClassEscape

      public void setAllowClassEscape(boolean allowClassEscape)
      Sets whether pass 3 (certified out-of-class seeds) may run; see seedMags(Graph, Node, Node, Set, long, boolean). False is "Step-Lemma-pure" mode: every commit is hosted by a representative of the current class -- the canonical Zhang MAG, another LEG, or a fork-flip certified Markov-equivalent -- so an oracle run that terminates at the true PAG with this false is direct Step-Lemma evidence, undiluted by the escape hatch.
      Parameters:
      allowClassEscape - true to permit the state-level escape pass (the default).

    • setUseClosureCoverSearch

      public void setUseClosureCoverSearch(boolean useClosureCoverSearch)
      Sets whether the closure-cover generator replaces the staged representative search; see useClosureCoverSearch. Same gates either way -- flipping this changes which candidates are proposed and in what order, never what is accepted. False by default.
      Parameters:
      useClosureCoverSearch - true to use the closure-cover generator.

    • setClosureFallbackToStaged

      public void setClosureFallbackToStaged(boolean closureFallbackToStaged)
      Sets whether a pair the closure-cover search cannot host is handed to the staged generator; see closureFallbackToStaged. True by default. Set false to measure the closure search's unaided reach.
      Parameters:
      closureFallbackToStaged - true to enable the fallback.

    • setClosureMaxPathLength

      public void setClosureMaxPathLength(int closureMaxPathLength)
      Sets the bound (in nodes) on the skeleton paths the closure-cover search enumerates.
      Parameters:
      closureMaxPathLength - the bound; see closureMaxPathLength.

    • setClosureMaxPaths

      public void setClosureMaxPaths(int closureMaxPaths)
      Sets the bound on the number of skeleton paths the closure-cover search enumerates.
      Parameters:
      closureMaxPaths - the bound; see closureMaxPaths.

    • setMaxCoverMoves

      public void setMaxCoverMoves(int maxCoverMoves)
      Sets the per-candidate move budget of the closure-cover search; the analog of maxForkFlips, but counting path-directed assignments.
      Parameters:
      maxCoverMoves - the budget; see maxCoverMoves.

    • setClosureAutoBudgetCap

      public void setClosureAutoBudgetCap(int closureAutoBudgetCap)
      Sets the ceiling on the AUTO move budget; see maxCoverMoves.
      Parameters:
      closureAutoBudgetCap - the cap.

    • setStartWith

      public void setStartWith(FcitSlScoreCheck.START_WITH startWith)
      Sets the algorithm to use to get the initial CPDAG.
      Parameters:
      startWith - the algorithm to use to get the initial CPDAG.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge used in search.
      Parameters:
      knowledge - This knowledge.

    • setVerbose

      public void setVerbose(boolean verbose)
      True, just in case good and restored changes are printed. The algorithm always moves to a legal PAG; if it doesn't, it is restored to the previous PAG, and a "restored" message is printed. Otherwise, a "good" message is printed.
      Parameters:
      verbose - True if changes to the graph should be printed.

    • setNumStarts

      public void setNumStarts(int numStarts)
      Sets the number of starts for BOSS.
      Parameters:
      numStarts - The number of starts.

    • setUseBes

      public void setUseBes(boolean useBes)
      Sets whether to use the BES (Backward Elimination Search) algorithm during the search.
      Parameters:
      useBes - true to use the BES algorithm, false otherwise

    • setUseDataOrder

      public void setUseDataOrder(boolean useDataOrder)
      Sets the flag indicating whether to use data order.
      Parameters:
      useDataOrder - true if the data order should be used, false otherwise.

    • setGraspUseRaskuttiUhler

      public void setGraspUseRaskuttiUhler(boolean graspUseRaskuttiUhler)
      Sets whether GRaSP, when used as the starting algorithm, should use the Raskutti-Uhler test-based method instead of the score-based method. Ignored unless the start-with option is GRaSP.
      Parameters:
      graspUseRaskuttiUhler - True to use the Raskutti-Uhler method.

    • setCompleteRuleSetUsed

      public void setCompleteRuleSetUsed(boolean completeRuleSetUsed)
      Sets whether the Zhang complete rule set should be used; false if only R1-R4 (the rule set of the original FCI) should be used. False by default.
      Parameters:
      completeRuleSetUsed - True for the complete Zhang rule set.

    • setDepth

      public void setDepth(int depth)
      Sets the depth of search, which is the maximum number of variables conditioned on in any test.
      Parameters:
      depth - This maximum.

    • setReplicatingGraph

      public void setReplicatingGraph(boolean replicatingGraph)
      Sets the flag indicating whether the graph should be replicated during the search process.
      Parameters:
      replicatingGraph - true to enable graph replication, false otherwise.

    • setExcludeSelectionBias

      public void setExcludeSelectionBias(boolean excludeSelectionBias)
      Sets whether selection bias should be excluded during the search process.
      Parameters:
      excludeSelectionBias - True to exclude selection bias, false otherwise.

    • setRbRadius

      public void setRbRadius(int rbRadius)
      Sets the radius for the RB (Recursive Blocking) algorithm, which bounds the scope of the recursive path-blocking search.
      Parameters:
      rbRadius - the radius to set; -1 for unlimited

    • getRecursiveDepth

      public int getRecursiveDepth()
      Retrieves the current depth of recursion.
      Returns:
      the depth of recursion as an integer

    • setRecursiveDepth

      public void setRecursiveDepth(int recursiveDepth)
      Sets the depth level for recursive operations.
      Parameters:
      recursiveDepth - the maximum depth to which the recursion is allowed

    • setMaxDiscriminatingPathLength

      public void setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)
      Sets the maximum length of the discriminating path.
      Parameters:
      maxDiscriminatingPathLength - the maximum number of steps or nodes allowed in the discriminating path.

    • setTimeout

      public void setTimeout(long timeout)
      Sets the timeout for the search algorithm, or -1 for unlimited.
      Parameters:
      timeout - the maximum time in milliseconds to allow the search to run.

    • getSepsetMap

      public SepsetMap getSepsetMap()
      Returns the map of committed separating sets discovered during the search. A pair {x, y} has an entry once its edge has been removed by a legal-PAG commit; the value is the conditioning set that separated it. This reflects only committed separations and is rolled back on a reverted removal.
      Returns:
      the separating-set map; never null, but empty before search() runs

    • setLvHeuristicOnly

      public void setLvHeuristicOnly(boolean lvHeuristicOnly)
      A flag indicating whether the LV-Heuristic results should be returned. If false, edges will be removed via further independence testing.
      Parameters:
      lvHeuristicOnly - Whether to return the LV-Heuristic results.