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