Implements BBP (Back-Belief-Propagation) [EaG09]. More...

#include <dai/bbp.h>

Classes
struct	Properties
	Parameters for BBP. More...

Public Member Functions
Constructors/destructors
	BBP (const InfAlg *ia, const PropertySet &opts)
	Construct BBP object from a InfAlg ia and a PropertySet opts. More...

Initialization
void	init (const std::vector< Prob > &adj_b_V, const std::vector< Prob > &adj_b_F, const std::vector< Prob > &adj_psi_V, const std::vector< Prob > &adj_psi_F)
	Initializes from given belief adjoints adj_b_V, adj_b_F and initial factor adjoints adj_psi_V, adj_psi_F. More...

void	init (const std::vector< Prob > &adj_b_V, const std::vector< Prob > &adj_b_F)
	Initializes from given belief adjoints adj_b_V and adj_b_F (setting initial factor adjoints to zero) More...

void	init_V (const std::vector< Prob > &adj_b_V)
	Initializes variable belief adjoints adj_b_V (and sets factor belief adjoints and initial factor adjoints to zero) More...

void	init_F (const std::vector< Prob > &adj_b_F)
	Initializes factor belief adjoints adj_b_F (and sets variable belief adjoints and initial factor adjoints to zero) More...

void	initCostFnAdj (const BBPCostFunction &cfn, const std::vector< size_t > *stateP)
	Initializes with adjoints calculated from cost function cfn, and state stateP. More...

BBP Algorithm
void	run ()
	Perform iterative updates until change is less than given tolerance. More...

Query results
Prob &	adj_psi_V (size_t i)
	Returns reference to variable factor adjoint. More...

const Prob &	adj_psi_V (size_t i) const
	Returns constant reference to variable factor adjoint. More...

Prob &	adj_psi_F (size_t I)
	Returns reference to factor adjoint. More...

const Prob &	adj_psi_F (size_t I) const
	Returns constant reference to factor adjoint. More...

Prob &	adj_b_V (size_t i)
	Returns reference to variable belief adjoint. More...

const Prob &	adj_b_V (size_t i) const
	Returns constant reference to variable belief adjoint. More...

Prob &	adj_b_F (size_t I)
	Returns reference to factor belief adjoint. More...

const Prob &	adj_b_F (size_t I) const
	Returns constant reference to factor belief adjoint. More...

size_t	Iterations ()
	Return number of iterations done so far. More...

Public Attributes
struct dai::BBP::Properties	props

Private Member Functions
Prob	unnormAdjoint (const Prob &w, Real Z_w, const Prob &adj_w)
	Computes the adjoint of the unnormed probability vector from the normalizer and the adjoint of the normalized probability vector. More...

Real	getUnMsgMag ()
	Calculates averaged L1 norm of unnormalized message adjoints. More...

void	getMsgMags (Real &s, Real &new_s)
	Calculates averaged L1 norms of current and new normalized message adjoints. More...

void	getArgmaxMsgM (size_t &i, size_t &_I, Real &mag)
	Returns indices and magnitude of the largest normalized factor->variable message adjoint. More...

Real	getMaxMsgM ()
	Returns magnitude of the largest (in L1-norm) normalized factor->variable message adjoint. More...

Real	getTotalMsgM ()
	Calculates sum of L1 norms of all normalized factor->variable message adjoints. More...

Real	getTotalNewMsgM ()
	Calculates sum of L1 norms of all updated normalized factor->variable message adjoints. More...

Real	getTotalMsgN ()
	Calculates sum of L1 norms of all normalized variable->factor message adjoints. More...

std::vector< Prob >	getZeroAdjF (const FactorGraph &fg)
	Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the factors in the factor graph fg. More...

std::vector< Prob >	getZeroAdjV (const FactorGraph &fg)
	Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the variables in the factor graph fg. More...

Initialization helper functions
void	RegenerateT ()
	Calculate T values; see eqn. (41) in [EaG09]. More...

void	RegenerateU ()
	Calculate U values; see eqn. (42) in [EaG09]. More...

void	RegenerateS ()
	Calculate S values; see eqn. (43) in [EaG09]. More...

