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