include/dai/daialg.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
   4  *
   5  *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
   6  */
   7
   8
   9 /// \file
  10 /// \brief Defines the general interface for inference methods in libDAI (classes InfAlg, DaiAlg<>, DaiAlgFG and DaiAlgRG).
  11
  12
  13 #ifndef __defined_libdai_daialg_h
  14 #define __defined_libdai_daialg_h
  15
  16
  17 #include <string>
  18 #include <iostream>
  19 #include <vector>
  20 #include <dai/factorgraph.h>
  21 #include <dai/regiongraph.h>
  22 #include <dai/cobwebgraph.h>
  23 #include <dai/properties.h>
  24
  25
  26 namespace dai {
  27
  28
  29 /// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.
  30 /** \idea General marginalization functions like calcMarginal() now copy a complete InfAlg object. Instead,
  31  *  it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph.
  32  *  Or they can simply be made methods of the general InfAlg class.
  33  *  \idea Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().
  34  */
  35 class InfAlg {
  36     public:
  37     /// \name Constructors/destructors
  38     //@{
  39         /// Virtual destructor (needed because this class contains virtual functions)
  40         virtual ~InfAlg() {}
  41
  42         /// Returns a pointer to a new, cloned copy of \c *this (i.e., virtual copy constructor)
  43         virtual InfAlg* clone() const = 0;
  44
  45         /// Returns a pointer to a newly constructed inference algorithm
  46         /** \param fg Factor graph on which to perform the inference algorithm;
  47          *  \param opts Parameters passed to constructor of inference algorithm;
  48          */
  49         virtual InfAlg* construct( const FactorGraph &fg, const PropertySet &opts ) const = 0;
  50     //@}
  51
  52     /// \name Queries
  53     //@{
  54         /// Returns the name of the algorithm
  55         virtual std::string name() const = 0;
  56
  57         /// Identifies itself for logging purposes
  58         virtual std::string identify() const {
  59             return name() + printProperties();
  60         }
  61
  62         /// Returns reference to underlying FactorGraph.
  63         virtual FactorGraph &fg() = 0;
  64
  65         /// Returns constant reference to underlying FactorGraph.
  66         virtual const FactorGraph &fg() const = 0;
  67     //@}
  68
  69     /// \name Inference interface
  70     //@{
  71         /// Initializes all data structures of the approximate inference algorithm.
  72         /** \note This method should be called at least once before run() is called.
  73          */
  74         virtual void init() = 0;
  75
  76         /// Initializes all data structures corresponding to some set of variables.
  77         /** This method can be used to do a partial initialization after a part of the factor graph has changed.
  78          *  Instead of initializing all data structures, it only initializes those involving the variables in \a vs.
  79          *  \throw NOT_IMPLEMENTED if not implemented/supported
  80          */
  81         virtual void init( const VarSet &vs ) = 0;
  82
  83         /// Runs the approximate inference algorithm.
  84         /** \note Before run() is called the first time, init() should have been called.
  85          */
  86         virtual Real run() = 0;
  87
  88         /// Returns the (approximate) marginal probability distribution of a variable.
  89         /** \note Before this method is called, run() should have been called.
  90          */
  91         virtual Factor belief( const Var &v ) const { return belief( VarSet(v) ); }
  92
  93         /// Returns the (approximate) marginal probability distribution of a set of variables.
  94         /** \note Before this method is called, run() should have been called.
  95          *  \throw NOT_IMPLEMENTED if not implemented/supported.
  96          *  \throw BELIEF_NOT_AVAILABLE if the requested belief cannot be calculated with this algorithm.
  97          */
  98         virtual Factor belief( const VarSet &vs ) const = 0;
  99
 100         /// Returns the (approximate) marginal probability distribution of the variable with index \a i.
 101         /** For some approximate inference algorithms, using beliefV() is preferred to belief() for performance reasons.
 102          *  \note Before this method is called, run() should have been called.
 103          */
 104         virtual Factor beliefV( size_t i ) const { return belief( fg().var(i) ); }
 105
 106         /// Returns the (approximate) marginal probability distribution of the variables on which factor \a I depends.
 107         /** For some approximate inference algorithms, using beliefF() is preferred to belief() for performance reasons.
 108          *  \note Before this method is called, run() should have been called.
 109          */
 110         virtual Factor beliefF( size_t I ) const { return belief( fg().factor(I).vars() ); }
 111
 112         /// Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm.
 113         /** \note Before this method is called, run() should have been called.
 114          */
 115         virtual std::vector<Factor> beliefs() const = 0;
 116
 117         /// Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).
 118         /** \note Before this method is called, run() should have been called.
 119          *  \throw NOT_IMPLEMENTED if not implemented/supported
 120          */
 121         virtual Real logZ() const = 0;
 122
 123         /// Calculates the joint state of all variables that has maximum probability
 124         /** \note Before this method is called, run() should have been called.
 125          *  \throw NOT_IMPLEMENTED if not implemented/supported
 126          */
 127         virtual std::vector<size_t> findMaximum() const { DAI_THROW(NOT_IMPLEMENTED); }
 128
 129         /// Returns maximum difference between single variable beliefs in the last iteration.
 130         /** \throw NOT_IMPLEMENTED if not implemented/supported
 131          */
 132         virtual Real maxDiff() const { DAI_THROW(NOT_IMPLEMENTED); };
 133
 134         /// Returns number of iterations done (one iteration passes over the complete factorgraph).
 135         /** \throw NOT_IMPLEMENTED if not implemented/supported
 136          */
 137         virtual size_t Iterations() const { DAI_THROW(NOT_IMPLEMENTED); };
 138
 139         /// Sets maximum number of iterations (one iteration passes over the complete factorgraph).
 140         /** \throw NOT_IMPLEMENTED if not implemented/supported
 141          */
 142         virtual void setMaxIter( size_t /*maxiter*/ ) { DAI_THROW(NOT_IMPLEMENTED); }
 143     //@}
 144
 145     /// \name Changing the factor graph
 146     //@{
 147         /// Clamp variable with index \a i to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
 148         /** If \a backup == \c true, make a backup of all factors that are changed.
 149          */
 150         virtual void clamp( size_t i, size_t x, bool backup = false ) = 0;
 151
 152         /// Sets all factors interacting with variable with index \a i to one.
 153         /** If \a backup == \c true, make a backup of all factors that are changed.
 154          */
 155         virtual void makeCavity( size_t i, bool backup = false ) = 0;
 156
 157         /// Sets all factors indicated by \a facInds to one.
 158         /** If \a backup == \c true, make a backup of all factors that are changed.
 159          */
 160         virtual void makeRegionCavity( std::vector<size_t> facInds, bool backup = false ) = 0;
 161     //@}
 162
 163     /// \name Backup/restore mechanism for factors
 164     //@{
 165         /// Make a backup copy of factor \a I
 166         /** \throw MULTIPLE_UNDO if a backup already exists
 167          */
 168         virtual void backupFactor( size_t I ) = 0;
 169         /// Make backup copies of all factors involving the variables in \a vs
 170         /** \throw MULTIPLE_UNDO if a backup already exists
 171          */
 172         virtual void backupFactors( const VarSet &vs ) = 0;
 173
 174         /// Restore factor \a I from its backup copy
 175         virtual void restoreFactor( size_t I ) = 0;
 176         /// Restore the factors involving the variables in \a vs from their backup copies
 177         virtual void restoreFactors( const VarSet &vs ) = 0;
 178     //@}
 179
 180     /// \name Managing parameters
 181     //@{
 182         /// Set parameters of this inference algorithm.
 183         /** The parameters are set according to the PropertySet \a opts.
 184          *  The values can be stored either as std::string or as the type of the corresponding MF::props member.
 185          */
 186         virtual void setProperties( const PropertySet &opts ) = 0;
 187         /// Returns parameters of this inference algorithm converted into a PropertySet.
 188         virtual PropertySet getProperties() const = 0;
 189         /// Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".
 190         virtual std::string printProperties() const = 0;
 191     //@}
 192 };
 193
 194
 195 /// Combines the abstract base class InfAlg with a graphical model (e.g., a FactorGraph or RegionGraph).
 196 /** Inference algorithms in libDAI directly inherit from a DAIAlg, currently either
 197  *  from a DAIAlg<FactorGraph> or from a DAIAlg<RegionGraph>.
 198  *
 199  *  \tparam GRM Should be castable to FactorGraph
 200  *  \idea A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should
 201  *  store a reference to the graphical model object. This prevents needless copying
 202  *  of (possibly large) data structures. Disadvantage: the caller must not change
 203  *  the graphical model between calls to the inference algorithm (maybe a smart_ptr
 204  *  or some locking mechanism would help here?).
 205  */
 206 template <class GRM>
 207 class DAIAlg : public InfAlg, public GRM {
 208     public:
 209     /// \name Constructors/destructors
 210     //@{
 211         /// Default constructor
 212         DAIAlg() : InfAlg(), GRM() {}
 213
 214         /// Construct from GRM
 215         DAIAlg( const GRM &grm ) : InfAlg(), GRM(grm) {}
 216     //@}
 217
 218     /// \name Queries
 219     //@{
 220         /// Returns reference to underlying FactorGraph.
 221         FactorGraph &fg() { return (FactorGraph &)(*this); }
 222
 223         /// Returns constant reference to underlying FactorGraph.
 224         const FactorGraph &fg() const { return (const FactorGraph &)(*this); }
 225     //@}
 226
 227     /// \name Changing the factor graph
 228     //@{
 229         /// Clamp variable with index \a i to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
 230         /** If \a backup == \c true, make a backup of all factors that are changed.
 231          */
 232         void clamp( size_t i, size_t x, bool backup = false ) { GRM::clamp( i, x, backup ); }
 233
 234         /// Sets all factors interacting with variable with index \a i to one.
 235         /** If \a backup == \c true, make a backup of all factors that are changed.
 236          */
 237         void makeCavity( size_t i, bool backup = false ) { GRM::makeCavity( i, backup ); }
 238
 239         /// Sets all factors indicated by \a facInds to one.
 240         /** If \a backup == \c true, make a backup of all factors that are changed.
 241          */
 242         void makeRegionCavity( std::vector<size_t> facInds, bool backup ){ GRM::makeRegionCavity( facInds, backup ); }
 243     //@}
 244
 245     /// \name Backup/restore mechanism for factors
 246     //@{
 247         /// Make a backup copy of factor \a I
 248         void backupFactor( size_t I ) { GRM::backupFactor( I ); }
 249         /// Make backup copies of all factors involving the variables in \a vs
 250         void backupFactors( const VarSet &vs ) { GRM::backupFactors( vs ); }
 251
 252         /// Restore factor \a I from its backup copy
 253         void restoreFactor( size_t I ) { GRM::restoreFactor( I ); }
 254         /// Restore the factors involving the variables in \a vs from their backup copies
 255         void restoreFactors( const VarSet &vs ) { GRM::restoreFactors( vs ); }
 256         /// Restore all factors from their backup copies
 257         void restoreFactors() { GRM::restoreFactors(); }
 258     //@}
 259 };
 260
 261
 262 /// Base class for inference algorithms that operate on a FactorGraph
 263 typedef DAIAlg<FactorGraph> DAIAlgFG;
 264
 265 /// Base class for inference algorithms that operate on a RegionGraph
 266 typedef DAIAlg<RegionGraph> DAIAlgRG;
 267
 268 /// Base class for GLC that operates on CobwebGraph
 269 typedef DAIAlg<CobwebGraph> DAIAlgCG;
 270
 271
 272 /// Calculates the marginal probability distribution for \a vs using inference algorithm \a obj.
 273 /** calcMarginal() works by clamping all variables in \a vs and calculating the partition sum for each clamped state.
 274  *  Therefore, it can be used in combination with any inference algorithm that can calculate/approximate partition sums.
 275  *  \param obj instance of inference algorithm to be used
 276  *  \param vs variables for which the marginal should be calculated
 277  *  \param reInit should be set to \c true if at least one of the possible clamped states would be invalid (leading to a factor graph with zero partition sum).
 278  */
 279 Factor calcMarginal( const InfAlg& obj, const VarSet& vs, bool reInit );
 280
 281
 282 /// Calculates beliefs for all pairs of variables in \a vs using inference algorithm \a obj.
 283 /** calcPairBeliefs() works by
 284  *  - clamping single variables in \a vs and calculating the partition sum and the single variable beliefs for each clamped state, if \a accurate == \c false;
 285  *  - clamping pairs of variables in \a vs and calculating the partition sum for each clamped state, if \a accurate == \c true.
 286  *
 287  *  Therefore, it can be used in combination with any inference algorithm that can calculate/approximate partition sums (and single variable beliefs, if
 288  *  \a accurate == \c true).
 289  *  \param obj instance of inference algorithm to be used
 290  *  \param vs variables for which the pair beliefs should be calculated
 291  *  \param reInit should be set to \c true if at least one of the possible clamped states would be invalid (leading to a factor graph with zero partition sum).
 292  *  \param accurate if \c true, uses a slower but more accurate approximation algorithm
 293  */
 294 std::vector<Factor> calcPairBeliefs( const InfAlg& obj, const VarSet& vs, bool reInit, bool accurate=false );
 295
 296
 297 /// Calculates the joint state of all variables that has maximum probability, according to the inference algorithm \a obj
 298 /** \note Before this method is called, obj.run() should have been called.
 299  */
 300 std::vector<size_t> findMaximum( const InfAlg& obj );
 301
 302
 303 } // end of namespace dai
 304
 305
 306 #endif