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 n
157 virtual VarSet
delta( const Var
& n
) const = 0;
159 /// Set all factors interacting with n to 1
160 virtual void makeCavity( const Var
& n
) = 0;
162 /// Set factor I to 1
163 virtual void makeFactorCavity( size_t I
) = 0;
165 /// Get index of variable n
166 virtual size_t findVar( const Var
& n
) const = 0;
168 /// Get index of first factor involving ns
169 virtual size_t findFactor( const VarSet
&ns
) const = 0;
171 /// Get number of variables
172 virtual size_t nrVars() const = 0;
174 /// Get number of factors
175 virtual size_t nrFactors() const = 0;
177 /// Get const reference to variable i
178 virtual const Var
& var(size_t i
) const = 0;
180 /// Get reference to variable i
181 virtual Var
& var(size_t i
) = 0;
183 /// Get const reference to factor I
184 virtual const Factor
& factor( size_t I
) const = 0;
186 /// Get reference to factor I
187 virtual Factor
& factor( size_t I
) = 0;
189 /// Factor I has been updated
190 virtual void updatedFactor( size_t I
) = 0;
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;
199 class DAIAlg
: public InfAlg
, public T
{
201 /// Default constructor
202 DAIAlg() : InfAlg(), T() {}
204 /// Construct DAIAlg with empty T but using the specified properties
205 DAIAlg( const Properties
&opts
) : InfAlg( opts
), T() {}
207 /// Construct DAIAlg using the specified properties
208 DAIAlg( const T
& t
, const Properties
&opts
) : InfAlg( opts
), T(t
) {}
211 DAIAlg( const DAIAlg
& x
) : InfAlg(x
), T(x
) {}
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
); }
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
); }
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
); }
226 /// Return all variables that interact with n (using T::delta)
227 VarSet
delta( const Var
& n
) const { return T::delta(n
); }
229 /// Set all factors interacting with n to 1 (using T::makeCavity)
230 void makeCavity( const Var
& n
) { T::makeCavity(n
); }
232 /// Set factor I to 1 (using T::makeFactorCavity)
233 void makeFactorCavity( size_t I
) { T::makeFactorCavity(I
); }
235 /// Get index of variable n (using T::findVar)
236 size_t findVar( const Var
& n
) const { return T::findVar(n
); }
238 /// Get index of first factor involving ns (using T::findFactor)
239 size_t findFactor( const VarSet
&ns
) const { return T::findFactor(ns
); }
241 /// Get number of variables (using T::nrFactors)
242 size_t nrVars() const { return T::nrVars(); }
244 /// Get number of factors (using T::nrFactors)
245 size_t nrFactors() const { return T::nrFactors(); }
247 /// Get const reference to variable i (using T::var)
248 const Var
& var( size_t i
) const { return T::var(i
); }
250 /// Get reference to variable i (using T::var)
251 Var
& var(size_t i
) { return T::var(i
); }
253 /// Get const reference to factor I (using T::factor)
254 const Factor
& factor( size_t I
) const { return T::factor(I
); }
256 /// Get reference to factor I (using T::factor)
257 Factor
& factor( size_t I
) { return T::factor(I
); }
259 /// Factor I has been updated (using T::updatedFactor)
260 void updatedFactor( size_t I
) { T::updatedFactor(I
); }
264 typedef DAIAlg
<FactorGraph
> DAIAlgFG
;
265 typedef DAIAlg
<RegionGraph
> DAIAlgRG
;
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
);
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
);
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
);
283 /// Calculate 2nd order interactions of the marginal of obj on ns
284 Factor
calcMarginal2ndO( const InfAlg
& obj
, const VarSet
& ns
, bool reInit
);
287 } // end of namespace dai