include/dai/lc.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) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 /// \file
  13 /// \brief Defines class LC, which implements loop corrections for approximate inference
  14
  15
  16 #ifndef __defined_libdai_lc_h
  17 #define __defined_libdai_lc_h
  18
  19
  20 #include <string>
  21 #include <dai/daialg.h>
  22 #include <dai/enum.h>
  23 #include <dai/factorgraph.h>
  24 #include <dai/properties.h>
  25 #include <dai/exceptions.h>
  26
  27
  28 namespace dai {
  29
  30
  31 /// Approximate inference algorithm "Loop Corrected Belief Propagation" [\ref MoK07]
  32 class LC : public DAIAlgFG {
  33     private:
  34         /// Stores for each variable the approximate cavity distribution multiplied with the omitted factors
  35         std::vector<Factor> _pancakes;
  36         /// Stores for each variable the approximate cavity distribution
  37         std::vector<Factor> _cavitydists;
  38         /// _phis[i][_I] corresponds to \f$ \phi^{\setminus i}_I(x_{I \setminus i}) \f$ in the paper
  39         std::vector<std::vector<Factor> > _phis;
  40         /// Single variable beliefs
  41         std::vector<Factor> _beliefs;
  42         /// Maximum difference encountered so far
  43         Real _maxdiff;
  44         /// Number of iterations needed
  45         size_t _iters;
  46
  47     public:
  48         /// Parameters of this inference algorithm
  49         struct Properties {
  50             /// Enumeration of possible ways to initialize the cavities
  51             /** The following initialization methods are defined:
  52              *  - FULL calculates the marginal using calcMarginal()
  53              *  - PAIR calculates only second order interactions using calcPairBeliefs() with \a accurate == \c false
  54              *  - PAIR2 calculates only second order interactions using calcPairBeliefs() with \a accurate == \c true
  55              *  - UNIFORM uses a uniform distribution
  56              */
  57             DAI_ENUM(CavityType,FULL,PAIR,PAIR2,UNIFORM);
  58
  59             /// Enumeration of different update schedules
  60             /** The following update schedules are defined:
  61              *  - SEQFIX sequential fixed schedule
  62              *  - SEQRND sequential random schedule
  63              */
  64             DAI_ENUM(UpdateType,SEQFIX,SEQRND);
  65
  66             /// Verbosity
  67             size_t verbose;
  68
  69             /// Maximum number of iterations
  70             size_t maxiter;
  71
  72             /// Tolerance
  73             Real tol;
  74
  75             /// Complete or partial reinitialization of cavity graphs?
  76             bool reinit;
  77
  78             /// Damping constant
  79             Real damping;
  80
  81             /// How to initialize the cavities
  82             CavityType cavity;
  83
  84             /// What update schedule to use
  85             UpdateType updates;
  86
  87             /// Name of the algorithm used to initialize the cavity distributions
  88             std::string cavainame;
  89
  90             /// Parameters for the algorithm used to initialize the cavity distributions
  91             PropertySet cavaiopts;
  92         } props;
  93
  94         /// Name of this inference algorithm
  95         static const char *Name;
  96
  97     public:
  98         /// Default constructor
  99         LC() : DAIAlgFG(), _pancakes(), _cavitydists(), _phis(), _beliefs(), _maxdiff(), _iters(), props() {}
 100
 101         /// Construct from FactorGraph \a fg and PropertySet \a opts
 102         /** \see Properties
 103          */
 104         LC( const FactorGraph &fg, const PropertySet &opts );
 105
 106
 107     /// \name General InfAlg interface
 108     //@{
 109         virtual LC* clone() const { return new LC(*this); }
 110         virtual std::string identify() const;
 111         virtual Factor belief( const Var &n ) const { return( _beliefs[findVar(n)] ); }
 112         virtual Factor belief( const VarSet &/*ns*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
 113         virtual Factor beliefV( size_t i ) const { return _beliefs[i]; }
 114         virtual std::vector<Factor> beliefs() const { return _beliefs; }
 115         virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
 116         virtual void init();
 117         virtual void init( const VarSet &/*ns*/ ) { init(); }
 118         virtual Real run();
 119         virtual Real maxDiff() const { return _maxdiff; }
 120         virtual size_t Iterations() const { return _iters; }
 121         virtual void setProperties( const PropertySet &opts );
 122         virtual PropertySet getProperties() const;
 123         virtual std::string printProperties() const;
 124     //@}
 125
 126     /// \name Additional interface specific for LC
 127     //@{
 128         /// Approximates the cavity distribution of variable \a i, using the inference algorithm \a name with parameters \a opts
 129         Real CalcCavityDist( size_t i, const std::string &name, const PropertySet &opts );
 130         /// Approximates all cavity distributions using inference algorithm \a name with parameters \a opts
 131         Real InitCavityDists( const std::string &name, const PropertySet &opts );
 132         /// Sets approximate cavity distributions to \a Q
 133         long SetCavityDists( std::vector<Factor> &Q );
 134         /// Updates the belief of the Markov blanket of variable \a i based upon the information from its \a _I 'th neighboring factor
 135         Factor NewPancake (size_t i, size_t _I, bool & hasNaNs);
 136         /// Calculates the belief of variable \a i
 137         void CalcBelief (size_t i);
 138         /// Returns the belief of variable \a i
 139         /** \deprecated Please use dai::LC::beliefV() instead
 140          */
 141         const Factor &belief (size_t i) const { return _beliefs[i]; };
 142         /// Returns the belief of the Markov blanket of variable \a i (including the variable itself)
 143         const Factor &pancake (size_t i) const { return _pancakes[i]; };
 144         /// Returns the approximate cavity distribution for variable \a i
 145         const Factor &cavitydist (size_t i) const { return _cavitydists[i]; };
 146     //@}
 147 };
 148
 149
 150 } // end of namespace dai
 151
 152
 153 #endif