libDAI
bbp.h
Go to the documentation of this file.
1 /* This file is part of libDAI - http://www.libdai.org/
2  *
3  * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4  *
5  * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6  */
7 
8 
12 
13 
14 #ifndef ___defined_libdai_bbp_h
15 #define ___defined_libdai_bbp_h
16 
17 
18 #include <vector>
19 #include <utility>
20 
21 #include <dai/prob.h>
22 #include <dai/daialg.h>
23 #include <dai/factorgraph.h>
24 #include <dai/enum.h>
25 #include <dai/bp_dual.h>
26 
27 
28 namespace dai {
29 
30 
32 
34 DAI_ENUM(BBPCostFunctionBase,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);
35 
36 
38 class BBPCostFunction : public BBPCostFunctionBase {
39  public:
41  BBPCostFunction() : BBPCostFunctionBase() {}
42 
44  BBPCostFunction( const BBPCostFunctionBase &x ) : BBPCostFunctionBase(x) {}
45 
47  bool needGibbsState() const;
48 
50  Real evaluate( const InfAlg &ia, const std::vector<size_t> *stateP ) const;
51 
53  BBPCostFunction& operator=( const BBPCostFunctionBase &x ) {
55  return *this;
56  }
57 };
58 
59 
61 
63 class BBP {
64  private:
66 
67 
70  const FactorGraph *_fg;
72  const InfAlg *_ia;
74 
76 
77 
78  std::vector<Prob> _adj_psi_V;
80  std::vector<Prob> _adj_psi_F;
82  std::vector<std::vector<Prob> > _adj_n;
84  std::vector<std::vector<Prob> > _adj_m;
86  std::vector<Prob> _adj_b_V;
88  std::vector<Prob> _adj_b_F;
90 
92 
93 
94  std::vector<Prob> _init_adj_psi_V;
96  std::vector<Prob> _init_adj_psi_F;
97 
99  std::vector<std::vector<Prob> > _adj_n_unnorm;
101  std::vector<std::vector<Prob> > _adj_m_unnorm;
103  std::vector<std::vector<Prob> > _new_adj_n;
105  std::vector<std::vector<Prob> > _new_adj_m;
107  std::vector<Prob> _adj_b_V_unnorm;
109  std::vector<Prob> _adj_b_F_unnorm;
110 
112  std::vector<std::vector<Prob > > _Tmsg;
114  std::vector<std::vector<Prob > > _Umsg;
116  std::vector<std::vector<std::vector<Prob > > > _Smsg;
118  std::vector<std::vector<std::vector<Prob > > > _Rmsg;
119 
121  size_t _iters;
123 
125 
126 
127  typedef std::vector<size_t> _ind_t;
129  std::vector<std::vector<_ind_t> > _indices;
131 
133  void RegenerateInds();
135  const _ind_t& _index(size_t i, size_t _I) const { return _indices[i][_I]; }
137 
139 
140 
141  void RegenerateT();
143  void RegenerateU();
145  void RegenerateS();
147  void RegenerateR();
149  void RegenerateInputs();
151 
153  void RegeneratePsiAdjoints();
155 
159 
165  void Regenerate();
167 
169 
170 
171  Prob & T(size_t i, size_t _I) { return _Tmsg[i][_I]; }
173  const Prob & T(size_t i, size_t _I) const { return _Tmsg[i][_I]; }
175  Prob & U(size_t I, size_t _i) { return _Umsg[I][_i]; }
177  const Prob & U(size_t I, size_t _i) const { return _Umsg[I][_i]; }
179  Prob & S(size_t i, size_t _I, size_t _j) { return _Smsg[i][_I][_j]; }
181  const Prob & S(size_t i, size_t _I, size_t _j) const { return _Smsg[i][_I][_j]; }
183  Prob & R(size_t I, size_t _i, size_t _J) { return _Rmsg[I][_i][_J]; }
185  const Prob & R(size_t I, size_t _i, size_t _J) const { return _Rmsg[I][_i][_J]; }
186 
188  Prob& adj_n(size_t i, size_t _I) { return _adj_n[i][_I]; }
190  const Prob& adj_n(size_t i, size_t _I) const { return _adj_n[i][_I]; }
192  Prob& adj_m(size_t i, size_t _I) { return _adj_m[i][_I]; }
194  const Prob& adj_m(size_t i, size_t _I) const { return _adj_m[i][_I]; }
196 
198 
199 
200 
203  void calcNewN( size_t i, size_t _I );
205 
208  void calcNewM( size_t i, size_t _I );
210  void calcUnnormMsgN( size_t i, size_t _I );
212  void calcUnnormMsgM( size_t i, size_t _I );
214  void upMsgN( size_t i, size_t _I );
216  void upMsgM( size_t i, size_t _I );
218  void doParUpdate();
220 
222 
223 
224  void incrSeqMsgM( size_t i, size_t _I, const Prob& p );
225  // DISABLED BECAUSE IT IS BUGGY:
226  // void updateSeqMsgM( size_t i, size_t _I );
228  void setSeqMsgM( size_t i, size_t _I, const Prob &p );
230  void sendSeqMsgN( size_t i, size_t _I, const Prob &f );
232  void sendSeqMsgM( size_t i, size_t _I );
234 
236 
238  Prob unnormAdjoint( const Prob &w, Real Z_w, const Prob &adj_w );
239 
241  Real getUnMsgMag();
243  void getMsgMags( Real &s, Real &new_s );
245  void getArgmaxMsgM( size_t &i, size_t &_I, Real &mag );
247  Real getMaxMsgM();
248 
250  Real getTotalMsgM();
254  Real getTotalMsgN();
255 
257  std::vector<Prob> getZeroAdjF( const FactorGraph &fg );
259  std::vector<Prob> getZeroAdjV( const FactorGraph &fg );
260 
261  public:
263 
264 
265 
268  BBP( const InfAlg *ia, const PropertySet &opts ) : _bp_dual(ia), _fg(&(ia->fg())), _ia(ia) {
269  props.set(opts);
270  }
272 
274 
275 
276  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 ) {
277  _adj_b_V = adj_b_V;
278  _adj_b_F = adj_b_F;
281  Regenerate();
282  }
283 
285  void init( const std::vector<Prob> &adj_b_V, const std::vector<Prob> &adj_b_F ) {
286  init( adj_b_V, adj_b_F, getZeroAdjV(*_fg), getZeroAdjF(*_fg) );
287  }
288 
290  void init_V( const std::vector<Prob> &adj_b_V ) {
291  init( adj_b_V, getZeroAdjF(*_fg) );
292  }
293 
295  void init_F( const std::vector<Prob> &adj_b_F ) {
296  init( getZeroAdjV(*_fg), adj_b_F );
297  }
298 
300 
304  void initCostFnAdj( const BBPCostFunction &cfn, const std::vector<size_t> *stateP );
306 
308 
309 
310  void run();
312 
314 
315 
316  Prob& adj_psi_V(size_t i) { return _adj_psi_V[i]; }
318  const Prob& adj_psi_V(size_t i) const { return _adj_psi_V[i]; }
320  Prob& adj_psi_F(size_t I) { return _adj_psi_F[I]; }
322  const Prob& adj_psi_F(size_t I) const { return _adj_psi_F[I]; }
324  Prob& adj_b_V(size_t i) { return _adj_b_V[i]; }
326  const Prob& adj_b_V(size_t i) const { return _adj_b_V[i]; }
328  Prob& adj_b_F(size_t I) { return _adj_b_F[I]; }
330  const Prob& adj_b_F(size_t I) const { return _adj_b_F[I]; }
332  size_t Iterations() { return _iters; }
334 
335  public:
337  /* PROPERTIES(props,BBP) {
345  DAI_ENUM(UpdateType,SEQ_FIX,SEQ_MAX,SEQ_BP_REV,SEQ_BP_FWD,PAR);
346 
348  size_t verbose = 0;
349 
351  size_t maxiter;
352 
355  Real tol;
356 
358  Real damping;
359 
361  UpdateType updates;
362 
363  // DISABLED BECAUSE IT IS BUGGY:
364  // bool clean_updates;
365  }
366  */
367 /* {{{ GENERATED CODE: DO NOT EDIT. Created by
368  ./scripts/regenerate-properties include/dai/bbp.h src/bbp.cpp
369 */
370  struct Properties {
372 
379  DAI_ENUM(UpdateType,SEQ_FIX,SEQ_MAX,SEQ_BP_REV,SEQ_BP_FWD,PAR);
381  size_t verbose;
383  size_t maxiter;
385 
391  UpdateType updates;
392 
394 
397  void set(const PropertySet &opts);
399  PropertySet get() const;
401  std::string toString() const;
402  } props;
403 /* }}} END OF GENERATED CODE */
404 };
405 
406 
408 
416 Real numericBBPTest( const InfAlg &bp, const std::vector<size_t> *state, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real h );
417 
418 
419 } // end of namespace dai
420 
421 
422 #endif