-/* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
- Radboud University Nijmegen, The Netherlands
-
+/* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
+ Radboud University Nijmegen, The Netherlands /
+ Max Planck Institute for Biological Cybernetics, Germany
+
This file is part of libDAI.
libDAI is free software; you can redistribute it and/or modify
*/
+/// \file
+/// \brief Defines abstract base class InfAlg, its descendants DAIAlg<T>, the specializations DAIAlgFG and DAIAlgRG and some generic inference methods.
+/// \todo Improve documentation
+
+
#ifndef __defined_libdai_daialg_h
#define __defined_libdai_daialg_h
#include <vector>
#include <dai/factorgraph.h>
#include <dai/regiongraph.h>
-#include <dai/properties.h>
namespace dai {
-/// The InfAlg class is the common denominator of the various approximate inference algorithms.
-/// A InfAlg object represents a discrete factorized probability distribution over multiple variables
-/// together with an inference algorithm.
+/// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.
+/** \todo General marginalization functions like calcMarginal now copy a complete InfAlg object. Instead,
+ * it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph.
+ * Or they can simply be made methods of the general InfAlg class.
+ * \idea Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().
+ */
class InfAlg {
- private:
- /// Properties of the algorithm (replaces _tol, _maxiter, _verbose)
- Properties _properties;
-
- /// Maximum difference encountered so far
- double _maxdiff;
-
-
public:
- /// Default constructor
- InfAlg() : _properties(), _maxdiff(0.0) {}
-
- /// Constructor with options
- InfAlg( const Properties &opts ) : _properties(opts), _maxdiff(0.0) {}
-
- /// Copy constructor
- InfAlg( const InfAlg & x ) : _properties(x._properties), _maxdiff(x._maxdiff) {}
+ /// Virtual desctructor (needed because this class contains virtual functions)
+ virtual ~InfAlg() {}
- /// Clone (virtual copy constructor)
+ public:
+ /// Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor)
virtual InfAlg* clone() const = 0;
- /// Assignment operator
- InfAlg & operator=( const InfAlg & x ) {
- if( this != &x ) {
- _properties = x._properties;
- _maxdiff = x._maxdiff;
- }
- return *this;
- }
+ /// Returns a pointer to a newly constructed object *this (i.e., virtual default constructor)
+ virtual InfAlg* create() const = 0;
- /// Virtual desctructor
- // (this is needed because this class contains virtual functions)
- virtual ~InfAlg() {}
-
- /// Returns true if a property with the given key is present
- bool HasProperty(const PropertyKey &key) const { return _properties.hasKey(key); }
-
- /// Gets a property
- const PropertyValue & GetProperty(const PropertyKey &key) const { return _properties.Get(key); }
-
- /// Gets a property, casted as ValueType
- template<typename ValueType>
- ValueType GetPropertyAs(const PropertyKey &key) const { return _properties.GetAs<ValueType>(key); }
-
- /// Sets a property
- void SetProperty(const PropertyKey &key, const PropertyValue &val) { _properties[key] = val; }
-
- /// Converts a property from string to ValueType, if necessary
- template<typename ValueType>
- void ConvertPropertyTo(const PropertyKey &key) { _properties.ConvertTo<ValueType>(key); }
-
- /// Gets all properties
- const Properties & GetProperties() const { return _properties; }
-
- /// Sets properties
- void SetProperties(const Properties &p) { _properties = p; }
-
- /// Sets tolerance
- void Tol( double tol ) { SetProperty("tol", tol); }
- /// Gets tolerance
- double Tol() const { return GetPropertyAs<double>("tol"); }
-
- /// Sets maximum number of iterations
- void MaxIter( size_t maxiter ) { SetProperty("maxiter", maxiter); }
- /// Gets maximum number of iterations
- size_t MaxIter() const { return GetPropertyAs<size_t>("maxiter"); }
-
- /// Sets verbosity
- void Verbose( size_t verbose ) { SetProperty("verbose", verbose); }
- /// Gets verbosity
- size_t Verbose() const { return GetPropertyAs<size_t>("verbose"); }
-
- /// Sets maximum difference encountered so far
- void MaxDiff( double maxdiff ) { _maxdiff = maxdiff; }
- /// Gets maximum difference encountered so far
- double MaxDiff() const { return _maxdiff; }
- /// Updates maximum difference encountered so far
- void updateMaxDiff( double maxdiff ) { if( maxdiff > _maxdiff ) _maxdiff = maxdiff; }
- /// Sets maximum difference encountered so far to zero
- void clearMaxDiff() { _maxdiff = 0.0; }
-
/// Identifies itself for logging purposes
virtual std::string identify() const = 0;
- /// Get single node belief
+ /// Returns the "belief" (i.e., approximate marginal probability distribution) of a variable
virtual Factor belief( const Var &n ) const = 0;
- /// Get general belief
+ /// Returns the "belief" (i.e., approximate marginal probability distribution) of a set of variables
virtual Factor belief( const VarSet &n ) const = 0;
- /// Get all beliefs
+ /// Returns all "beliefs" (i.e., approximate marginal probability distribution) calculated by the algorithm
virtual std::vector<Factor> beliefs() const = 0;
- /// Get log partition sum
+ /// Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph)
virtual Real logZ() const = 0;
- /// Clear messages and beliefs
+ /// Initializes all data structures of the approximate inference algorithm
+ /** This method should be called at least once before run() is called
+ */
virtual void init() = 0;
- /// The actual approximate inference algorithm
- virtual double run() = 0;
+ /// Initializes all data structures corresponding to some set of variables
+ /** This method can be used to do a partial initialization after a part of the factor graph has changed.
+ * Instead of initializing all data structures, it only initializes those involving the variables in ns.
+ */
+ virtual void init( const VarSet &ns ) = 0;
- /// Save factor I
- virtual void saveProb( size_t I ) = 0;
- /// Save Factors involving ns
- virtual void saveProbs( const VarSet &ns ) = 0;
-
- /// Restore factor I
- virtual void undoProb( size_t I ) = 0;
- /// Restore Factors involving ns
- virtual void undoProbs( const VarSet &ns ) = 0;
+ /// Runs the approximate inference algorithm
+ /* Before run() is called the first time, init() should be called.
+ * If run() returns successfully, the results can be queried using the methods belief(), beliefs() and logZ().
+ */
+ virtual double run() = 0;
/// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
- virtual void clamp( const Var & n, size_t i ) = 0;
+ virtual void clamp( const Var & n, size_t i, bool backup = false ) = 0;
/// Set all factors interacting with var(i) to 1
- virtual void makeCavity( size_t i ) = 0;
+ virtual void makeCavity( size_t i, bool backup = false ) = 0;
+
+ /// Return maximum difference between single node beliefs in the last pass
+ /// \throw Exception if not implemented/supported
+ virtual double maxDiff() const = 0;
+
+ /// Return number of passes over the factorgraph
+ /// \throw Exception if not implemented/supported
+ virtual size_t Iterations() const = 0;
+
/// Get reference to underlying FactorGraph
virtual FactorGraph &fg() = 0;
/// Get const reference to underlying FactorGraph
virtual const FactorGraph &fg() const = 0;
- /// Checks whether all necessary properties have been set
- /// and casts string-valued properties to other values if necessary
- virtual bool checkProperties() = 0;
+ /// Save factor I
+ virtual void backupFactor( size_t I ) = 0;
+ /// Save Factors involving ns
+ virtual void backupFactors( const VarSet &ns ) = 0;
+
+ /// Restore factor I
+ virtual void restoreFactor( size_t I ) = 0;
+ /// Restore Factors involving ns
+ virtual void restoreFactors( const VarSet &ns ) = 0;
};
-template <class T>
-class DAIAlg : public InfAlg, public T {
+/// Combines an InfAlg and a graphical model, e.g., a FactorGraph or RegionGraph
+/** \tparam GRM Should be castable to FactorGraph
+ * \todo A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should
+ * store a reference to the graphical model object. This prevents needless copying
+ * of (possibly large) data structures. Disadvantage: the caller must not change
+ * the graphical model between calls to the inference algorithm (maybe a smart_ptr
+ * or some locking mechanism would help here?).
+ */
+template <class GRM>
+class DAIAlg : public InfAlg, public GRM {
public:
/// Default constructor
- DAIAlg() : InfAlg(), T() {}
-
- /// Construct DAIAlg with empty T but using the specified properties
- DAIAlg( const Properties &opts ) : InfAlg( opts ), T() {}
-
- /// Construct DAIAlg using the specified properties
- DAIAlg( const T & t, const Properties &opts ) : InfAlg( opts ), T(t) {}
+ DAIAlg() : InfAlg(), GRM() {}
- /// Copy constructor
- DAIAlg( const DAIAlg & x ) : InfAlg(x), T(x) {}
+ /// Construct from GRM
+ DAIAlg( const GRM &grm ) : InfAlg(), GRM(grm) {}
- /// Save factor I (using T::saveProb)
- void saveProb( size_t I ) { T::saveProb( I ); }
- /// Save Factors involving ns (using T::saveProbs)
- void saveProbs( const VarSet &ns ) { T::saveProbs( ns ); }
+ /// Save factor I
+ void backupFactor( size_t I ) { GRM::backupFactor( I ); }
+ /// Save Factors involving ns
+ void backupFactors( const VarSet &ns ) { GRM::backupFactors( ns ); }
- /// Restore factor I (using T::undoProb)
- void undoProb( size_t I ) { T::undoProb( I ); }
- /// Restore Factors involving ns (using T::undoProbs)
- void undoProbs( const VarSet &ns ) { T::undoProbs( ns ); }
+ /// Restore factor I
+ void restoreFactor( size_t I ) { GRM::restoreFactor( I ); }
+ /// Restore Factors involving ns
+ void restoreFactors( const VarSet &ns ) { GRM::restoreFactors( ns ); }
- /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$) (using T::clamp)
- void clamp( const Var & n, size_t i ) { T::clamp( n, i ); }
+ /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
+ void clamp( const Var & n, size_t i, bool backup = false ) { GRM::clamp( n, i, backup ); }
- /// Set all factors interacting with var(i) to 1 (using T::makeCavity)
- void makeCavity( size_t i ) { T::makeCavity( i ); }
+ /// Set all factors interacting with var(i) to 1
+ void makeCavity( size_t i, bool backup = false ) { GRM::makeCavity( i, backup ); }
/// Get reference to underlying FactorGraph
FactorGraph &fg() { return (FactorGraph &)(*this); }
};
+/// Base class for inference algorithms that operate on a FactorGraph
typedef DAIAlg<FactorGraph> DAIAlgFG;
+
+/// Base class for inference algorithms that operate on a RegionGraph
typedef DAIAlg<RegionGraph> DAIAlgRG;
-/// Calculate the marginal of obj on ns by clamping
-/// all variables in ns and calculating logZ for each joined state
Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit );
-
-
-/// Calculate beliefs of all pairs in ns (by clamping
-/// nodes in ns and calculating logZ and the beliefs for each state)
std::vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reInit );
-
-
-/// Calculate beliefs of all pairs in ns (by clamping
-/// pairs in ns and calculating logZ for each joined state)
std::vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool reInit );
-
-
-/// Calculate 2nd order interactions of the marginal of obj on ns
Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit );
projects / libdai.git / blobdiff