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