Class for CBP (Conditioned Belief Propagation) [EaG09]. More...

#include <dai/cbp.h>

Inheritance diagram for dai::CBP:

Classes
struct	Properties
	Parameters for CBP. More...

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

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

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

virtual CBP *	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 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...

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	setMaxIter (size_t maxiter)
	Sets maximum number of iterations (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 std::vector< size_t >	findMaximum () const
	Calculates the joint state of all variables that has maximum probability. More...

Public Attributes
struct dai::CBP::Properties	props

Private Member Functions
void	printDebugInfo ()
	Prints beliefs, variables and partition sum, in case of a debugging build. More...

void	runRecurse (InfAlg *bp, Real orig_logZ, std::vector< size_t > clamped_vars_list, size_t &num_leaves, size_t &choose_count, Real &sum_level, Real &lz_out, std::vector< Factor > &beliefs_out)
	Called by run(), and by itself. Implements the main algorithm. More...

virtual bool	chooseNextClampVar (InfAlg bp, std::vector< size_t > &clamped_vars_list, size_t &i, std::vector< size_t > &xis, Real maxVarOut)
	Choose the next variable to clamp. More...

InfAlg *	getInfAlg ()
	Return the InfAlg to use at each step of the recursion. More...

void	setBeliefs (const std::vector< Factor > &bs, Real logZ)
	Sets variable beliefs, factor beliefs and log partition sum to the specified values. More...

void	construct ()
	Constructor helper function. More...

Private Attributes
std::vector< Factor >	_beliefsV
	Variable beliefs. More...

std::vector< Factor >	_beliefsF
	Factor beliefs. More...

Real	_logZ
	Logarithm of partition sum. More...

size_t	_iters
	Numer of iterations needed. More...

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

Real	_sum_level
	Number of clampings at each leaf node. More...

size_t	_num_leaves
	Number of leaves of recursion tree. More...

boost::shared_ptr< std::ofstream >	_clamp_ofstream
	Output stream where information about the clampings is written. More...

Related Functions
(Note that these are not member functions.)
std::pair< size_t, size_t >	BBPFindClampVar (const InfAlg &in_bp, bool clampingVar, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real *maxVarOut)
	Find the best variable/factor to clamp using BBP. More...

Detailed Description

Class for CBP (Conditioned Belief Propagation) [EaG09].

This approximate inference algorithm uses configurable heuristics to choose a variable $ x_i $ and a state $ x_i^* $ . Inference is done with $ x_i $ "clamped" to (i.e., conditional on $ x_i = x_i^* $ ), and also with the negation of this condition. Clamping is done recursively up to a fixed number of levels (other stopping criteria are also implemented, see the CBP::Properties::RecurseType property). The resulting approximate marginals are combined using estimates of the partition sum.

Author: Frederik Eaton

Constructor & Destructor Documentation

dai::CBP::CBP ( )

inline

Default constructor.

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

inline

Construct CBP object from FactorGraph fg and PropertySet opts.

Parameters

fg	Factor graph.
opts	Parameters

See also: Properties

Member Function Documentation

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

inlinevirtual

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

Implements dai::InfAlg.

virtual CBP* dai::CBP::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::CBP::name ( ) const

inlinevirtual

Returns the name of the algorithm.

Implements dai::InfAlg.

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

virtual Factor dai::CBP::belief ( const VarSet & vs ) const

inlinevirtual

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.

virtual Factor dai::CBP::beliefV ( size_t i ) const

inlinevirtual

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.

virtual Factor dai::CBP::beliefF ( size_t I ) const

inlinevirtual

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.

virtual std::vector<Factor> dai::CBP::beliefs ( ) const

inlinevirtual

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

virtual void dai::CBP::setProperties ( const PropertySet & opts )

inlinevirtual

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.

virtual PropertySet dai::CBP::getProperties ( ) const

inlinevirtual

Returns parameters of this inference algorithm converted into a PropertySet.

Implements dai::InfAlg.

virtual std::string dai::CBP::printProperties ( ) const

inlinevirtual

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

Implements dai::InfAlg.

void dai::CBP::printDebugInfo ( )

private

Prints beliefs, variables and partition sum, in case of a debugging build.

void dai::CBP::runRecurse	(	InfAlg *	bp,
		Real	orig_logZ,
		std::vector< size_t >	clamped_vars_list,
		size_t &	num_leaves,
		size_t &	choose_count,
		Real &	sum_level,
		Real &	lz_out,
		std::vector< Factor > &	beliefs_out
	)

private

Called by run(), and by itself. Implements the main algorithm.

Chooses a variable to clamp, recurses, combines the partition sum and belief estimates of the children, and returns the improved estimates in lz_out and beliefs_out to its parent.

Idea:: dai::CBP::runRecurse() could be implemented more efficiently with a nesting version of backupFactors/restoreFactors

bool dai::CBP::chooseNextClampVar	(	InfAlg *	bp,
		std::vector< size_t > &	clamped_vars_list,
		size_t &	i,
		std::vector< size_t > &	xis,
		Real *	maxVarOut
	)

privatevirtual

Choose the next variable to clamp.

Choose the next variable to clamp, given a converged InfAlg bp, and a vector of variables that are already clamped (clamped_vars_list). Returns the chosen variable in i, and the set of states in xis. If maxVarOut is non-NULL and props.choose == CHOOSE_BBP then it is used to store the adjoint of the chosen variable.

InfAlg * dai::CBP::getInfAlg ( )

private

Return the InfAlg to use at each step of the recursion.

Todo:: At present, CBP::getInfAlg() only returns a BP instance; it should be possible to select other inference algorithms via a property

void dai::CBP::setBeliefs	(	const std::vector< Factor > &	bs,
		Real	logZ
	)

private

Sets variable beliefs, factor beliefs and log partition sum to the specified values.

Parameters

bs	should be a concatenation of the variable beliefs followed by the factor beliefs
logZ	log partition sum

void dai::CBP::construct ( )

private

Constructor helper function.

Friends And Related Function Documentation

std::pair< size_t, size_t > BBPFindClampVar	(	const InfAlg &	in_bp,
		bool	clampingVar,
		const PropertySet &	bbp_props,
		const BBPCostFunction &	cfn,
		Real *	maxVarOut
	)

Takes a converged inference algorithm as input, runs Gibbs and BP_dual, creates and runs a BBP object, finds the best variable/factor (the one with the maximum factor adjoint), and returns the corresponding (index,state) pair.

Parameters

in_bp	inference algorithm (compatible with BP) that should have converged;
clampingVar	if `true`, finds best variable, otherwise, finds best factor;
bbp_props	BBP parameters to use;
cfn	BBP cost function to use;
maxVarOut	maximum adjoint value (only set if not NULL).

See also: BBP

Member Data Documentation

std::vector<Factor> dai::CBP::_beliefsV

private

Variable beliefs.

std::vector<Factor> dai::CBP::_beliefsF

private

Factor beliefs.

Real dai::CBP::_logZ

private

Logarithm of partition sum.

size_t dai::CBP::_iters

private

Numer of iterations needed.

Real dai::CBP::_maxdiff

private

Maximum difference encountered so far.

Real dai::CBP::_sum_level

private

Number of clampings at each leaf node.

size_t dai::CBP::_num_leaves

private

Number of leaves of recursion tree.

boost::shared_ptr<std::ofstream> dai::CBP::_clamp_ofstream

private

Output stream where information about the clampings is written.

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

include/dai/cbp.h
src/cbp.cpp

Classes

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation