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
  14 /// \todo Improve documentation
  15
  16
  17 #ifndef __defined_libdai_lc_h
  18 #define __defined_libdai_lc_h
  19
  20
  21 #include <string>
  22 #include <dai/daialg.h>
  23 #include <dai/enum.h>
  24 #include <dai/factorgraph.h>
  25 #include <dai/properties.h>
  26 #include <dai/exceptions.h>
  27
  28
  29 namespace dai {
  30
  31
  32 /// Approximate inference algorithm "Loop Corrected Belief Propagation" by Mooij and Kappen
  33 class LC : public DAIAlgFG {
  34     private:
  35         std::vector<Factor>      _pancakes;      // used by all LC types (psi_I is stored in the pancake)
  36         std::vector<Factor>      _cavitydists;   // used by all LC types to store the approximate cavity distribution
  37         /// _phis[i][_I] corresponds to \f$ \phi^{\setminus i}_I(x_{I \setminus i}) \f$
  38         std::vector<std::vector<Factor> >      _phis;
  39
  40         /// Single variable beliefs
  41         std::vector<Factor>      _beliefs;
  42
  43         /// Maximum difference encountered so far
  44         double                  _maxdiff;
  45         /// Number of iterations needed
  46         size_t                  _iters;
  47
  48     public:
  49         /// Parameters of this inference algorithm
  50         struct Properties {
  51             /// Enumeration of possible ways to initialize the cavities
  52             DAI_ENUM(CavityType,FULL,PAIR,PAIR2,UNIFORM);
  53
  54             /// Enumeration of different update schedules
  55             DAI_ENUM(UpdateType,SEQFIX,SEQRND,NONE);
  56
  57             /// Verbosity
  58             size_t verbose;
  59
  60             /// Maximum number of iterations
  61             size_t maxiter;
  62
  63             /// Tolerance
  64             double tol;
  65
  66             /// Complete or partial reinit of cavity graphs?
  67             bool reinit;
  68
  69             /// Damping constant
  70             double damping;
  71
  72             /// How to initialize the cavities
  73             CavityType cavity;
  74
  75             /// What update schedule to use
  76             UpdateType updates;
  77
  78             /// Name of the algorithm used to initialize the cavity distributions
  79             std::string cavainame;      // FIXME: needs assignment operator?
  80
  81             /// Parameters for the algorithm used to initialize the cavity distributions
  82             PropertySet cavaiopts;      // FIXME: needs assignment operator?
  83         } props;
  84
  85         /// Name of this inference algorithm
  86         static const char *Name;
  87
  88     public:
  89         /// Default constructor
  90         LC() : DAIAlgFG(), _pancakes(), _cavitydists(), _phis(), _beliefs(), _maxdiff(), _iters(), props() {}
  91
  92         /// Construct from FactorGraph fg and PropertySet opts
  93         LC( const FactorGraph &fg, const PropertySet &opts );
  94
  95
  96         /// @name General InfAlg interface
  97         //@{
  98         virtual LC* clone() const { return new LC(*this); }
  99         virtual std::string identify() const;
 100         virtual Factor belief( const Var &n ) const { return( _beliefs[findVar(n)] ); }
 101         virtual Factor belief( const VarSet &/*ns*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
 102         virtual std::vector<Factor> beliefs() const { return _beliefs; }
 103         virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
 104         virtual void init();
 105         virtual void init( const VarSet &/*ns*/ ) { init(); }
 106         virtual double run();
 107         virtual double maxDiff() const { return _maxdiff; }
 108         virtual size_t Iterations() const { return _iters; }
 109         //@}
 110
 111         Factor beliefV( size_t i ) const { return _beliefs[i]; }
 112
 113         /// @name Additional interface specific for LC
 114         //@{
 115         double CalcCavityDist( size_t i, const std::string &name, const PropertySet &opts );
 116         double InitCavityDists( const std::string &name, const PropertySet &opts );
 117         long SetCavityDists( std::vector<Factor> &Q );
 118
 119         Factor NewPancake (size_t i, size_t _I, bool & hasNaNs);
 120
 121         void CalcBelief (size_t i);
 122         const Factor &belief (size_t i) const { return _beliefs[i]; };
 123         const Factor &pancake (size_t i) const { return _pancakes[i]; };
 124         const Factor &cavitydist (size_t i) const { return _cavitydists[i]; };
 125         //@}
 126
 127     private:
 128         void setProperties( const PropertySet &opts );
 129         PropertySet getProperties() const;
 130         std::string printProperties() const;
 131 };
 132
 133
 134 } // end of namespace dai
 135
 136
 137 #endif