Studies in Lower Bounding Probability of Evidence using the Markov Inequality
Venue
UAI, Morgan Kaufmann (2007)
Publication Year
2007
Authors
Vibhav Gogate, Bozhena Bidyuk, Rina Dechter
BibTeX
Abstract
Computing the probability of evidence even with known error bounds is NP-hard. In
this paper we address this hard problem by settling on an easier problem. We
propose an approximation that provides high confidence lower bounds on probability
of evidence. Our proposed approximation is a randomized importance sampling based
scheme that uses the Markov inequality. However, a straight-forward application of
the Markov inequality may lead to poor lower bounds. We, therefore propose several
heuristic measures to improve its performance in practice. Empirical evaluation of
our scheme with state-of-the-art lower bounding schemes reveals the promise of our
approach.
