dai::TRWBP Class Reference

Approximate inference algorithm "Tree-Reweighted Belief Propagation" [WJW03]. More...

#include <dai/trwbp.h>

Inheritance diagram for dai::TRWBP:

dai::BP dai::DAIAlg< GRM > dai::InfAlg

List of all members.

TRWBP accessors/mutators for scale parameters

Real Weight (size_t I) const
 Returns weight corresponding to the I 'th factor.
const std::vector< Real > & Weights () const
 Returns constant reference to vector of all weights.
void setWeight (size_t I, Real c)
 Sets the weight of the I 'th factor to c.
void setWeights (const std::vector< Real > &c)
 Sets the weights of all factors simultaenously.
virtual Prob calcIncomingMessageProduct (size_t I, bool without_i, size_t i) const
 Calculate the product of factor I and the incoming messages.
virtual void calcBeliefV (size_t i, Prob &p) const
 Calculates unnormalized belief of variable i.
virtual void calcBeliefF (size_t I, Prob &p) const
 Calculates unnormalized belief of factor I.
virtual void construct ()
 Helper function for constructors.

Public Member Functions

Constructors/destructors
 TRWBP ()
 Default constructor.
 TRWBP (const FactorGraph &fg, const PropertySet &opts)
 Construct from FactorGraph fg and PropertySet opts.
General InfAlg interface
virtual TRWBPclone () const
 Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor).
virtual std::string identify () const
 Identifies itself for logging purposes.
virtual Real logZ () const
 Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).

Static Public Attributes

static const char * Name = "TRWBP"
 Name of this inference algorithm.

Protected Attributes

std::vector< Real_weight
 "Edge weights" (indexed by factor ID)


Detailed Description

Approximate inference algorithm "Tree-Reweighted Belief Propagation" [WJW03].

The Tree-Reweighted Belief Propagation algorithm is like Belief Propagation, but associates each factor with a scale parameter. which controls the divergence measure being minimized.

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 \sum_{x_{N_I\setminus\{i\}}} f_I(x_I)^{1/c_I} \prod_{j\in N_I\setminus\{i\}} m_{I\to j}^{c_I-1} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}^{c_J} \]

After convergence, the variable beliefs are calculated by:

\[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i}^{c_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}^{c_I-1} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}^{c_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 \]

Note:
TRWBP is actually equivalent to FBP
Todo:
Add nice way to set weights
Todo:
Merge code of FBP and TRWBP

Constructor & Destructor Documentation

dai::TRWBP::TRWBP (  )  [inline]

Default constructor.

dai::TRWBP::TRWBP ( const FactorGraph fg,
const PropertySet opts 
) [inline]

Construct from FactorGraph fg and PropertySet opts.

Parameters:
opts Parameters
See also:
BP::Properties


Member Function Documentation

virtual TRWBP* dai::TRWBP::clone (  )  const [inline, virtual]

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

Reimplemented from dai::BP.

string dai::TRWBP::identify (  )  const [virtual]

Identifies itself for logging purposes.

Reimplemented from dai::BP.

Real dai::TRWBP::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::TRWBP::Weight ( size_t  I  )  const [inline]

Returns weight corresponding to the I 'th factor.

const std::vector<Real>& dai::TRWBP::Weights (  )  const [inline]

Returns constant reference to vector of all weights.

void dai::TRWBP::setWeight ( size_t  I,
Real  c 
) [inline]

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

void dai::TRWBP::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::TRWBP::calcIncomingMessageProduct ( size_t  I,
bool  without_i,
size_t  i 
) const [protected, virtual]

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::TRWBP::calcBeliefV ( size_t  i,
Prob p 
) const [protected, virtual]

Calculates unnormalized belief of variable i.

Reimplemented from dai::BP.

virtual void dai::TRWBP::calcBeliefF ( size_t  I,
Prob p 
) const [inline, protected, virtual]

Calculates unnormalized belief of factor I.

Reimplemented from dai::BP.

void dai::TRWBP::construct (  )  [protected, virtual]

Helper function for constructors.

Reimplemented from dai::BP.


Member Data Documentation

std::vector<Real> dai::TRWBP::_weight [protected]

"Edge weights" (indexed by factor ID)

In [WJW03], only unary or pairwise factors are considered. Here we are more general by having a weight for each factor in the factor graph. If unary factors have weight 1, and higher-order factors are absent, then we have the special case considered in [WJW03].

const char * dai::TRWBP::Name = "TRWBP" [static]

Name of this inference algorithm.

Reimplemented from dai::BP.


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

Generated on Thu Feb 11 12:26:07 2010 for libDAI by  doxygen 1.5.5