dai::MR Class Reference

Approximate inference algorithm by Montanari and Rizzo [MoR05]. More...

#include <dai/mr.h>

Inheritance diagram for dai::MR:

dai::DAIAlg< GRM > dai::InfAlg

List of all members.

Public Member Functions

 MR ()
 Default constructor.
 MR (const FactorGraph &fg, const PropertySet &opts)
 Construct from FactorGraph fg and PropertySet opts.
General InfAlg interface
virtual MRclone () const
 Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor).
virtual std::string identify () const
 Identifies itself for logging purposes.
virtual Factor belief (const Var &v) const
 Returns the (approximate) marginal probability distribution of a variable.
virtual Factor belief (const VarSet &) const
 Returns the (approximate) marginal probability distribution of a set of variables.
virtual Factor beliefV (size_t i) const
 Returns the (approximate) marginal probability distribution of the variable with index i.
virtual std::vector< Factorbeliefs () const
 Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm.
virtual Real logZ () const
 Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).
virtual void init ()
 Initializes all data structures of the approximate inference algorithm.
virtual void init (const VarSet &)
 Initializes all data structures corresponding to some set of variables.
virtual Real run ()
 Runs the approximate inference algorithm.
virtual Real maxDiff () const
 Returns maximum difference between single variable beliefs in the last iteration.
virtual size_t Iterations () const
 Returns number of iterations done (one iteration passes over the complete factorgraph).
virtual void setProperties (const PropertySet &opts)
 Set parameters of this inference algorithm.
virtual PropertySet getProperties () const
 Returns parameters of this inference algorithm converted into a PropertySet.
virtual std::string printProperties () const
 Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".

Public Attributes

struct dai::MR::Properties props

Static Public Attributes

static const char * Name = "MR"
 Name of this inference method.

Private Types

typedef boost::dynamic_bitset sub_nb
 Type used for managing a subset of neighbors.

Private Member Functions

Real sign (Real a)
 Returns the signum of a.
void init (size_t Nin, Real *_w, Real *_th)
 Initialize N, con, nb, tJ, theta.
void makekindex ()
 Initialize kindex.
Real init_cor ()
 Initialize cors.
Real init_cor_resp ()
 Calculate cors using response propagation.
void solvemcav ()
 Iterate update equations for cavity fields.
void solveM ()
 Calculate magnetizations.
Real _tJ (size_t i, sub_nb A)
 Calculate the product of all tJ[i][_j] for _j in A.
Real Omega (size_t i, size_t _j, size_t _l)
 Calculate $ \Omega^{(i)}_{j,l} $ as defined in [MoR05] eqn. (2.15).
Real T (size_t i, sub_nb A)
 Calculate $ T^{(i)}_A $ as defined in [MoR05] eqn. (2.17) with $ A = \{l_1,l_2,\dots\} $.
Real T (size_t i, size_t _j)
 Calculates $ T^{(i)}_j $ where j is the _j 'th neighbor of i.
Real Gamma (size_t i, size_t _j, size_t _l1, size_t _l2)
 Calculates $ \Gamma^{(i)}_{j,l_1l_2} $ as defined in [MoR05] eqn. (2.16).
Real Gamma (size_t i, size_t _l1, size_t _l2)
 Calculates $ \Gamma^{(i)}_{l_1l_2} $ as defined in [MoK07] on page 1141.
Real appM (size_t i, sub_nb A)
 Approximates moments of variables in A.
void sum_subs (size_t j, sub_nb A, Real *sum_even, Real *sum_odd)
 Calculate sum over all even/odd subsets B of A of _tJ(j,B) appM(j,B).

Private Attributes

bool supported
 Is the underlying factor graph supported?
std::vector< size_t > con
 con[i] = connectivity of spin i
std::vector< std::vector
< size_t > > 
nb
 nb[i] are the neighbours of spin i
std::vector< std::vector< Real > > tJ
 tJ[i][_j] is the hyperbolic tangent of the interaction between spin i and its neighbour nb[i][_j]
std::vector< Realtheta
 theta[i] is the local field on spin i
std::vector< std::vector< Real > > M
 M[i][_j] is $ M^{(i)}_j $.
std::vector< std::vector
< size_t > > 
kindex
 The _j 'th neighbour of spin i has spin i as its kindex[i][_j]'th neighbour.
std::vector< std::vector
< std::vector< Real > > > 
cors
 Cavity correlations.
