a21ea7cfcfed4d19c43b17061c14cbaee7473365
[libdai.git] / include / dai / hak.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 HAK.
25
26
27 #ifndef __defined_libdai_hak_h
28 #define __defined_libdai_hak_h
29
30
31 #include <string>
32 #include <dai/daialg.h>
33 #include <dai/regiongraph.h>
34 #include <dai/enum.h>
35 #include <dai/properties.h>
36
37
38 namespace dai {
39
40
41 /// Approximate inference algorithm: implementation of single-loop ("Generalized Belief Propagation") and double-loop algorithms by Heskes, Albers and Kappen
42 class HAK : public DAIAlgRG {
43 private:
44 std::vector<Factor> _Qa;
45 std::vector<Factor> _Qb;
46 std::vector<std::vector<Factor> > _muab;
47 std::vector<std::vector<Factor> > _muba;
48 /// Maximum difference encountered so far
49 double _maxdiff;
50 /// Number of iterations needed
51 size_t _iters;
52
53 public:
54 /// Parameters of this inference algorithm
55 struct Properties {
56 /// Enumeration of possible cluster choices
57 DAI_ENUM(ClustersType,MIN,DELTA,LOOP)
58
59 /// Verbosity
60 size_t verbose;
61
62 /// Maximum number of iterations
63 size_t maxiter;
64
65 /// Tolerance
66 double tol;
67
68 /// Damping constant
69 double damping;
70
71 /// How to choose the clusters
72 ClustersType clusters;
73
74 /// Use single-loop (GBP) or double-loop (HAK)
75 bool doubleloop;
76
77 /// Depth of loops (only relevant for clusters == ClustersType::LOOP)
78 size_t loopdepth;
79 } props;
80
81 /// Name of this inference algorithm
82 static const char *Name;
83
84 public:
85 /// Default constructor
86 HAK() : DAIAlgRG(), _Qa(), _Qb(), _muab(), _muba(), _maxdiff(0.0), _iters(0U), props() {}
87
88 /// Copy constructor
89 HAK( const HAK &x ) : DAIAlgRG(x), _Qa(x._Qa), _Qb(x._Qb), _muab(x._muab), _muba(x._muba), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
90
91 /// Assignment operator
92 HAK& operator=( const HAK &x ) {
93 if( this != &x ) {
94 DAIAlgRG::operator=( x );
95 _Qa = x._Qa;
96 _Qb = x._Qb;
97 _muab = x._muab;
98 _muba = x._muba;
99 _maxdiff = x._maxdiff;
100 _iters = x._iters;
101 props = x.props;
102 }
103 return *this;
104 }
105
106 /// Construct from FactorGraph fg and PropertySet opts
107 HAK( const FactorGraph &fg, const PropertySet &opts );
108
109 /// Construct from RegionGraph rg and PropertySet opts
110 HAK( const RegionGraph &rg, const PropertySet &opts );
111
112
113 /// @name General InfAlg interface
114 //@{
115 virtual HAK* clone() const { return new HAK(*this); }
116 virtual HAK* create() const { return new HAK(); }
117 virtual std::string identify() const;
118 virtual Factor belief( const Var &n ) const;
119 virtual Factor belief( const VarSet &ns ) const;
120 virtual std::vector<Factor> beliefs() const;
121 virtual Real logZ() const;
122 virtual void init();
123 virtual void init( const VarSet &ns );
124 virtual double run();
125 virtual double maxDiff() const { return _maxdiff; }
126 virtual size_t Iterations() const { return _iters; }
127 //@}
128
129
130 /// @name Additional interface specific for HAK
131 //@{
132 Factor & muab( size_t alpha, size_t _beta ) { return _muab[alpha][_beta]; }
133 Factor & muba( size_t alpha, size_t _beta ) { return _muba[alpha][_beta]; }
134 const Factor& Qa( size_t alpha ) const { return _Qa[alpha]; };
135 const Factor& Qb( size_t beta ) const { return _Qb[beta]; };
136
137 double doGBP();
138 double doDoubleLoop();
139 //@}
140
141 private:
142 void constructMessages();
143 void findLoopClusters( const FactorGraph &fg, std::set<VarSet> &allcl, VarSet newcl, const Var & root, size_t length, VarSet vars );
144
145 void setProperties( const PropertySet &opts );
146 PropertySet getProperties() const;
147 std::string printProperties() const;
148 };
149
150
151 } // end of namespace dai
152
153
154 #endif