BOSS (TETRAD)

Module name	tetrad_boss
Package	TETRAD
Version	1.10.0
Language	Java
Docs	here
Paper	Ramsey[1], Andrews et al.[2]
Graph type	CPDAG
MCMC	No
Edge constraints	Yes
Data type	C, D
Data missingness
Intervention type
Docker	bpimages/causal-cmd:1.10.0

Best Order Score Search

BOSS (Best Order Score Search) is an algorithm that, like GRaSP, generalizes and extends the GSP (Greedy Sparsest Permutation) algorithm. It has been tested to 1000 variables with an average degree of 20 and gives near perfect precisions and recalls for N = 10,000 (with recall that drop to 0.9 for N = 1000). The algorithms works by building DAGs given permutations in ways similar to those described in Raskutti and Uhler and Solus et al.

Example

Config file: boss_SEM.json

Command:

snakemake --cores all --use-singularity --configfile workflow/rules/structure_learning_algorithms/tetrad_boss/config/boss_SEM.json

Fig. 26 and Fig. 27 show FP/P vs. TP/P and timings based on 10 datsets corresponding to 10 realisations of a 60-variables random Gaussian SEM, with an average indegree of 4. Each dataset contains 300 samples. Fig. 28 and Fig. 29 show the type of graphs estimated and the properties of the true graphs, respectively.

FP/P vs. TP/P BOSS example — Fig. 26 FP/P vs. TP/P.

Timings BOSS example — Fig. 27 Timings.

Graph types example — Fig. 28 Type of graphs estimated.

Properties of the true graphs — Fig. 29 Graph properties.

Some fields described

allowInternalRandomess If true, the algorithm allow the algorithm to use certain heuristic random steps. This can improve performance, but may make the algorithm non-deterministic.
edgeConstraints Name of the JSON file containing background knowledge
useBes True if the final BES (Backward Equivalence Search) step is used from the GES (Greedy Equivalence Search) algorithm. This step is needed for correctness but for large models, since usually nearly all edges are oriented in the CPDAG, it is heurically not needed.

Example JSON

[
  {
    "id": "boss-bic",
    "score": "sem-bic-score",
    "datatype": "continuous",
    "samplePrior": null,
    "useBes": true,
    "allowInternalRandomess": false,
    "semBicStructurePrior": 1,
    "penaltyDiscount": [
      0.8,
      1,
      1.5
    ],
    "timeout": null,
    "edgeConstraints": "edgeConstraints.json"
  },
  {
    "id": "boss-bdeu",
    "score": "bdeu-score",
    "datatype": "discrete",
    "samplePrior": [
      1,
      10,
      20
    ],
    "useBes": true,
    "allowInternalRandomess": false,
    "semBicStructurePrior": null,
    "penaltyDiscount": null,
    "timeout": null,
    "edgeConstraints": "edgeConstraints.json"
  }
]