libDAI
|
Approximate inference algorithm "Fractional Belief Propagation" [WiH03]. More...
#include <dai/fbp.h>
Public Member Functions | |
Constructors/destructors | |
FBP () | |
Default constructor. More... | |
FBP (const FactorGraph &fg, const PropertySet &opts) | |
Construct from FactorGraph fg and PropertySet opts. More... | |
General InfAlg interface | |
virtual FBP * | clone () const |
Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor) More... | |
virtual FBP * | 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... | |
Public Member Functions inherited from dai::BP | |
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... | |
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... | |
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... | |
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... | |
Protected Attributes | |
std::vector< Real > | _weight |
Factor weights (indexed by factor ID) More... | |
Protected Attributes inherited from dai::BP | |
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... | |
FBP accessors/mutators for weights | |
Real | Weight (size_t I) const |
Returns weight of the I 'th factor. More... | |
const std::vector< Real > & | Weights () const |
Returns constant reference to vector of all factor weights. More... | |
void | setWeight (size_t I, Real c) |
Sets the weight of the I 'th factor to c. More... | |
void | setWeights (const std::vector< Real > &c) |
Sets the weights of all factors simultaenously. 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... | |
virtual void | calcBeliefF (size_t I, Prob &p) const |
Calculates unnormalized belief of factor I. More... | |
virtual void | construct () |
Helper function for constructors. More... | |
Additional Inherited Members | |
Public Attributes inherited from dai::BP | |
struct dai::BP::Properties | props |
bool | recordSentMessages |
Specifies whether the history of message updates should be recorded. More... | |
Protected Types inherited from dai::BP | |
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 inherited from dai::BP | |
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... | |
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... | |
Approximate inference algorithm "Fractional Belief Propagation" [WiH03].
The Fractional Belief Propagation algorithm is like Belief Propagation, but associates each factor with a weight (scale parameter) which controls the divergence measure being minimized. Standard Belief Propagation corresponds to the case of FBP where each weight is 1. When cast as an EP algorithm, BP (and EP) minimize the inclusive KL-divergence, i.e. (note that the Bethe free energy is typically derived from ). If each factor I has weight , then FBP minimizes the alpha-divergence with for that factor, which also corresponds to Power EP [Min05].
The messages are passed from factors to variables . The update equation is given by:
After convergence, the variable beliefs are calculated by:
and the factor beliefs are calculated by:
The logarithm of the partition sum is approximated by:
where the variable weights are defined as
|
inline |
Default constructor.
|
inline |
Construct from FactorGraph fg and PropertySet opts.
fg | Factor graph. |
opts | Parameters |
|
inlinevirtual |
Returns a pointer to a new, cloned copy of *this
(i.e., virtual copy constructor)
Reimplemented from dai::BP.
|
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; |
Reimplemented from dai::BP.
|
inlinevirtual |
Returns the name of the algorithm.
Reimplemented from dai::BP.
|
virtual |
|
inline |
Returns weight of the I 'th factor.
|
inline |
Returns constant reference to vector of all factor weights.
|
inline |
Sets the weight of the I 'th factor to c.
|
inline |
Sets the weights of all factors simultaenously.
|
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 from dai::BP.
|
protectedvirtual |
Calculate the updated message from the _I 'th neighbor of variable i to variable i.
Reimplemented from dai::BP.
|
inlineprotectedvirtual |
Calculates unnormalized belief of factor I.
Reimplemented from dai::BP.
|
protectedvirtual |
Helper function for constructors.
Reimplemented from dai::BP.
|
protected |
Factor weights (indexed by factor ID)