Analysis of the behaviour of the MPE in a Bayesian network that is subject to changes

Abstract

An important computational problem in Bayesian networks is to find the most likely set of states of all unobserved variables in the network given the states of the observed variables, the evidence. This problem is known as the MPE problem. Especially for applications with real- time requirements, re-computations of the MPE after changes in the evidence will not always be manageable. In this thesis, we will investigate how the MPE changes as a result of a change in the evidence. The research is performed on basis of a junction tree that can be constructed from a Bayesian network. We present theoretical results about how changes in the evidence affect the probabilities in the junction tree and introduce a way to visualize this. We further on carry out several experiments on well-known Bayesian networks. In these experiments, the consequences of a single change in the evidence are studied. We investigate how the change is propagated through the junction tree and how the MPE variables are affected. We extend these experiments by considering the more general problem - the MAP problem. The results of these experiments indicate that changes caused by a change in evidence decreases quickly as we propagate it through the junction tree. Furthermore, in general only a small number of MPE and MAP variables change of state and these variables are close to the variable that changed in the evidence.