# Presentation: 322937

## Belief Propagation and Loop Series on Planar Graphs

**Volodya Chernyak, **Misha Chertkov and Razvan Teodorescu
- Department of Chemistry, Wayne State University
- Theory Division, Los Alamos National Laboratory

## Acknowledgements

- John Klein (Wayne State)

## Outline

- Vertex model formulation for statistical inference problem
- Traces and graphical traces
- Gauge-invariant formulation of loop calculus
- From single-connected partition to dimer matching problem
- Pfaffian expression for the single partition
- Tractable models
- From general binary model to the dimer-monomer matching problem and Pfaffian series on planar graphs
- Fermion (Grassman), continuous and supersymmetric cases

## Statistical inference

## Vertex model formulation

- q-ary variables reside on edges

- Probability of a configuration

- Partition function

- Reduced variables

- Marginal probabilities

- can be expressed in terms of
- the derivatives of the free energy
- with respect to factor-functions

- Forney ’01; Loeliger ’01
- Baxter

## Loop calculus (binary alphabet)

- Belief Propagation (BP) is exact on a tree

## Equivalent models: gauge fixing and transformations

**Replace the model with an equivalent more convenient model**

- Invariant approach

- Coordinate approach

- (i) Introduce an invariant object that
-      describes partition function Z
- (ii) Different equivalent models
-      correspond to different coordinate
-      choices (gauge fixing)
- (iii) Gauge transformations are
-       changing the basis sets

- (i) Introduce a set of gauge transformations
-       that do not change Z
- (ii) Gauge transformations build new
-       equivalent models

**General strategy (based on linear algebra)**

- Replace q-ary alphabet with a q-dimensional vector space
- (letters are basis vectors)
- (ii) Represent Z by an invariant object graphical trace
- (iii) Gauge fixing is a basis set choice
- (iv) Gauge transformations are linear transformation of basis sets

## Gauge invariance: matrix formulation

- Gauge transformations of factor-functions

- with orthogonality conditions

**do not change the partition function**

## BP equations: matrix (coordinate) formulation

- No-loose-ends condition

- results in BP equations

- with

## BP equations: standard form

- A standard form of BP equations

- is reproduced using the following
- representation for the ground state

- Side remark: relation to iterative BP

## Graphical representation of trace and cyclic trace

- Trace

- Cyclic trace

- Summation over repeating subscripts/superscripts

- scalar product

## Graphic trace and partition function

- Collection of tensors (poly-vectors)

- Scalar products

- Graphic trace

- Orthogonality condition

- Tensors and factor-functions

## Partition function and graphic trace: gauge invariance

- Dual basis set of co-vectors
- (elements of the dual space)

- Orthogonality condition (two equivalent forms)

- Graphic trace: Evaluate scalar products (reside on edges) on tensors (reside vertices)

**Gauge invariance: graphic trace is an invariant object,**
**factor-functions are basis-set dependent**

**“****Gauge fixing” is a choice of an orthogonal basis set**

## Belief propagation gauge and BP equations

- Introduce local ground

- and excited (painted) states

- BP gauge: painted structures with
- loose ends should be forbidden
- (in particular, no allowed painted
- structures in a tree case)

**or, stated differently, results in BP equations in invariant form:**

## Loop decomposition: binary case

**A generalized loop visualizes**
**a single-configuration contribution**
**to the partition function in BP gauge**

- Beliefs (marginal probabilities)

## Homogeneous valence-three graphs

- From arbitrary- to valence-three vertices

- Transformation for Tanner graphs

- Planar valence-three graphs
- dual to a triangulation

## Single-connected partition: dimer model

- Transformation to the extended graph
- (Fisher’s trick)

- Single partition equivalent to dimer-matching
- problem on the extended graph

- “Single” partition function (regular loops)

## Pfaffian expression for dimer model

- Kasteleyn representation as a Pfaffian
- (from symmetric to skew-symmetric matrix)

## Tractable problems: reduction to single-connected

- BP equations: loose ends (valence one vertices) forbidden

- Additional equations: valence three vertices forbidden

**The model is equivalent to the dimer-matching problem**

## Pfaffian series for monomer-dimer model

- Expansion in dimers (triple colored vertices)

- Each term is computationally tractable

## Fermion representation and models

- Grassman variables

- Berezin integral

- Berezin-integral representation of  a Pfaffian

## Continuous and supersymmetric case: graphical sigma-models

- Scalar product: the space of states and its dual are equivalent

- No-loose-end requirement