void	RegenerateR ()
	Calculate R values; see eqn. (44) in [EaG09]. More...

void	RegenerateInputs ()
	Calculate _adj_b_V_unnorm and _adj_b_F_unnorm from _adj_b_V and _adj_b_F. More...

void	RegeneratePsiAdjoints ()
	Initialise members for factor adjoints. More...

void	RegenerateParMessageAdjoints ()
	Initialise members for message adjoints for parallel algorithm. More...

void	RegenerateSeqMessageAdjoints ()
	Initialise members for message adjoints for sequential algorithm. More...

void	Regenerate ()
	Called by init, recalculates intermediate values. More...

Accessors/mutators
Prob &	T (size_t i, size_t _I)
	Returns reference to T value; see eqn. (41) in [EaG09]. More...

const Prob &	T (size_t i, size_t _I) const
	Returns constant reference to T value; see eqn. (41) in [EaG09]. More...

Prob &	U (size_t I, size_t _i)
	Returns reference to U value; see eqn. (42) in [EaG09]. More...

const Prob &	U (size_t I, size_t _i) const
	Returns constant reference to U value; see eqn. (42) in [EaG09]. More...

Prob &	S (size_t i, size_t _I, size_t _j)
	Returns reference to S value; see eqn. (43) in [EaG09]. More...

const Prob &	S (size_t i, size_t _I, size_t _j) const
	Returns constant reference to S value; see eqn. (43) in [EaG09]. More...

Prob &	R (size_t I, size_t _i, size_t _J)
	Returns reference to R value; see eqn. (44) in [EaG09]. More...

const Prob &	R (size_t I, size_t _i, size_t _J) const
	Returns constant reference to R value; see eqn. (44) in [EaG09]. More...

Prob &	adj_n (size_t i, size_t _I)
	Returns reference to variable->factor message adjoint. More...

const Prob &	adj_n (size_t i, size_t _I) const
	Returns constant reference to variable->factor message adjoint. More...

Prob &	adj_m (size_t i, size_t _I)
	Returns reference to factor->variable message adjoint. More...

const Prob &	adj_m (size_t i, size_t _I) const
	Returns constant reference to factor->variable message adjoint. More...

Parallel algorithm
void	calcNewN (size_t i, size_t _I)
	Calculates new variable->factor message adjoint. More...

void	calcNewM (size_t i, size_t _I)
	Calculates new factor->variable message adjoint. More...

void	calcUnnormMsgN (size_t i, size_t _I)
	Calculates unnormalized variable->factor message adjoint from the normalized one. More...

void	calcUnnormMsgM (size_t i, size_t _I)
	Calculates unnormalized factor->variable message adjoint from the normalized one. More...

void	upMsgN (size_t i, size_t _I)
	Updates (un)normalized variable->factor message adjoints. More...

void	upMsgM (size_t i, size_t _I)
	Updates (un)normalized factor->variable message adjoints. More...

void	doParUpdate ()
	Do one parallel update of all message adjoints. More...

Sequential algorithm
void	incrSeqMsgM (size_t i, size_t _I, const Prob &p)
	Helper function for sendSeqMsgM(): increases factor->variable message adjoint by p and calculates the corresponding unnormalized adjoint. More...

void	setSeqMsgM (size_t i, size_t _I, const Prob &p)
	Sets normalized factor->variable message adjoint and calculates the corresponding unnormalized adjoint. More...

void	sendSeqMsgN (size_t i, size_t _I, const Prob &f)
	Implements routine Send-n in Figure 5 in [EaG09]. More...

void	sendSeqMsgM (size_t i, size_t _I)
	Implements routine Send-m in Figure 5 in [EaG09]. More...

Private Attributes
Input variables
BP_dual	_bp_dual
	Stores a BP_dual helper object. More...

const FactorGraph *	_fg
	Pointer to the factor graph. More...

const InfAlg *	_ia
	Pointer to the approximate inference algorithm (currently, only BP objects are supported) More...

Output variables
std::vector< Prob >	_adj_psi_V
	Variable factor adjoints. More...

std::vector< Prob >	_adj_psi_F
	Factor adjoints. More...

