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