Next: Introduction
Bound Propagation
Martijn Leisink martijn@mbfys.kun.nl
Bert Kappen bert@mbfys.kun.nl
University of Nijmegen, Department of Biophysics
Geert Grooteplein 21, 6525EZ Nijmegen, The Netherlands
Abstract:
In this article we present an algorithm to compute bounds on the
marginals of a graphical model. For several small clusters of nodes upper
and lower bounds on the marginal values are computed independently of
the rest of the network. The range of allowed probability distributions
over the surrounding nodes is restricted using earlier computed bounds.
As we will show, this can be considered as a set of constraints in
a linear programming problem of which the objective function is the
marginal probability of the center nodes. In this way knowledge about
the maginals of neighbouring clusters is passed to other clusters thereby
tightening the bounds on their marginals. We show that sharp bounds
can be obtained for undirected and directed graphs that are used for
practical applications, but for which exact computations are
infeasible.
Martijn Leisink
2003-08-18