include/dai/daialg.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) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 /// \file
  13 /// \brief Defines abstract base class InfAlg, its descendants DAIAlg<>, the specializations DAIAlgFG and DAIAlgRG and some generic inference methods.
  14 /// \todo Improve documentation
  15
  16
  17 #ifndef __defined_libdai_daialg_h
  18 #define __defined_libdai_daialg_h
  19
  20
  21 #include <string>
  22 #include <iostream>
  23 #include <vector>
  24 #include <dai/factorgraph.h>
  25 #include <dai/regiongraph.h>
  26
  27
  28 namespace dai {
  29
  30
  31 /// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.
  32 /** \todo General marginalization functions like calcMarginal now copy a complete InfAlg object. Instead,
  33  *  it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph.
  34  *  Or they can simply be made methods of the general InfAlg class.
  35  *  \idea Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().
  36  */
  37 class InfAlg {
  38     public:
  39         /// Virtual desctructor (needed because this class contains virtual functions)
  40         virtual ~InfAlg() {}
  41
  42     public:
  43         /// Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor)
  44         virtual InfAlg* clone() const = 0;
  45
  46         /// Identifies itself for logging purposes
  47         virtual std::string identify() const = 0;
  48
  49         /// Returns the "belief" (i.e., approximate marginal probability distribution) of a variable
  50         virtual Factor belief( const Var &n ) const = 0;
  51
  52         /// Returns the "belief" (i.e., approximate marginal probability distribution) of a set of variables
  53         virtual Factor belief( const VarSet &n ) const = 0;
  54
  55         /// Returns marginal for a variable.
  56         /** Sometimes preferred to belief() for performance reasons.
  57           * Faster implementations exist in e.g. BP.
  58           */
  59         virtual Factor beliefV( size_t i ) const { return belief( fg().var(i) ); }
  60
  61         /// Returns marginal for a factor.
  62         /** Sometimes preferred to belief() for performance reasons.
  63           * Faster implementations exist in e.g. BP.
  64           */
  65         virtual Factor beliefF( size_t I ) const { return belief( fg().factor(I).vars() ); }
  66
  67         /// Returns all "beliefs" (i.e., approximate marginal probability distribution) calculated by the algorithm
  68         virtual std::vector<Factor> beliefs() const = 0;
  69
  70         /// Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph)
  71         virtual Real logZ() const = 0;
  72
  73         /// Initializes all data structures of the approximate inference algorithm
  74         /** This method should be called at least once before run() is called
  75          */
  76         virtual void init() = 0;
  77
  78         /// Initializes all data structures corresponding to some set of variables
  79         /** This method can be used to do a partial initialization after a part of the factor graph has changed.
  80          *  Instead of initializing all data structures, it only initializes those involving the variables in ns.
  81          */
  82         virtual void init( const VarSet &ns ) = 0;
  83
  84         /// Runs the approximate inference algorithm
  85         /*  Before run() is called the first time, init() should be called.
  86          *  If run() returns successfully, the results can be queried using the methods belief(), beliefs() and logZ().
  87          */
  88         virtual Real run() = 0;
  89
  90         /// Clamp variable with index i to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
  91         /** If backup == true, make a backup of all factors that are changed
  92          */
  93         virtual void clamp( size_t i, size_t x, bool backup = false ) = 0;
  94
  95         // OBSOLETE
  96         /// Only for backwards compatibility (to be removed soon)
  97         virtual void clamp( const Var &v, size_t x, bool backup = false ) = 0;
  98
  99         /// Set all factors interacting with var(i) to 1
 100         virtual void makeCavity( size_t i, bool backup = false ) = 0;
 101
 102         /// Return maximum difference between single node beliefs in the last pass
 103         /// \throw Exception if not implemented/supported
 104         virtual Real maxDiff() const = 0;
 105
 106         /// Return number of passes over the factorgraph
 107         /// \throw Exception if not implemented/supported
 108         virtual size_t Iterations() const = 0;
 109
 110
 111         /// Get reference to underlying FactorGraph
 112         virtual FactorGraph &fg() = 0;
 113
 114         /// Get const reference to underlying FactorGraph
 115         virtual const FactorGraph &fg() const = 0;
 116
 117         /// Save factor I
 118         virtual void backupFactor( size_t I ) = 0;
 119         /// Save Factors involving ns
 120         virtual void backupFactors( const VarSet &ns ) = 0;
 121
 122         /// Restore factor I
 123         virtual void restoreFactor( size_t I ) = 0;
 124         /// Restore Factors involving ns
 125         virtual void restoreFactors( const VarSet &ns ) = 0;
 126 };
 127
 128
 129 /// Combines an InfAlg and a graphical model, e.g., a FactorGraph or RegionGraph
 130 /** \tparam GRM Should be castable to FactorGraph
 131  *  \todo A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should
 132  *  store a reference to the graphical model object. This prevents needless copying
 133  *  of (possibly large) data structures. Disadvantage: the caller must not change
 134  *  the graphical model between calls to the inference algorithm (maybe a smart_ptr
 135  *  or some locking mechanism would help here?).
 136  */
 137 template <class GRM>
 138 class DAIAlg : public InfAlg, public GRM {
 139     public:
 140         /// Default constructor
 141         DAIAlg() : InfAlg(), GRM() {}
 142
 143         /// Construct from GRM
 144         DAIAlg( const GRM &grm ) : InfAlg(), GRM(grm) {}
 145
 146         /// Save factor I
 147         void backupFactor( size_t I ) { GRM::backupFactor( I ); }
 148         /// Save Factors involving ns
 149         void backupFactors( const VarSet &ns ) { GRM::backupFactors( ns ); }
 150
 151         /// Restore factor I
 152         void restoreFactor( size_t I ) { GRM::restoreFactor( I ); }
 153         /// Restore Factors involving ns
 154         void restoreFactors( const VarSet &ns ) { GRM::restoreFactors( ns ); }
 155
 156         /// Clamp variable with index i to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
 157         void clamp( size_t i, size_t x, bool backup = false ) { GRM::clamp( i, x, backup ); }
 158
 159         // OBSOLETE
 160         /// Only for backwards compatibility (to be removed soon)
 161         void clamp( const Var &v, size_t x, bool backup = false ) {
 162             GRM::clamp( v, x, backup );
 163             std::cerr << "Warning: this DAIAlg<...>::clamp(const Var&,...) interface is obsolete!" << std::endl;
 164         }
 165
 166         /// Set all factors interacting with var(i) to 1
 167         void makeCavity( size_t i, bool backup = false ) { GRM::makeCavity( i, backup ); }
 168
 169         /// Get reference to underlying FactorGraph
 170         FactorGraph &fg() { return (FactorGraph &)(*this); }
 171
 172         /// Get const reference to underlying FactorGraph
 173         const FactorGraph &fg() const { return (const FactorGraph &)(*this); }
 174 };
 175
 176
 177 /// Base class for inference algorithms that operate on a FactorGraph
 178 typedef DAIAlg<FactorGraph> DAIAlgFG;
 179
 180 /// Base class for inference algorithms that operate on a RegionGraph
 181 typedef DAIAlg<RegionGraph> DAIAlgRG;
 182
 183
 184 Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit );
 185 std::vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reInit );
 186 std::vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool reInit );
 187 Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit );
 188
 189
 190 } // end of namespace dai
 191
 192
 193 #endif