Title: On the Construction of the Inclusion Boundary Neighbourhood for Markov Equivalence Classes of Bayesian network
Authors: Vincent Auvray, Louis Wehenkel
Level: Advanced
Abstract:
classes of Bayesian network structures may be
solved by searching for the maximum of a scor-
ing metric in a space of these classes. This paper
deals with the de?nition and analysis of one such
search space. We use a theoretically motivated
neighbourhood, the inclusion boundary, and rep-
resent equivalence classes by essential graphs.
We show that this search space is connected and
that the score of the neighbours can be evalu-
ated incrementally. We devise a practical way
of building this neighbourhood for an essential
graph that is purely graphical and does not ex-
plicitely refer to the underlying independences.
We ?nd that its size can be intractable, depend-
ing on the complexity of the essential graph of
the equivalence class. The emphasis is put on
the potential use of this space with greedy hill-
climbing search.
The problem of learning Markov equivalence classes of Bayesian network structures may be solved by searching for the maximum of a scoring metric in a space of these classes. This paper deals with the de?nition and analysis of one such search space. We use a theoretically motivated neighbourhood, the inclusion boundary, and represent equivalence classes by essential graphs. We show that this search space is connected and that the score of the neighbours can be evaluated incrementally. We devise a practical way of building this neighbourhood for an essential graph that is purely graphical and does not explicitely refer to the underlying independences. We ?nd that its size can be intractable, depending on the complexity of the essential graph of the equivalence class. The emphasis is put on the potential use of this space with greedy hillclimbing search.
Categories: Articles
Langages: English
Files: *.pdf
Title: Markov Equivalence in Bayesian Networks
Authors: Ildik o Flesch, Peter Lucas
Level: Advanced
Abstract:
Probabilistic graphical models, such as Bayesian networks, allow representing conditional
independence information of randomvariables. These relations are graphically represented
by the presence and absence of arcs and edges between vertices. Probabilistic graphical
models are nonunique representations of the independence information of a joint proba-
bility distribution. However, the concept of Markov equivalence of probabilistic graphical
models is able to o er unique representations, called essential graphs. In this survey paper
the theory underlying these concepts is reviewed.
Probabilistic graphical models, such as Bayesian networks, allow representing conditional independence information of randomvariables. These relations are graphically represented by the presence and absence of arcs and edges between vertices. Probabilistic graphical models are nonunique representations of the independence information of a joint probability distribution. However, the concept of Markov equivalence of probabilistic graphical models is able to o er unique representations, called essential graphs. In this survey paper the theory underlying these concepts is reviewed.
Categories: Articles
Langages: English
Files: *.pdf
Title: A Study on the Evolution of Bayesian Network Graph Structures
Authors: Jorge Muruzábal, Carlos Cotta
Level: Advanced
Abstract:
Bayesian Networks (BN) are often sought as useful descriptive and predictive models for the available data. Learning algorithms trying to ascertain automatically the best BN model (graph structure) for some input data are of the greatest interest for practical reasons. In this paper we examine a number of evolutionary programming algorithms for this network induction problem. Our algorithms build on recent advances in the field and are based on selection and various kinds of mutation operators (working at both the directed acyclic and essential graph level). A review of related evolutionary work is also provided. We analyze and discuss the merit and computational toll of these EP algorithms in a couple of benchmark tasks. Some general conclusions about the most efficient algorithms, and the most appropriate search landscapes are presented.
Categories: Articles
Langages: English
Files: *.pdf
Title: A Primer on the Evolution of Equivalence Classes of Bayesian-Network Structures
Authors: Jorge Muruzábal, Carlos Cotta
Level: Advanced
Abstract:
Bayesian networks (BN) constitute a useful tool to model the joint distribution of a set of random variables of interest. To deal with the problem of learning sensible BN models from data, we have previously considered various evolutionary algorithms for searching the space of BN structures directly. In this paper, we explore a simple evolutionary algorithm designed to search the space of BN equivalence classes. We discuss a number of issues arising in this evolutionary context and provide a first assessment of the new class of algorithms.
Categories: Articles
Langages: English
Files: *.pdf
On the Construction of the Inclusion Boundary Neighbourhood for Markov Equivalence Classes of BN
05/26/2010
Hits: 28