Learning Equivalence Classes of Bayesian Network Structures

By David Maxwell Chickering. 1996

Approaches to learning Bayesian networks from data typically combine a scoring function with a heuristic search procedure. Given a Bayesian network structure, many of the scoring functions derived in the literature return a score for the entire equivalence class to which the structure belongs. When using such a scoring function, it is appropriate for the heuristic search algorithm to search over equivalence classes of Bayesian networks as opposed to individual structures. We present the general formulation of a search space for which the states of the search correspond to equivalence classes of structures. Using this space, any one of a number of heuristic search algorithms can easily be applied. We compare greedy search performance in the proposed search space to greedy search performance in a search space for which the states correspond to individual Bayesian network structures.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs (2011, methodology): “It is well-known in the observational case that such an approach performs markedly worse than one accounting for Markov equivalence (Chickering, 2002b; Castelo and Koˇcka, 2003), and we will see in our simulations (Section 5.2) that the same is true in the interventional case as long as few…”
Order-independent constraint-based causal structure learning (2012, background): “Step 1 ﬁnds the skeleton and separation sets, while Steps 2 and 3 determine the orientations of the edges.”
Causal Structure Learning (2017, methodology): “Limiting ourselves to algorithms with an implementation in R (R Core Team, 2017), we obtain the following selection of methods, with assumptions summarized in Table 1: • Constraint-based methods: PC (Spirtes et al., 2000), rankPC (Harris and Drton, 2013), FCI (Spirtes et al., 2000), and rankFCI • Sc”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, methodology): “The results (Figure S9) are quite similar, although with a slight decrease in the performance of the PC algorithm and a notable worsening for GES for the larger networks.”
Optimal Structure Identification With Greedy Search (2002, methodology): “Lemma 35 (Chickering, 2002)For any directed edge X→Y in a completed PDAG, X is a parent of every node reachable by Y via undirected edges.”
Estimating the effect of joint interventions from observational data in sparse high-dimensional settings (2014, background): “class if and only if they have the same skeleton and the same v-structures [33]. A Markov equivalence class of DAGs can be uniquely represented by a completed partially directed acyclic graph (CPDAG) [4], which is a graph that can contain both directed and undirected edges. Figure 3 shows an example”
Graphical criteria for efficient total effect estimation via adjustment in causal linear models (2019, methodology): “Under the assumptions of causal sufficiency and faithfulness, one can, however, learn a Markov equivalence class of DAGs, which can be uniquely represented by a CPDAG (Andersson et al., 1997; Chickering, 2002; Colombo & Maathuis, 2014; Meek, 1995; Spirtes et al., 2000).”
A Scoring Function for Learning Bayesian Networks based on Mutual Information and Conditional Independence Tests (2006, background): “In other words, undirected cycles are forbidden in RPDAGs, whereas in essential graphs only undirected non-chordal cycles are forbidden.”
Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets (2020, methodology): “Next to Bayesian score-based methods [Chickering, 2002], classical Granger causality (GC) [Granger, 1969], and the more recent restricted structural causal models (SCM) framework [Peters et al., 2017, Spirtes and Zhang, 2016], conditional independence (CI) based network learning algorithms [Spirtes…”
Learning high-dimensional directed acyclic graphs with latent and selection variables (2011, background): “Markov equivalence classes of DAGs can be described uniquely by a completed partially directed acyclic graph (CPDAG) [3, 4].”
Bayesian Networks for Data Mining (2004, background): “Nonetheless, several researchers have shown experimentally that the selection of a single good hypothesis using greedy search often yields accurate predictions (Cooper and Herskovits, 1992; Aliferis and Cooper, 1994; Heckerman et al., 1995b; Spirtes and Meek, 1995; Chickering, 1996), and that model ”
Interventions and Causal Inference (2007, methodology): “They are also sometimes referred to as “hard” or “ideal” interventions. Korb (2004) refers to them as “independent” interventions.”
A survey of Bayesian Network structure learning (2021, methodology): “Note that whilst some approximate algorithms can guarantee to return the highest scoring graph as 𝑁 → ∞ (Chickering, 2002; Chickering and Meek, 2002), exact algorithms guarantee to return the highest scoring graph for the input dataset, however small the sample size might be.”
The donor is in the details (2013, unknown): “The GES algorithm (Chickering, 1996) is implemented in TETRAD 4 (www.phil.cmu.edu/projects/tetrad/tetrad4.html ).”