- Continuous version of BP equations

## Supersymmetric sigma-models: supermanifolds

- dimension

- substrate (usual) manifold

- additional Grassman (anticommuting variables)

- Functions on a supermanifold

- Berezin integral (measure in a supermanifold)

- Any function on a supermanifold can be represented
- as a sum of its even and odd components

## Supersymmetric sigma models: graphic supertrace I

- Natural assumption: factor-functions
- are even functions on

- Introduce parities of the beliefs

- BP equations for parities

- Follows from the first two

- Edge parity is well-defined

- elements

- (number of connected components)

- Euler characteristic

## Supersymmetric sigma models: graphic supertrace II

- Decompose the vector spaces

- Graphic supertrace decomposition (generalizes the supertrace)

- results in a multi-reference loop expansion

- into reduced vector spaces

- is the graphic trace (partition function) of a reduced model

## We have formulated the statistical inference problem in terms of a graphical trace, which leads to the invariance of the partition function under a set of gauge transformations.
BP equations have been interpreted as a special choice of gauge
The generalized loop (net) expansion appears in a natural way in the BP gauge
For a planar graph we have performed the summation over single-connected loops
A class of tractable models have been identified
A Pfaffian series for a general binary vertex model case on a planar graph have been formulated

- BP equations have been interpreted as a special choice of gauge
- The generalized loop (net) expansion appears in a natural way in the BP gauge
- For a planar graph we have performed the summation over single-connected loops
- A class of tractable models have been identified
- A Pfaffian series for a general binary vertex model case on a planar graph have been formulated

- Summary

## Bibliography

-  M. Chertkov, V.Y. Chernyak, R. Teodorescu
*Belief Propagation and Loop Series on Planar Graphs*,
- arXiv:0802.3950v1 [cond-mat.stat-mech] (2008)
-  V.Y. Chernyak, M. Chertkov,
*Loop Calculus and Belief Propagation for q-ary Alphabet: Loop Tower*,
- proceeding of ISIT 2007, June2007, Nice, cs.IT/0701086
-   M. Chertkov, V.Y. Chernyak,
*Loop Calculus Helps to Improve Belief Propagation and *
*Linear Programming Decodings of Low-Density-Parity-Check Codes*,
- 44th Allerton Conference (September 27-29, 2006, Allerton, IL); arXiv:cs.IT/0609154
-   M. Chertkov, V.Y. Chernyak,
*Loop Calculus in Statistical Physics and Information Science*,
- Phys. Rev. E 73, 065102(R)(2006); cond-mat/0601487
-   M. Chertkov, V.Y. Chernyak,
*Loop series for discrete statistical models on graphs*,
- J. Stat. Mech. (2006) P06009,cond-mat/0603189

## Path forward: interplay of topological and geometrical equivalence

- Topological structure: the graph

- Geometrical structure: factor-functions

- Use topologically
- equivalent models

- Use geometrically
- equivalent models

**Combine**

- e.g. Weitz ’06

- +
-  improving BP
-  quantum version
-  etc

## Homotopy approach to loop decomposition

- Graph (arbitrary)

- Bouquet of circles

- Equivalent (same homotopy type)
- by contracting the tree to a point

- “circles”

**Both models are equivalent**

- Loop calculus for the bouquet model (independent loops) constitutes
- a resummation for the original model (generalized loops)

## Loop towers for q-ary alphabet: first step

- A generalized loop defines a vertex model on the corresponding subgraph
- with (q-1)-ary alphabet (first store above the ground store)

- Partition function for the subgraph model

**q>2 (non-binary case): more than one local excited state**

## Loop-tower expansion for q-ary alphabet

- Building the next level (store)

- Loop tower

## “Reduced Bethe free energy” (variational approach)

- Reduced Bethe free energy

- is an attempt to approximate the partition function Z in terms of the  ground-state
- contribution in a proper gauge

- with

- BP equations are recovered by the stationary point conditions

- Not a standard variational scheme: corrections can be of either sign

**What is the relation of the introduced functional to the Bethe free energy**
**(****Yedidia, Freeman, Weiss ‘01****)?**

## Bethe free energy for q-ary alphabet

- BP equations can be obtained as stationary points of the Bethe free energy
- functional of beliefs

- with natural constraints

## Bethe effective Lagrangian

- Variation of beliefs

- Values of beliefs

## Relation to Bethe free energy

- Variation of the
- ground state

- Variation of beliefs

- Gauge fixing

- Reduced Bethe free energy