Approximate inference algorithm "Fractional Belief Propagation" [WiH03]. More...

#include <dai/fbp.h>

Inheritance diagram for dai::FBP:

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

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

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

virtual FBP *	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 Real	logZ () const
	Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph). More...

Public Member Functions inherited from dai::BP
	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...

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

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

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

Protected Attributes
std::vector< Real >	_weight
	Factor weights (indexed by factor ID) More...

Protected Attributes inherited from dai::BP
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...

FBP accessors/mutators for weights
Real	Weight (size_t I) const
	Returns weight of the I 'th factor. More...

const std::vector< Real > &	Weights () const
	Returns constant reference to vector of all factor weights. More...

void	setWeight (size_t I, Real c)
	Sets the weight of the I 'th factor to c. More...

void	setWeights (const std::vector< Real > &c)
	Sets the weights of all factors simultaenously. 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...

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

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

Additional Inherited Members
Public Attributes inherited from dai::BP
struct dai::BP::Properties	props

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

Protected Types inherited from dai::BP
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 inherited from dai::BP
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...

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

Detailed Description

Approximate inference algorithm "Fractional Belief Propagation" [WiH03].

The Fractional Belief Propagation algorithm is like Belief Propagation, but associates each factor with a weight (scale parameter) which controls the divergence measure being minimized. Standard Belief Propagation corresponds to the case of FBP where each weight is 1. When cast as an EP algorithm, BP (and EP) minimize the inclusive KL-divergence, i.e. $\min_q KL(p||q)$ (note that the Bethe free energy is typically derived from $ KL(q||p) $ ). If each factor I has weight $ c_I $ , then FBP minimizes the alpha-divergence with $\alpha=1/c_I$ for that factor, which also corresponds to Power EP [Min05].

The messages $m_{I\to i}(x_i)$ are passed from factors $I$ to variables $i$ . The update equation is given by:

$m_{I\to i}(x_i) \propto \left( \sum_{x_{N_I\setminus\{i\}}} f_I(x_I)^{1/c_I} \prod_{j\in N_I\setminus\{i\}} m_{I\to j}^{1-1/c_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j} \right)^{c_I}$

After convergence, the variable beliefs are calculated by:

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

and the factor beliefs are calculated by:

$b_I(x_I) \propto f_I(x_I)^{1/c_I} \prod_{j \in N_I} m_{I\to j}^{1-1/c_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}$

The logarithm of the partition sum is approximated by:

$\log Z = \sum_{I} \sum_{x_I} b_I(x_I) \big( \log f_I(x_I) - c_I \log b_I(x_I) \big) + \sum_{i} (c_i - 1) \sum_{x_i} b_i(x_i) \log b_i(x_i)$

where the variable weights are defined as

$c_i := \sum_{I \in N_i} c_I$

Todo:

Add nice way to set weights

Author: Frederik Eaton

Constructor & Destructor Documentation

dai::FBP::FBP ( )

inline

Default constructor.

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

inline

Construct from FactorGraph fg and PropertySet opts.

Parameters

fg	Factor graph.
opts	Parameters

See also: BP::Properties

Member Function Documentation

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

inlinevirtual

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

Reimplemented from dai::BP.

virtual FBP* dai::FBP::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;

Reimplemented from dai::BP.

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

inlinevirtual

Returns the name of the algorithm.

Reimplemented from dai::BP.

Real dai::FBP::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

Reimplemented from dai::BP.

Real dai::FBP::Weight ( size_t I ) const

inline

Returns weight of the I 'th factor.

const std::vector<Real>& dai::FBP::Weights ( ) const

inline

Returns constant reference to vector of all factor weights.

void dai::FBP::setWeight	(	size_t	I,
		Real	c
	)

inline

Sets the weight of the I 'th factor to c.

void dai::FBP::setWeights ( const std::vector< Real > & c )

inline

Sets the weights of all factors simultaenously.

Note: Faster than calling setWeight(size_t,Real) for each factor

Prob dai::FBP::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 from dai::BP.

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

protectedvirtual

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

Reimplemented from dai::BP.

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

inlineprotectedvirtual

Calculates unnormalized belief of factor I.

Reimplemented from dai::BP.

void dai::FBP::construct ( )

protectedvirtual

Helper function for constructors.

Reimplemented from dai::BP.

Member Data Documentation

std::vector<Real> dai::FBP::_weight

protected

Factor weights (indexed by factor ID)

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

include/dai/fbp.h
src/fbp.cpp

Public Member Functions

Protected Attributes

FBP accessors/mutators for weights

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation