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
5 This file is part of libDAI.
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.
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.
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
24 /// \brief Defines class HAK.
25 /// \todo Improve documentation
28 #ifndef __defined_libdai_hak_h
29 #define __defined_libdai_hak_h
33 #include <dai/daialg.h>
34 #include <dai/regiongraph.h>
36 #include <dai/properties.h>
42 /// Approximate inference algorithm: implementation of single-loop ("Generalized Belief Propagation") and double-loop algorithms by Heskes, Albers and Kappen
43 /** \todo Optimize HAK with precalculated indices, similarly to BP.
45 class HAK
: public DAIAlgRG
{
47 std::vector
<Factor
> _Qa
;
48 std::vector
<Factor
> _Qb
;
49 std::vector
<std::vector
<Factor
> > _muab
;
50 std::vector
<std::vector
<Factor
> > _muba
;
51 /// Maximum difference encountered so far
53 /// Number of iterations needed
57 /// Parameters of this inference algorithm
59 /// Enumeration of possible cluster choices
60 DAI_ENUM(ClustersType
,MIN
,DELTA
,LOOP
)
65 /// Maximum number of iterations
74 /// How to choose the clusters
75 ClustersType clusters
;
77 /// Use single-loop (GBP) or double-loop (HAK)
80 /// Depth of loops (only relevant for clusters == ClustersType::LOOP)
84 /// Name of this inference algorithm
85 static const char *Name
;
88 /// Default constructor
89 HAK() : DAIAlgRG(), _Qa(), _Qb(), _muab(), _muba(), _maxdiff(0.0), _iters(0U), props() {}
92 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
) {}
94 /// Assignment operator
95 HAK
& operator=( const HAK
&x
) {
97 DAIAlgRG::operator=( x
);
102 _maxdiff
= x
._maxdiff
;
109 /// Construct from FactorGraph fg and PropertySet opts
110 HAK( const FactorGraph
&fg
, const PropertySet
&opts
);
112 /// Construct from RegionGraph rg and PropertySet opts
113 HAK( const RegionGraph
&rg
, const PropertySet
&opts
);
116 /// @name General InfAlg interface
118 virtual HAK
* clone() const { return new HAK(*this); }
119 virtual HAK
* create() const { return new HAK(); }
120 virtual std::string
identify() const;
121 virtual Factor
belief( const Var
&n
) const;
122 virtual Factor
belief( const VarSet
&ns
) const;
123 virtual std::vector
<Factor
> beliefs() const;
124 virtual Real
logZ() const;
126 virtual void init( const VarSet
&ns
);
127 virtual double run();
128 virtual double maxDiff() const { return _maxdiff
; }
129 virtual size_t Iterations() const { return _iters
; }
133 /// @name Additional interface specific for HAK
135 Factor
& muab( size_t alpha
, size_t _beta
) { return _muab
[alpha
][_beta
]; }
136 Factor
& muba( size_t alpha
, size_t _beta
) { return _muba
[alpha
][_beta
]; }
137 const Factor
& Qa( size_t alpha
) const { return _Qa
[alpha
]; };
138 const Factor
& Qb( size_t beta
) const { return _Qb
[beta
]; };
141 double doDoubleLoop();
145 void constructMessages();
146 void findLoopClusters( const FactorGraph
&fg
, std::set
<VarSet
> &allcl
, VarSet newcl
, const Var
& root
, size_t length
, VarSet vars
);
148 void setProperties( const PropertySet
&opts
);
149 PropertySet
getProperties() const;
150 std::string
printProperties() const;
154 } // end of namespace dai