include/dai/daialg.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
   2     Radboud University Nijmegen, The Netherlands
   3
   4     This file is part of libDAI.
   5
   6     libDAI is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     libDAI is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with libDAI; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19 */
  20
  21
  22 #ifndef __defined_libdai_daialg_h
  23 #define __defined_libdai_daialg_h
  24
  25
  26 #include <string>
  27 #include <iostream>
  28 #include <vector>
  29 #include <dai/factorgraph.h>
  30 #include <dai/regiongraph.h>
  31 #include <dai/properties.h>
  32
  33
  34 namespace dai {
  35
  36
  37 /// The InfAlg class is the common denominator of the various approximate inference algorithms.
  38 /// A InfAlg object represents a discrete factorized probability distribution over multiple variables
  39 /// together with an inference algorithm.
  40 class InfAlg {
  41     private:
  42         /// Properties of the algorithm (replaces _tol, _maxiter, _verbose)
  43         Properties              _properties;
  44
  45         /// Maximum difference encountered so far
  46         double                  _maxdiff;
  47
  48
  49     public:
  50         /// Default constructor
  51         InfAlg() : _properties(), _maxdiff(0.0) {}
  52
  53         /// Constructor with options
  54         InfAlg( const Properties &opts ) : _properties(opts), _maxdiff(0.0) {}
  55
  56         /// Copy constructor
  57         InfAlg( const InfAlg & x ) : _properties(x._properties), _maxdiff(x._maxdiff) {}
  58
  59         /// Clone (virtual copy constructor)
  60         virtual InfAlg* clone() const = 0;
  61
  62         /// Assignment operator
  63         InfAlg & operator=( const InfAlg & x ) {
  64             if( this != &x ) {
  65                 _properties = x._properties;
  66                 _maxdiff    = x._maxdiff;
  67             }
  68             return *this;
  69         }
  70
  71         /// Virtual desctructor
  72         // (this is needed because this class contains virtual functions)
  73         virtual ~InfAlg() {}
  74
  75         /// Returns true if a property with the given key is present
  76         bool HasProperty(const PropertyKey &key) const { return _properties.hasKey(key); }
  77
  78         /// Gets a property
  79         const PropertyValue & GetProperty(const PropertyKey &key) const { return _properties.Get(key); }
  80
  81         /// Gets a property, casted as ValueType
  82         template<typename ValueType>
  83         ValueType GetPropertyAs(const PropertyKey &key) const { return _properties.GetAs<ValueType>(key); }
  84
  85         /// Sets a property
  86         void SetProperty(const PropertyKey &key, const PropertyValue &val) { _properties[key] = val; }
  87
  88         /// Converts a property from string to ValueType, if necessary
  89         template<typename ValueType>
  90         void ConvertPropertyTo(const PropertyKey &key) { _properties.ConvertTo<ValueType>(key); }
  91
  92         /// Gets all properties
  93         const Properties & GetProperties() const { return _properties; }
  94
  95         /// Sets properties
  96         void SetProperties(const Properties &p) { _properties = p; }
  97
  98         /// Sets tolerance
  99         void Tol( double tol ) { SetProperty("tol", tol); }
 100         /// Gets tolerance
 101         double Tol() const { return GetPropertyAs<double>("tol"); }
 102
 103         /// Sets maximum number of iterations
 104         void MaxIter( size_t maxiter ) { SetProperty("maxiter", maxiter); }
 105         /// Gets maximum number of iterations
 106         size_t MaxIter() const { return GetPropertyAs<size_t>("maxiter"); }
 107
 108         /// Sets verbosity
 109         void Verbose( size_t verbose ) { SetProperty("verbose", verbose); }
 110         /// Gets verbosity
 111         size_t Verbose() const { return GetPropertyAs<size_t>("verbose"); }
 112
 113         /// Sets maximum difference encountered so far
 114         void MaxDiff( double maxdiff ) { _maxdiff = maxdiff; }
 115         /// Gets maximum difference encountered so far
 116         double MaxDiff() const { return _maxdiff; }
 117         /// Updates maximum difference encountered so far
 118         void updateMaxDiff( double maxdiff ) { if( maxdiff > _maxdiff ) _maxdiff = maxdiff; }
 119         /// Sets maximum difference encountered so far to zero
 120         void clearMaxDiff() { _maxdiff = 0.0; }
 121
 122         /// Identifies itself for logging purposes
 123         virtual std::string identify() const = 0;
 124
 125         /// Get single node belief
 126         virtual Factor belief( const Var &n ) const = 0;
 127
 128         /// Get general belief
 129         virtual Factor belief( const VarSet &n ) const = 0;
 130
 131         /// Get all beliefs
 132         virtual std::vector<Factor> beliefs() const = 0;
 133
 134         /// Get log partition sum
 135         virtual Complex logZ() const = 0;
 136
 137         /// Clear messages and beliefs
 138         virtual void init() = 0;
 139
 140         /// The actual approximate inference algorithm
 141         virtual double run() = 0;
 142
 143         /// Save factor I
 144         virtual void saveProb( size_t I ) = 0;
 145         /// Save Factors involving ns
 146         virtual void saveProbs( const VarSet &ns ) = 0;
 147
 148         /// Restore factor I
 149         virtual void undoProb( size_t I ) = 0;
 150         /// Restore Factors involving ns
 151         virtual void undoProbs( const VarSet &ns ) = 0;
 152
 153         /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
 154         virtual void clamp( const Var & n, size_t i ) = 0;
 155
 156         /// Return all variables that interact with n
 157         virtual VarSet delta( const Var & n ) const = 0;
 158
 159         /// Set all factors interacting with n to 1
 160         virtual void makeCavity( const Var & n ) = 0;
 161
 162         /// Set factor I to 1
 163         virtual void makeFactorCavity( size_t I ) = 0;
 164
 165         /// Get index of variable n
 166         virtual size_t findVar( const Var & n ) const = 0;
 167
 168         /// Get index of first factor involving ns
 169         virtual size_t findFactor( const VarSet &ns ) const = 0;
 170
 171         /// Get number of variables
 172         virtual size_t nrVars() const = 0;
 173
 174         /// Get number of factors
 175         virtual size_t nrFactors() const = 0;
 176
 177         /// Get const reference to variable i
 178         virtual const Var & var(size_t i) const = 0;
 179
 180         /// Get reference to variable i
 181         virtual Var & var(size_t i) = 0;
 182
 183         /// Get const reference to factor I
 184         virtual const Factor & factor( size_t I ) const = 0;
 185
 186         /// Get reference to factor I
 187         virtual Factor & factor( size_t I ) = 0;
 188
 189         /// Factor I has been updated
 190         virtual void updatedFactor( size_t I ) = 0;
 191
 192         /// Checks whether all necessary properties have been set
 193         /// and casts string-valued properties to other values if necessary
 194         virtual bool checkProperties() = 0;
 195 };
 196
 197
 198 template <class T>
 199 class DAIAlg : public InfAlg, public T {
 200     public:
 201         /// Default constructor
 202         DAIAlg() : InfAlg(), T() {}
 203
 204         /// Construct DAIAlg with empty T but using the specified properties
 205         DAIAlg( const Properties &opts ) : InfAlg( opts ), T() {}
 206
 207         /// Construct DAIAlg using the specified properties
 208         DAIAlg( const T & t, const Properties &opts ) : InfAlg( opts ), T(t) {}
 209
 210         /// Copy constructor
 211         DAIAlg( const DAIAlg & x ) : InfAlg(x), T(x) {}
 212
 213         /// Save factor I (using T::saveProb)
 214         void saveProb( size_t I ) { T::saveProb( I ); }
 215         /// Save Factors involving ns (using T::saveProbs)
 216         void saveProbs( const VarSet &ns ) { T::saveProbs( ns ); }
 217
 218         /// Restore factor I (using T::undoProb)
 219         void undoProb( size_t I ) { T::undoProb( I ); }
 220         /// Restore Factors involving ns (using T::undoProbs)
 221         void undoProbs( const VarSet &ns ) { T::undoProbs( ns ); }
 222
 223         /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$) (using T::clamp)
 224         void clamp( const Var & n, size_t i ) { T::clamp( n, i ); }
 225
 226         /// Return all variables that interact with n (using T::delta)
 227         VarSet delta( const Var & n ) const { return T::delta(n); }
 228
 229         /// Set all factors interacting with n to 1 (using T::makeCavity)
 230         void makeCavity( const Var & n ) { T::makeCavity(n); }
 231
 232         /// Set factor I to 1 (using T::makeFactorCavity)
 233         void makeFactorCavity( size_t I ) { T::makeFactorCavity(I); }
 234
 235         /// Get index of variable n (using T::findVar)
 236         size_t findVar( const Var & n ) const { return T::findVar(n); }
 237
 238         /// Get index of first factor involving ns (using T::findFactor)
 239         size_t findFactor( const VarSet &ns ) const { return T::findFactor(ns); }
 240
 241         /// Get number of variables (using T::nrFactors)
 242         size_t nrVars() const { return T::nrVars(); }
 243
 244         /// Get number of factors (using T::nrFactors)
 245         size_t nrFactors() const { return T::nrFactors(); }
 246
 247         /// Get const reference to variable i (using T::var)
 248         const Var & var( size_t i ) const { return T::var(i); }
 249
 250         /// Get reference to variable i (using T::var)
 251         Var & var(size_t i) { return T::var(i); }
 252
 253         /// Get const reference to factor I (using T::factor)
 254         const Factor & factor( size_t I ) const { return T::factor(I); }
 255
 256         /// Get reference to factor I (using T::factor)
 257         Factor & factor( size_t I ) { return T::factor(I); }
 258
 259         /// Factor I has been updated (using T::updatedFactor)
 260         void updatedFactor( size_t I ) { T::updatedFactor(I); }
 261 };
 262
 263
 264 typedef DAIAlg<FactorGraph> DAIAlgFG;
 265 typedef DAIAlg<RegionGraph> DAIAlgRG;
 266
 267
 268 /// Calculate the marginal of obj on ns by clamping
 269 /// all variables in ns and calculating logZ for each joined state
 270 Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit );
 271
 272
 273 /// Calculate beliefs of all pairs in ns (by clamping
 274 /// nodes in ns and calculating logZ and the beliefs for each state)
 275 std::vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reInit );
 276
 277
 278 /// Calculate beliefs of all pairs in ns (by clamping
 279 /// pairs in ns and calculating logZ for each joined state)
 280 std::vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool reInit );
 281
 282
 283 /// Calculate 2nd order interactions of the marginal of obj on ns
 284 Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit );
 285
 286
 287 } // end of namespace dai
 288
 289
 290 #endif