Removed DAI_ACCMUT macro and improved documentation of include/dai/util.h
[libdai.git] / include / dai / bbp.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) 2009 Frederik Eaton [frederik at ofb dot net]
8 */
9
10
11 /// \file
12 /// \brief Defines class BBP [\ref EaG09]
13 /// \todo Improve documentation
14
15
16 #ifndef ___defined_libdai_bbp_h
17 #define ___defined_libdai_bbp_h
18
19
20 #include <vector>
21 #include <utility>
22
23 #include <dai/prob.h>
24 #include <dai/daialg.h>
25 #include <dai/factorgraph.h>
26 #include <dai/enum.h>
27 #include <dai/bp_dual.h>
28
29
30 namespace dai {
31
32
33 /// Computes the adjoint of the unnormed probability vector from the normalizer and the adjoint of the normalized probability vector @see eqn. (13) in [\ref EaG09]
34 Prob unnormAdjoint( const Prob &w, Real Z_w, const Prob &adj_w );
35
36 /// Runs Gibbs sampling for \a iters iterations on ia.fg(), and returns state
37 std::vector<size_t> getGibbsState( const InfAlg &ia, size_t iters );
38
39
40 /// Implements BBP (Back-Belief-Propagation) [\ref EaG09]
41 class BBP {
42 protected:
43 /// @name Inputs
44 //@{
45 BP_dual _bp_dual;
46 const FactorGraph *_fg;
47 const InfAlg *_ia;
48 //@}
49
50 /// Number of iterations done
51 size_t _iters;
52
53 /// @name Outputs
54 //@{
55 /// Variable factor adjoints
56 std::vector<Prob> _adj_psi_V;
57 /// Factor adjoints
58 std::vector<Prob> _adj_psi_F;
59 /// Variable->factor message adjoints (indexed [i][_I])
60 std::vector<std::vector<Prob> > _adj_n;
61 /// Factor->variable message adjoints (indexed [i][_I])
62 std::vector<std::vector<Prob> > _adj_m;
63 /// Normalized variable belief adjoints
64 std::vector<Prob> _adj_b_V;
65 /// Normalized factor belief adjoints
66 std::vector<Prob> _adj_b_F;
67 //@}
68
69 /// @name Helper quantities computed from the BP messages
70 //@{
71 /// _T[i][_I] (see eqn. (41) in [\ref EaG09])
72 std::vector<std::vector<Prob > > _T;
73 /// _U[I][_i] (see eqn. (42) in [\ref EaG09])
74 std::vector<std::vector<Prob > > _U;
75 /// _S[i][_I][_j] (see eqn. (43) in [\ref EaG09])
76 std::vector<std::vector<std::vector<Prob > > > _S;
77 /// _R[I][_i][_J] (see eqn. (44) in [\ref EaG09])
78 std::vector<std::vector<std::vector<Prob > > > _R;
79 //@}
80
81 /// Unnormalized variable belief adjoints
82 std::vector<Prob> _adj_b_V_unnorm;
83 /// Unnormalized factor belief adjoints
84 std::vector<Prob> _adj_b_F_unnorm;
85
86 /// Initial variable factor adjoints
87 std::vector<Prob> _init_adj_psi_V;
88 /// Initial factor adjoints
89 std::vector<Prob> _init_adj_psi_F;
90
91 /// Unnormalized variable->factor message adjoint (indexed [i][_I])
92 std::vector<std::vector<Prob> > _adj_n_unnorm;
93 /// Unnormalized factor->variable message adjoint (indexed [i][_I])
94 std::vector<std::vector<Prob> > _adj_m_unnorm;
95 /// Updated normalized variable->factor message adjoint (indexed [i][_I])
96 std::vector<std::vector<Prob> > _new_adj_n;
97 /// Updated normalized factor->variable message adjoint (indexed [i][_I])
98 std::vector<std::vector<Prob> > _new_adj_m;
99
100 /// @name Optimized indexing (for performance)
101 //@{
102 /// Calculates _indices, which is a cache of IndexFor @see bp.cpp
103 void RegenerateInds();
104
105 /// Index type
106 typedef std::vector<size_t> _ind_t;
107 /// Cached indices (indexed [i][_I])
108 std::vector<std::vector<_ind_t> > _indices;
109 /// Returns an index from the cache
110 const _ind_t& _index(size_t i, size_t _I) const { return _indices[i][_I]; }
111 //@}
112
113 /// @name Initialization
114 //@{
115 /// Calculate T values; see eqn. (41) in [\ref EaG09]
116 void RegenerateT();
117 /// Calculate U values; see eqn. (42) in [\ref EaG09]
118 void RegenerateU();
119 /// Calculate S values; see eqn. (43) in [\ref EaG09]
120 void RegenerateS();
121 /// Calculate R values; see eqn. (44) in [\ref EaG09]
122 void RegenerateR();
123 /// Calculate _adj_b_V_unnorm and _adj_b_F_unnorm from _adj_b_V and _adj_b_F
124 void RegenerateInputs();
125 /// Initialise members for factor adjoints (call after RegenerateInputs)
126 void RegeneratePsiAdjoints();
127 /// Initialise members for message adjoints (call after RegenerateInputs) for parallel algorithm
128 void RegenerateParMessageAdjoints();
129 /// Initialise members for message adjoints (call after RegenerateInputs) for sequential algorithm
130 /** Same as RegenerateMessageAdjoints, but calls sendSeqMsgN rather
131 * than updating _adj_n (and friends) which are unused in the sequential algorithm.
132 */
133 void RegenerateSeqMessageAdjoints();
134 //@}
135
136 /// Returns reference to T value; see eqn. (41) in [\ref EaG09]
137 Prob & T(size_t i, size_t _I) { return _T[i][_I]; }
138 /// Returns constant reference to T value; see eqn. (41) in [\ref EaG09]
139 const Prob & T(size_t i, size_t _I) const { return _T[i][_I]; }
140 /// Returns reference to U value; see eqn. (42) in [\ref EaG09]
141 Prob & U(size_t I, size_t _i) { return _U[I][_i]; }
142 /// Returns constant reference to U value; see eqn. (42) in [\ref EaG09]
143 const Prob & U(size_t I, size_t _i) const { return _U[I][_i]; }
144 /// Returns reference to S value; see eqn. (43) in [\ref EaG09]
145 Prob & S(size_t i, size_t _I, size_t _j) { return _S[i][_I][_j]; }
146 /// Returns constant reference to S value; see eqn. (43) in [\ref EaG09]
147 const Prob & S(size_t i, size_t _I, size_t _j) const { return _S[i][_I][_j]; }
148 /// Returns reference to R value; see eqn. (44) in [\ref EaG09]
149 Prob & R(size_t I, size_t _i, size_t _J) { return _R[I][_i][_J]; }
150 /// Returns constant reference to R value; see eqn. (44) in [\ref EaG09]
151 const Prob & R(size_t I, size_t _i, size_t _J) const { return _R[I][_i][_J]; }
152
153 /// @name Parallel algorithm
154 //@{
155 /// Calculates new variable->factor message adjoint
156 /** Increases variable factor adjoint according to eqn. (27) in [\ref EaG09] and
157 * calculates the new variable->factor message adjoint according to eqn. (29) in [\ref EaG09].
158 */
159 void calcNewN( size_t i, size_t _I );
160 /// Calculates new factor->variable message adjoint
161 /** Increases factor adjoint according to eqn. (28) in [\ref EaG09] and
162 * calculates the new factor->variable message adjoint according to the r.h.s. of eqn. (30) in [\ref EaG09].
163 */
164 void calcNewM( size_t i, size_t _I );
165 /// Calculates unnormalized variable->factor message adjoint from the normalized one
166 void calcUnnormMsgN( size_t i, size_t _I );
167 /// Calculates unnormalized factor->variable message adjoint from the normalized one
168 void calcUnnormMsgM( size_t i, size_t _I );
169 /// Updates (un)normalized variable->factor message adjoints
170 void upMsgN( size_t i, size_t _I );
171 /// Updates (un)normalized factor->variable message adjoints
172 void upMsgM( size_t i, size_t _I );
173 /// Do one parallel update of all message adjoints
174 void doParUpdate();
175 //@}
176
177 /// @name Sequential algorithm
178 //@{
179 /// Helper function for sendSeqMsgM: increases factor->variable message adjoint by p and calculates the corresponding unnormalized adjoint
180 void incrSeqMsgM( size_t i, size_t _I, const Prob& p );
181 // DISABLED BECAUSE IT IS BUGGY:
182 // void updateSeqMsgM( size_t i, size_t _I );
183 /// Sets normalized factor->variable message adjoint and calculates the corresponding unnormalized adjoint
184 void setSeqMsgM( size_t i, size_t _I, const Prob &p );
185 /// Implements routine Send-n in Figure 5 in [\ref EaG09]
186 void sendSeqMsgN( size_t i, size_t _I, const Prob &f );
187 /// Implements routine Send-m in Figure 5 in [\ref EaG09]
188 void sendSeqMsgM( size_t i, size_t _I );
189 //@}
190
191 /// Calculates averaged L-1 norm of unnormalized message adjoints
192 Real getUnMsgMag();
193 /// Calculates averaged L-1 norms of current and new normalized message adjoints
194 void getMsgMags( Real &s, Real &new_s );
195
196 /// Sets all vectors _adj_b_F to zero
197 void zero_adj_b_F() {
198 _adj_b_F.clear();
199 _adj_b_F.reserve( _fg->nrFactors() );
200 for( size_t I = 0; I < _fg->nrFactors(); I++ )
201 _adj_b_F.push_back( Prob( _fg->factor(I).states(), Real( 0.0 ) ) );
202 }
203
204 /// Returns indices and magnitude of the largest normalized factor->variable message adjoint
205 void getArgmaxMsgM( size_t &i, size_t &_I, Real &mag );
206 /// Returns magnitude of the largest (in L1-norm) normalized factor->variable message adjoint
207 Real getMaxMsgM();
208 /// Calculates sum of L1 norms of all normalized factor->variable message adjoints
209 Real getTotalMsgM();
210 /// Calculates sum of L1 norms of all updated normalized factor->variable message adjoints
211 Real getTotalNewMsgM();
212 /// Calculates sum of L1 norms of all normalized variable->factor message adjoints
213 Real getTotalMsgN();
214
215 public:
216 /// Called by \a init, recalculates intermediate values
217 void Regenerate();
218
219 /// Constructor
220 BBP( const InfAlg *ia, const PropertySet &opts ) : _bp_dual(ia), _fg(&(ia->fg())), _ia(ia) {
221 props.set(opts);
222 }
223
224 /// Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the factors in the factor graph fg
225 std::vector<Prob> getZeroAdjF( const FactorGraph &fg );
226 /// Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the variables in the factor graph fg
227 std::vector<Prob> getZeroAdjV( const FactorGraph &fg );
228
229 /// Initializes belief adjoints and initial factor adjoints and regenerates
230 void init( const std::vector<Prob> &adj_b_V, const std::vector<Prob> &adj_b_F, const std::vector<Prob> &adj_psi_V, const std::vector<Prob> &adj_psi_F ) {
231 _adj_b_V = adj_b_V;
232 _adj_b_F = adj_b_F;
233 _init_adj_psi_V = adj_psi_V;
234 _init_adj_psi_F = adj_psi_F;
235 Regenerate();
236 }
237
238 /// Initializes belief adjoints and with zero initial factor adjoints and regenerates
239 void init( const std::vector<Prob> &adj_b_V, const std::vector<Prob> &adj_b_F ) {
240 init( adj_b_V, adj_b_F, getZeroAdjV(*_fg), getZeroAdjF(*_fg) );
241 }
242
243 /// Initializes variable belief adjoints (and sets factor belief adjoints to zero) and with zero initial factor adjoints and regenerates
244 void init( const std::vector<Prob> &adj_b_V ) {
245 init(adj_b_V, getZeroAdjF(*_fg));
246 }
247
248 /// Run until change is less than given tolerance
249 void run();
250
251 /// Return number of iterations done so far
252 size_t doneIters() { return _iters; }
253
254 /// Returns reference to variable factor adjoint
255 Prob& adj_psi_V(size_t i) { return _adj_psi_V[i]; }
256 /// Returns constant reference to variable factor adjoint
257 const Prob& adj_psi_V(size_t i) const { return _adj_psi_V[i]; }
258 /// Returns reference to factor adjoint
259 Prob& adj_psi_F(size_t I) { return _adj_psi_F[I]; }
260 /// Returns constant reference to factor adjoint
261 const Prob& adj_psi_F(size_t I) const { return _adj_psi_F[I]; }
262 /// Returns reference to variable belief adjoint
263 Prob& adj_b_V(size_t i) { return _adj_b_V[i]; }
264 /// Returns constant reference to variable belief adjoint
265 const Prob& adj_b_V(size_t i) const { return _adj_b_V[i]; }
266 /// Returns reference to factor belief adjoint
267 Prob& adj_b_F(size_t I) { return _adj_b_F[I]; }
268 /// Returns constant reference to factor belief adjoint
269 const Prob& adj_b_F(size_t I) const { return _adj_b_F[I]; }
270
271 protected:
272 /// Returns reference to variable->factor message adjoint
273 Prob& adj_n(size_t i, size_t _I) { return _adj_n[i][_I]; }
274 /// Returns constant reference to variable->factor message adjoint
275 const Prob& adj_n(size_t i, size_t _I) const { return _adj_n[i][_I]; }
276 /// Returns reference to factor->variable message adjoint
277 Prob& adj_m(size_t i, size_t _I) { return _adj_m[i][_I]; }
278 /// Returns constant reference to factor->variable message adjoint
279 const Prob& adj_m(size_t i, size_t _I) const { return _adj_m[i][_I]; }
280
281 public:
282 /// Parameters of this algorithm
283 /* PROPERTIES(props,BBP) {
284 /// Enumeration of possible update schedules
285 DAI_ENUM(UpdateType,SEQ_FIX,SEQ_MAX,SEQ_BP_REV,SEQ_BP_FWD,PAR);
286
287 /// Verbosity
288 size_t verbose;
289
290 /// Maximum number of iterations
291 size_t maxiter;
292
293 /// Tolerance (not used for updates = SEQ_BP_REV, SEQ_BP_FWD)
294 Real tol;
295
296 /// Damping constant (0 for none); damping = 1 - lambda where lambda is the damping constant used in [\ref EaG09]
297 Real damping;
298
299 /// Update schedule
300 UpdateType updates;
301
302 // DISABLED BECAUSE IT IS BUGGY:
303 // bool clean_updates;
304 }
305 */
306 /* {{{ GENERATED CODE: DO NOT EDIT. Created by
307 ./scripts/regenerate-properties include/dai/bbp.h src/bbp.cpp
308 */
309 struct Properties {
310 /// Enumeration of possible update schedules
311 DAI_ENUM(UpdateType,SEQ_FIX,SEQ_MAX,SEQ_BP_REV,SEQ_BP_FWD,PAR);
312 /// Verbosity
313 size_t verbose;
314 /// Maximum number of iterations
315 size_t maxiter;
316 /// Tolerance (not used for updates = SEQ_BP_REV, SEQ_BP_FWD)
317 Real tol;
318 /// Damping constant (0 for none); damping = 1 - lambda where lambda is the damping constant used in [\ref EaG09]
319 Real damping;
320 /// Update schedule
321 UpdateType updates;
322
323 /// Set members from PropertySet
324 void set(const PropertySet &opts);
325 /// Get members into PropertySet
326 PropertySet get() const;
327 /// Convert to a string which can be parsed as a PropertySet
328 std::string toString() const;
329 } props;
330 /* }}} END OF GENERATED CODE */
331 };
332
333
334 /// Enumeration of several cost functions that can be used with BBP.
335 DAI_ENUM(bbp_cfn_t,CFN_GIBBS_B,CFN_GIBBS_B2,CFN_GIBBS_EXP,CFN_GIBBS_B_FACTOR,CFN_GIBBS_B2_FACTOR,CFN_GIBBS_EXP_FACTOR,CFN_VAR_ENT,CFN_FACTOR_ENT,CFN_BETHE_ENT);
336
337 /// Initialise BBP using InfAlg, cost function, and stateP
338 /** Calls bbp.init with adjoints calculated from ia.beliefV and
339 * ia.beliefF. stateP is a Gibbs state and can be NULL, it will be
340 * initialised using a Gibbs run of 2*fg.Iterations() iterations.
341 */
342 void initBBPCostFnAdj( BBP &bbp, const InfAlg &ia, bbp_cfn_t cfn_type, const std::vector<size_t> *stateP );
343
344 /// Answers question: does the given cost function depend on having a Gibbs state?
345 bool needGibbsState( bbp_cfn_t cfn );
346
347 /// Calculate actual value of cost function (cfn_type, stateP)
348 /** This function returns the actual value of the cost function whose
349 * gradient with respect to singleton beliefs is given by
350 * gibbsToB1Adj on the same arguments
351 */
352 Real getCostFn( const InfAlg &fg, bbp_cfn_t cfn_type, const std::vector<size_t> *stateP );
353
354 /// Function to test the validity of adjoints computed by BBP given a state for each variable using numerical derivatives.
355 /** Factors containing a variable are multiplied by psi_1 adjustments to verify accuracy of _adj_psi_V.
356 * \param bp BP object.
357 * \param state Global state of all variables.
358 * \param bbp_props BBP Properties.
359 * \param cfn Cost function to be used.
360 * \param h controls size of perturbation.
361 */
362 Real numericBBPTest( const InfAlg &bp, const std::vector<size_t> *state, const PropertySet &bbp_props, bbp_cfn_t cfn, Real h );
363
364
365 } // end of namespace dai
366
367
368 #endif