Merge branch 'vaske'
[libdai.git] / include / dai / bp.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 BP
25 /// \todo Improve documentation
26
27
28 #ifndef __defined_libdai_bp_h
29 #define __defined_libdai_bp_h
30
31
32 #include <string>
33 #include <dai/daialg.h>
34 #include <dai/factorgraph.h>
35 #include <dai/properties.h>
36 #include <dai/enum.h>
37
38
39 namespace dai {
40
41
42 /// Approximate inference algorithm "(Loopy) Belief Propagation"
43 class BP : public DAIAlgFG {
44 private:
45 typedef std::vector<size_t> ind_t;
46 typedef std::multimap<double, std::pair<std::size_t, std::size_t> > LutType;
47 struct EdgeProp {
48 ind_t index;
49 Prob message;
50 Prob newMessage;
51 double residual;
52 };
53 std::vector<std::vector<EdgeProp> > _edges;
54 std::vector<std::vector<LutType::iterator> > _edge2lut;
55 LutType _lut;
56 /// Maximum difference encountered so far
57 double _maxdiff;
58 /// Number of iterations needed
59 size_t _iters;
60
61 public:
62 /// Parameters of this inference algorithm
63 struct Properties {
64 /// Enumeration of possible update schedules
65 DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL)
66
67 /// Enumeration of inference variants
68 DAI_ENUM(InfType,SUMPROD,MAXPROD)
69
70 /// Verbosity
71 size_t verbose;
72
73 /// Maximum number of iterations
74 size_t maxiter;
75
76 /// Tolerance
77 double tol;
78
79 /// Do updates in logarithmic domain?
80 bool logdomain;
81
82 /// Damping constant
83 double damping;
84
85 /// Update schedule
86 UpdateType updates;
87
88 /// Type of inference: sum-product or max-product?
89 InfType inference;
90 } props;
91
92 /// Name of this inference algorithm
93 static const char *Name;
94
95 public:
96 /// Default constructor
97 BP() : DAIAlgFG(), _edges(), _edge2lut(), _lut(), _maxdiff(0.0), _iters(0U), props() {}
98
99 /// Copy constructor
100 BP( const BP &x ) : DAIAlgFG(x), _edges(x._edges), _edge2lut(x._edge2lut), _lut(x._lut), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {
101 for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
102 _edge2lut[l->second.first][l->second.second] = l;
103 }
104
105 /// Assignment operator
106 BP& operator=( const BP &x ) {
107 if( this != &x ) {
108 DAIAlgFG::operator=( x );
109 _edges = x._edges;
110 _lut = x._lut;
111 for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
112 _edge2lut[l->second.first][l->second.second] = l;
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 BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), props() {
122 setProperties( opts );
123 construct();
124 }
125
126
127 /// @name General InfAlg interface
128 //@{
129 virtual BP* clone() const { return new BP(*this); }
130 virtual std::string identify() const;
131 virtual Factor belief( const Var &n ) const;
132 virtual Factor belief( const VarSet &ns ) const;
133 virtual std::vector<Factor> beliefs() const;
134 virtual Real logZ() const;
135 virtual void init();
136 virtual void init( const VarSet &ns );
137 virtual double run();
138 virtual double maxDiff() const { return _maxdiff; }
139 virtual size_t Iterations() const { return _iters; }
140 //@}
141
142
143 /// @name Additional interface specific for BP
144 //@{
145 Factor beliefV( size_t i ) const;
146 Factor beliefF( size_t I ) const;
147 //@}
148
149 /// Calculates the joint state of all variables that has maximum probability
150 /** Assumes that run() has been called and that props.inference == MAXPROD
151 */
152 std::vector<std::size_t> findMaximum() const;
153
154 private:
155 const Prob & message(size_t i, size_t _I) const { return _edges[i][_I].message; }
156 Prob & message(size_t i, size_t _I) { return _edges[i][_I].message; }
157 Prob & newMessage(size_t i, size_t _I) { return _edges[i][_I].newMessage; }
158 const Prob & newMessage(size_t i, size_t _I) const { return _edges[i][_I].newMessage; }
159 ind_t & index(size_t i, size_t _I) { return _edges[i][_I].index; }
160 const ind_t & index(size_t i, size_t _I) const { return _edges[i][_I].index; }
161 double & residual(size_t i, size_t _I) { return _edges[i][_I].residual; }
162 const double & residual(size_t i, size_t _I) const { return _edges[i][_I].residual; }
163
164 void calcNewMessage( size_t i, size_t _I );
165 void updateMessage( size_t i, size_t _I );
166 void updateResidual( size_t i, size_t _I, double r );
167 void findMaxResidual( size_t &i, size_t &_I );
168 /// Calculates unnormalized belief of variable
169 void calcBeliefV( size_t i, Prob &p ) const;
170 /// Calculates unnormalized belief of factor
171 void calcBeliefF( size_t I, Prob &p ) const;
172
173 void construct();
174 /// Set Props according to the PropertySet opts, where the values can be stored as std::strings or as the type of the corresponding Props member
175 void setProperties( const PropertySet &opts );
176 PropertySet getProperties() const;
177 std::string printProperties() const;
178 };
179
180
181 } // end of namespace dai
182
183
184 #endif