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