Lm. De Campos et al., Accelerating chromosome evaluation for partial abductive inference in Bayesian networks by means of explanation set absorption, INT J APPRO, 27(2), 2001, pp. 121-142
Partial abductive inference in Bayesian belief networks (BBNs) is intended
as the process of generating the K most probable configurations for a set o
f unobserved variables (the explanation set). This problem is NP-hard and s
o exact computation is not always possible. In previous works genetic algor
ithms (GAs) have been used to solve the problem in an approximate way by us
ing exact probabilities propagation as the evaluation function. However, al
though the translation of a partial abductive inference problem into a (set
of) probabilities propagation problem(s) enlarges the class of solvable pr
oblems, it is not enough for large networks. In this paper we try to enlarg
e the class of solvable problems by reducing the size of the graphical stru
cture in which probabilities propagation will be carried out, To achieve th
is reduction we present a method that yields a (forest of) clique tree(s) f
rom which the variables of the explanation set have been removed, but in wh
ich configurations of these variables can be evaluated. Experimental result
s show a significant speedup of the evaluation function when propagation is
performed over the obtained reduced graphical structure, (C) 2001 Elsevier
Science Inc. All rights reserved.