Approximate inference algorithm "(Loopy) Belief Propagation". More...

#include <dai/bp.h>

Inheritance diagram for dai::BP:

Classes
struct	EdgeProp
	Type used for storing edge properties. More...

struct	Properties
	Parameters for BP. More...

Public Member Functions
Constructors/destructors
	BP ()
	Default constructor. More...

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

	BP (const BP &x)
	Copy constructor. More...

BP &	operator= (const BP &x)
	Assignment operator. More...

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

virtual BP *	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 &vs) 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 Factor	beliefF (size_t I) const
	Returns the (approximate) marginal probability distribution of the variables on which factor I depends. 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...

std::vector< size_t >	findMaximum () const

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

virtual void	init (const VarSet &ns)
	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	setMaxIter (size_t maxiter)
	Sets maximum number of iterations (one iteration passes over the complete factorgraph). More...

virtual void	setProperties (const PropertySet &opts)

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

Additional interface specific for BP
const std::vector< std::pair< size_t, size_t > > &	getSentMessages () const
	Returns history of which messages have been updated. More...

void	clearSentMessages ()
	Clears history of which messages have been updated. 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...

Public Attributes
struct dai::BP::Properties	props

bool	recordSentMessages
	Specifies whether the history of message updates should be recorded. More...

Protected Types
typedef std::vector< size_t >	ind_t
	Type used for index cache. More...

typedef std::multimap< Real, std::pair< size_t, size_t > >	LutType
	Type of lookup table (only used for maximum-residual BP) More...

Protected Member Functions
const Prob &	message (size_t i, size_t _I) const
	Returns constant reference to message from the _I 'th neighbor of variable i to variable i. More...

Prob &	message (size_t i, size_t _I)
	Returns reference to message from the _I 'th neighbor of variable i to variable i. More...

const Prob &	newMessage (size_t i, size_t _I) const
	Returns constant reference to updated message from the _I 'th neighbor of variable i to variable i. More...

Prob &	newMessage (size_t i, size_t _I)
	Returns reference to updated message from the _I 'th neighbor of variable i to variable i. More...

const ind_t &	index (size_t i, size_t _I) const
	Returns constant reference to cached index for the edge between variable i and its _I 'th neighbor. More...

ind_t &	index (size_t i, size_t _I)
	Returns reference to cached index for the edge between variable i and its _I 'th neighbor. More...

const Real &	residual (size_t i, size_t _I) const
	Returns constant reference to residual for the edge between variable i and its _I 'th neighbor. More...

Real &	residual (size_t i, size_t _I)
	Returns reference to residual for the edge between variable i and its _I 'th neighbor. More...

virtual Prob	calcIncomingMessageProduct (size_t I, bool without_i, size_t i) const
	Calculate the product of factor I and the incoming messages. More...

virtual void	calcNewMessage (size_t i, size_t _I)
	Calculate the updated message from the _I 'th neighbor of variable i to variable i. More...

void	updateMessage (size_t i, size_t _I)
	Replace the "old" message from the _I 'th neighbor of variable i to variable i by the "new" (updated) message. More...

void	updateResidual (size_t i, size_t _I, Real r)
	Set the residual (difference between new and old message) for the edge between variable i and its _I 'th neighbor to r. More...

void	findMaxResidual (size_t &i, size_t &_I)
	Finds the edge which has the maximum residual (difference between new and old message) More...

virtual void	calcBeliefV (size_t i, Prob &p) const
	Calculates unnormalized belief of variable i. More...

virtual void	calcBeliefF (size_t I, Prob &p) const
	Calculates unnormalized belief of factor I. More...

virtual void	construct ()
	Helper function for constructors. More...

Protected Attributes
std::vector< std::vector< EdgeProp > >	_edges
	Stores all edge properties. More...

std::vector< std::vector< LutType::iterator > >	_edge2lut
	Lookup table (only used for maximum-residual BP) More...

LutType	_lut
	Lookup table (only used for maximum-residual BP) More...

Real	_maxdiff
	Maximum difference between variable beliefs encountered so far. More...

size_t	_iters
	Number of iterations needed. More...

std::vector< std::pair< size_t, size_t > >	_sentMessages
	The history of message updates (only recorded if recordSentMessages is `true`) More...

std::vector< Factor >	_oldBeliefsV
	Stores variable beliefs of previous iteration. More...

std::vector< Factor >	_oldBeliefsF
	Stores factor beliefs of previous iteration. More...

std::vector< Edge >	_updateSeq
	Stores the update schedule. More...

Detailed Description

Approximate inference algorithm "(Loopy) Belief Propagation".

