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