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) 2008-2009 Joris Mooij [joris dot mooij at libdai dot org]

8 */

11 /** \file

12 * \brief Contains additional doxygen documentation

13 *

14 * \todo Improve documentation

15 *

16 * \todo Merge COPYING into doxygen documentation

17 * \todo Merge README into doxygen documentation

18 * \todo Document examples, tests and utils

19 *

20 * \todo Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming

21 *

22 * \todo Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html

23 * \todo Investigate whether switching to cmake as cross-platform build system would be a good idea.

24 *

25 * \todo Replace VarSets by SmallSet<size_t> where appropriate, in order to minimize the use of FactorGraph::findVar().

26 *

27 * \idea Disentangle structures. In particular, ensure that graphical properties are not

28 * entangled with probabilistic properties. For example, a FactorGraph contains several

29 * components:

30 * - a BipartiteGraph

31 * - an array of variable labels

32 * - an array of variable state space sizes

33 * - an array of pointers to factor value vectors

34 * In this way, each factor could be implemented differently, e.g., we could have

35 * some sparse factors, some noisy-OR factors, some dense factors, some arbitrary

36 * precision factors, etc.

37 *

38 * \idea Use Boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.

39 * See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm

40 * I read somewhere that boost::uBLAS concentrates more on correct implementation than on performance.

41 *

42 * \idea Introduce naming scheme:

43 * - all Vars should be named v_..., e.g. v_i instead of i

44 * - all VarSets should be named vs_..., e.g. v_i instead of i

45 * - all Factors should be named f_..., e.g. f_I instead of I

46 * - all indices should be named _..., e.g. _k instead of k

47 * - all iterators should be named i_, e.g. i_i is an iterator to i

48 * - all const_iterators should be named ci_, e.g. ci_i is an iterator to i

49 **/

52 /** \page discussion Discussion of possible improvements

53 * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs

54 *

55 * A FactorGraph and a RegionGraph are often equipped with

56 * additional properties for nodes and edges. The code to initialize those

57 * is often quite similar. Maybe one could abstract this, e.g.:

58 * \code

59 * template <typename Node1Properties, typename Node2Properties, typename EdgeProperties>

60 * class ExtFactorGraph : public FactorGraph {

61 * public:

62 * std::vector<Node1Properties> node1Props;

63 * std::vector<Node2Properties> node2Props;

64 * std::vector<std::vector<EdgeProperties> > edgeProps;

65 * // ...

66 * }

67 * \endcode

68 *

69 * Advantages:

70 * - Less code duplication.

71 * - Easier maintainability.

72 * - Easier to write new inference algorithms.

73 *

74 * Disadvantages:

75 * - Cachability may be worse.

76 * - A problem is the case where there are no properties for either type of nodes or for edges.

77 * Maybe this can be solved using specializations, or using variadac template arguments?

78 * Another possible solution would be to define a "class Empty {}", and add some code

79 * that checks for the typeid, comparing it with Empty, and doing something special in that case

80 * (e.g., not allocating memory).

81 * - The main disadvantage of this approach seems to be that it leads to even more entanglement.

82 * Therefore this is probably a bad idea.

83 *

84 * \section discuss_templates Polymorphism by template parameterization

85 * Instead of polymorphism by inheritance, use polymorphism by template parameterization.

86 * For example, the real reason for introducing the complicated inheritance scheme of dai::InfAlg

87 * was for functions like dai::calcMarginal. Instead, one could use a template function:

88 * \code

89 * template<typename InfAlg>

90 * Factor calcMarginal( const InfAlg &obj, const VarSet &ns, bool reInit );

91 * \endcode

92 * This would assume that the type InfAlg supports certain methods. Ideally, one would use

93 * concepts to define different classes of inference algorithms with different capabilities,

94 * for example the ability to calculate logZ, the ability to calculate marginals, the ability to

95 * calculate bounds, the ability to calculate MAP states, etc. Then, one would use traits

96 * classes in order to be able to query the capabilities of the model. For example, one would be

97 * able to query whether the inference algorithm supports calculation of logZ. Unfortunately,

98 * this is compile-time polymorphism, whereas tests/testdai needs runtime polymorphism.

99 * Therefore this is probably a bad idea.

100 */

