Variational Chernoff Bounds for Graphical Models
This provides rigorous probability bounds for graphical models, addressing a limitation in variational estimates, though it is incremental as it builds on existing work.
The paper tackled the problem of bounding event probabilities in graphical models, deriving rigorous upper and lower bounds using generalized Chernoff bounds and convex optimization, with simulations showing useful results at comparable computational cost to heuristic methods.
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.