We propose a novel bound on single-variable marginal probability distributions in factor graphs with discrete variables. The bound is obtained by propagating local bounds (convex sets of probability distributions) over a subtree of the factor graph, rooted in the variable of interest. By construction, the method not only bounds the exact marginal probability distribution of a variable, but also its approximate Belief Propagation marginal ("belief"). Thus, apart from providing a practical means to calculate bounds on marginals, our contribution also lies in providing a better understanding of the error made by Belief Propagation. We show that our bound outperforms the state-of-the-art on some inference problems arising in medical diagnosis.
| Author(s): | Mooij, JM. and Kappen, B. |
| Book Title: | Advances in neural information processing systems 21 |
| Journal: | Advances in neural information processing systems 21 : 22nd Annual Conference on Neural Information Processing Systems 2008 |
| Pages: | 1105-1112 |
| Year: | 2009 |
| Month: | June |
| Day: | 0 |
| Editors: | Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou |
| Publisher: | Curran |
| Bibtex Type: | Conference Paper (inproceedings) |
| Address: | Red Hook, NY, USA |
| Event Name: | Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS 2008) |
| Event Place: | Vancouver, BC, Canada |
| Digital: | 0 |
| Electronic Archiving: | grant_archive |
| ISBN: | 978-1-605-60949-2 |
| Language: | en |
| Organization: | Max-Planck-Gesellschaft |
| School: | Biologische Kybernetik |
| Links: | |
BibTex
@inproceedings{5407,
title = {Bounds on marginal probability distributions},
journal = {Advances in neural information processing systems 21 : 22nd Annual Conference on Neural Information Processing Systems 2008},
booktitle = {Advances in neural information processing systems 21},
abstract = {We propose a novel bound on single-variable marginal probability distributions in factor graphs with discrete variables. The bound is obtained by propagating local
bounds (convex sets of probability distributions) over a subtree of the factor graph, rooted in the variable of interest. By construction, the method not only bounds
the exact marginal probability distribution of a variable, but also its approximate Belief Propagation marginal ("belief"). Thus, apart from providing a practical
means to calculate bounds on marginals, our contribution also lies in providing a better understanding of the error made by Belief Propagation. We show that our bound outperforms the state-of-the-art on some inference problems arising in medical diagnosis.},
pages = {1105-1112},
editors = {Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou},
publisher = {Curran},
organization = {Max-Planck-Gesellschaft},
school = {Biologische Kybernetik},
address = {Red Hook, NY, USA},
month = jun,
year = {2009},
slug = {5407},
author = {Mooij, JM. and Kappen, B.},
month_numeric = {6}
}