Partial abductive inference in Bayesian belief networks by simulated annealing

AbstractAbductive inference in Bayesian belief networks (BBN) is intended as the process of generating the K most probable configurations given observed evidence. When we are only interested in a subset of the network variables, this problem is called partial abductive inference. Due to the noncommutative behaviour of the two operators (summation and maximum) involved in the computational process of solving partial abductive inference in BBNs, the process can be unfeasible by exact computation even for networks in which other types of probabilistic reasoning are not very complicated. This paper describes an approximate method to perform partial abductive inference in BBNs based on the simulated annealing (SA) algorithm. The algorithm can be applied to multiple connected networks and for any value of K. The evaluation function is based on clique tree propagation, and allow to evaluate neighbour configurations by means of local computations, in this way the efficiency with respect to previous algorithms (based on the use of genetic algorithms (GAs)) is improved