Class MagOrderProjection

java.lang.Object
edu.cmu.tetrad.search.work_in_progress.MagOrderProjection
@Experimental public class MagOrderProjection extends Object
Projects a total order of the observed variables to a high-scoring ancestral graph consistent with that order: the latent-variable analog of BOSS's grow-shrink projection, and the inner step of the planned LV-BOSS. Directed edges only ever run from earlier to later in the order; each ordered pair may carry a directed edge, a bidirected edge, or no edge; ancestrality (no almost-directed cycles) is enforced on every move, and acyclicity is automatic from the order.

Coverage of the space. Every MAG's directed part is acyclic, so every MAG is consistent with some total order; the order space with this projection therefore reaches all of MAG space, up to the projection finding the best member of M(order), the ancestral graphs whose directed edges respect the order.

Procedure. Two phases, both hill climbs on MagRicfBicScorer.score(Graph) (exact Gaussian BIC; the scorer's district cache makes repeated evaluations cheap):

  1. Forward pass: for each variable v in order, best-first single moves restricted to v's incoming pairs (add a directed or bidirected edge from a predecessor, delete, or retype), until none improves — a typed grow-shrink.
  2. Polish: the same best-first single moves over all order-respecting pairs, until none improves. This repairs choices the forward pass made before later structure existed, since a bidirected edge couples the fit of both endpoints' districts and per-node choices are not separable as they are for DAGs.

Deterministic: moves are enumerated in a fixed order (later endpoint, then earlier endpoint, then move type with deletions first and directed before bidirected), and the first move achieving the best strict improvement wins ties.

Honest status. The hill climbs come with no reachability guarantee: there is no theorem that the best-scoring member of M(order) is found, nor (even at the true order, in the population) that the true MAG's equivalence class is reached — that is exactly what the oracle tests probe empirically. The output is an ancestral graph but is not forced to be maximal; in the population, under faithfulness, a non-maximal output would fit strictly worse than its completion wherever the missing inducing-path edge's parameter is needed, so maximality is expected rather than enforced, and the tests check it.

Author:
josephramsey
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    MagOrderProjection(MagRicfBicScorer scorer)
    Constructs the projection over the given scorer.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getPlateauEscapes()
    The number of successful plateau escapes in the last projection.
    int
    getUnscorableMoves()
    The number of candidate moves in the last projection whose scoring threw (singular subproblem) and were treated as non-improving.
    boolean
    isPlateauCapHit()
    Whether some plateau-escape attempt in the last projection hit its state cap (if so, an exit from the plateau may have been missed).
    boolean
    isPolishCapHit()
    Whether the last projection hit the polish-phase move cap (it should not; if it did, the result may not be at a local optimum).
    Graph
    project(List<Node> order)
    Projects the order to a high-scoring ancestral graph consistent with it.
    Graph
    project(List<Node> order, Graph warmStart)
    Projects the order, warm-started from an earlier projection's graph: the warm start's order-consistent edges (directed edges whose tail precedes their head in the new order, and all bidirected edges) seed the state, the forward phases are skipped, and only the polish and plateau-escape phases run.
    void
    setImprovementEpsilon(double improvementEpsilon)
    Sets the minimum score improvement for a move to be accepted.
    void
    setMaxPlateauDepth(int maxPlateauDepth)
    Sets the cap on the length of a plateau path (chain of neutral retypes) per escape attempt.
    void
    setMaxPlateauStates(int maxPlateauStates)
    Sets the cap on distinct plateau states visited per escape attempt.
    void
    setMaxPolishMoves(int maxPolishMoves)
    Sets the safety cap on accepted moves in the polish phase.
    void
    setPlateauEscapesEnabled(boolean plateauEscapesEnabled)
    Turns the polish phase's plateau escapes on or off; see the field.

    Methods inherited from class Object

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

  • Constructor Details

    • MagOrderProjection

      public MagOrderProjection(MagRicfBicScorer scorer)
      Constructs the projection over the given scorer.
      Parameters:
      scorer - the MAG BIC scorer; its covariance matrix fixes the variable set.

  • Method Details

    • project

      public Graph project(List<Node> order)
      Projects the order to a high-scoring ancestral graph consistent with it.
      Parameters:
      order - a total order of the scorer's variables (matched by name; must be a permutation of all of them).
      Returns:
      the projected graph, over the given order's nodes.

    • project

      public Graph project(List<Node> order, Graph warmStart)
      Projects the order, warm-started from an earlier projection's graph: the warm start's order-consistent edges (directed edges whose tail precedes their head in the new order, and all bidirected edges) seed the state, the forward phases are skipped, and only the polish and plateau-escape phases run. Intended for the outer order search, where successive orders differ by one relocation and most of the previous graph remains both legal and right.
      Parameters:
      order - a total order of the scorer's variables.
      warmStart - a graph from an earlier projection over the same variables, or null for a cold projection (the full four phases).
      Returns:
      the projected graph, over the given order's nodes.

    • setImprovementEpsilon

      public void setImprovementEpsilon(double improvementEpsilon)
      Sets the minimum score improvement for a move to be accepted.
      Parameters:
      improvementEpsilon - a positive threshold on score deltas.

    • setMaxPolishMoves

      public void setMaxPolishMoves(int maxPolishMoves)
      Sets the safety cap on accepted moves in the polish phase.
      Parameters:
      maxPolishMoves - a positive cap.

    • setPlateauEscapesEnabled

      public void setPlateauEscapesEnabled(boolean plateauEscapesEnabled)
      Turns the polish phase's plateau escapes on or off; see the field. Default on.
      Parameters:
      plateauEscapesEnabled - true to attempt plateau escapes.

    • setMaxPlateauStates

      public void setMaxPlateauStates(int maxPlateauStates)
      Sets the cap on distinct plateau states visited per escape attempt.
      Parameters:
      maxPlateauStates - a positive cap.

    • setMaxPlateauDepth

      public void setMaxPlateauDepth(int maxPlateauDepth)
      Sets the cap on the length of a plateau path (chain of neutral retypes) per escape attempt.
      Parameters:
      maxPlateauDepth - a positive cap.

    • isPolishCapHit

      public boolean isPolishCapHit()
      Whether the last projection hit the polish-phase move cap (it should not; if it did, the result may not be at a local optimum).
      Returns:
      true iff the cap was hit.

    • isPlateauCapHit

      public boolean isPlateauCapHit()
      Whether some plateau-escape attempt in the last projection hit its state cap (if so, an exit from the plateau may have been missed).
      Returns:
      true iff the cap was hit.

    • getPlateauEscapes

      public int getPlateauEscapes()
      The number of successful plateau escapes in the last projection.
      Returns:
      the count.

    • getUnscorableMoves

      public int getUnscorableMoves()
      The number of candidate moves in the last projection whose scoring threw (singular subproblem) and were treated as non-improving.
      Returns:
      the count.