last updated : 11/10/2009
created      : 11/10/2009

DESCRIPTION:
------------

This code implements the Z2 algorithm [1], a particular way of
correcting the Belief Propagation (BP) solution based on a truncation
of the Loop Series Expansion proposed by Chertkov & Chernyak 
for planar graphs [2,3].

ARGUMENTS:
----------
																				
Required options:
  --filename arg        Filename of FactorGraph
  --all_comb arg        if 0 computes Z_2 corrections. If 1, all combinations of triplets (default 0) 
  --methods arg         AI methods to test

Allowed options:
  --help                produce help message
  --aliases arg         Filename for aliases
  --tol arg             Override tolerance
  --maxiter arg         Override maximum number of iterations
  --verbose arg         Override verbosity
  --R arg               random seed. If R!=0, BP messages are initialized randomly

REQUIREMENTS:
-------------

- Two boost libraries:

	libboost-graph-dev
	libboost_program_options

- GSL 

- libDAI [4] is required and included in directory ./libdai
	You will need to install the following packages for that
  apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev libboost-test-dev libgmp-dev cimg-dev


INSTALLATION:
-------------

Type:

$ chmod +x make_all.sh
$ make_all.sh

This should compile the libDAI library and generate an executable 'test_z2'.

EXAMPLE:
--------

The following example runs BP on the graph 'ising3x3.fg' and corrects the BP solution
using the Z_2 correction. The error of BP is corrected from 1.61281958499814e-03
to 2.05668091731801e-08.

-------------------------------------------------------------
$ ./test_z2 --filename ising3x3.fg --verbose 1 --tol 1e-14 --methods JTREE[updates=HUGIN,tol=1e-14,verbose=0]


-------------------------------------------------------------
The output is:

BP_SEQRANDOM
BP converged after 40 iterations using BP_SEQFIX maxdiff = 7.461370930828e-15
converting to Forney
6 of 6 triplets are not zero
60 vertices in Gext ~ O(216000)

1st. Pfaffian
0 Z_0: 0 loops. correction = 0.98488497391355
m_ZPfaffian 9.84884973913552e-01
sqrt(det(P)) = 9.84884973913552e-01
logZ_exact   = 9.44323116260007e+00 1.26224362296123e+04
logZ_bp      = 9.45846139076478e+00 1.28161502230687e+04
logZ_Pfaff   = 9.44323096838294e+00 2.24529818519847e+00

err_Z_bp     = 1.61281958499814e-03
err_Z0_Pfaff = 2.05668091731801e-08
err_Z_Pfaff  = 2.05668091731801e-08

-------------------------------------------------------------

The following example runs BP on the graph 'ising3x3.fg' and corrects the BP solution
using the full Pfaffian series. The error of BP is corrected from 1.61281958499814e-03
to 1.21609533995613e-16.

-------------------------------------------------------------
./test_z2 --all_comb 1 --filename ising3x3.fg --verbose 1 --tol 1e-14 --methods JTREE[updates=HUGIN,tol=1e-14,verbose=0]

-------------------------------------------------------------
The output is:

32 total combinations. 0 total loops 
m_ZPfaffian 9.84885165195106e-01
sqrt(det(P)) = 9.84885165195106e-01
logZ_exact   = 9.44323116260007e+00 1.26224362296123e+04
logZ_bp      = 9.45846139076478e+00 1.28161502230687e+04
logZ_Pfaff   = 9.44323116260007e+00 2.24529820576528e+00

err_Z_bp     = 1.61281958499814e-03
err_Z0_Pfaff = 2.05668091731801e-08
err_Z_Pfaff  = 1.21609533995613e-16

-------------------------------------------------------------
Vicenç Gomez,
v.gomez@science.ru.nl


REFERENCES:
-----------

[1] "Approximate inference on planar graphs using Loop Calculus and Belief Propagation"
    V. Gómez, H. J. Kappen, M. Chertkov
    Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009), Montreal, Canada. 
 
[2] "Loop series for discrete statistical models on graphs"
    M. Chertkov, V.Y. Chernyak
    Journal of Statistical Mechanics: Theory and Experiment (2006) P06009
    http://arxiv.org/abs/cond-mat/0603189

[3] "Belief Propagation and Loop Series on Planar Graphs"
    Journal of Statistical Mechanics: Theory and Experiment (2008) P05003 
    M. Chertkov, V.Y. Chernyak, R. Teodorescu
    http://www.iop.org/EJ/abstract/1742-5468/2008/05/P05003

[4] "libDAI - A free/open source C++ library for Discrete Approximate Inference methods"
    J.M. Mooij
    http://www.kyb.mpg.de/bs/people/jorism/libDAI/
