include/dai/lc.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
   2     Radboud University Nijmegen, The Netherlands /
   3     Max Planck Institute for Biological Cybernetics, Germany
   4
   5     This file is part of libDAI.
   6
   7     libDAI is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     libDAI is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with libDAI; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22
  23 /// \file
  24 /// \brief Defines class LC
  25 /// \todo Improve documentation
  26
  27
  28 #ifndef __defined_libdai_lc_h
  29 #define __defined_libdai_lc_h
  30
  31
  32 #include <string>
  33 #include <dai/daialg.h>
  34 #include <dai/enum.h>
  35 #include <dai/factorgraph.h>
  36 #include <dai/properties.h>
  37 #include <dai/exceptions.h>
  38
  39
  40 namespace dai {
  41
  42
  43 /// Approximate inference algorithm "Loop Corrected Belief Propagation" by Mooij and Kappen
  44 class LC : public DAIAlgFG {
  45     private:
  46         std::vector<Factor>      _pancakes;      // used by all LC types (psi_I is stored in the pancake)
  47         std::vector<Factor>      _cavitydists;   // used by all LC types to store the approximate cavity distribution
  48         /// _phis[i][_I] corresponds to \f$ \phi^{\setminus i}_I(x_{I \setminus i}) \f$
  49         std::vector<std::vector<Factor> >      _phis;
  50
  51         /// Single variable beliefs
  52         std::vector<Factor>      _beliefs;
  53
  54         /// Maximum difference encountered so far
  55         double                  _maxdiff;
  56         /// Number of iterations needed
  57         size_t                  _iters;
  58
  59     public:
  60         /// Parameters of this inference algorithm
  61         struct Properties {
  62             /// Enumeration of possible ways to initialize the cavities
  63             DAI_ENUM(CavityType,FULL,PAIR,PAIR2,UNIFORM)
  64
  65             /// Enumeration of different update schedules
  66             DAI_ENUM(UpdateType,SEQFIX,SEQRND,NONE)
  67
  68             /// Verbosity
  69             size_t verbose;
  70
  71             /// Maximum number of iterations
  72             size_t maxiter;
  73
  74             /// Tolerance
  75             double tol;
  76
  77             /// Complete or partial reinit of cavity graphs?
  78             bool reinit;
  79
  80             /// Damping constant
  81             double damping;
  82
  83             /// How to initialize the cavities
  84             CavityType cavity;
  85
  86             /// What update schedule to use
  87             UpdateType updates;
  88
  89             /// Name of the algorithm used to initialize the cavity distributions
  90             std::string cavainame;      // FIXME: needs assignment operator?
  91
  92             /// Parameters for the algorithm used to initialize the cavity distributions
  93             PropertySet cavaiopts;      // FIXME: needs assignment operator?
  94         } props;
  95
  96         /// Name of this inference algorithm
  97         static const char *Name;
  98
  99     public:
 100         /// Default constructor
 101         LC() : DAIAlgFG(), _pancakes(), _cavitydists(), _phis(), _beliefs(), _maxdiff(), _iters(), props() {}
 102
 103         /// Construct from FactorGraph fg and PropertySet opts
 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 std::vector<Factor> beliefs() const { return _beliefs; }
 114         virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
 115         virtual void init();
 116         virtual void init( const VarSet &/*ns*/ ) { init(); }
 117         virtual double run();
 118         virtual double maxDiff() const { return _maxdiff; }
 119         virtual size_t Iterations() const { return _iters; }
 120         //@}
 121
 122
 123         /// @name Additional interface specific for LC
 124         //@{
 125         double CalcCavityDist( size_t i, const std::string &name, const PropertySet &opts );
 126         double InitCavityDists( const std::string &name, const PropertySet &opts );
 127         long SetCavityDists( std::vector<Factor> &Q );
 128
 129         Factor NewPancake (size_t i, size_t _I, bool & hasNaNs);
 130
 131         void CalcBelief (size_t i);
 132         const Factor &belief (size_t i) const { return _beliefs[i]; };
 133         const Factor &pancake (size_t i) const { return _pancakes[i]; };
 134         const Factor &cavitydist (size_t i) const { return _cavitydists[i]; };
 135         //@}
 136
 137     private:
 138         void setProperties( const PropertySet &opts );
 139         PropertySet getProperties() const;
 140         std::string printProperties() const;
 141 };
 142
 143
 144 } // end of namespace dai
 145
 146
 147 #endif