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

#include <dai/mr.h>

Inheritance diagram for dai::MR:

Classes
struct	Properties
	Parameters for MR. More...

Public Member Functions
	MR ()
	Default constructor. More...

	MR (const FactorGraph &fg, const PropertySet &opts)
	Construct from FactorGraph fg and PropertySet opts. More...

General InfAlg interface
virtual MR *	clone () const
	Returns a pointer to a new, cloned copy of `*this` (i.e., virtual copy constructor) More...

virtual MR *	construct (const FactorGraph &fg, const PropertySet &opts) const
	Returns a pointer to a newly constructed inference algorithm. More...

virtual std::string	name () const
	Returns the name of the algorithm. More...

virtual Factor	belief (const Var &v) const
	Returns the (approximate) marginal probability distribution of a variable. More...

virtual Factor	belief (const VarSet &) const
	Returns the (approximate) marginal probability distribution of a set of variables. More...

virtual Factor	beliefV (size_t i) const
	Returns the (approximate) marginal probability distribution of the variable with index i. More...

virtual std::vector< Factor >	beliefs () const
	Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm. More...

virtual Real	logZ () const
	Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph). More...

virtual void	init ()
	Initializes all data structures of the approximate inference algorithm. More...

virtual void	init (const VarSet &)
	Initializes all data structures corresponding to some set of variables. More...

virtual Real	run ()
	Runs the approximate inference algorithm. More...

virtual Real	maxDiff () const
	Returns maximum difference between single variable beliefs in the last iteration. More...

virtual size_t	Iterations () const
	Returns number of iterations done (one iteration passes over the complete factorgraph). More...

virtual void	setProperties (const PropertySet &opts)
	Set parameters of this inference algorithm. More...

virtual PropertySet	getProperties () const
	Returns parameters of this inference algorithm converted into a PropertySet. More...

virtual std::string	printProperties () const
	Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]". More...

Public Member Functions inherited from dai::DAIAlg< GRM >
	DAIAlg ()
	Default constructor. More...

	DAIAlg (const GRM &grm)
	Construct from GRM. More...

FactorGraph &	fg ()
	Returns reference to underlying FactorGraph. More...

const FactorGraph &	fg () const
	Returns constant reference to underlying FactorGraph. More...

void	clamp (size_t i, size_t x, bool backup=false)
	Clamp variable with index i to value x (i.e. multiply with a Kronecker delta $\delta_{x_i, x}$ ) More...

void	makeCavity (size_t i, bool backup=false)
	Sets all factors interacting with variable with index i to one. More...

void	makeRegionCavity (std::vector< size_t > facInds, bool backup)
	Sets all factors indicated by facInds to one. More...

void	backupFactor (size_t I)
	Make a backup copy of factor I. More...

void	backupFactors (const VarSet &vs)
	Make backup copies of all factors involving the variables in vs. More...

void	restoreFactor (size_t I)
	Restore factor I from its backup copy. More...

void	restoreFactors (const VarSet &vs)
	Restore the factors involving the variables in vs from their backup copies. More...

void	restoreFactors ()
	Restore all factors from their backup copies. More...

Public Member Functions inherited from dai::InfAlg
virtual	~InfAlg ()
	Virtual destructor (needed because this class contains virtual functions) More...

virtual std::string	identify () const
	Identifies itself for logging purposes. More...

virtual Factor	beliefF (size_t I) const
	Returns the (approximate) marginal probability distribution of the variables on which factor I depends. More...

virtual std::vector< size_t >	findMaximum () const
	Calculates the joint state of all variables that has maximum probability. More...

virtual void	setMaxIter (size_t)
	Sets maximum number of iterations (one iteration passes over the complete factorgraph). More...

Public Attributes
struct dai::MR::Properties	props

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

Private Member Functions
Real	calcCavityCorrelations ()
	Initialize cors. More...

void	propagateCavityFields ()
	Iterate update equations for cavity fields. More...

void	calcMagnetizations ()
	Calculate magnetizations. More...

Real	_tJ (size_t i, sub_nb A)
	Calculate the product of all tJ[i][_j] for _j in A. More...

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

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\}$ . More...

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

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) More...

Real	Gamma (size_t i, size_t _l1, size_t _l2)
	Calculates $\Gamma^{(i)}_{l_1l_2}$ as defined in [MoK07] on page 1141. More...

Real	appM (size_t i, sub_nb A)
	Approximates moments of variables in A. More...

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) More...

Private Attributes
bool	supported
	Is the underlying factor graph supported? More...

GraphAL	G
	The interaction graph (Markov graph) More...

std::vector< std::vector< Real > >	tJ
	tJ[i][_j] is the hyperbolic tangent of the interaction between spin i and its neighbour G.nb(i,_j) More...

std::vector< Real >	theta
	theta[i] is the local field on spin i More...

std::vector< std::vector< Real > >	M
	M[i][_j] is $M^{(i)}_j$ . More...

std::vector< std::vector< std::vector< Real > > >	cors
	Cavity correlations. More...

std::vector< Real >	Mag
	Magnetizations. More...

Real	_maxdiff
	Maximum difference encountered so far. More...

size_t	_iters
	Number of iterations needed. More...

Detailed Description

Approximate inference algorithm by Montanari and Rizzo [MoR05].

Author: Bastian Wemmenhove wrote the original implementation before it was merged into libDAI

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

fg	Factor graph.
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

inlinevirtual

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

Implements dai::InfAlg.

virtual MR* dai::MR::construct	(	const FactorGraph &	fg,
		const PropertySet &	opts
	)		const

inlinevirtual

Returns a pointer to a newly constructed inference algorithm.

Parameters

fg	Factor graph on which to perform the inference algorithm;
opts	Parameters passed to constructor of inference algorithm;

Implements dai::InfAlg.

virtual std::string dai::MR::name ( ) const

inlinevirtual

Returns the name of the algorithm.

Implements dai::InfAlg.

virtual Factor dai::MR::belief ( const Var & v ) const

inlinevirtual

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

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

Reimplemented from dai::InfAlg.

Factor dai::MR::belief ( const VarSet & vs ) const

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

inlinevirtual

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 ( )

inlinevirtual

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 )

inlinevirtual

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

inlinevirtual

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

Exceptions

NOT_IMPLEMENTED if not implemented/supported

Reimplemented from dai::InfAlg.

virtual size_t dai::MR::Iterations ( ) const

inlinevirtual

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

Exceptions

NOT_IMPLEMENTED if not implemented/supported

Reimplemented from 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::calcCavityCorrelations ( )

private

Initialize cors.

void dai::MR::propagateCavityFields ( )

private

Iterate update equations for cavity fields.

void dai::MR::calcMagnetizations ( )

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?

GraphAL dai::MR::G

private

The interaction graph (Markov graph)

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 G.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<std::vector<Real> > > dai::MR::cors

private

Cavity correlations.

std::vector<Real> dai::MR::Mag

private

Magnetizations.

Real dai::MR::_maxdiff

private

Maximum difference encountered so far.

size_t dai::MR::_iters

private

Number of iterations needed.

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

include/dai/mr.h
src/mr.cpp

Classes

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation