0633a34477f90b37b15593d6f322a2fade8101d7
[libdai.git] / 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 /// Copy constructor
101 MR( const MR &x ) : DAIAlgFG(x), supported(x.supported), con(x.con), nb(x.nb), tJ(x.tJ), theta(x.theta), M(x.M), kindex(x.kindex), cors(x.cors), N(x.N), Mag(x.Mag), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
102
103 /// Assignment operator
104 MR& operator=( const MR &x ) {
105 if( this != &x ) {
106 DAIAlgFG::operator=(x);
107 supported = x.supported;
108 con = x.con;
109 nb = x.nb;
110 tJ = x.tJ;
111 theta = x.theta;
112 M = x.M;
113 kindex = x.kindex;
114 cors = x.cors;
115 N = x.N;
116 Mag = x.Mag;
117 _maxdiff = x._maxdiff;
118 _iters = x._iters;
119 props = x.props;
120 }
121 return *this;
122 }
123
124 /// Construct from FactorGraph fg and PropertySet opts
125 MR( const FactorGraph &fg, const PropertySet &opts );
126
127
128 /// @name General InfAlg interface
129 //@{
130 virtual MR* clone() const { return new MR(*this); }
131 virtual MR* create() const { return new MR(); }
132 virtual std::string identify() const;
133 virtual Factor belief( const Var &n ) const;
134 virtual Factor belief( const VarSet &/*ns*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
135 virtual std::vector<Factor> beliefs() const;
136 virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
137 virtual void init() {}
138 virtual void init( const VarSet &/*ns*/ ) { DAI_THROW(NOT_IMPLEMENTED); }
139 virtual double run();
140 virtual double maxDiff() const { return _maxdiff; }
141 virtual size_t Iterations() const { return _iters; }
142 //@}
143
144
145 /// @name Additional interface specific for MR
146 //@{
147 //@}
148
149 private:
150 void init(size_t Nin, double *_w, double *_th);
151 void makekindex();
152 void init_cor();
153 double init_cor_resp();
154 void solvemcav();
155 void solveM();
156
157 double _tJ(size_t i, sub_nb A);
158
159 double Omega(size_t i, size_t _j, size_t _l);
160 double T(size_t i, sub_nb A);
161 double T(size_t i, size_t _j);
162 double Gamma(size_t i, size_t _j, size_t _l1, size_t _l2);
163 double Gamma(size_t i, size_t _l1, size_t _l2);
164
165 double appM(size_t i, sub_nb A);
166 void sum_subs(size_t j, sub_nb A, double *sum_even, double *sum_odd);
167
168 double sign(double a) { return (a >= 0) ? 1.0 : -1.0; }
169
170 void setProperties( const PropertySet &opts );
171 PropertySet getProperties() const;
172 std::string printProperties() const;
173 };
174
175
176 } // end of namespace dai
177
178
179 #endif