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

9 /// \file

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

13 #ifndef __defined_libdai_daialg_h

14 #define __defined_libdai_daialg_h

17 #include <string>

18 #include <iostream>

19 #include <vector>

20 #include <dai/factorgraph.h>

21 #include <dai/regiongraph.h>

22 #include <dai/cobwebgraph.h>

23 #include <dai/properties.h>

29 /// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.

30 /** \idea General marginalization functions like calcMarginal() now copy a complete InfAlg object. Instead,

31 * it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph.

32 * Or they can simply be made methods of the general InfAlg class.

33 * \idea Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().

34 */

37 /// \name Constructors/destructors

38 //@{

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

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

45 /// Returns a pointer to a newly constructed inference algorithm

46 /** \param fg Factor graph on which to perform the inference algorithm;

47 * \param opts Parameters passed to constructor of inference algorithm;

48 */

50 //@}

52 /// \name Queries

53 //@{

54 /// Returns the name of the algorithm

57 /// Identifies itself for logging purposes

60 }

62 /// Returns reference to underlying FactorGraph.

65 /// Returns constant reference to underlying FactorGraph.

67 //@}

69 /// \name Inference interface

70 //@{

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

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

73 */

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

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

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

79 * \throw NOT_IMPLEMENTED if not implemented/supported

80 */

83 /// Runs the approximate inference algorithm.

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

85 */

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

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

90 */

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

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

95 * \throw NOT_IMPLEMENTED if not implemented/supported.

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

97 */

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

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

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

103 */

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

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

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

109 */

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

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

114 */

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

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

119 * \throw NOT_IMPLEMENTED if not implemented/supported

120 */

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

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

125 * \throw NOT_IMPLEMENTED if not implemented/supported

126 */

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

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

131 */

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

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

136 */

139 /// Sets maximum number of iterations (one iteration passes over the complete factorgraph).

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

141 */

143 //@}

145 /// \name Changing the factor graph

146 //@{

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

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

149 */

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

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

154 */

157 /// Sets all factors indicated by \a facInds to one.

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

159 */

161 //@}

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

164 //@{

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

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

167 */

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

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

171 */

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

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

178 //@}

180 /// \name Managing parameters

181 //@{

182 /// Set parameters of this inference algorithm.

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

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

185 */

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

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

191 //@}

192 };

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

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

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

198 *

199 * \tparam GRM Should be castable to FactorGraph

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

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

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

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

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

205 */

209 /// \name Constructors/destructors

210 //@{

211 /// Default constructor

214 /// Construct from GRM

216 //@}

218 /// \name Queries

219 //@{

220 /// Returns reference to underlying FactorGraph.

223 /// Returns constant reference to underlying FactorGraph.

225 //@}

227 /// \name Changing the factor graph

228 //@{

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

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

231 */

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

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

236 */

239 /// Sets all factors indicated by \a facInds to one.

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

241 */

242 void makeRegionCavity( std::vector<size_t> facInds, bool backup ){ GRM::makeRegionCavity( facInds, backup ); }

243 //@}

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

246 //@{

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

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

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

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

256 /// Restore all factors from their backup copies

258 //@}

259 };

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

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

268 /// Base class for GLC that operates on CobwebGraph

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

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

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

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

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

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

278 */

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

283 /** calcPairBeliefs() works by

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

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

286 *

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

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

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

290 * \param vs variables for which the pair beliefs should be calculated

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

292 * \param accurate if \c true, uses a slower but more accurate approximation algorithm

293 */

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

297 /// Calculates the joint state of all variables that has maximum probability, according to the inference algorithm \a obj

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

299 */

306 #endif