Updated copyright headers
[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<double> > tJ; // tJ[i][_j] is the tanh of the interaction between spin i and its neighbour nb[i][_j]
43 std::vector<double> theta; // theta[i] is the local field on spin i
44 std::vector<std::vector<double> > 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<double> > > 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<double> Mag;
54
55 double _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 double 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 double run();
102 virtual double maxDiff() const { return _maxdiff; }
103 virtual size_t Iterations() const { return _iters; }
104 //@}
105
106
107 /// @name Additional interface specific for MR
108 //@{
109 //@}
110
111 private:
112 void init(size_t Nin, double *_w, double *_th);
113 void makekindex();
114 void init_cor();
115 double init_cor_resp();
116 void solvemcav();
117 void solveM();
118
119 double _tJ(size_t i, sub_nb A);
120
121 double Omega(size_t i, size_t _j, size_t _l);
122 double T(size_t i, sub_nb A);
123 double T(size_t i, size_t _j);
124 double Gamma(size_t i, size_t _j, size_t _l1, size_t _l2);
125 double Gamma(size_t i, size_t _l1, size_t _l2);
126
127 double appM(size_t i, sub_nb A);
128 void sum_subs(size_t j, sub_nb A, double *sum_even, double *sum_odd);
129
130 double sign(double a) { return (a >= 0) ? 1.0 : -1.0; }
131
132 void setProperties( const PropertySet &opts );
133 PropertySet getProperties() const;
134 std::string printProperties() const;
135 };
136
137
138 } // end of namespace dai
139
140
141 #endif