Gaining insight in the solution space of the MPE problem when changing evidence or parameter values

Abstract

For Bayesian networks, the MPE problem is the problem of finding a configuration of all unobserved variables such that this configuration has the highest posterior probability given the evidence. In this paper, we aim to gain more insight in the solution space of the MP E problem when evidence or a parameter value is changed and the previous MP E solution is known. Gaining more insight is a requisite for developing better algorithms for solving the problem. We do so by introducing a new representation of the probabilities of configurations in the Bayesian network.