On Inclusion-Driven Learning of Bayesian Networks

By Robert Castelo, Tomas Kocka. 2003

97 citations recorded by the source corpus.

Two or more Bayesian network structures are Markov equivalent when the corresponding acyclic digraphs encode the same set of conditional independencies. Therefore, the search space of Bayesian network structures may be organized in equivalence classes, where each of them represents a different set of conditional independencies. The collection of sets of conditional independencies obeys a partial order, the so-called "inclusion order." This paper discusses in depth the role that the inclusion order plays in learning the structure of Bayesian networks. In particular, this role involves the way a learning algorithm traverses the search space. We introduce a condition for traversal operators, the inclusion boundary condition, which, when it is satisfied, guarantees that the search strategy can avoid local maxima. This is proved under the assumptions that the data is sampled from a probability distribution which is faithful to an acyclic digraph, and the length of the sample is unbounded. The previous discussion leads to the design of a new traversal operator and two new learning algorithms in the context of heuristic search and the Markov Chain Monte Carlo method. We carry out a set of experiments with synthetic and real-world data that show empirically the benefit of striving for the inclusion order when learning Bayesian networks from data.

Subfields: General Health Professions, Philosophy

How researchers see this paper

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

In General Health Professions

In Philosophy

Citations in the corpus

Causal inference by using invariant prediction: identification and confidence intervals (2015, background): “…al., 1997, Hauser and B¨uhlmann, 2012], estimate such a class based on observational or interventional data [Spirtes et al., 2000, Chickering, 2002, Castelo and Kocka, 2003, Kalisch and B¨uhlmann, 2007, He and Geng., 2008, Hauser and B¨uhlmann, 2015, cf.], and ﬁnally infer the iden-tiﬁable causal…”
Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs (2011, methodology): “A heuristic approach to guarantee polynomial runtime of a greedy search has been proposed by Castelo and Koˇcka (2003) for the observational case.”
Learning Bayesian networks: approaches and issues (2011, background): “Following on from this work, Castelo and Kočka (2003) show a more general way of looking at the search problem and illustrate certain conditions that operators on the search space should obey, to avoid local maxima.”
Causal inference in partially linear structural equation models (2016, methodology): “For example, as mentioned before, in the spirit of [4], or also for Monte Carlo sampling in Bayesian settings, see a related discussion in [1], Section 1.”
Bayesian network learning for natural hazard analyses (2014, background): “For this we traverse the space of BNs (Castelo and Kocka, 2003) looking for a candidate maximizing a fitness score that reflects the “usefulness” of the BN.”
Sequences of regressions and their independences (2011, background): “…Markov equivalent models is essential for designing search procedures which converge with an increasing sample size to a true generating graph; see Castelo and Kocka (2003) for searches within the class of directed acyclic graphs which consist exclusively of arrows and capture independences of…”
Exact Bayesian Structure Discovery in Bayesian Networks (2004, methodology): “, a recent paper by Castelo and Kočka (2003) and references therein.”