The Loopy Belief Propagation algorithm uses message passing to approximate marginal probability distributions ("beliefs") for variables and factors (more precisely, for the subset of variables depending on the factor). There are two variants, the sum-product algorithm (corresponding to finite temperature) and the max-product algorithm (corresponding to zero temperature).

The messages $m_{I\to i}(x_i)$ are passed from factors $I$ to variables $i$ . In case of the sum-product algorith, the update equation is:

$m_{I\to i}(x_i) \propto \sum_{x_{N_I\setminus\{i\}}} f_I(x_I) \prod_{j\in N_I\setminus\{i\}} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}$

and in case of the max-product algorithm:

$m_{I\to i}(x_i) \propto \max_{x_{N_I\setminus\{i\}}} f_I(x_I) \prod_{j\in N_I\setminus\{i\}} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}$

In order to improve convergence, the updates can be damped. For improved numerical stability, the updates can be done in the log-domain alternatively.

After convergence, the variable beliefs are calculated by:

$b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i}(x_i)$

and the factor beliefs are calculated by:

$b_I(x_I) \propto f_I(x_I) \prod_{j\in N_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}(x_j)$

The logarithm of the partition sum is calculated by:

$\log Z = \sum_i (1 - |N_i|) \sum_{x_i} b_i(x_i) \log b_i(x_i) - \sum_I \sum_{x_I} b_I(x_I) \log \frac{b_I(x_I)}{f_I(x_I)}$

For the max-product algorithm, a heuristic way of finding the MAP state (the joint configuration of all variables which has maximum probability) is provided by the findMaximum() method, which can be called after convergence.

Note: There are two implementations, an optimized one (the default) which caches IndexFor objects, and a slower, less complicated one which is easier to maintain/understand. The slower one can be enabled by defining DAI_BP_FAST as false in the source file.

Examples:: example.cpp.

Member Typedef Documentation

typedef std::vector<size_t> dai::BP::ind_t

protected

Type used for index cache.

typedef std::multimap<Real, std::pair<size_t, size_t> > dai::BP::LutType

protected

Type of lookup table (only used for maximum-residual BP)

Constructor & Destructor Documentation

dai::BP::BP ( )

inline

Default constructor.

dai::BP::BP	(	const FactorGraph &	fg,
		const PropertySet &	opts
	)

inline

Construct from FactorGraph fg and PropertySet opts.

Parameters

fg	Factor graph.
opts	Parameters

See also: Properties

dai::BP::BP ( const BP & x )

inline

Copy constructor.

Member Function Documentation

BP& dai::BP::operator= ( const BP & x )

inline

Assignment operator.

virtual BP* dai::BP::clone ( ) const

inlinevirtual

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

Implements dai::InfAlg.

Reimplemented in dai::TRWBP, and dai::FBP.

virtual BP* dai::BP::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.

Reimplemented in dai::TRWBP, and dai::FBP.

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

inlinevirtual

Returns the name of the algorithm.

Implements dai::InfAlg.

Reimplemented in dai::TRWBP, and dai::FBP.

virtual Factor dai::BP::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.

Examples:: example.cpp.

Factor dai::BP::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::BP::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.

Factor dai::BP::beliefF ( size_t I ) const

virtual

Returns the (approximate) marginal probability distribution of the variables on which factor I depends.

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

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

Reimplemented from dai::InfAlg.

Examples:: example.cpp.

vector< Factor > dai::BP::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.

Real dai::BP::logZ ( ) const

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.

Reimplemented in dai::TRWBP, and dai::FBP.

Examples:: example.cpp.

std::vector<size_t> dai::BP::findMaximum ( ) const

inlinevirtual

Precondition: Assumes that run() has been called and that props.inference == MAXPROD

Reimplemented from dai::InfAlg.

Examples:: example.cpp.

void dai::BP::init ( )

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.

Examples:: example.cpp.

void dai::BP::init ( const VarSet & vs )

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::BP::run ( )

virtual

Runs the approximate inference algorithm.

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

Implements dai::InfAlg.

Examples:: example.cpp.

virtual Real dai::BP::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::BP::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.

virtual void dai::BP::setMaxIter ( size_t )

inlinevirtual

Sets maximum number of iterations (one iteration passes over the complete factorgraph).

Exceptions

NOT_IMPLEMENTED if not implemented/supported

Reimplemented from dai::InfAlg.

void dai::BP::setProperties ( const PropertySet & opts )

virtual

Todo:: Make DAI_BP_FAST a compile-time choice, as it is a memory/speed tradeoff

Implements dai::InfAlg.

Reimplemented in dai::TRWBP.

PropertySet dai::BP::getProperties ( ) const

virtual

Returns parameters of this inference algorithm converted into a PropertySet.

Implements dai::InfAlg.