103 /** \mainpage libDAI reference manual

104 * \author Joris Mooij

105 * \version git HEAD

106 * \date October 10, 2008

107 *

108 * \section about About libDAI

109 * libDAI is a free/open source C++ library (licensed under GPLv2+) that provides

110 * implementations of various (approximate) inference methods for discrete

111 * graphical models. libDAI supports arbitrary factor graphs with discrete

112 * variables; this includes discrete Markov Random Fields and Bayesian

113 * Networks.

114 *

115 * The library is targeted at researchers. To be able to use the library, a

116 * good understanding of graphical models is needed.

117 *

118 * \section limitations Limitations

119 * libDAI is not intended to be a complete package for approximate inference.

120 * Instead, it should be considered as an "inference engine", providing

121 * various inference methods. In particular, it contains no GUI, currently

122 * only supports its own file format for input and output (although support

123 * for standard file formats may be added later), and provides very limited

124 * visualization functionalities. The only learning method supported currently

125 * is EM for learning factor parameters.

126 *

127 * \section features Features

128 * Currently, libDAI supports the following (approximate) inference methods:

129 * - Exact inference by brute force enumeration;

130 * - Exact inference by junction-tree methods;

131 * - Mean Field;

132 * - Loopy Belief Propagation [\ref KFL01];

133 * - Tree Expectation Propagation [\ref MiQ04];

134 * - Generalized Belief Propagation [\ref YFW05];

135 * - Double-loop GBP [\ref HAK03];

136 * - Various variants of Loop Corrected Belief Propagation

137 * [\ref MoK07, \ref MoR05];

138 * - Gibbs sampler;

139 * - Conditioned BP [\ref EaG09];

140 *

141 * In addition, libDAI supports parameter learning of conditional probability

142 * tables by Expectation Maximization.

143 *

144 * \section language Why C++?

145 * Because libDAI is implemented in C++, it is very fast compared with

146 * implementations in MatLab (a factor 1000 faster is not uncommon).

147 * libDAI does provide a MatLab interface for easy integration with MatLab.

148 */

151 /** \example example.cpp

152 */

155 /** \page quickstart Quick start

156 * An example program illustrating basic usage of libDAI is given in examples/example.cpp.

157 */

160 /** \page bibliography Bibliography

161 * \section Bibliograpy

162 * \anchor KFL01 \ref KFL01

163 * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):

164 * "Factor Graphs and the Sum-Product Algorithm",

165 * <em>IEEE Transactions on Information Theory</em> 47(2):498-519.

166 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572

167 *

168 * \anchor MiQ04 \ref MiQ04

169 * T. Minka and Y. Qi (2004):

170 * "Tree-structured Approximations by Expectation Propagation",

171 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.

172 * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf

173 *

174 * \anchor MoR05 \ref MoR05

175 * A. Montanari and T. Rizzo (2005):

176 * "How to Compute Loop Corrections to the Bethe Approximation",

177 * <em>Journal of Statistical Mechanics: Theory and Experiment</em>

178 * 2005(10)-P10011.

179 * http://stacks.iop.org/1742-5468/2005/P10011

180 *

181 * \anchor YFW05 \ref YFW05

182 * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):

183 * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",

184 * <em>IEEE Transactions on Information Theory</em>

185 * 51(7):2282-2312.

186 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044

187 *

188 * \anchor HAK03 \ref HAK03

189 * T. Heskes and C. A. Albers and H. J. Kappen (2003):

190 * "Approximate Inference and Constrained Optimization",

191 * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.

192 * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz

193 *

194 * \anchor MoK07 \ref MoK07

195 * J. M. Mooij and H. J. Kappen (2007):

196 * "Loop Corrections for Approximate Inference on Factor Graphs",

197 * <em>Journal of Machine Learning Research</em> 8:1113-1143.

198 * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf

199 *

200 * \anchor MoK07b \ref MoK07b

201 * J. M. Mooij and H. J. Kappen (2007):

202 * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",

203 * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.

204 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778

205 *

206 * \anchor EaG09 \ref EaG09

207 * F. Eaton and Z. Ghahramani (2009):

208 * "Choosing a Variable to Clamp",

209 * <em>Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS 2009)</em> 5:145-152

210 * http://jmlr.csail.mit.edu/proceedings/papers/v5/eaton09a/eaton09a.pdf

211 *

212 * \anchor StW99 \ref StW99

213 * A. Steger and N. C. Wormald (1999):

214 * "Generating Random Regular Graphs Quickly",

215 * <em>Combinatorics, Probability and Computing</em> Vol 8, Issue 4, pp. 377-396

216 * http://www.math.uwaterloo.ca/~nwormald/papers/randgen.pdf

217 *

218 * \anchor EMK06 \ref EMK06

219 * G. Elidan and I. McGraw and D. Koller (2006):

220 * "Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing",

221 * <em>Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)</em>

222 */

