include/dai/mr.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) 2007       Bastian Wemmenhove
   8  *  Copyright (C) 2007-2009  Joris Mooij         [joris dot mooij at libdai dot org]
   9  *  Copyright (C) 2007       Radboud University Nijmegen, The Netherlands
  10  */
  11
  12
  13 /// \file
  14 /// \brief Defines class MR
  15 /// \todo Improve documentation
  16
  17
  18 #ifndef __defined_libdai_mr_h
  19 #define __defined_libdai_mr_h
  20
  21
  22 #include <vector>
  23 #include <string>
  24 #include <dai/factorgraph.h>
  25 #include <dai/daialg.h>
  26 #include <dai/enum.h>
  27 #include <dai/properties.h>
  28 #include <dai/exceptions.h>
  29 #include <boost/dynamic_bitset.hpp>
  30
  31
  32 namespace dai {
  33
  34
  35 /// Approximate inference algorithm by Montanari and Rizzo
  36 class MR : public DAIAlgFG {
  37     private:
  38         bool supported;                                            // is the underlying factor graph supported?
  39
  40         std::vector<size_t>                             con;       // con[i] = connectivity of spin i
  41         std::vector<std::vector<size_t> >               nb;        // nb[i] are the neighbours of spin i
  42         std::vector<std::vector<Real> >                 tJ;        // tJ[i][_j] is the tanh of the interaction between spin i and its neighbour nb[i][_j]
  43         std::vector<Real>                               theta;     // theta[i] is the local field on spin i
  44         std::vector<std::vector<Real> >                 M;         // M[i][_j] is M^{(i)}_j
  45         std::vector<std::vector<size_t> >               kindex;    // the _j'th neighbour of spin i has spin i as its kindex[i][_j]'th neighbour
  46         std::vector<std::vector<std::vector<Real> > >   cors;
  47
  48         static const size_t kmax = 31;
  49         typedef boost::dynamic_bitset<> sub_nb;
  50
  51         size_t N;
  52
  53         std::vector<Real> Mag;
  54
  55         Real _maxdiff;
  56         size_t _iters;
  57
  58     public:
  59         /// Parameters of this inference algorithm
  60         struct Properties {
  61             /// Enumeration of different types of update equations
  62             DAI_ENUM(UpdateType,FULL,LINEAR);
  63
  64             /// Enumeration of different ways of initializing the cavity correlations
  65             DAI_ENUM(InitType,RESPPROP,CLAMPING,EXACT);
  66
  67             /// Verbosity
  68             size_t verbose;
  69
  70             /// Tolerance
  71             Real tol;
  72
  73             /// Update equations
  74             UpdateType updates;
  75
  76             /// How to initialize the cavity correlations
  77             InitType inits;
  78         } props;
  79
  80         /// Name of this inference method
  81         static const char *Name;
  82
  83     public:
  84         /// Default constructor
  85         MR() : DAIAlgFG(), supported(), con(), nb(), tJ(), theta(), M(), kindex(), cors(), N(), Mag(), _maxdiff(), _iters(), props() {}
  86
  87         /// Construct from FactorGraph fg and PropertySet opts
  88         MR( const FactorGraph &fg, const PropertySet &opts );
  89
  90
  91     /// \name General InfAlg interface
  92     //@{
  93         virtual MR* clone() const { return new MR(*this); }
  94         virtual std::string identify() const;
  95         virtual Factor belief( const Var &n ) const;
  96         virtual Factor belief( const VarSet &/*ns*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
  97         virtual std::vector<Factor> beliefs() const;
  98         virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
  99         virtual void init() {}
 100         virtual void init( const VarSet &/*ns*/ ) { DAI_THROW(NOT_IMPLEMENTED); }
 101         virtual Real run();
 102         virtual Real maxDiff() const { return _maxdiff; }
 103         virtual size_t Iterations() const { return _iters; }
 104         virtual void setProperties( const PropertySet &opts );
 105         virtual PropertySet getProperties() const;
 106         virtual std::string printProperties() const;
 107     //@}
 108
 109     private:
 110         void init(size_t Nin, Real *_w, Real *_th);
 111         void makekindex();
 112         void init_cor();
 113         Real init_cor_resp();
 114         void solvemcav();
 115         void solveM();
 116
 117         Real _tJ(size_t i, sub_nb A);
 118
 119         Real Omega(size_t i, size_t _j, size_t _l);
 120         Real T(size_t i, sub_nb A);
 121         Real T(size_t i, size_t _j);
 122         Real Gamma(size_t i, size_t _j, size_t _l1, size_t _l2);
 123         Real Gamma(size_t i, size_t _l1, size_t _l2);
 124
 125         Real appM(size_t i, sub_nb A);
 126         void sum_subs(size_t j, sub_nb A, Real *sum_even, Real *sum_odd);
 127
 128         Real sign(Real a) { return (a >= 0) ? 1.0 : -1.0; }
 129 };
 130
 131
 132 } // end of namespace dai
 133
 134
 135 #endif