Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Active Structure Learning of Bayesian Networks in an Observational Setting
Authors: Noa Ben-David, Sivan Sabato
JMLR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To supplement the theoretical results, we report experiments that compare the performance of the new active algorithm to the naive baseline and demonstrate the sample complexity improvements. Code for the algorithm and for the experiments is provided at https://github.com/noabdavid/active BNSL. |
| Researcher Affiliation | Academia | Noa Ben-David EMAIL Sivan Sabato EMAIL Department of Computer Science Ben-Gurion Univesity of the Negev Beer Sheva 8410501, Israel. |
| Pseudocode | Yes | Active BNSL, listed in Alg. 1, gets d (the number of variables) and k (the maximal number of parents) as inputs, in addition to a confidence parameter δ, the required accuracy level ϵ. Active BNSL maintains a set V [d] of the variables whose families have been accepted so far (that is, their parent sets in the output structure have been fixed). The set of accepted families is denoted Accj, where j denotes an iteration within the algorithm. Accj includes exactly one family for each v V. The set of candidate families is denoted Cand(V). This is the set of families that have not been precluded so far from participating in the output structure. For simplicity, we set Cand(V) to the set of all the families with a child variable not in V. Note that this does not preclude, for instance, families that would create a cycle when combined with Accj. As will be evident below, including redundant families in Cand(V) does not harm the correctness of Active BNSL. |
| Open Source Code | Yes | Code for the algorithm and for the experiments is provided at https://github.com/noabdavid/active BNSL. |
| Open Datasets | Yes | We ran experiments using data generated from synthetically constructed networks, and from discrete networks from the Bayesian Network Repository,3 which provides Bayesian networks that are commonly used as benchmarks. Footnote 3: https://www.bnlearn.com/bnrepository/ |
| Dataset Splits | No | The paper focuses on structure learning of Bayesian networks using samples and discusses sample complexity. It describes how synthetic networks are constructed and mentions using benchmark networks, but does not specify traditional training/test/validation dataset splits, as the experimental goal is not typical predictive performance evaluation requiring such splits. |
| Hardware Specification | No | The paper describes the algorithms, experimental setup, and results, but does not provide any specific details about the hardware (e.g., GPU models, CPU types, memory) used to run the experiments. |
| Software Dependencies | No | We use the well-established algorithm GOBNILP (Cussens, 2011), as implemented in the e BNSL package2 (Liao et al., 2019)... The input to e BNSL includes the score of each family and a positive real number ϵ. The algorithm heuristically attempts to output all network structures in Gd,k with a score gap of at most ϵ from the maximal achievable score. To compute Lj, Active BNSL sets the ϵ input value of e BNSL to θj. While specific software packages (GOBNILP, e BNSL) are mentioned, their exact version numbers are not provided in the text. |
| Experiment Setup | Yes | In all the networks, all nodes represented Bernoulli random variables taking values in {0, 1}, except for the benchmark networks Survey and Sachs, which include multinomially distributed variables with 3 possible values. The synthetic networks describe stable distributions of the type presented in Section 8, in which each of the network variables has at most two parents. ... In all networks, X1 has no parents and is a Bernoulli(1-ρ) random variable, where ρ = 0.99. X2 has only X1 as a parent and is equal to X1 with an independent probability of 1 ρ (otherwise, it is equal to 1 X1). Each of the variables Xi for i {3, ..., d 2} has two parents Xj, Xj for some j, j < i. The value of Xi is xor(Xj, Xj ) with an independent probability of ρ. In all networks, Xa is the child of X3 and X4, and the value of Xa is xor(X3, X4) with an independent probability of ρ. Xb is a slightly noisy version of Xa, such that Xa = Xb with an independent probability of 1 5 10 6. This construction satisfies the conditions in Section 8 with X1 := {X1, . . . , Xd 2, Xa}. Since Xb is almost always equal to Xa, it is hard to distinguish between them using samples. In particular, the structure in which X3, X4 are the parents of Xb and the latter is the parent of Xa has a score which is very close to optimal. ... In all of the synthetic and benchmark networks, the true network could be represented with k = 2, except for the benchmark Sachs network, in which the true network requires k = 3. Accordingly, the value of k was set to 2 for all but the Sachs network, where it was set to 3. In all of the experiments, we set δ = 0.05. To set the values of ϵ in each experiment in a comparable way, we adjusted this value by the number of network nodes, denoted by d, by fixing the ratio r := d/ϵ and calculating ϵ based on this ratio. We ran experiments with r := 2j for a range of values of j. Each experiment configuration was ran 10 times, and we report the average and standard deviation of the results. ... Formally, we used the following modified empirical score: ˆH(Xi | Πi(G)) + β|Πi(G)| ˆH(Xi) , (9) where β := 0.001. |