Publications & Technical Reports | |
R150 | ||
An anytime scheme for bounding posterior beliefs
Bozhena Bidyuk, Rina Dechter,
Emma Rollon |
Abstract
This paper presents an any-time scheme for computing lower and upper
bounds
on the posterior marginals in Bayesian networks with discrete
variables.
Its power is in that it can use any available scheme that bounds the
probability of evidence, enhance its performance in an anytime
manner, and
transform it effectively into bounds for posterior marginals. The
scheme is
novel in that using the cutset condition principle (Pearl, 1988),
it converts a bound on joint probabilities into a bound on the
posterior
marginals that is tighter than earlier schemes, while at the same
time
facilitates anytime improved performance. At the heart of the scheme
is a
new data structure which facilitate the efficient computation of such
a
bound without enumerating all the cutset tuples. Using a variant of
bound
propagation algorithm (Leisink and Kappen, 2003) as the plugged-in
scheme,
we demonstrate empirically the value of our scheme, for bounding
posterior
marginals and probability of evidence.
[pdf] |