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/properties.h>

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

36 /// \name Constructors/destructors

37 //@{

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

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

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

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

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

47 */

49 //@}

51 /// \name Queries

52 //@{

53 /// Returns the name of the algorithm

56 /// Identifies itself for logging purposes

59 }

61 /// Returns reference to underlying FactorGraph.

64 /// Returns constant reference to underlying FactorGraph.

66 //@}

68 /// \name Inference interface

69 //@{

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

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

72 */

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

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

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

78 * \throw NOT_IMPLEMENTED if not implemented/supported

79 */

82 /// Runs the approximate inference algorithm.

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

84 */

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

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

89 */

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

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

94 * \throw NOT_IMPLEMENTED if not implemented/supported.

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

96 */

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

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

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

102 */

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

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

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

108 */

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

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

113 */

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

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

118 * \throw NOT_IMPLEMENTED if not implemented/supported

119 */

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

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

124 * \throw NOT_IMPLEMENTED if not implemented/supported

125 */

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

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

130 */

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

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

135 */

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

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

140 */

142 //@}

144 /// \name Changing the factor graph

145 //@{

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

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

148 */

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

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

153 */

155 //@}

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

158 //@{

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

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

161 */

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

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

165 */

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

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

172 //@}

174 /// \name Managing parameters

175 //@{

176 /// Set parameters of this inference algorithm.

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

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

179 */

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

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

185 //@}

186 };

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

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

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

192 *

193 * \tparam GRM Should be castable to FactorGraph

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

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

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

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

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

199 */

203 /// \name Constructors/destructors

204 //@{

205 /// Default constructor

208 /// Construct from GRM

210 //@}

212 /// \name Queries

213 //@{

214 /// Returns reference to underlying FactorGraph.

217 /// Returns constant reference to underlying FactorGraph.

219 //@}

221 /// \name Changing the factor graph

222 //@{

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

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

225 */

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

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

230 */

232 //@}

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

235 //@{

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

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

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

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

245 //@}

246 };

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

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

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

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

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

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

260 * \param vs variables for which the marginal 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 */

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

267 /** calcPairBeliefs() works by

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

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

270 *

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

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

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

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

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

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

277 */

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

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

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

283 */

290 #endif