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