size_t N
 Number of variables (spins).
std::vector< RealMag
 Magnetizations.
Real _maxdiff
 Maximum difference encountered so far.
size_t _iters
 Number of iterations needed.

Static Private Attributes

static const size_t kmax = 31
 Maximum connectivity.

Classes

struct  Properties
 Parameters for MR. More...


Detailed Description

Approximate inference algorithm by Montanari and Rizzo [MoR05].

Author:
Bastian Wemmenhove wrote the original implementation before it was merged into libDAI
Todo:
Clean up code (use a BipartiteGraph-like implementation for the graph structure, and BBP for response propagation).

Member Typedef Documentation

typedef boost::dynamic_bitset dai::MR::sub_nb [private]

Type used for managing a subset of neighbors.


Constructor & Destructor Documentation

dai::MR::MR (  )  [inline]

Default constructor.

dai::MR::MR ( const FactorGraph fg,
const PropertySet opts 
)

Construct from FactorGraph fg and PropertySet opts.

Parameters:
opts Parameters
See also:
Properties
Note:
This implementation only deals with binary variables and pairwise interactions.
Exceptions:
NOT_IMPLEMENTED if fg has factors depending on three or more variables or has variables with more than two possible states.


Member Function Documentation

virtual MR* dai::MR::clone (  )  const [inline, virtual]

Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor).

Implements dai::InfAlg.

string dai::MR::identify (  )  const [virtual]

Identifies itself for logging purposes.

Implements dai::InfAlg.

virtual Factor dai::MR::belief ( const Var v  )  const [inline, virtual]

Returns the (approximate) marginal probability distribution of a variable.

Note:
Before this method is called, run() should have been called.

Reimplemented from dai::InfAlg.

virtual Factor dai::MR::belief ( const VarSet vs  )  const [inline, virtual]

Returns the (approximate) marginal probability distribution of a set of variables.

Note:
Before this method is called, run() should have been called.
Exceptions:
NOT_IMPLEMENTED if not implemented/supported.
BELIEF_NOT_AVAILABLE if the requested belief cannot be calculated with this algorithm.

Implements dai::InfAlg.

Factor dai::MR::beliefV ( size_t  i  )  const [virtual]

Returns the (approximate) marginal probability distribution of the variable with index i.

For some approximate inference algorithms, using beliefV() is preferred to belief() for performance reasons.

Note:
Before this method is called, run() should have been called.

Reimplemented from dai::InfAlg.

vector< Factor > dai::MR::beliefs (  )  const [virtual]

Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm.

Note:
Before this method is called, run() should have been called.

Implements dai::InfAlg.

virtual Real dai::MR::logZ (  )  const [inline, virtual]

Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).

Note:
Before this method is called, run() should have been called.
Exceptions:
NOT_IMPLEMENTED if not implemented/supported

Implements dai::InfAlg.

virtual void dai::MR::init (  )  [inline, virtual]

Initializes all data structures of the approximate inference algorithm.

Note:
This method should be called at least once before run() is called.

Implements dai::InfAlg.

virtual void dai::MR::init ( const VarSet vs  )  [inline, virtual]

Initializes all data structures corresponding to some set of variables.

This method can be used to do a partial initialization after a part of the factor graph has changed. Instead of initializing all data structures, it only initializes those involving the variables in vs.

Exceptions:
NOT_IMPLEMENTED if not implemented/supported

Implements dai::InfAlg.

Real dai::MR::run (  )  [virtual]

Runs the approximate inference algorithm.

Note:
Before run() is called the first time, init() should have been called.

Implements dai::InfAlg.

virtual Real dai::MR::maxDiff (  )  const [inline, virtual]

Returns maximum difference between single variable beliefs in the last iteration.

Exceptions:
NOT_IMPLEMENTED if not implemented/supported

Implements dai::InfAlg.

virtual size_t dai::MR::Iterations (  )  const [inline, virtual]

Returns number of iterations done (one iteration passes over the complete factorgraph).

Exceptions:
NOT_IMPLEMENTED if not implemented/supported

Implements dai::InfAlg.

void dai::MR::setProperties ( const PropertySet opts  )  [virtual]

Set parameters of this inference algorithm.

The parameters are set according to the PropertySet opts. The values can be stored either as std::string or as the type of the corresponding MF::props member.

Implements dai::InfAlg.

PropertySet dai::MR::getProperties (  )  const [virtual]

Returns parameters of this inference algorithm converted into a PropertySet.