Reimplemented in dai::TRWBP.

string dai::BP::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.

Reimplemented in dai::TRWBP.

const std::vector<std::pair<size_t, size_t> >& dai::BP::getSentMessages ( ) const

inline

Returns history of which messages have been updated.

void dai::BP::clearSentMessages ( )

inline

Clears history of which messages have been updated.

const Prob& dai::BP::message	(	size_t	i,
		size_t	_I
	)		const

inlineprotected

Returns constant reference to message from the _I 'th neighbor of variable i to variable i.

Prob& dai::BP::message	(	size_t	i,
		size_t	_I
	)

inlineprotected

Returns reference to message from the _I 'th neighbor of variable i to variable i.

const Prob& dai::BP::newMessage	(	size_t	i,
		size_t	_I
	)		const

inlineprotected

Returns constant reference to updated message from the _I 'th neighbor of variable i to variable i.

Prob& dai::BP::newMessage	(	size_t	i,
		size_t	_I
	)

inlineprotected

Returns reference to updated message from the _I 'th neighbor of variable i to variable i.

const ind_t& dai::BP::index	(	size_t	i,
		size_t	_I
	)		const

inlineprotected

Returns constant reference to cached index for the edge between variable i and its _I 'th neighbor.

ind_t& dai::BP::index	(	size_t	i,
		size_t	_I
	)

inlineprotected

Returns reference to cached index for the edge between variable i and its _I 'th neighbor.

const Real& dai::BP::residual	(	size_t	i,
		size_t	_I
	)		const

inlineprotected

Returns constant reference to residual for the edge between variable i and its _I 'th neighbor.

Real& dai::BP::residual	(	size_t	i,
		size_t	_I
	)

inlineprotected

Returns reference to residual for the edge between variable i and its _I 'th neighbor.

Prob dai::BP::calcIncomingMessageProduct	(	size_t	I,
		bool	without_i,
		size_t	i
	)		const

protectedvirtual

Calculate the product of factor I and the incoming messages.

If without_i == true, the message coming from variable i is omitted from the product

Note: This function is used by calcNewMessage() and calcBeliefF()

Reimplemented in dai::TRWBP, and dai::FBP.

void dai::BP::calcNewMessage	(	size_t	i,
		size_t	_I
	)

protectedvirtual

Calculate the updated message from the _I 'th neighbor of variable i to variable i.

Reimplemented in dai::FBP.

void dai::BP::updateMessage	(	size_t	i,
		size_t	_I
	)

protected

Replace the "old" message from the _I 'th neighbor of variable i to variable i by the "new" (updated) message.

void dai::BP::updateResidual	(	size_t	i,
		size_t	_I,
		Real	r
	)

protected

Set the residual (difference between new and old message) for the edge between variable i and its _I 'th neighbor to r.

void dai::BP::findMaxResidual	(	size_t &	i,
		size_t &	_I
	)

protected

Finds the edge which has the maximum residual (difference between new and old message)

void dai::BP::calcBeliefV	(	size_t	i,
		Prob &	p
	)		const

protectedvirtual

Calculates unnormalized belief of variable i.

Reimplemented in dai::TRWBP.

virtual void dai::BP::calcBeliefF	(	size_t	I,
		Prob &	p
	)		const

inlineprotectedvirtual

Calculates unnormalized belief of factor I.

Reimplemented in dai::TRWBP, and dai::FBP.

void dai::BP::construct ( )

protectedvirtual

Helper function for constructors.

Reimplemented in dai::TRWBP, and dai::FBP.

Member Data Documentation

std::vector<std::vector<EdgeProp> > dai::BP::_edges

protected

Stores all edge properties.

std::vector<std::vector<LutType::iterator> > dai::BP::_edge2lut

protected

Lookup table (only used for maximum-residual BP)

LutType dai::BP::_lut

protected

Lookup table (only used for maximum-residual BP)

Real dai::BP::_maxdiff

protected

Maximum difference between variable beliefs encountered so far.

size_t dai::BP::_iters

protected

Number of iterations needed.

std::vector<std::pair<size_t, size_t> > dai::BP::_sentMessages

protected

The history of message updates (only recorded if recordSentMessages is true)

std::vector<Factor> dai::BP::_oldBeliefsV

protected

Stores variable beliefs of previous iteration.

std::vector<Factor> dai::BP::_oldBeliefsF

protected

Stores factor beliefs of previous iteration.

std::vector<Edge> dai::BP::_updateSeq

protected

Stores the update schedule.

bool dai::BP::recordSentMessages

Specifies whether the history of message updates should be recorded.

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

include/dai/bp.h
src/bp.cpp

Classes

Public Member Functions

Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation