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