position of the partition function into a weighted sum over partition functions of spanning tractable (zero field) planar models. The resulting problem **is a convex optimization problem and, since exact inference can be done in each planar** *sub-***model, the bound can be**
calculated in polynomial time.

Another example is the work of Schraudolph and Kamenetsky (2008) which provides a framework for exact inference on a restricted class of planar graphs using the approach of Kasteleyn and Fisher. More precisely, they showed that any joint probability function defined on binary variables can be expressed in a functional form without external fields by adding a new auxiliary node linked to all the existing nodes. **Under this transformation,**
single-variable external fields can be allowed for a subset B **of variables. If the graphical**
model is B−**outerplanar, which means that there exists a planar embedding in which the**
subset B of the nodes lie on the same face, the techniques of Kasteleyn **and Fisher can still**
be applied.

Contrary to the two aforementioned approaches which rely on **exact inference on a**
tractable planar model, the loop calculus directly leads to **a framework for approximate** inference on general planar graphs. Truncating the loop series according to Chertkov et al.

(2008) already gives the exact result in the zero external field case. In the general planar case, however, this truncation may result into an accurate approximation that can be incrementally corrected by considering subsequent terms in the series.

In the next Section we review the main theoretical results of **the loop calculus approach for planar graphs and introduce the proposed algorithm. In Section 3 we provide**
experimental results on approximation of the partition function for regular grids and other types of planar graphs. We focus on a planar-intractable binary model with symmetric pairwise interactions but nonzero single variable potentials. The source code used to derive these results is freely available at http://www.mbfys.ru.nl/staff/v.gomez/**. We end this**
manuscript with conclusions and future work in Section 4.

## 2. Belief Propagation And Loop Series For Planar Graphs

We consider the Forney graph representation, also called general vertex model (Forney, 2001; Loeliger, 2004), of a probability distribution p(σ) defined over a vector σ **of binary**
variables (vectors are denoted using bold symbols). Forney **graphs are associated with** general graphical models which subsume other factor graphs, e.g. those correspondent to BNs and MRFs. In Appendix A we show how to convert a factor graph model to its equivalent Forney graph representation.

A binary Forney graph G := (V, E) consists of a set of nodes V where each node a ∈ V
represents an interaction and each edge (a, b) ∈ E represents a binary variable ab **which take**
values σab := {±1}. We denote ¯a the set of neighbors of node a. Interactions fa (σa**) are**
arbitrary functions defined over typically small subsets of variables where σa **is the vector**
of variables associated with node a, i.e. σa **:= (**σab1
, σab2
, . . .**) where** bi ∈ a¯.

The joint probability distribution of such a model factorizes as:

$$p\left(\mathbf{\sigma}\right)=Z^{-1}\prod_{a\in\mathcal{V}}f_{a}\left(\mathbf{\sigma}_{a}\right),\tag{1}$$

where Z **is the normalization factor, also called the partition function.**

