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