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 scale parameter
  33  *  which controls the divergence measure being minimized. Standard
  34  *  Belief Propagation corresponds to the case of FBP where each scale
  35  *  parameter 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 scale parameter \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}\right)^{c_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j} \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  *
  50  *  \todo Implement logZ
  51  *  \todo Why are the _scale_var necessary?
  52  *  \todo Add nice way to set scale parameters
  53  *
  54  *  \author Frederik Eaton
  55  */
  56 class FBP : public BP {
  57     protected:
  58         /// Factor scale parameters (indexed by factor ID)
  59         std::vector<Real> _scale_factor;
  60         /// Variable scale parameters (indexed by variable ID)
  61         /** \note Equal to sum of scale parameters of neighboring factors
  62          */
  63         std::vector<Real> _scale_var;
  64
  65     public:
  66         /// Name of this inference algorithm
  67         static const char *Name;
  68
  69     public:
  70     /// \name Constructors/destructors
  71     //@{
  72         /// Default constructor
  73         FBP() : BP(), _scale_factor(), _scale_var() {}
  74
  75         /// Construct from FactorGraph \a fg and PropertySet \a opts
  76         /** \param opts Parameters @see BP::Properties
  77          */
  78         FBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _scale_factor(), _scale_var() {
  79             setProperties( opts );
  80             construct();
  81         }
  82     //@}
  83
  84     /// \name General InfAlg interface
  85     //@{
  86         virtual FBP* clone() const { return new FBP(*this); }
  87         virtual std::string identify() const;
  88     //@}
  89
  90     /// \name FBP accessors/mutators for scale parameters
  91     //@{
  92         /// Returns scale parameter of the \a I 'th factor
  93         Real scaleF( size_t I ) const { return _scale_factor[I]; }
  94
  95         /// Returns constant reference to vector of all factor scale parameters
  96         const std::vector<Real>& scaleFs() const { return _scale_factor; }
  97
  98         /// Returns scale parameter of the \a i 'th variable
  99         Real scaleV( size_t i ) const { return _scale_var[i]; }
 100
 101         /// Returns constant reference to vector of all variable scale parameters
 102         const std::vector<Real>& scaleVs() const { return _scale_var; }
 103
 104         /// Sets the scale parameter of the \a I 'th factor to \a c
 105         void setScaleF( size_t I, Real c ) {
 106             _scale_factor[I] = c;
 107             foreach( const Neighbor &i, nbF(I) )
 108                 recalcScaleV(i);
 109         }
 110
 111         /// Sets the scale parameters of all factors simultaenously
 112         /** \note Faster than calling setScaleF(size_t,Real) for each factor
 113          */
 114         void setScaleFs( const std::vector<Real> &c ) {
 115             _scale_factor = c;
 116             recalcScaleVs();
 117         }
 118
 119         /// Recalculates all variable scale parameters
 120         /** \note For each variable, its scale parameter is set to
 121          *  the sum of the scale parameters of its neighboring factors.
 122          */
 123         void recalcScaleVs() {
 124             for( size_t i = 0; i < nrVars(); i++ )
 125                 recalcScaleV(i);
 126         }
 127
 128         /// Recalculates the scale parameter of the \a i 'th variable
 129         /** \note The scale parameter is set to the sum of the scale parameters of its neighboring factors.
 130          */
 131         void recalcScaleV( size_t i ) {
 132             // Set _scale_var[i] to the sum of its neighbors
 133             Real c_i = 0.0;
 134             foreach( const Neighbor &I, nbV(i) )
 135                 c_i += scaleF(I);
 136             _scale_var[i] = c_i;
 137         }
 138
 139     protected:
 140         // Calculate the updated message from the \a _I 'th neighbor of variable \a i to variable \a i
 141         virtual void calcNewMessage( size_t i, size_t _I );
 142
 143         // Calculates unnormalized belief of factor \a I
 144         virtual void calcBeliefF( size_t I, Prob &p ) const;
 145
 146         // Helper function for constructors
 147         virtual void construct();
 148
 149         /// (Re)constructs the scale parameters data structures
 150         void constructScaleParams() {
 151             _scale_factor.resize( nrFactors(), 1.0 );
 152             _scale_var.resize( nrVars() );
 153             recalcScaleVs();
 154         }
 155 };
 156
 157
 158 } // end of namespace dai
 159
 160
 161 #endif