  We derive two related novel bounds on single-variable marginal probability
distributions in factor graphs with discrete variables. The first method
propagates bounds over a subtree of the factor graph rooted in the variable,
and the second method propagates bounds over the self-avoiding walk tree
starting at the variable. By construction, both methods not only bound 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
an increased understanding of the error made by Belief Propagation.
Empirically, we show that our bounds often outperform existing bounds in terms
of accuracy and/or computation time. We also show that our bounds can yield
nontrivial results for medical diagnosis inference problems.
