1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
4 This file is part of libDAI.
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.
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.
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
22 #ifndef __defined_libdai_daialg_h
23 #define __defined_libdai_daialg_h
29 #include <dai/factorgraph.h>
30 #include <dai/regiongraph.h>
31 #include <dai/properties.h>
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.
42 /// Properties of the algorithm (replaces _tol, _maxiter, _verbose)
43 Properties _properties
;
45 /// Maximum difference encountered so far
50 /// Default constructor
51 InfAlg() : _properties(), _maxdiff(0.0) {}
53 /// Constructor with options
54 InfAlg( const Properties
&opts
) : _properties(opts
), _maxdiff(0.0) {}
57 InfAlg( const InfAlg
& x
) : _properties(x
._properties
), _maxdiff(x
._maxdiff
) {}
59 /// Clone (virtual copy constructor)
60 virtual InfAlg
* clone() const = 0;
62 /// Assignment operator
63 InfAlg
& operator=( const InfAlg
& x
) {
65 _properties
= x
._properties
;
66 _maxdiff
= x
._maxdiff
;
71 /// Virtual desctructor
72 // (this is needed because this class contains virtual functions)
75 /// Returns true if a property with the given key is present
76 bool HasProperty(const PropertyKey
&key
) const { return _properties
.hasKey(key
); }
79 const PropertyValue
& GetProperty(const PropertyKey
&key
) const { return _properties
.Get(key
); }
81 /// Gets a property, casted as ValueType
82 template<typename ValueType
>
83 ValueType
GetPropertyAs(const PropertyKey
&key
) const { return _properties
.GetAs
<ValueType
>(key
); }
86 void SetProperty(const PropertyKey
&key
, const PropertyValue
&val
) { _properties
[key
] = val
; }
88 /// Converts a property from string to ValueType, if necessary
89 template<typename ValueType
>
90 void ConvertPropertyTo(const PropertyKey
&key
) { _properties
.ConvertTo
<ValueType
>(key
); }
92 /// Gets all properties
93 const Properties
& GetProperties() const { return _properties
; }
96 void SetProperties(const Properties
&p
) { _properties
= p
; }
99 void Tol( double tol
) { SetProperty("tol", tol
); }
101 double Tol() const { return GetPropertyAs
<double>("tol"); }
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"); }
109 void Verbose( size_t verbose
) { SetProperty("verbose", verbose
); }
111 size_t Verbose() const { return GetPropertyAs
<size_t>("verbose"); }
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; }
122 /// Identifies itself for logging purposes
123 virtual std::string
identify() const = 0;
125 /// Get single node belief
126 virtual Factor
belief( const Var
&n
) const = 0;
128 /// Get general belief
129 virtual Factor
belief( const VarSet
&n
) const = 0;
132 virtual std::vector
<Factor
> beliefs() const = 0;
134 /// Get log partition sum
135 virtual Complex
logZ() const = 0;
137 /// Clear messages and beliefs
138 virtual void init() = 0;
140 /// The actual approximate inference algorithm
141 virtual double run() = 0;
144 virtual void saveProb( size_t I
) = 0;
145 /// Save Factors involving ns
146 virtual void saveProbs( const VarSet
&ns
) = 0;
149 virtual void undoProb( size_t I
) = 0;
150 /// Restore Factors involving ns
151 virtual void undoProbs( const VarSet
&ns
) = 0;
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;
156 /// Return all variables that interact with var(i)
157 virtual VarSet
delta( size_t i
) const = 0;
159 /// Set all factors interacting with var(i) to 1
160 virtual void makeCavity( size_t i
) = 0;
162 /// Get index of variable n
163 virtual size_t findVar( const Var
& n
) const = 0;
165 /// Get index of first factor involving ns
166 virtual size_t findFactor( const VarSet
&ns
) const = 0;
168 /// Get number of variables
169 virtual size_t nrVars() const = 0;
171 /// Get number of factors
172 virtual size_t nrFactors() const = 0;
174 /// Get const reference to variable i
175 virtual const Var
& var(size_t i
) const = 0;
177 /// Get reference to variable i
178 virtual Var
& var(size_t i
) = 0;
180 /// Get const reference to factor I
181 virtual const Factor
& factor( size_t I
) const = 0;
183 /// Get reference to factor I
184 virtual Factor
& factor( size_t I
) = 0;
186 /// Factor I has been updated
187 virtual void updatedFactor( size_t I
) = 0;
189 /// Checks whether all necessary properties have been set
190 /// and casts string-valued properties to other values if necessary
191 virtual bool checkProperties() = 0;
196 class DAIAlg
: public InfAlg
, public T
{
198 /// Default constructor
199 DAIAlg() : InfAlg(), T() {}
201 /// Construct DAIAlg with empty T but using the specified properties
202 DAIAlg( const Properties
&opts
) : InfAlg( opts
), T() {}
204 /// Construct DAIAlg using the specified properties
205 DAIAlg( const T
& t
, const Properties
&opts
) : InfAlg( opts
), T(t
) {}
208 DAIAlg( const DAIAlg
& x
) : InfAlg(x
), T(x
) {}
210 /// Save factor I (using T::saveProb)
211 void saveProb( size_t I
) { T::saveProb( I
); }
212 /// Save Factors involving ns (using T::saveProbs)
213 void saveProbs( const VarSet
&ns
) { T::saveProbs( ns
); }
215 /// Restore factor I (using T::undoProb)
216 void undoProb( size_t I
) { T::undoProb( I
); }
217 /// Restore Factors involving ns (using T::undoProbs)
218 void undoProbs( const VarSet
&ns
) { T::undoProbs( ns
); }
220 /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$) (using T::clamp)
221 void clamp( const Var
& n
, size_t i
) { T::clamp( n
, i
); }
223 /// Return all variables that interact with var(i) (using T::delta)
224 VarSet
delta( size_t i
) const { return T::delta( i
); }
226 /// Set all factors interacting with var(i) to 1 (using T::makeCavity)
227 void makeCavity( size_t i
) { T::makeCavity( i
); }
229 /// Get index of variable n (using T::findVar)
230 size_t findVar( const Var
& n
) const { return T::findVar(n
); }
232 /// Get index of first factor involving ns (using T::findFactor)
233 size_t findFactor( const VarSet
&ns
) const { return T::findFactor(ns
); }
235 /// Get number of variables (using T::nrFactors)
236 size_t nrVars() const { return T::nrVars(); }
238 /// Get number of factors (using T::nrFactors)
239 size_t nrFactors() const { return T::nrFactors(); }
241 /// Get const reference to variable i (using T::var)
242 const Var
& var( size_t i
) const { return T::var(i
); }
244 /// Get reference to variable i (using T::var)
245 Var
& var(size_t i
) { return T::var(i
); }
247 /// Get const reference to factor I (using T::factor)
248 const Factor
& factor( size_t I
) const { return T::factor(I
); }
250 /// Get reference to factor I (using T::factor)
251 Factor
& factor( size_t I
) { return T::factor(I
); }
253 /// Factor I has been updated (using T::updatedFactor)
254 void updatedFactor( size_t I
) { T::updatedFactor(I
); }
258 typedef DAIAlg
<FactorGraph
> DAIAlgFG
;
259 typedef DAIAlg
<RegionGraph
> DAIAlgRG
;
262 /// Calculate the marginal of obj on ns by clamping
263 /// all variables in ns and calculating logZ for each joined state
264 Factor
calcMarginal( const InfAlg
& obj
, const VarSet
& ns
, bool reInit
);
267 /// Calculate beliefs of all pairs in ns (by clamping
268 /// nodes in ns and calculating logZ and the beliefs for each state)
269 std::vector
<Factor
> calcPairBeliefs( const InfAlg
& obj
, const VarSet
& ns
, bool reInit
);
272 /// Calculate beliefs of all pairs in ns (by clamping
273 /// pairs in ns and calculating logZ for each joined state)
274 std::vector
<Factor
> calcPairBeliefsNew( const InfAlg
& obj
, const VarSet
& ns
, bool reInit
);
277 /// Calculate 2nd order interactions of the marginal of obj on ns
278 Factor
calcMarginal2ndO( const InfAlg
& obj
, const VarSet
& ns
, bool reInit
);
281 } // end of namespace dai