# Bound Propagation

## Martijn Leisink Bert Kappen

University of Nimegen, Department of Biophysics Geert Grooteplein 21, 6525EZ Nimegen, The Netherlands MARTIJN@MBFYS.KUN.NL
BEKT © M BFY S . KUN . N L

## 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.

## 1. Introduction

Graphical models have become a popular and powerful tool to deal with dependencies in a complex probability model. For small networks an exact computation of the marginal probabilities for certain nodes is feasible (see, for example Zhang & Poole, 1994).  Unfortunately, due to an exponential scaling of the computational complexity, these exact algorithms soon fail for somewhat more complex and more realistic networks.

To deal with this computational problem two main streams can be distinguished. Firstly, there is the approach of approximating the exact solution. Numerous algorithms have been developed among which are mean field (Peterson & Anderson, 1987; Saul et al., 1996) and TAP (Thouless et al., 1977; Plefka, 1981). Nowadays, approximation methods such as belief propagation (Murphy et al., 1999; Yedidia et al., 2000) using the Bethe or Kikuchi energy are gaining popularity. In contrast with mean field expansions, the latter methods try to model only the local probability distributions of several small clusters, which communicate with each other in a way known as message passing.

The second approach is that of finding upper and lower bounds on important quantities of the graphical model. In contrast to approximation techniques, these methods give reliable information. One may find, for instance, that a marginal probability is definitely between 0.4 and 0.5.  These methods usually focus on the partition function of the network, which can be lower bounded (Leisink & Kappen, 2001) or upper bounded (Wainwright et al., 2002).

Little work has been done, however, on bounding the marginal probabities for certain nodes in the network directly. Up to now researchers have focused their attention on combining upper and lower bounds on the partition function in which way bounds on the marginals can be derived. For the special case of the Boltzmann machine this was done by Leisink and Kappen (2002).