Bound Propagation

Details Bound Propagation Bound Propagation

2011-06-24

arxiv.org/abs/1106.4865v1

Journal Of Artificial Intelligence Research, Volume 19, pages 139-154, 2003

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1130

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.

Affiliated with

Also associated with

No associations

Rating

Bound Propagation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bound Propagation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bound Propagation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393610