std::vector< std::vector< Prob > >	_adj_n
	Variable->factor message adjoints (indexed [i][_I]) More...

std::vector< std::vector< Prob > >	_adj_m
	Factor->variable message adjoints (indexed [i][_I]) More...

std::vector< Prob >	_adj_b_V
	Normalized variable belief adjoints. More...

std::vector< Prob >	_adj_b_F
	Normalized factor belief adjoints. More...

Internal state variables
std::vector< Prob >	_init_adj_psi_V
	Initial variable factor adjoints. More...

std::vector< Prob >	_init_adj_psi_F
	Initial factor adjoints. More...

std::vector< std::vector< Prob > >	_adj_n_unnorm
	Unnormalized variable->factor message adjoint (indexed [i][_I]) More...

std::vector< std::vector< Prob > >	_adj_m_unnorm
	Unnormalized factor->variable message adjoint (indexed [i][_I]) More...

std::vector< std::vector< Prob > >	_new_adj_n
	Updated normalized variable->factor message adjoint (indexed [i][_I]) More...

std::vector< std::vector< Prob > >	_new_adj_m
	Updated normalized factor->variable message adjoint (indexed [i][_I]) More...

std::vector< Prob >	_adj_b_V_unnorm
	Unnormalized variable belief adjoints. More...

std::vector< Prob >	_adj_b_F_unnorm
	Unnormalized factor belief adjoints. More...

std::vector< std::vector< Prob > >	_Tmsg
	_Tmsg[i]_I in [EaG09]) More...

std::vector< std::vector< Prob > >	_Umsg
	_Umsg[I]_i in [EaG09]) More...

std::vector< std::vector< std::vector< Prob > > >	_Smsg
	_Smsg[i][_I]_j in [EaG09]) More...

std::vector< std::vector< std::vector< Prob > > >	_Rmsg
	_Rmsg[I][_i]_J in [EaG09]) More...

size_t	_iters
	Number of iterations done. More...

Related Functions
(Note that these are not member functions.)
Real	numericBBPTest (const InfAlg &bp, const std::vector< size_t > *state, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real h)
	Function to verify the validity of adjoints computed by BBP using numerical differentiation. More...

Index cache management (for performance)
typedef std::vector< size_t >	_ind_t
	Index type. More...

std::vector< std::vector< _ind_t > >	_indices
	Cached indices (indexed [i][_I]) More...

void	RegenerateInds ()
	Prepares index cache _indices. More...

const _ind_t &	_index (size_t i, size_t _I) const
	Returns an index from the cache. More...

Detailed Description

Implements BBP (Back-Belief-Propagation) [EaG09].

Author: Frederik Eaton

Member Typedef Documentation

typedef std::vector<size_t> dai::BBP::_ind_t

private

Index type.

Constructor & Destructor Documentation

dai::BBP::BBP	(	const InfAlg *	ia,
		const PropertySet &	opts
	)

inline

Construct BBP object from a InfAlg ia and a PropertySet opts.

Parameters

ia	should be a BP object or something compatible
opts	Parameters

See also: Properties

Member Function Documentation

void dai::BBP::RegenerateInds ( )

private

Prepares index cache _indices.

See also: bp.cpp

const _ind_t& dai::BBP::_index	(	size_t	i,
		size_t	_I
	)		const

inlineprivate

Returns an index from the cache.

void dai::BBP::RegenerateT ( )

private

Calculate T values; see eqn. (41) in [EaG09].

void dai::BBP::RegenerateU ( )

private

Calculate U values; see eqn. (42) in [EaG09].

void dai::BBP::RegenerateS ( )

private

Calculate S values; see eqn. (43) in [EaG09].

void dai::BBP::RegenerateR ( )

private

Calculate R values; see eqn. (44) in [EaG09].

void dai::BBP::RegenerateInputs ( )

private

Calculate _adj_b_V_unnorm and _adj_b_F_unnorm from _adj_b_V and _adj_b_F.

void dai::BBP::RegeneratePsiAdjoints ( )

private

Initialise members for factor adjoints.

Precondition: RegenerateInputs() should be called first

