Grammar-Guided Evolutionary Construction of Bayesian Networks - Foundations on Natural and Artificial Computation - page 60

Grammar-Guided Evolutionary Construction of
Bayesian Networks

José M. Font, Daniel Manrique, and Eduardo Pascua

Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid. Campus
de Montegancedo, 28660 Boadilla del Monte, Spain
[e-mail], [e-mail], [e-mail]

Abstract. This paper proposes the EvoBANE system. EvoBANE auto-
matically generates Bayesian networks for solving special-purpose prob-
lems. EvoBANE evolves a population of individuals that codify Bayesian
networks until it finds near optimal individual that solves a given classi-
fication problem. EvoBANE has the flexibility to modify the constraints
that condition the solution search space, self-adapting to the specifi-
cations of the problem to be solved. The system extends the GGEAS
architecture. GGEAS is a general-purpose grammar-guided evolution-
ary automatic system, whose modular structure favors its application to
the automatic construction of intelligent systems. EvoBANE has been
applied to two classification benchmark datasets belonging to different
application domains, and statistically compared with a genetic algorithm
performing the same tasks. Results show that the proposed system per-
formed better, as it manages different complexity constraints in order to
find the simplest solution that best solves every problem.

Keywords: Evolutionary computation, Bayesian network, grammar-
guided genetic programming.

1 Introduction

Bayesian networks (BN) are computational tools that can perform probabistic
inference from data with uncertainty [1]. They have been applied as an auto-
matic reasoning mechanism to a wide range of domains [2,3]. A BN is a directed
acyclic graph (DAG) that codifies the existing dependencies between its nodes,
each of what contains a conditional probability table [4]. The automatic learning
of a BN from data is a two-step procedure composed of the design of the net-
work topology and the calculation of its conditional probability tables [5]. This
has been proven to be an NP-Hard procedure [6]. For this reason, knowledge
engineering techniques need to be used to achieve quality solutions [7].
Evolutionary computation has been successfully applied to solve search and
optimization problems, such as the generation of both symbolic and sub-symbolic
self-adapting intelligent systems [8]. Its application to the automatic construc-
tion of BN must overcome several diculties, such as the design of an accurate
codification system that can manage acyclic graphs and the implementation of