225 /** \page fileformat libDAI factorgraph file format

226 *

227 * This page describes the .fg fileformat used in libDAI to store factor graphs.

228 * Markov Random Fields are special cases of factor graphs, as are Bayesian

229 * networks. A factor graph can be specified as follows: for each factor, one has

230 * to specify which variables occur in the factor, what their respective

231 * cardinalities (i.e., number of possible values) are, and a table listing all

232 * the values of that factor for all possible configurations of these variables.

233 * A .fg file is not much more than that. It starts with a line containing the

234 * number of factors in that graph, followed by an empty line. Then all factors

235 * are specified, one block for each factor, where the blocks are seperated by

236 * empty lines. Each variable occurring in the factor graph has a unique

237 * identifier, its index (which should be a nonnegative integer). Comment lines

238 * start with #.

239 *

240 * Each block starts with a line containing the number of variables in that

241 * factor. The second line contains the indices of these variables, seperated by

242 * spaces (indices are nonnegative integers and to avoid confusion, it is

243 * suggested to start counting at 0). The third line contains the number of

244 * possible values of each of these variables, also seperated by spaces. Note that

245 * there is some redundancy here, since if a variable appears in more than one

246 * factor, the cardinality of that variable appears several times in the .fg file.

247 * The fourth line contains the number of nonzero entries in the factor table.

248 * The rest of the lines contain these nonzero entries; each entry consists of a

249 * table index, followed by white-space, followed by the value corresponding to

250 * that table index. The most difficult part is getting the indexing right. The

251 * convention that is used is that the left-most variables cycle through their

252 * values the fastest (similar to MATLAB indexing of multidimensional arrays). An

253 * example block describing one factor is:

254 *

255 * 3\n

256 * 4 8 7\n

257 * 3 2 2\n

258 * 11\n

259 * 0 0.1\n

260 * 1 3.5\n

261 * 2 2.8\n

262 * 3 6.3\n

263 * 4 8.4\n

264 * 6 7.4\n

265 * 7 2.4\n

266 * 8 8.9\n

267 * 9 1.3\n

268 * 10 1.6\n

269 * 12 6.4\n

270 * 11 2.6\n

271 *

272 * which corresponds to the following factor:

273 *

274 * \f[

275 * \begin{array}{ccc|c}

276 * x_4 & x_8 & x_7 & \mbox{value}\\

277 * \hline

278 * 0 & 0 & 0 & 0.1\\

279 * 1 & 0 & 0 & 3.5\\

280 * 2 & 0 & 0 & 2.8\\

281 * 0 & 1 & 0 & 6.3\\

282 * 1 & 1 & 0 & 8.4\\

283 * 2 & 1 & 0 & 0.0\\

284 * 0 & 0 & 1 & 7.4\\

285 * 1 & 0 & 1 & 2.4\\

286 * 2 & 0 & 1 & 8.9\\

287 * 0 & 1 & 1 & 1.3\\

288 * 1 & 1 & 1 & 1.6\\

289 * 2 & 1 & 1 & 2.6

290 * \end{array}

291 * \f]

292 *

293 * Note that the value of x_4 changes fastest, followed by that of x_8, and x_7

294 * varies the slowest, corresponding to the second line of the block ("4 8 7").

295 * Further, x_4 can take on three values, and x_8 and x_7 each have two possible

296 * values, as described in the third line of the block ("3 2 2"). The table

297 * contains 11 non-zero entries (all except for the fifth entry). Note that the

298 * eleventh and twelveth entries are interchanged.

299 *

300 * A final note: the internal representation in libDAI of the factor above is

301 * different, because the variables are ordered according to their indices

302 * (i.e., the ordering would be x_4 x_7 x_8) and the values of the table are

303 * stored accordingly, with the variable having the smallest index changing

304 * fastest:

305 *

306 * \f[

307 * \begin{array}{ccc|c}

308 * x_4 & x_7 & x_8 & \mbox{value}\\

309 * \hline

310 * 0 & 0 & 0 & 0.1\\

311 * 1 & 0 & 0 & 3.5\\

312 * 2 & 0 & 0 & 2.8\\

313 * 0 & 1 & 0 & 7.4\\

314 * 1 & 1 & 0 & 2.4\\

315 * 2 & 1 & 0 & 8.9\\

316 * 0 & 0 & 1 & 6.3\\

317 * 1 & 0 & 1 & 8.4\\

318 * 2 & 0 & 1 & 0.0\\

319 * 0 & 1 & 1 & 1.3\\

320 * 1 & 1 & 1 & 1.6\\

321 * 2 & 1 & 1 & 2.6

322 * \end{array}

323 * \f]

324 */

327 /** \page license License

328 * \verbinclude COPYING

329 */