Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Variational Chernoff Bounds for Graphical Models
Pradeep Ravikumar, John Lafferty
Recent research has made significant progress on the problem of bounding log partition functions for exponential family graphical models. Such bounds have associated dual parameters that are often used as heuristic estimates of the marginal probabilities required in inference and learning. However these variational estimates do not give rigorous bounds on marginal probabilities, nor do they give estimates for probabilities of more general events than simple marginals. In this paper we build on this recent work by deriving rigorous upper and lower bounds on event probabilities for graphical models. Our approach is based on the use of generalized Chernoff bounds to express bounds on event probabilities in terms of convex optimization problems; these optimization problems, in turn, require estimates of generalized log partition functions. Simulations indicate that this technique can result in useful, rigorous bounds to complement the heuristic variational estimates, with comparable computational cost.
Keywords: null
Pages: 462-469
PS Link:
PDF Link: /papers/04/p462-ravikumar.pdf
AUTHOR = "Pradeep Ravikumar and John Lafferty",
TITLE = "Variational Chernoff Bounds for Graphical Models",
BOOKTITLE = "Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-04)",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "462--469"

hosted by DSL   •   site info   •   help