void dai::BBP::RegenerateParMessageAdjoints ( )

private

Initialise members for message adjoints for parallel algorithm.

Precondition: RegenerateInputs() should be called first

void dai::BBP::RegenerateSeqMessageAdjoints ( )

private

Initialise members for message adjoints for sequential algorithm.

Same as RegenerateMessageAdjoints, but calls sendSeqMsgN rather than updating _adj_n (and friends) which are unused in the sequential algorithm.

Precondition: RegenerateInputs() should be called first

void dai::BBP::Regenerate ( )

private

Called by init, recalculates intermediate values.

Prob& dai::BBP::T	(	size_t	i,
		size_t	_I
	)

inlineprivate

Returns reference to T value; see eqn. (41) in [EaG09].

const Prob& dai::BBP::T	(	size_t	i,
		size_t	_I
	)		const

inlineprivate

Returns constant reference to T value; see eqn. (41) in [EaG09].

Prob& dai::BBP::U	(	size_t	I,
		size_t	_i
	)

inlineprivate

Returns reference to U value; see eqn. (42) in [EaG09].

const Prob& dai::BBP::U	(	size_t	I,
		size_t	_i
	)		const

inlineprivate

Returns constant reference to U value; see eqn. (42) in [EaG09].

Prob& dai::BBP::S	(	size_t	i,
		size_t	_I,
		size_t	_j
	)

inlineprivate

Returns reference to S value; see eqn. (43) in [EaG09].

const Prob& dai::BBP::S	(	size_t	i,
		size_t	_I,
		size_t	_j
	)		const

inlineprivate

Returns constant reference to S value; see eqn. (43) in [EaG09].

Prob& dai::BBP::R	(	size_t	I,
		size_t	_i,
		size_t	_J
	)

inlineprivate

Returns reference to R value; see eqn. (44) in [EaG09].

const Prob& dai::BBP::R	(	size_t	I,
		size_t	_i,
		size_t	_J
	)		const

inlineprivate

Returns constant reference to R value; see eqn. (44) in [EaG09].

Prob& dai::BBP::adj_n	(	size_t	i,
		size_t	_I
	)

inlineprivate

Returns reference to variable->factor message adjoint.

const Prob& dai::BBP::adj_n	(	size_t	i,
		size_t	_I
	)		const

inlineprivate

Returns constant reference to variable->factor message adjoint.

Prob& dai::BBP::adj_m	(	size_t	i,
		size_t	_I
	)

inlineprivate

Returns reference to factor->variable message adjoint.

const Prob& dai::BBP::adj_m	(	size_t	i,
		size_t	_I
	)		const

inlineprivate

Returns constant reference to factor->variable message adjoint.

void dai::BBP::calcNewN	(	size_t	i,
		size_t	_I
	)

private

Calculates new variable->factor message adjoint.

Increases variable factor adjoint according to eqn. (27) in [EaG09] and calculates the new variable->factor message adjoint according to eqn. (29) in [EaG09].

void dai::BBP::calcNewM	(	size_t	i,
		size_t	_I
	)

private

Calculates new factor->variable message adjoint.

Increases factor adjoint according to eqn. (28) in [EaG09] and calculates the new factor->variable message adjoint according to the r.h.s. of eqn. (30) in [EaG09].

void dai::BBP::calcUnnormMsgN	(	size_t	i,
		size_t	_I
	)

private

Calculates unnormalized variable->factor message adjoint from the normalized one.

void dai::BBP::calcUnnormMsgM	(	size_t	i,
		size_t	_I
	)

private

Calculates unnormalized factor->variable message adjoint from the normalized one.

void dai::BBP::upMsgN	(	size_t	i,
		size_t	_I
	)

private

Updates (un)normalized variable->factor message adjoints.

void dai::BBP::upMsgM	(	size_t	i,
		size_t	_I
	)

private

Updates (un)normalized factor->variable message adjoints.

void dai::BBP::doParUpdate ( )

private

Do one parallel update of all message adjoints.

void dai::BBP::incrSeqMsgM	(	size_t	i,
		size_t	_I,
		const Prob &	p
	)

