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