Implements dai::InfAlg.

string dai::MR::printProperties (  )  const [virtual]

Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".

Implements dai::InfAlg.

Real dai::MR::sign ( Real  a  )  [inline, private]

Returns the signum of a.

void dai::MR::init ( size_t  Nin,
Real _w,
Real _th 
) [private]

Initialize N, con, nb, tJ, theta.

void dai::MR::makekindex (  )  [private]

Initialize kindex.

Real dai::MR::init_cor (  )  [private]

Initialize cors.

Real dai::MR::init_cor_resp (  )  [private]

Calculate cors using response propagation.

void dai::MR::solvemcav (  )  [private]

Iterate update equations for cavity fields.

void dai::MR::solveM (  )  [private]

Calculate magnetizations.

Real dai::MR::_tJ ( size_t  i,
sub_nb  A 
) [private]

Calculate the product of all tJ[i][_j] for _j in A.

Parameters:
i variable index
A subset of neighbors of variable i

Real dai::MR::Omega ( size_t  i,
size_t  _j,
size_t  _l 
) [private]

Calculate $ \Omega^{(i)}_{j,l} $ as defined in [MoR05] eqn. (2.15).

Real dai::MR::T ( size_t  i,
sub_nb  A 
) [private]

Calculate $ T^{(i)}_A $ as defined in [MoR05] eqn. (2.17) with $ A = \{l_1,l_2,\dots\} $.

Parameters:
i variable index
A subset of neighbors of variable i

Real dai::MR::T ( size_t  i,
size_t  _j 
) [private]

Calculates $ T^{(i)}_j $ where j is the _j 'th neighbor of i.

Real dai::MR::Gamma ( size_t  i,
size_t  _j,
size_t  _l1,
size_t  _l2 
) [private]

Calculates $ \Gamma^{(i)}_{j,l_1l_2} $ as defined in [MoR05] eqn. (2.16).

Real dai::MR::Gamma ( size_t  i,
size_t  _l1,
size_t  _l2 
) [private]

Calculates $ \Gamma^{(i)}_{l_1l_2} $ as defined in [MoK07] on page 1141.

Real dai::MR::appM ( size_t  i,
sub_nb  A 
) [private]

Approximates moments of variables in A.

Calculate the moment of variables in A from M and cors, neglecting higher order cumulants, defined as the sum over all partitions of A into subsets of cardinality two at most of the product of the cumulants (either first order, i.e. M, or second order, i.e. cors) of the entries of the partitions.

Parameters:
i variable index
A subset of neighbors of variable i

void dai::MR::sum_subs ( size_t  j,
sub_nb  A,
Real sum_even,
Real sum_odd 
) [private]

Calculate sum over all even/odd subsets B of A of _tJ(j,B) appM(j,B).

Parameters:
j variable index
A subset of neighbors of variable j
sum_even on return, will contain the sum over all even subsets
sum_odd on return, will contain the sum over all odd subsets


Member Data Documentation

bool dai::MR::supported [private]

Is the underlying factor graph supported?

std::vector<size_t> dai::MR::con [private]

con[i] = connectivity of spin i

std::vector<std::vector<size_t> > dai::MR::nb [private]

nb[i] are the neighbours of spin i

std::vector<std::vector<Real> > dai::MR::tJ [private]

tJ[i][_j] is the hyperbolic tangent of the interaction between spin i and its neighbour nb[i][_j]

std::vector<Real> dai::MR::theta [private]

theta[i] is the local field on spin i

std::vector<std::vector<Real> > dai::MR::M [private]

M[i][_j] is $ M^{(i)}_j $.

std::vector<std::vector<size_t> > dai::MR::kindex [private]

The _j 'th neighbour of spin i has spin i as its kindex[i][_j]'th neighbour.

std::vector<std::vector<std::vector<Real> > > dai::MR::cors [private]

Cavity correlations.

const size_t dai::MR::kmax = 31 [static, private]

Maximum connectivity.

size_t dai::MR::N [private]

Number of variables (spins).

std::vector<Real> dai::MR::Mag [private]

Magnetizations.

Maximum difference encountered so far.

size_t dai::MR::_iters [private]

Number of iterations needed.

const char * dai::MR::Name = "MR" [static]

Name of this inference method.


The documentation for this class was generated from the following files:

Generated on Thu Feb 11 12:26:06 2010 for libDAI by  doxygen 1.5.5