include/dai/trwbp.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
   4  *
   5  *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
   6  */
   7
   8
   9 /// \file
  10 /// \brief Defines class TRWBP, which implements Tree-Reweighted Belief Propagation
  11
  12
  13 #ifndef __defined_libdai_trwbp_h
  14 #define __defined_libdai_trwbp_h
  15
  16
  17 #include <dai/dai_config.h>
  18 #ifdef DAI_WITH_TRWBP
  19
  20
  21 #include <string>
  22 #include <dai/daialg.h>
  23 #include <dai/factorgraph.h>
  24 #include <dai/properties.h>
  25 #include <dai/enum.h>
  26 #include <dai/bp.h>
  27
  28
  29 namespace dai {
  30
  31
  32 /// Approximate inference algorithm "Tree-Reweighted Belief Propagation" [\ref WJW03]
  33 /** The Tree-Reweighted Belief Propagation algorithm is like Belief
  34  *  Propagation, but associates each factor with a scale parameter.
  35  *  which controls the divergence measure being minimized.
  36  *
  37  *  The messages \f$m_{I\to i}(x_i)\f$ are passed from factors \f$I\f$ to variables \f$i\f$.
  38  *  The update equation is given by:
  39  *    \f[ 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} \f]
  40  *  After convergence, the variable beliefs are calculated by:
  41  *    \f[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i}^{c_I} \f]
  42  *  and the factor beliefs are calculated by:
  43  *    \f[ 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} \f]
  44  *  The logarithm of the partition sum is approximated by:
  45  *    \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]
  46  *  where the variable weights are defined as
  47  *    \f[ c_i := \sum_{I \in N_i} c_I \f]
  48  *
  49  *  \note TRWBP is actually equivalent to FBP
  50  *  \todo Merge code of FBP and TRWBP
  51  */
  52 class TRWBP : public BP {
  53     protected:
  54         /// "Edge weights" (indexed by factor ID)
  55         /** In [\ref WJW03], only unary or pairwise factors are considered.
  56          *  Here we are more general by having a weight for each factor in the
  57          *  factor graph. If unary factors have weight 1, and higher-order factors
  58          *  are absent, then we have the special case considered in [\ref WJW03].
  59          */
  60         std::vector<Real> _weight;
  61
  62     public:
  63         /// Size of sample of trees used to set the weights
  64         /** \todo See if there is a way to wrap TRWBP::nrtrees in a props struct
  65          *  together with the other properties currently in TRWBP::props
  66          *  (without copying al lot of BP code literally)
  67          */
  68         size_t nrtrees;
  69
  70     public:
  71     /// \name Constructors/destructors
  72     //@{
  73         /// Default constructor
  74         TRWBP() : BP(), _weight() {}
  75
  76         /// Construct from FactorGraph \a fg and PropertySet \a opts.
  77         /** There is an additional property "nrtrees" which allows to specify the
  78          *  number of random spanning trees used to set the scale parameters.
  79          *  \param fg Factor graph.
  80          *  \param opts Parameters @see BP::Properties.
  81          */
  82         TRWBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _weight() {
  83             setProperties( opts );
  84             construct();
  85         }
  86     //@}
  87
  88     /// \name General InfAlg interface
  89     //@{
  90         virtual TRWBP* clone() const { return new TRWBP(*this); }
  91         virtual TRWBP* construct( const FactorGraph &fg, const PropertySet &opts ) const { return new TRWBP( fg, opts ); }
  92         virtual std::string name() const { return "TRWBP"; }
  93         virtual Real logZ() const;
  94         virtual void setProperties( const PropertySet &opts );
  95         virtual PropertySet getProperties() const;
  96         virtual std::string printProperties() const;
  97     //@}
  98
  99     /// \name TRWBP accessors/mutators for scale parameters
 100     //@{
 101         /// Returns weight corresponding to the \a I 'th factor
 102         Real Weight( size_t I ) const { return _weight[I]; }
 103
 104         /// Returns constant reference to vector of all weights
 105         const std::vector<Real>& Weights() const { return _weight; }
 106
 107         /// Sets the weight of the \a I 'th factor to \a c
 108         void setWeight( size_t I, Real c ) { _weight[I] = c; }
 109
 110         /// Sets the weights of all factors simultaenously
 111         /** \note Faster than calling setWeight(size_t,Real) for each factor
 112          */
 113         void setWeights( const std::vector<Real> &c ) { _weight = c; }
 114
 115         /// Increases weights corresponding to pairwise factors in \a tree with 1
 116         void addTreeToWeights( const RootedTree &tree );
 117
 118         /// Samples weights from a sample of \a nrTrees random spanning trees
 119         void sampleWeights( size_t nrTrees );
 120
 121     protected:
 122         /// Calculate the product of factor \a I and the incoming messages
 123         /** If \a without_i == \c true, the message coming from variable \a i is omitted from the product
 124          *  \note This function is used by calcNewMessage() and calcBeliefF()
 125          */
 126         virtual Prob calcIncomingMessageProduct( size_t I, bool without_i, size_t i ) const;
 127
 128         /// Calculates unnormalized belief of variable \a i
 129         virtual void calcBeliefV( size_t i, Prob &p ) const;
 130
 131         // Calculates unnormalized belief of factor \a I
 132         virtual void calcBeliefF( size_t I, Prob &p ) const {
 133             p = calcIncomingMessageProduct( I, false, 0 );
 134         }
 135
 136         // Helper function for constructors
 137         virtual void construct();
 138 };
 139
 140
 141 } // end of namespace dai
 142
 143
 144 #endif
 145
 146
 147 #endif