include/dai/mr.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     Copyright (C) 2007  Bastian Wemmenhove
   6     Radboud University Nijmegen, The Netherlands
   7
   8     This file is part of libDAI.
   9
  10     libDAI is free software; you can redistribute it and/or modify
  11     it under the terms of the GNU General Public License as published by
  12     the Free Software Foundation; either version 2 of the License, or
  13     (at your option) any later version.
  14
  15     libDAI is distributed in the hope that it will be useful,
  16     but WITHOUT ANY WARRANTY; without even the implied warranty of
  17     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18     GNU General Public License for more details.
  19
  20     You should have received a copy of the GNU General Public License
  21     along with libDAI; if not, write to the Free Software
  22     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  23 */
  24
  25
  26 /// \file
  27 /// \brief Defines class MR
  28 /// \todo Improve documentation
  29
  30
  31 #ifndef __defined_libdai_mr_h
  32 #define __defined_libdai_mr_h
  33
  34
  35 #include <vector>
  36 #include <string>
  37 #include <dai/factorgraph.h>
  38 #include <dai/daialg.h>
  39 #include <dai/enum.h>
  40 #include <dai/properties.h>
  41 #include <dai/exceptions.h>
  42 #include <boost/dynamic_bitset.hpp>
  43
  44
  45 namespace dai {
  46
  47
  48 /// Approximate inference algorithm by Montanari and Rizzo
  49 class MR : public DAIAlgFG {
  50     private:
  51         bool supported;                                            // is the underlying factor graph supported?
  52
  53         std::vector<size_t>                             con;       // con[i] = connectivity of spin i
  54         std::vector<std::vector<size_t> >               nb;        // nb[i] are the neighbours of spin i
  55         std::vector<std::vector<double> >               tJ;        // tJ[i][_j] is the tanh of the interaction between spin i and its neighbour nb[i][_j]
  56         std::vector<double>                             theta;     // theta[i] is the local field on spin i
  57         std::vector<std::vector<double> >               M;         // M[i][_j] is M^{(i)}_j
  58         std::vector<std::vector<size_t> >               kindex;    // the _j'th neighbour of spin i has spin i as its kindex[i][_j]'th neighbour
  59         std::vector<std::vector<std::vector<double> > > cors;
  60
  61         static const size_t kmax = 31;
  62         typedef boost::dynamic_bitset<> sub_nb;
  63
  64         size_t N;
  65
  66         std::vector<double> Mag;
  67
  68         double _maxdiff;
  69         size_t _iters;
  70
  71     public:
  72         /// Parameters of this inference algorithm
  73         struct Properties {
  74             /// Enumeration of different types of update equations
  75             DAI_ENUM(UpdateType,FULL,LINEAR)
  76
  77             /// Enumeration of different ways of initializing the cavity correlations
  78             DAI_ENUM(InitType,RESPPROP,CLAMPING,EXACT)
  79
  80             /// Verbosity
  81             size_t verbose;
  82
  83             /// Tolerance
  84             double tol;
  85
  86             /// Update equations
  87             UpdateType updates;
  88
  89             /// How to initialize the cavity correlations
  90             InitType inits;
  91         } props;
  92
  93         /// Name of this inference method
  94         static const char *Name;
  95
  96     public:
  97         /// Default constructor
  98         MR() : DAIAlgFG(), supported(), con(), nb(), tJ(), theta(), M(), kindex(), cors(), N(), Mag(), _maxdiff(), _iters(), props() {}
  99
 100         /// Construct from FactorGraph fg and PropertySet opts
 101         MR( const FactorGraph &fg, const PropertySet &opts );
 102
 103
 104         /// @name General InfAlg interface
 105         //@{
 106         virtual MR* clone() const { return new MR(*this); }
 107         virtual MR* create() const { return new MR(); }
 108         virtual std::string identify() const;
 109         virtual Factor belief( const Var &n ) const;
 110         virtual Factor belief( const VarSet &/*ns*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
 111         virtual std::vector<Factor> beliefs() const;
 112         virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
 113         virtual void init() {}
 114         virtual void init( const VarSet &/*ns*/ ) { DAI_THROW(NOT_IMPLEMENTED); }
 115         virtual double run();
 116         virtual double maxDiff() const { return _maxdiff; }
 117         virtual size_t Iterations() const { return _iters; }
 118         //@}
 119
 120
 121         /// @name Additional interface specific for MR
 122         //@{
 123         //@}
 124
 125     private:
 126         void init(size_t Nin, double *_w, double *_th);
 127         void makekindex();
 128         void init_cor();
 129         double init_cor_resp();
 130         void solvemcav();
 131         void solveM();
 132
 133         double _tJ(size_t i, sub_nb A);
 134
 135         double Omega(size_t i, size_t _j, size_t _l);
 136         double T(size_t i, sub_nb A);
 137         double T(size_t i, size_t _j);
 138         double Gamma(size_t i, size_t _j, size_t _l1, size_t _l2);
 139         double Gamma(size_t i, size_t _l1, size_t _l2);
 140
 141         double appM(size_t i, sub_nb A);
 142         void sum_subs(size_t j, sub_nb A, double *sum_even, double *sum_odd);
 143
 144         double sign(double a) { return (a >= 0) ? 1.0 : -1.0; }
 145
 146         void setProperties( const PropertySet &opts );
 147         PropertySet getProperties() const;
 148         std::string printProperties() const;
 149 };
 150
 151
 152 } // end of namespace dai
 153
 154
 155 #endif