Studies in Lower Bounding Probability of Evidence using the Markov Inequality
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.
Research Areas
