include/dai/mf.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 MF which implements the Mean Field algorithm
  11
  12
  13 #ifndef __defined_libdai_mf_h
  14 #define __defined_libdai_mf_h
  15
  16
  17 #include <dai/dai_config.h>
  18 #ifdef DAI_WITH_MF
  19
  20
  21 #include <string>
  22 #include <dai/enum.h>
  23 #include <dai/daialg.h>
  24 #include <dai/factorgraph.h>
  25 #include <dai/properties.h>
  26
  27
  28 namespace dai {
  29
  30
  31 /// Approximate inference algorithm "Mean Field"
  32 /** The Mean Field algorithm iteratively calculates approximations of
  33  *  single variable marginals (beliefs). The update equation for
  34  *  a single belief \f$b_i\f$ is given by:
  35  *    \f[ b_i^{\mathrm{new}}(x_i) \propto \prod_{I\in N_i} \exp \left( \sum_{x_{N_I \setminus \{i\}}} \log f_I(x_I) \prod_{j \in N_I \setminus \{i\}} b_j(x_j) \right) \f]
  36  *  for naive mean field and by
  37  *    \f[ b_i^{\mathrm{new}}(x_i) \propto \prod_{I\in N_i} \left( \sum_{x_{N_I \setminus \{i\}}} f_I(x_I) \prod_{j \in N_I \setminus \{i\}} b_j(x_j) \right) \f]
  38  *  for hard-spin mean field.
  39  *  These update equations are performed for all variables until convergence.
  40  */
  41 class MF : public DAIAlgFG {
  42     private:
  43         /// Current approximations of single variable marginals
  44         std::vector<Factor>  _beliefs;
  45         /// Maximum difference encountered so far
  46         Real _maxdiff;
  47         /// Number of iterations needed
  48         size_t _iters;
  49
  50     public:
  51         /// Parameters for MF
  52         struct Properties {
  53             /// Enumeration of possible message initializations
  54             DAI_ENUM(InitType,UNIFORM,RANDOM);
  55
  56             /// Enumeration of possible update types
  57             DAI_ENUM(UpdateType,NAIVE,HARDSPIN);
  58
  59             /// Verbosity (amount of output sent to stderr)
  60             size_t verbose;
  61
  62             /// Maximum number of iterations
  63             size_t maxiter;
  64
  65             /// Tolerance for convergence test
  66             Real tol;
  67
  68             /// Damping constant (0.0 means no damping, 1.0 is maximum damping)
  69             Real damping;
  70
  71             /// How to initialize the messages/beliefs
  72             InitType init;
  73
  74             /// How to update the messages/beliefs
  75             UpdateType updates;
  76         } props;
  77
  78     public:
  79     /// \name Constructors/destructors
  80     //@{
  81         /// Default constructor
  82         MF() : DAIAlgFG(), _beliefs(), _maxdiff(0.0), _iters(0U), props() {}
  83
  84         /// Construct from FactorGraph \a fg and PropertySet \a opts
  85         /** \param fg Factor graph.
  86          *  \param opts Parameters @see Properties
  87          */
  88         MF( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), _beliefs(), _maxdiff(0.0), _iters(0U), props() {
  89             setProperties( opts );
  90             construct();
  91         }
  92     //@}
  93
  94     /// \name General InfAlg interface
  95     //@{
  96         virtual MF* clone() const { return new MF(*this); }
  97         virtual MF* construct( const FactorGraph &fg, const PropertySet &opts ) const { return new MF( fg, opts ); }
  98         virtual std::string name() const { return "MF"; }
  99         virtual Factor belief( const Var &v ) const { return beliefV( findVar( v ) ); }
 100         virtual Factor belief( const VarSet &vs ) const;
 101         virtual Factor beliefV( size_t i ) const;
 102         virtual std::vector<Factor> beliefs() const;
 103         virtual Real logZ() const;
 104         virtual void init();
 105         virtual void init( const VarSet &ns );
 106         virtual Real run();
 107         virtual Real maxDiff() const { return _maxdiff; }
 108         virtual size_t Iterations() const { return _iters; }
 109         virtual void setMaxIter( size_t maxiter ) { props.maxiter = maxiter; }
 110         virtual void setProperties( const PropertySet &opts );
 111         virtual PropertySet getProperties() const;
 112         virtual std::string printProperties() const;
 113     //@}
 114
 115     private:
 116         /// Helper function for constructors
 117         void construct();
 118
 119         /// Calculates an updated belief of variable \a i
 120         Factor calcNewBelief( size_t i );
 121 };
 122
 123
 124 } // end of namespace dai
 125
 126
 127 #endif
 128
 129
 130 #endif