The Persistence of Most Probable Explanations in Bayesian Networks

Monitoring applications of Bayesian networks require computing a sequence of most probable explanations for the observations from a monitored entity at consecutive time steps. Such applications rapidly become impracticable, especially when computations are performed in real time. In this paper, we argue that a sequence of explanations can often be feasibly computed if consecutive time steps share large numbers of observed features. We show more specifically that we can conclude persistence of an explanation at an early stage of propagation. We present an algorithm that exploits this result to forestall unnecessary re-computation of explanation