include/dai/bp_dual.h

   1 /*  Copyright (C) 2009  Frederik Eaton [frederik at ofb dot net]
   2
   3     This file is part of libDAI.
   4
   5     libDAI is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     libDAI is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with libDAI; if not, write to the Free Software
  17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18 */
  19
  20
  21 /// \file
  22 /// \brief Defines class BP_dual
  23 /// \todo This replicates a large part of the functionality of BP; would it not be shorter to adapt BP instead?
  24
  25
  26 #ifndef __defined_libdai_bp_dual_h
  27 #define __defined_libdai_bp_dual_h
  28
  29
  30 #include <dai/daialg.h>
  31 #include <dai/factorgraph.h>
  32 #include <dai/enum.h>
  33
  34
  35 namespace dai {
  36
  37
  38 /// Calculates both types of BP messages and their normalizers from an InfAlg.
  39 /** BP_dual calculates "dual" versions of BP messages (both messages from factors
  40  *  to variables and messages from variables to factors), and normalizers, given an InfAlg.
  41  *  These are computed from the variable and factor beliefs of the InfAlg.
  42  *  This class is used primarily by BBP.
  43  */
  44 class BP_dual {
  45
  46     protected:
  47         /// Convenience label for storing edge properties
  48         template<class T>
  49         struct _edges_t : public std::vector<std::vector<T> > {};
  50
  51         /// Groups together the data structures for storing the two types of messages and their normalizers
  52         struct messages {
  53             /// Unnormalized variable->factor messages
  54             _edges_t<Prob> n;
  55             /// Normalizers of variable->factor messages
  56             _edges_t<Real> Zn;
  57             /// Unnormalized Factor->variable messages
  58             _edges_t<Prob> m;
  59             /// Normalizers of factor->variable messages
  60             _edges_t<Real> Zm;
  61         };
  62         /// Stores all messages
  63         messages _msgs;
  64
  65         /// Groups together the data structures for storing the two types of beliefs and their normalizers
  66         struct beliefs {
  67             /// Unnormalized variable beliefs
  68             std::vector<Prob> b1;
  69             /// Normalizers of variable beliefs
  70             std::vector<Real> Zb1;
  71             /// Unnormalized factor beliefs
  72             std::vector<Prob> b2;
  73             /// Normalizers of factor beliefs
  74             std::vector<Real> Zb2;
  75         };
  76         /// Stores all beliefs
  77         beliefs _beliefs;
  78
  79         /// Pointer to the InfAlg object
  80         const InfAlg *_ia;
  81
  82         /// Does all necessary preprocessing
  83         void init();
  84         /// Allocates space for _msgs
  85         void regenerateMessages();
  86         /// Allocates space for _beliefs
  87         void regenerateBeliefs();
  88
  89         /// Calculate all messages from InfAlg beliefs
  90         void calcMessages();
  91         /// Update factor->variable message (i->I)
  92         void calcNewM(size_t i, size_t _I);
  93         /// Update variable->factor message (I->i)
  94         void calcNewN(size_t i, size_t _I);
  95
  96         /// Calculate all variable and factor beliefs from messages
  97         void calcBeliefs();
  98         /// Calculate variable belief
  99         void calcBeliefV(size_t i);
 100         /// Calculate factor belief
 101         void calcBeliefF(size_t I);
 102
 103     public:
 104         /// Construct BP_dual object from (converged) InfAlg object's beliefs and factors.
 105         /*  A pointer to the the InfAlg object is stored,
 106          *  so the object must not be destroyed before the BP_dual is destroyed.
 107          */
 108         BP_dual( const InfAlg *ia ) : _ia(ia) { init(); }
 109
 110         /// Returns the underlying FactorGraph
 111         const FactorGraph& fg() const { return _ia->fg(); }
 112
 113         /// Returns factor -> var message (I->i)
 114         DAI_ACCMUT(Prob & msgM( size_t i, size_t _I ), { return _msgs.m[i][_I]; });
 115         /// Returns var -> factor message (i->I)
 116         DAI_ACCMUT(Prob & msgN( size_t i, size_t _I ), { return _msgs.n[i][_I]; });
 117         /// Returns normalizer for msgM
 118         DAI_ACCMUT(Real & zM( size_t i, size_t _I ), { return _msgs.Zm[i][_I]; });
 119         /// Returns normalizer for msgN
 120         DAI_ACCMUT(Real & zN( size_t i, size_t _I ), { return _msgs.Zn[i][_I]; });
 121
 122         /// Returns variable belief
 123         Factor beliefV( size_t i ) const { return Factor( _ia->fg().var(i), _beliefs.b1[i] ); }
 124         /// Returns factor belief
 125         Factor beliefF( size_t I ) const { return Factor( _ia->fg().factor(I).vars(), _beliefs.b2[I] ); }
 126
 127         /// Returns normalizer for variable belief
 128         Real beliefVZ( size_t i ) const { return _beliefs.Zb1[i]; }
 129         /// Returns normalizer for factor belief
 130         Real beliefFZ( size_t I ) const { return _beliefs.Zb2[I]; }
 131 };
 132
 133
 134 } // end of namespace dai
 135
 136
 137 #endif