private

Helper function for sendSeqMsgM(): increases factor->variable message adjoint by p and calculates the corresponding unnormalized adjoint.

void dai::BBP::setSeqMsgM	(	size_t	i,
		size_t	_I,
		const Prob &	p
	)

private

Sets normalized factor->variable message adjoint and calculates the corresponding unnormalized adjoint.

void dai::BBP::sendSeqMsgN	(	size_t	i,
		size_t	_I,
		const Prob &	f
	)

private

Implements routine Send-n in Figure 5 in [EaG09].

void dai::BBP::sendSeqMsgM	(	size_t	i,
		size_t	_I
	)

private

Implements routine Send-m in Figure 5 in [EaG09].

Prob dai::BBP::unnormAdjoint	(	const Prob &	w,
		Real	Z_w,
		const Prob &	adj_w
	)

private

Computes the adjoint of the unnormed probability vector from the normalizer and the adjoint of the normalized probability vector.

See also: eqn. (13) in [EaG09]

Real dai::BBP::getUnMsgMag ( )

private

Calculates averaged L1 norm of unnormalized message adjoints.

void dai::BBP::getMsgMags	(	Real &	s,
		Real &	new_s
	)

private

Calculates averaged L1 norms of current and new normalized message adjoints.

void dai::BBP::getArgmaxMsgM	(	size_t &	i,
		size_t &	_I,
		Real &	mag
	)

private

Returns indices and magnitude of the largest normalized factor->variable message adjoint.

Real dai::BBP::getMaxMsgM ( )

private

Returns magnitude of the largest (in L1-norm) normalized factor->variable message adjoint.

Real dai::BBP::getTotalMsgM ( )

private

Calculates sum of L1 norms of all normalized factor->variable message adjoints.

Real dai::BBP::getTotalNewMsgM ( )

private

Calculates sum of L1 norms of all updated normalized factor->variable message adjoints.

Real dai::BBP::getTotalMsgN ( )

private

Calculates sum of L1 norms of all normalized variable->factor message adjoints.

std::vector< Prob > dai::BBP::getZeroAdjF ( const FactorGraph & fg )

private

Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the factors in the factor graph fg.

std::vector< Prob > dai::BBP::getZeroAdjV ( const FactorGraph & fg )

private

Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the variables in the factor graph fg.

void dai::BBP::init	(	const std::vector< Prob > &	adj_b_V,
		const std::vector< Prob > &	adj_b_F,
		const std::vector< Prob > &	adj_psi_V,
		const std::vector< Prob > &	adj_psi_F
	)

inline

Initializes from given belief adjoints adj_b_V, adj_b_F and initial factor adjoints adj_psi_V, adj_psi_F.

void dai::BBP::init	(	const std::vector< Prob > &	adj_b_V,
		const std::vector< Prob > &	adj_b_F
	)

inline

Initializes from given belief adjoints adj_b_V and adj_b_F (setting initial factor adjoints to zero)

void dai::BBP::init_V ( const std::vector< Prob > & adj_b_V )

inline

Initializes variable belief adjoints adj_b_V (and sets factor belief adjoints and initial factor adjoints to zero)

void dai::BBP::init_F ( const std::vector< Prob > & adj_b_F )

inline

Initializes factor belief adjoints adj_b_F (and sets variable belief adjoints and initial factor adjoints to zero)

void dai::BBP::initCostFnAdj	(	const BBPCostFunction &	cfn,
		const std::vector< size_t > *	stateP
	)

Initializes with adjoints calculated from cost function cfn, and state stateP.

Uses the internal pointer to an inference algorithm in combination with the cost function and state for initialization.

Parameters

cfn	Cost function used for initialization;
stateP	is a Gibbs state and can be NULL; it will be initialised using a Gibbs run.

void dai::BBP::run ( )

Perform iterative updates until change is less than given tolerance.

Prob& dai::BBP::adj_psi_V ( size_t i )

inline

Returns reference to variable factor adjoint.

const Prob& dai::BBP::adj_psi_V ( size_t i ) const

inline

Returns constant reference to variable factor adjoint.

