Approximate inference algorithm "Tree Expectation Propagation" [MiQ04]. More...

#include <dai/treeep.h>

Inheritance diagram for dai::TreeEP:

Classes
struct	Properties
	Parameters for TreeEP. More...

class	TreeEPSubTree
	Stores the data structures needed to efficiently update the approximation of an off-tree factor. More...

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

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

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

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

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

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

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::JTree
	JTree ()
	Default constructor. More...

	JTree (const FactorGraph &fg, const PropertySet &opts, bool automatic=true)
	Construct from FactorGraph fg and PropertySet opts. More...

virtual Factor	belief (const VarSet &vs) const
	Returns the (approximate) marginal probability distribution of a set of variables. 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

void	construct (const FactorGraph &fg, const std::vector< VarSet > &cl, bool verify=false)
	Constructs a junction tree based on the cliques cl (corresponding to some elimination sequence). More...

void	GenerateJT (const FactorGraph &fg, const std::vector< VarSet > &cl)
	Constructs a junction tree based on the cliques cl (corresponding to some elimination sequence). More...

const Factor &	message (size_t alpha, size_t _beta) const
	Returns constant reference to the message from outer region alpha to its _beta 'th neighboring inner region. More...

Factor &	message (size_t alpha, size_t _beta)
	Returns reference to the message from outer region alpha to its _beta 'th neighboring inner region. More...

void	runHUGIN ()
	Runs junction tree algorithm using HUGIN (message-free) updates. More...

void	runShaferShenoy ()
	Runs junction tree algorithm using Shafer-Shenoy updates. More...

size_t	findEfficientTree (const VarSet &vs, RootedTree &Tree, size_t PreviousRoot=(size_t)-1) const
	Finds an efficient subtree for calculating the marginal of the variables in vs. More...

Factor	calcMarginal (const VarSet &vs)
	Calculates the marginal of a set of variables (using cutset conditioning, if necessary) 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	belief (const Var &v) const
	Returns the (approximate) marginal probability distribution of a variable. 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...

Public Attributes
struct dai::TreeEP::Properties	props

Public Attributes inherited from dai::JTree
RootedTree	RTree
	The junction tree (stored as a rooted tree) More...

std::vector< Factor >	Qa
	Outer region beliefs. More...

std::vector< Factor >	Qb
	Inner region beliefs. More...

struct dai::JTree::Properties	props

Private Member Functions
void	construct (const FactorGraph &fg, const RootedTree &tree)
	Helper function for constructors. More...

bool	offtree (size_t I) const
	Returns `true` if factor I is not part of the tree. More...

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

size_t	_iters
	Number of iterations needed. More...

std::map< size_t, TreeEPSubTree >	_Q
	Stores a TreeEPSubTree object for each off-tree factor. More...

Additional Inherited Members
Related Functions inherited from dai::JTree
std::pair< size_t, BigInt >	boundTreewidth (const FactorGraph &fg, greedyVariableElimination::eliminationCostFunction fn, size_t maxStates=0)
	Calculates upper bound to the treewidth of a FactorGraph, using the specified heuristic. More...

Detailed Description

Approximate inference algorithm "Tree Expectation Propagation" [MiQ04].

Constructor & Destructor Documentation

dai::TreeEP::TreeEP ( )

inline

Default constructor.

dai::TreeEP::TreeEP ( const TreeEP & x )

inline

Copy constructor.

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

Construct from FactorGraph fg and PropertySet opts.

Parameters

fg	Factor graph.
opts	Parameters

See also: Properties

Member Function Documentation

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

inline

Assignment operator.

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

inlinevirtual

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

Reimplemented from dai::JTree.

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

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

inlinevirtual

Returns the name of the algorithm.

Reimplemented from dai::JTree.

Real dai::TreeEP::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::JTree.

void dai::TreeEP::init ( )

virtual

Initializes all data structures of the approximate inference algorithm.

Note: This method should be called at least once before run() is called.

Reimplemented from dai::JTree.

virtual void dai::TreeEP::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

Reimplemented from dai::JTree.

Real dai::TreeEP::run ( )

virtual

Runs the approximate inference algorithm.

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

Reimplemented from dai::JTree.

virtual Real dai::TreeEP::maxDiff ( ) const

inlinevirtual

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

Exceptions

NOT_IMPLEMENTED if not implemented/supported

Reimplemented from dai::JTree.

virtual size_t dai::TreeEP::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::JTree.

virtual void dai::TreeEP::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::TreeEP::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.

Reimplemented from dai::JTree.

PropertySet dai::TreeEP::getProperties ( ) const

virtual

Returns parameters of this inference algorithm converted into a PropertySet.

Reimplemented from dai::JTree.

string dai::TreeEP::printProperties ( ) const

virtual

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

Reimplemented from dai::JTree.

void dai::TreeEP::construct	(	const FactorGraph &	fg,
		const RootedTree &	tree
	)

private

Helper function for constructors.

bool dai::TreeEP::offtree ( size_t I ) const

inlineprivate

Returns true if factor I is not part of the tree.

Member Data Documentation

Real dai::TreeEP::_maxdiff

private

Maximum difference encountered so far.

size_t dai::TreeEP::_iters

private

Number of iterations needed.

std::map<size_t, TreeEPSubTree> dai::TreeEP::_Q

private

Stores a TreeEPSubTree object for each off-tree factor.

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

include/dai/treeep.h
src/treeep.cpp

Classes

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation