Bound Propagation

F or sev eral small lusters of no des upp er and lo w er b ounds on the marginal v alues are omputed indep enden tly of the rest of the net w ork. The range of allo w ed proba-bilit y distributions o v er the surrounding no des is restri ted using earlier omputed b ounds. As w e will sho w, this an b e onsidered as a set of onstrain ts in a linear programming problem of whi h the ob je tiv e fun tion is the marginal probabilit y of the en ter no des. In this w a y kno wledge ab out the maginals of neigh b ouring lusters is passed to other lusters thereb y tigh tening the b ounds on their marginals. W e sho w that sharp b ounds an b e obtained for undire ted and dire ted graphs that are used for pra ti al appli ations, but for whi h exa t omputations are infeasible. F or small net w orks an exa t omputation of the marginal probabilities for ertain no des is feasible (see, for example Zhang & P o ole, 1994). Unfortunately, due to an exp onen tial s aling of the omputational omplexit y, these exa t algorithms so on fail for somewhat more omplex and more realisti net w orks. T o deal with this omputational problem t w o main streams an b e distinguished. Firstly, there is the approa h of appro ximating the exa t solution.