1 /* This file is part of libDAI - http://www.libdai.org/
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.
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
14 /// \brief Defines class MR
15 /// \todo Improve documentation
18 #ifndef __defined_libdai_mr_h
19 #define __defined_libdai_mr_h
24 #include <dai/factorgraph.h>
25 #include <dai/daialg.h>
27 #include <dai/properties.h>
28 #include <dai/exceptions.h>
29 #include <boost/dynamic_bitset.hpp>
35 /// Approximate inference algorithm by Montanari and Rizzo
36 class MR
: public DAIAlgFG
{
38 bool supported
; // is the underlying factor graph supported?
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
;
48 static const size_t kmax
= 31;
49 typedef boost::dynamic_bitset
<> sub_nb
;
53 std::vector
<Real
> Mag
;
59 /// Parameters of this inference algorithm
61 /// Enumeration of different types of update equations
62 DAI_ENUM(UpdateType
,FULL
,LINEAR
);
64 /// Enumeration of different ways of initializing the cavity correlations
65 DAI_ENUM(InitType
,RESPPROP
,CLAMPING
,EXACT
);
76 /// How to initialize the cavity correlations
80 /// Name of this inference method
81 static const char *Name
;
84 /// Default constructor
85 MR() : DAIAlgFG(), supported(), con(), nb(), tJ(), theta(), M(), kindex(), cors(), N(), Mag(), _maxdiff(), _iters(), props() {}
87 /// Construct from FactorGraph fg and PropertySet opts
88 MR( const FactorGraph
&fg
, const PropertySet
&opts
);
91 /// \name General InfAlg interface
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
); }
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;
110 void init(size_t Nin
, Real
*_w
, Real
*_th
);
113 Real
init_cor_resp();
117 Real
_tJ(size_t i
, sub_nb A
);
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
);
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
);
128 Real
sign(Real a
) { return (a
>= 0) ? 1.0 : -1.0; }
132 } // end of namespace dai