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