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 */

12 /// \file

13 /// \brief Defines the general interface for inference methods in libDAI (classes InfAlg, DaiAlg<>, DaiAlgFG and DaiAlgRG).

16 #ifndef __defined_libdai_daialg_h

17 #define __defined_libdai_daialg_h

20 #include <string>

21 #include <iostream>

22 #include <vector>

23 #include <dai/factorgraph.h>

24 #include <dai/regiongraph.h>

25 #include <dai/properties.h>

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 */

39 /// \name Constructors/destructors

40 //@{

41 /// Virtual destructor (needed because this class contains virtual functions)

44 /// Returns a pointer to a new, cloned copy of \c *this (i.e., virtual copy constructor)

46 //@}

48 /// \name Queries

49 //@{

50 /// Identifies itself for logging purposes

53 /// Returns reference to underlying FactorGraph.

56 /// Returns constant reference to underlying FactorGraph.

58 //@}

60 /// \name Inference interface

61 //@{

62 /// Initializes all data structures of the approximate inference algorithm.

63 /** \note This method should be called at least once before run() is called.

64 */

67 /// Initializes all data structures corresponding to some set of variables.

68 /** This method can be used to do a partial initialization after a part of the factor graph has changed.

69 * Instead of initializing all data structures, it only initializes those involving the variables in \a vs.

70 * \throw NOT_IMPLEMENTED if not implemented/supported

71 */

74 /// Runs the approximate inference algorithm.

75 /** \note Before run() is called the first time, init() should have been called.

76 */

79 /// Returns the (approximate) marginal probability distribution of a variable.

80 /** \note Before this method is called, run() should have been called.

81 */

84 /// Returns the (approximate) marginal probability distribution of a set of variables.

85 /** \note Before this method is called, run() should have been called.

86 * \throw NOT_IMPLEMENTED if not implemented/supported.

87 * \throw BELIEF_NOT_AVAILABLE if the requested belief cannot be calculated with this algorithm.

88 */

91 /// Returns the (approximate) marginal probability distribution of the variable with index \a i.

92 /** For some approximate inference algorithms, using beliefV() is preferred to belief() for performance reasons.

93 * \note Before this method is called, run() should have been called.

94 */

97 /// Returns the (approximate) marginal probability distribution of the variables on which factor \a I depends.

98 /** For some approximate inference algorithms, using beliefF() is preferred to belief() for performance reasons.

99 * \note Before this method is called, run() should have been called.

100 */

103 /// Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm.

104 /** \note Before this method is called, run() should have been called.

105 */

108 /// Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).

109 /** \note Before this method is called, run() should have been called.

110 * \throw NOT_IMPLEMENTED if not implemented/supported

111 */

114 /// Calculates the joint state of all variables that has maximum probability

115 /** \note Before this method is called, run() should have been called.

116 * \throw NOT_IMPLEMENTED if not implemented/supported

117 */

120 /// Returns maximum difference between single variable beliefs in the last iteration.

121 /** \throw NOT_IMPLEMENTED if not implemented/supported

122 */

125 /// Returns number of iterations done (one iteration passes over the complete factorgraph).

126 /** \throw NOT_IMPLEMENTED if not implemented/supported

127 */

129 //@}

131 /// \name Changing the factor graph

132 //@{

133 /// Clamp variable with index \a i to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)

134 /** If \a backup == \c true, make a backup of all factors that are changed.

135 */

138 /// Sets all factors interacting with variable with index \a i to one.

139 /** If \a backup == \c true, make a backup of all factors that are changed.

140 */

142 //@}

144 /// \name Backup/restore mechanism for factors

145 //@{

146 /// Make a backup copy of factor \a I

147 /** \throw MULTIPLE_UNDO if a backup already exists

148 */

150 /// Make backup copies of all factors involving the variables in \a vs

151 /** \throw MULTIPLE_UNDO if a backup already exists

152 */

155 /// Restore factor \a I from its backup copy

157 /// Restore the factors involving the variables in \a vs from their backup copies

159 //@}

161 /// \name Managing parameters

162 //@{

163 /// Set parameters of this inference algorithm.

164 /** The parameters are set according to the PropertySet \a opts.

165 * The values can be stored either as std::string or as the type of the corresponding MF::props member.

166 */

168 /// Returns parameters of this inference algorithm converted into a PropertySet.

170 /// Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".

172 //@}

173 };

176 /// Combines the abstract base class InfAlg with a graphical model (e.g., a FactorGraph or RegionGraph).

177 /** Inference algorithms in libDAI directly inherit from a DAIAlg, currently either

178 * from a DAIAlg<FactorGraph> or from a DAIAlg<RegionGraph>.

179 *

180 * \tparam GRM Should be castable to FactorGraph

181 * \idea A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should

182 * store a reference to the graphical model object. This prevents needless copying

183 * of (possibly large) data structures. Disadvantage: the caller must not change

184 * the graphical model between calls to the inference algorithm (maybe a smart_ptr

185 * or some locking mechanism would help here?).

186 */

190 /// \name Constructors/destructors

191 //@{

192 /// Default constructor

195 /// Construct from GRM

197 //@}

199 /// \name Queries

200 //@{

201 /// Returns reference to underlying FactorGraph.

204 /// Returns constant reference to underlying FactorGraph.

206 //@}

208 /// \name Changing the factor graph

209 //@{

210 /// Clamp variable with index \a i to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)

211 /** If \a backup == \c true, make a backup of all factors that are changed.

212 */

215 /// Sets all factors interacting with variable with index \a i to one.

216 /** If \a backup == \c true, make a backup of all factors that are changed.

217 */

219 //@}

221 /// \name Backup/restore mechanism for factors

222 //@{

223 /// Make a backup copy of factor \a I

225 /// Make backup copies of all factors involving the variables in \a vs

228 /// Restore factor \a I from its backup copy

230 /// Restore the factors involving the variables in \a vs from their backup copies

232 //@}

233 };

236 /// Base class for inference algorithms that operate on a FactorGraph

239 /// Base class for inference algorithms that operate on a RegionGraph

243 /// Calculates the marginal probability distribution for \a vs using inference algorithm \a obj.

244 /** calcMarginal() works by clamping all variables in \a vs and calculating the partition sum for each clamped state.

245 * Therefore, it can be used in combination with any inference algorithm that can calculate/approximate partition sums.

246 * \param obj instance of inference algorithm to be used

247 * \param vs variables for which the marginal should be calculated

248 * \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).

249 */

252 /// Calculates beliefs for all pairs of variables in \a vs using inference algorithm \a obj.

253 /** calcPairBeliefs() works by

254 * - 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;

255 * - clamping pairs of variables in \a vs and calculating the partition sum for each clamped state, if \a accurate == \c true.

256 *

257 * Therefore, it can be used in combination with any inference algorithm that can calculate/approximate partition sums (and single variable beliefs, if

258 * \a accurate == \c true).

259 * \param obj instance of inference algorithm to be used

260 * \param vs variables for which the pair beliefs 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 * \param accurate if \c true, uses a slower but more accurate approximation algorithm

263 */

264 std::vector<Factor> calcPairBeliefs( const InfAlg& obj, const VarSet& vs, bool reInit, bool accurate=false );

270 #endif