libDAI
|
Approximate inference algorithm "(Loopy) Belief Propagation". More...
#include <dai/bp.h>
Classes | |
struct | EdgeProp |
Type used for storing edge properties. More... | |
struct | Properties |
Parameters for BP. More... | |
Public Member Functions | |
Constructors/destructors | |
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... | |
General InfAlg interface | |
virtual BP * | clone () const |
Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor) More... | |
virtual BP * | 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 &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... | |
virtual Real | logZ () const |
Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph). 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... | |
Additional interface specific for BP | |
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 ) 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... | |
Public Attributes | |
struct dai::BP::Properties | props |
bool | recordSentMessages |
Specifies whether the history of message updates should be recorded. More... | |
Protected Types | |
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 | |
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... | |
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... | |
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... | |
virtual void | calcBeliefF (size_t I, Prob &p) const |
Calculates unnormalized belief of factor I. More... | |
virtual void | construct () |
Helper function for constructors. More... | |
Protected Attributes | |
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... | |
Approximate inference algorithm "(Loopy) Belief Propagation".
The Loopy Belief Propagation algorithm uses message passing to approximate marginal probability distributions ("beliefs") for variables and factors (more precisely, for the subset of variables depending on the factor). There are two variants, the sum-product algorithm (corresponding to finite temperature) and the max-product algorithm (corresponding to zero temperature).
The messages are passed from factors to variables . In case of the sum-product algorith, the update equation is:
and in case of the max-product algorithm:
In order to improve convergence, the updates can be damped. For improved numerical stability, the updates can be done in the log-domain alternatively.
After convergence, the variable beliefs are calculated by:
and the factor beliefs are calculated by:
The logarithm of the partition sum is calculated by:
For the max-product algorithm, a heuristic way of finding the MAP state (the joint configuration of all variables which has maximum probability) is provided by the findMaximum() method, which can be called after convergence.
|
protected |
Type used for index cache.
|
protected |
Type of lookup table (only used for maximum-residual BP)
|
inline |
Default constructor.
|
inline |
Construct from FactorGraph fg and PropertySet opts.
fg | Factor graph. |
opts | Parameters |
|
inline |
Copy constructor.
|
inlinevirtual |
Returns a pointer to a new, cloned copy of *this
(i.e., virtual copy constructor)
Implements dai::InfAlg.
Reimplemented in dai::TRWBP, and dai::FBP.
|
inlinevirtual |
Returns a pointer to a newly constructed inference algorithm.
fg | Factor graph on which to perform the inference algorithm; |
opts | Parameters passed to constructor of inference algorithm; |
Implements dai::InfAlg.
Reimplemented in dai::TRWBP, and dai::FBP.
|
inlinevirtual |
Returns the name of the algorithm.
Implements dai::InfAlg.
Reimplemented in dai::TRWBP, and dai::FBP.
Returns the (approximate) marginal probability distribution of a variable.
Reimplemented from dai::InfAlg.
Returns the (approximate) marginal probability distribution of a set of variables.
NOT_IMPLEMENTED | if not implemented/supported. |
BELIEF_NOT_AVAILABLE | if the requested belief cannot be calculated with this algorithm. |
Implements dai::InfAlg.
|
virtual |
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.
Reimplemented from dai::InfAlg.
|
virtual |
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.
Reimplemented from dai::InfAlg.
|
virtual |
Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm.
Implements dai::InfAlg.
|
virtual |
Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).
NOT_IMPLEMENTED | if not implemented/supported |
Implements dai::InfAlg.
Reimplemented in dai::TRWBP, and dai::FBP.
|
inlinevirtual |
MAXPROD
Reimplemented from dai::InfAlg.
|
virtual |
Initializes all data structures of the approximate inference algorithm.
Implements dai::InfAlg.
|
virtual |
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.
NOT_IMPLEMENTED | if not implemented/supported |
Implements dai::InfAlg.
|
virtual |
|
inlinevirtual |
Returns maximum difference between single variable beliefs in the last iteration.
NOT_IMPLEMENTED | if not implemented/supported |
Reimplemented from dai::InfAlg.
|
inlinevirtual |
Returns number of iterations done (one iteration passes over the complete factorgraph).
NOT_IMPLEMENTED | if not implemented/supported |
Reimplemented from dai::InfAlg.
|
inlinevirtual |
Sets maximum number of iterations (one iteration passes over the complete factorgraph).
NOT_IMPLEMENTED | if not implemented/supported |
Reimplemented from dai::InfAlg.
|
virtual |
Implements dai::InfAlg.
Reimplemented in dai::TRWBP.
|
virtual |
Returns parameters of this inference algorithm converted into a PropertySet.
Implements dai::InfAlg.
Reimplemented in dai::TRWBP.
|
virtual |
Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".
Implements dai::InfAlg.
Reimplemented in dai::TRWBP.
|
inline |
Returns history of which messages have been updated.
|
inline |
Clears history of which messages have been updated.
|
inlineprotected |
Returns constant reference to message from the _I 'th neighbor of variable i to variable i.
|
inlineprotected |
Returns reference to message from the _I 'th neighbor of variable i to variable i.
|
inlineprotected |
Returns constant reference to updated message from the _I 'th neighbor of variable i to variable i.
|
inlineprotected |
Returns reference to updated message from the _I 'th neighbor of variable i to variable i.
|
inlineprotected |
Returns constant reference to cached index for the edge between variable i and its _I 'th neighbor.
|
inlineprotected |
Returns reference to cached index for the edge between variable i and its _I 'th neighbor.
|
inlineprotected |
Returns constant reference to residual for the edge between variable i and its _I 'th neighbor.
|
inlineprotected |
Returns reference to residual for the edge between variable i and its _I 'th neighbor.
|
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
Reimplemented in dai::TRWBP, and dai::FBP.
|
protectedvirtual |
Calculate the updated message from the _I 'th neighbor of variable i to variable i.
Reimplemented in dai::FBP.
|
protected |
Replace the "old" message from the _I 'th neighbor of variable i to variable i by the "new" (updated) message.
|
protected |
Set the residual (difference between new and old message) for the edge between variable i and its _I 'th neighbor to r.
|
protected |
Finds the edge which has the maximum residual (difference between new and old message)
|
protectedvirtual |
Calculates unnormalized belief of variable i.
Reimplemented in dai::TRWBP.
|
inlineprotectedvirtual |
Calculates unnormalized belief of factor I.
Reimplemented in dai::TRWBP, and dai::FBP.
|
protectedvirtual |
Helper function for constructors.
Reimplemented in dai::TRWBP, and dai::FBP.
|
protected |
Stores all edge properties.
|
protected |
Lookup table (only used for maximum-residual BP)
|
protected |
Maximum difference between variable beliefs encountered so far.
|
protected |
Number of iterations needed.
|
protected |
The history of message updates (only recorded if recordSentMessages is true
)
|
protected |
Stores variable beliefs of previous iteration.
|
protected |
Stores factor beliefs of previous iteration.
|
protected |
Stores the update schedule.
bool dai::BP::recordSentMessages |
Specifies whether the history of message updates should be recorded.