Prob& dai::BBP::adj_psi_F ( size_t I )

inline

Returns reference to factor adjoint.

const Prob& dai::BBP::adj_psi_F ( size_t I ) const

inline

Returns constant reference to factor adjoint.

Prob& dai::BBP::adj_b_V ( size_t i )

inline

Returns reference to variable belief adjoint.

const Prob& dai::BBP::adj_b_V ( size_t i ) const

inline

Returns constant reference to variable belief adjoint.

Prob& dai::BBP::adj_b_F ( size_t I )

inline

Returns reference to factor belief adjoint.

const Prob& dai::BBP::adj_b_F ( size_t I ) const

inline

Returns constant reference to factor belief adjoint.

size_t dai::BBP::Iterations ( )

inline

Return number of iterations done so far.

Friends And Related Function Documentation

Real numericBBPTest	(	const InfAlg &	bp,
		const std::vector< size_t > *	state,
		const PropertySet &	bbp_props,
		const BBPCostFunction &	cfn,
		Real	h
	)

Factors containing a variable are multiplied by small adjustments to verify accuracy of calculated variable factor adjoints.

Parameters

bp	BP object;
state	Global state of all variables;
bbp_props	BBP parameters;
cfn	Cost function to be used;
h	Size of perturbation.

Member Data Documentation

BP_dual dai::BBP::_bp_dual

private

Stores a BP_dual helper object.

const FactorGraph* dai::BBP::_fg

private

Pointer to the factor graph.

const InfAlg* dai::BBP::_ia

private

Pointer to the approximate inference algorithm (currently, only BP objects are supported)

std::vector<Prob> dai::BBP::_adj_psi_V

private

Variable factor adjoints.

std::vector<Prob> dai::BBP::_adj_psi_F

private

Factor adjoints.

std::vector<std::vector<Prob> > dai::BBP::_adj_n

private

Variable->factor message adjoints (indexed [i][_I])

std::vector<std::vector<Prob> > dai::BBP::_adj_m

private

Factor->variable message adjoints (indexed [i][_I])

std::vector<Prob> dai::BBP::_adj_b_V

private

Normalized variable belief adjoints.

std::vector<Prob> dai::BBP::_adj_b_F

private

Normalized factor belief adjoints.

std::vector<Prob> dai::BBP::_init_adj_psi_V

private

Initial variable factor adjoints.

std::vector<Prob> dai::BBP::_init_adj_psi_F

private

Initial factor adjoints.

std::vector<std::vector<Prob> > dai::BBP::_adj_n_unnorm

private

Unnormalized variable->factor message adjoint (indexed [i][_I])

std::vector<std::vector<Prob> > dai::BBP::_adj_m_unnorm

private

Unnormalized factor->variable message adjoint (indexed [i][_I])

std::vector<std::vector<Prob> > dai::BBP::_new_adj_n

private

Updated normalized variable->factor message adjoint (indexed [i][_I])

std::vector<std::vector<Prob> > dai::BBP::_new_adj_m

private

Updated normalized factor->variable message adjoint (indexed [i][_I])

std::vector<Prob> dai::BBP::_adj_b_V_unnorm

private

Unnormalized variable belief adjoints.

std::vector<Prob> dai::BBP::_adj_b_F_unnorm

private

Unnormalized factor belief adjoints.

std::vector<std::vector<Prob > > dai::BBP::_Tmsg

private

_Tmsg[i]_I in [EaG09])

std::vector<std::vector<Prob > > dai::BBP::_Umsg

private

_Umsg[I]_i in [EaG09])

std::vector<std::vector<std::vector<Prob > > > dai::BBP::_Smsg

private

_Smsg[i][_I]_j in [EaG09])

std::vector<std::vector<std::vector<Prob > > > dai::BBP::_Rmsg

private

_Rmsg[I][_i]_J in [EaG09])

size_t dai::BBP::_iters

private

Number of iterations done.

std::vector<std::vector<_ind_t> > dai::BBP::_indices

private

Cached indices (indexed [i][_I])

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

include/dai/bbp.h
src/bbp.cpp

Classes

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Related Functions

Index cache management (for performance)

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation