and b is irrelevant as long as it is the same for both. The constraint that q ( š,ep ) should be normalized can be incorporated in A and b by requiring

$$\sum_{\vec{s}_{\rm tsp}}q\left(\vec{s}_{\rm tsp}\right)\leq1\qquad\mbox{and}\qquad-\sum_{\vec{s}_{\rm tsp}}q\left(\vec{s}_{\rm tsp}\right)\leq-1\tag{11}$$

The maximum of c ⋅ x corresponds to p + ( š mar ). The negative of p − ( š mar ) can be found by using - c " x as the objective function.

## 2.2  A Simple Example

Imagine a single neuron, so, that is separated from the rest of the network by two other neurons, s 1 and s 2 .  We want to compute bounds on the marginal p ( s 0 = 1).  Since we do not know the distribution over the separator nodes, we have to consider all possible distributions as in Equation 5. Therefore we introduce the free parameters q ( s 1 s 2 ). The goal is now to compute the minimum and maximum of the function ∑ s1s2P ( s0 = 1 | s1 s2 ) q ( s1 s2 ).

In Figure 2a we show in three dimensions the space (the large pyramid) in which the distribution q ( s 1 s 2 ) lies. q (00) is implicitly given by one minus the three other values.

We can add, however, the earlier computed (single node) bounds on p ( s 1 ) and p ( s 2 )
to the problem. These restrict the space in Figure 2a further, since for instance (see also Equation 6)

$$q\left(s_{1}=1\right)=\sum_{s_{2}}q\left(s_{1}=1,\,s_{2}\right)=q\left(10\right)+q\left(11\right)\leq p_{+}\left(\,s_{1}=1\right)\tag{12}$$

We have four independent constraints, which are shown in Figure 2a as planes in the pyramid.

Obviously, by adding this information the space in which q ( s 1 s 2 ) may lie is restricted to that shown in Figure 2b. In the same figure we have added black lines, which correspond to the planes where the objective function is constant. A standard linear programming tool will immediately return the maximum and the minimum of this function thus bounding the marginal p ( so = 1 ).

## 3. The Algorithm In Detail

To solve an arbitrary network we first determine the set Ω of all S ico we will use for the problem. We choose

$$\Omega\left(N\right)=\,\left\{S_{\mathrm{sep}}\,\mid\,\|S_{\mathrm{cl}}\|\,\leq\,N\,\land\,\forall_{s\not\in S_{\mathrm{cl}}}\,\,\|S_{\mathrm{cl}}\,\cup\,s\|\,>\,N\,\right\}$$
$$(13)$$

where S cl is the cluster S tep U S mar U S oth and s denotes a single node. This choice limits the state space of S cl to N, which more or less determines the computation time. If we choose, for example, N = 2 5 for the Ising grid in Figure 1 assuming binary nodes, only the configuration in Figure 1a would be included in Ω. Choosing N = 2 8 puts the configurations in Figure 1b–d and a few others not shown into Ω, but not Figure 1a, since that separator is already embedded in larger ones (e.g. Figure 1d). In other words: Ω( N ) is the set of all S,ep for which ‖ S,ep ∪ S mar ∪ S oth ‖ is not larger than N, but if we add a single node it would cross that boundary.