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