include/dai/fbp.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2009 Frederik Eaton
   8  */
   9
  10
  11 /// \file
  12 /// \brief Defines class FBP, which implements Fractional Belief Propagation
  13
  14
  15 #ifndef __defined_libdai_fbp_h
  16 #define __defined_libdai_fbp_h
  17
  18
  19 #include <string>
  20 #include <dai/daialg.h>
  21 #include <dai/factorgraph.h>
  22 #include <dai/properties.h>
  23 #include <dai/enum.h>
  24 #include <dai/bp.h>
  25
  26
  27 namespace dai {
  28
  29
  30 /// Approximate inference algorithm "Fractional Belief Propagation" [\ref WiH03]
  31 /** The Fractional Belief Propagation algorithm is like Belief
  32  *  Propagation, but associates each factor with a weight (scale parameter)
  33  *  which controls the divergence measure being minimized. Standard
  34  *  Belief Propagation corresponds to the case of FBP where each weight
  35  *  is 1. When cast as an EP algorithm, BP (and EP) minimize
  36  *  the inclusive KL-divergence, i.e. \f$\min_q KL(p||q)\f$ (note that the
  37  *  Bethe free energy is typically derived from \f$ KL(q||p) \f$). If each
  38  *  factor \a I has weight \f$ c_I \f$, then FBP minimizes the
  39  *  alpha-divergence with \f$ \alpha=1/c_I \f$ for that factor, which also
  40  *  corresponds to Power EP [\ref Min05].
  41  *
  42  *  The messages \f$m_{I\to i}(x_i)\f$ are passed from factors \f$I\f$ to variables \f$i\f$.
  43  *  The update equation is given by:
  44  *    \f[ m_{I\to i}(x_i) \propto \left( \sum_{x_{N_I\setminus\{i\}}} f_I(x_I)^{1/c_I} \prod_{j\in N_I\setminus\{i\}} m_{I\to j}^{1-1/c_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j} \right)^{c_I} \f]
  45  *  After convergence, the variable beliefs are calculated by:
  46  *    \f[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i} \f]
  47  *  and the factor beliefs are calculated by:
  48  *    \f[ b_I(x_I) \propto f_I(x_I)^{1/c_I} \prod_{j \in N_I} m_{I\to j}^{1-1/c_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j} \f]
  49  *  The logarithm of the partition sum is approximated by:
  50  *    \f[ \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) \f]
  51  *  where the variable weights are defined as
  52  *    \f[ c_i := \sum_{I \in N_i} c_I \f]
  53  *
  54  *  \todo Add nice way to set weights
  55  *  \author Frederik Eaton
  56  */
  57 class FBP : public BP {
  58     protected:
  59         /// Factor weights (indexed by factor ID)
  60         std::vector<Real> _weight;
  61
  62     public:
  63         /// Name of this inference algorithm
  64         static const char *Name;
  65
  66     public:
  67     /// \name Constructors/destructors
  68     //@{
  69         /// Default constructor
  70         FBP() : BP(), _weight() {}
  71
  72         /// Construct from FactorGraph \a fg and PropertySet \a opts
  73         /** \param opts Parameters @see BP::Properties
  74          */
  75         FBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _weight() {
  76             setProperties( opts );
  77             construct();
  78         }
  79     //@}
  80
  81     /// \name General InfAlg interface
  82     //@{
  83         virtual FBP* clone() const { return new FBP(*this); }
  84         virtual std::string identify() const;
  85         virtual Real logZ() const;
  86     //@}
  87
  88     /// \name FBP accessors/mutators for weights
  89     //@{
  90         /// Returns weight of the \a I 'th factor
  91         Real Weight( size_t I ) const { return _weight[I]; }
  92
  93         /// Returns constant reference to vector of all factor weights
  94         const std::vector<Real>& Weights() const { return _weight; }
  95
  96         /// Sets the weight of the \a I 'th factor to \a c
  97         void setWeight( size_t I, Real c ) { _weight[I] = c; }
  98
  99         /// Sets the weights of all factors simultaenously
 100         /** \note Faster than calling setWeight(size_t,Real) for each factor
 101          */
 102         void setWeights( const std::vector<Real> &c ) { _weight = c; }
 103
 104     protected:
 105         /// Calculate the product of factor \a I and the incoming messages
 106         /** If \a without_i == \c true, the message coming from variable \a i is omitted from the product
 107          *  \note This function is used by calcNewMessage() and calcBeliefF()
 108          */
 109         virtual Prob calcIncomingMessageProduct( size_t I, bool without_i, size_t i ) const;
 110
 111         // Calculate the updated message from the \a _I 'th neighbor of variable \a i to variable \a i
 112         virtual void calcNewMessage( size_t i, size_t _I );
 113
 114         // Calculates unnormalized belief of factor \a I
 115         virtual void calcBeliefF( size_t I, Prob &p ) const {
 116             p = calcIncomingMessageProduct( I, false, 0 );
 117         }
 118
 119         // Helper function for constructors
 120         virtual void construct();
 121 };
 122
 123
 124 } // end of namespace dai
 125
 126
 127 #endif