Extended InfAlg interface with setProperties(), getProperties() and printProperties()
[libdai.git] / 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