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 Write a concept/notations page for the documentation,

15 * explaining the concepts of "state" (index into a

16 * multi-dimensional array, e.g., one corresponding

17 * to the Cartesian product of statespaces of variables)

18 * and "linear index". This should make it easier to

19 * document index.h and varset.h

20 *

21 * \todo Document tests and utils

22 *

23 * \todo Add FAQ

24 *

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

26 *

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

28 *

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

30 *

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

32 * entangled with probabilistic properties. For example, a FactorGraph contains several components:

33 * - a BipartiteGraph

34 * - an array of variable labels

35 * - an array of variable state space sizes

36 * - an array of pointers to factor value vectors

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

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

39 * precision factors, etcetera.

40 *

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

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

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

44 *

45 * \idea Introduce naming scheme:

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

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

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

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

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

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

52 **/

55 /** \mainpage Reference manual for libDAI - A free/open source C++ library for Discrete Approximate Inference methods

56 * \author Joris Mooij

57 * \version git HEAD

58 * \date January 12, 2010 - or later

59 *

60 * <hr size="1">

61 * \section about About libDAI

62 * libDAI is a free/open source C++ library (licensed under GPL 2+) that provides

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

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

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

66 * Networks.

67 *

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

69 * good understanding of graphical models is needed.

70 *

71 * The best way to use libDAI is by writing C++ code that invokes the library;

72 * in addition, part of the functionality is accessibly by using the

73 * - command line interface

74 * - (limited) MatLab interface

75 * - (experimental) python interface

76 * - (experimental) octave interface.

77 *

78 * libDAI can be used to implement novel (approximate) inference algorithms

79 * and to easily compare the accuracy and performance with existing algorithms

80 * that have been implemented already.

81 *

82 * \section features Features

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

84 * - Exact inference by brute force enumeration;

85 * - Exact inference by junction-tree methods;

86 * - Mean Field;

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

88 * - Fractional Belief Propagation [\ref WiH03];

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

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

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

92 * - Various variants of Loop Corrected Belief Propagation

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

94 * - Gibbs sampler;

95 * - Clamped Belief Propagation [\ref EaG09].

96 *

97 * These inference methods can be used to calculate partition sums, marginals

98 * over subsets of variables, and MAP states (the joint state of variables that

99 * has maximum probability).

100 *

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

102 * tables by Expectation Maximization.

103 *

104 * \section limitations Limitations

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

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

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

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

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

110 * visualization functionalities. The only learning method supported currently

111 * is Expectation Maximization (or Maximum Likelihood if no data is missing)

112 * for learning factor parameters.

113 *

114 * \section rationale Rationale

115 *

116 * In my opinion, the lack of open source "reference" implementations hampers

117 * progress in research on approximate inference. Methods differ widely in terms

118 * of quality and performance characteristics, which also depend in different

119 * ways on various properties of the graphical models. Finding the best

120 * approximate inference method for a particular application therefore often

121 * requires empirical comparisons. However, implementing and debugging these

122 * methods takes a lot of time which could otherwise be spent on research. I hope

123 * that this code will aid researchers to be able to easily compare various

124 * (existing as well as new) approximate inference methods, in this way

125 * accelerating research and stimulating real-world applications of approximate

126 * inference.

127 *

128 * \section language Language

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

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

131 * libDAI does provide a (limited) MatLab interface for easy integration with MatLab.

132 * It also provides a command line interface and experimental python and octave

133 * interfaces (thanks to Patrick Pletscher).

134 *

135 * \section compatibility Compatibility

136 *

137 * The code has been developed under Debian GNU/Linux with the GCC compiler suite.

138 * libDAI compiles successfully with g++ versions 3.4, 4.1, 4.2 and 4.3.

139 *

140 * libDAI has also been successfully compiled with MS Visual Studio 2008 under Windows

141 * (but not all build targets are supported yet) and with Cygwin under Windows.

142 *

143 * Finally, libDAI has been compiled successfully on MacOS X.

144 *

145 * \section download Downloading libDAI

146 * The libDAI sources and documentation can be downloaded from the libDAI website:

147 * http://www.libdai.org.

148 *

149 * \section support Mailing list

150 * The Google group "libDAI" (http://groups.google.com/group/libdai)

151 * can be used for getting support and discussing development issues.

152 */

155 /** \page license License

156 * <hr size="1">

157 * \section license-license License

158 *

159 * libDAI is free software; you can redistribute it and/or modify

160 * it under the terms of the GNU General Public License as published by

161 * the Free Software Foundation; either version 2 of the License, or

162 * (at your option) any later version.

163 *

164 * libDAI is distributed in the hope that it will be useful,

165 * but WITHOUT ANY WARRANTY; without even the implied warranty of

166 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

167 * GNU General Public License for more details.

168 *

169 * <hr size="1">

170 * \section license-gpl GNU General Public License version 2

171 *

172 * \verbinclude COPYING

173 */

176 /** \page citations Citing libDAI

177 * <hr size="1">

178 * \section citations-citations Citing libDAI

179 *

180 * If you write a scientific paper describing research that made substantive use

181 * of this program, please:

182 * - mention the fashion in which this software was

183 * used, including the version number, with a citation to the literature,

184 * to allow replication;

185 * - mention this software in the Acknowledgements section.

186 *

187 * An appropriate citation would be:\n

188 * J. M. Mooij (2009) "libDAI 0.2.3: A free/open source C++ library for Discrete

189 * Approximate Inference", http://www.libdai.org

190 *

191 * Moreover, as a personal note, I would appreciate it if you would email

192 * (citations of) papers referencing this work to joris dot mooij at libdai dot org.

193 */

196 /** \page authors Authors

197 * \section authors-authors People who contributed to libDAI

198 *

199 * \verbinclude AUTHORS

200 */

203 /** \page build Building libDAI

204 * <hr size="1">

205 * \section build-unix Building libDAI under UNIX variants (Linux / Cygwin / Mac OS X)

206 *

207 * You need:

208 * - a recent version of gcc (at least version 3.4)

209 * - GNU make

210 * - doxygen

211 * - graphviz

212 * - recent boost C++ libraries (at least version 1.34, or 1.37 for cygwin;

213 * version 1.37 shipped with Ubuntu 9.04 is known not to work)

214 *

215 * On Debian/Ubuntu, you can easily install all these packages with a single command:

216 * <pre> apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev</pre>

217 * (root permissions needed).

218 *

219 * On Mac OS X (10.4 is known to work), these packages can be installed easily via MacPorts.

220 * If MacPorts is not already installed, install it according to the instructions at http://www.macports.org/.

221 * Then, a simple

222 * <pre> sudo port install gmake boost doxygen graphviz</pre>

223 * should be enough to install everything that is needed.

224 *

225 * On Cygwin, the prebuilt Cygwin package boost-1.33.1-x is known not to work.

226 * You can however obtain the latest boost version (you need at least 1.37.0)

227 * from http://www.boost.org/ and compile/install it with:

228 *

229 * <pre> ./configure

230 * make

231 * make install

232 * </pre>

233 *

234 * To build the libDAI source, first copy a template Makefile.* to Makefile.conf

235 * (for example, copy Makefile.LINUX to Makefile.conf if you use GNU/Linux).

236 * Then, edit the Makefile.conf template to adapt it to your local setup.

237 * Especially directories may differ from system to system. Finally, run

238 * <pre> make</pre>

239 * The build includes a regression test, which may take a while to complete.

240 *

241 * If the build was successful, you can test the example program:

242 * <pre> examples/example tests/alarm.fg</pre>

243 * or the more elaborate test program:

244 * <pre> tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>

245 *

246 *

247 * <hr size="1">

248 * \section build-windows Building libDAI under Windows

249 *

250 * You need:

251 * - A recent version of MicroSoft Visual Studio (2008 works)

252 * - recent boost C++ libraries (version 1.34 or higher)

253 * - GNU make (can be obtained from http://gnuwin32.sourceforge.net)

254 *

255 * For the regression test, you need:

256 * - GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)

257 *

258 * To build the source, copy Makefile.WINDOWS to Makefile.conf. Then, edit

259 * Makefile.conf to adapt it to your local setup. Finally, run (from the command line)

260 * <pre> make</pre>

261 * The build includes a regression test, which may take a while to complete.

262 *

263 * If the build was successful, you can test the example program:

264 * <pre> examples\\example tests\\alarm.fg</pre>

265 * or the more elaborate test program:

266 * <pre> tests\\testdai --aliases tests\\aliases.conf --filename tests\\alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>

267 *

268 *

269 * <hr size="1">

270 * \section build-matlab Building the libDAI MatLab interface

271 *

272 * You need:

273 * - MatLab

274 * - The platform-dependent requirements described above

275 *

276 * First, you need to build the libDAI source as described above for your

277 * platform. By default, the MatLab interface is disabled, so before compiling the

278 * source, you have to enable it in the Makefile.conf by setting

279 * <pre> WITH_MATLAB=true</pre>

280 * Also, you have to configure the MatLab-specific parts of

281 * Makefile.conf to match your system (in particular, the Makefile variables ME,

282 * MATLABDIR and MEX). The MEX file extension depends on your platform; for a

283 * 64-bit linux x86_64 system this would be "ME=.mexa64", for a 32-bit linux x86

284 * system "ME=.mexglx". If you are unsure about your MEX file

285 * extension: it needs to be the same as what the MatLab command "mexext" returns.

286 * The required MEX files are built by issuing

287 * <pre> make</pre>

288 * from the command line. The MatLab interface is much less powerful than using

289 * libDAI from C++. There are two reasons for this: (i) it is boring to write MEX

290 * files; (ii) the large performance penalty paid when large data structures (like

291 * factor graphs) have to be converted between their native C++ data structure to

292 * something that MatLab understands.

293 *

294 * A simple example of how to use the MatLab interface is the following (entered

295 * at the MatLab prompt), which performs exact inference by the junction tree

296 * algorithm and approximate inference by belief propagation on the ALARM network:

297 * <pre> cd path_to_libdai/matlab

298 * [psi] = dai_readfg ('../examples/alarm.fg');

299 * [logZ,q,md,qv,qf] = dai (psi, 'JTREE', '[updates=HUGIN,verbose=0]')

300 * [logZ,q,md,qv,qf] = dai (psi, 'BP', '[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0]')</pre>

301 * where "path_to_libdai" has to be replaced with the directory in which libDAI

302 * was installed. For other algorithms and some default parameters, see the file

303 * tests/aliases.conf.

304 *

305 * <hr size="1">

306 * \section build-doxygen Building the documentation

307 *

308 * Install doxygen, graphviz and a TeX distribution and use

309 * <pre> make doc</pre>

310 * to build the documentation. If the documentation is not clear enough, feel free

311 * to send me an email (or even better, to improve the documentation and send a patch!).

312 * The documentation can also be browsed online at http://www.libdai.org.

313 */

316 /** \page changelog Change Log

317 * \verbinclude ChangeLog

318 */

321 /** \page inference Graphical models and approximate inference

322 *

323 * \section inference-graphicalmodels Graphical models

324 *

325 * Commonly used graphical models are Bayesian networks and Markov random fields.

326 * In libDAI, both types of graphical models are represented by a slightly more

327 * general type of graphical model: a factor graph [\ref KFL01].

328 *

329 * An example of a Bayesian network is:

330 * \dot

331 * digraph bayesnet {

332 * size="1,1";

333 * x0 [label="0"];

334 * x1 [label="1"];

335 * x2 [label="2"];

336 * x3 [label="3"];

337 * x4 [label="4"];

338 * x0 -> x1;

339 * x0 -> x2;

340 * x1 -> x3;

341 * x1 -> x4;

342 * x2 -> x4;

343 * }

344 * \enddot

345 * The probability distribution of a Bayesian network factorizes as:

346 * \f[ P(\mathbf{x}) = \prod_{i\in\mathcal{V}} P(x_i \,|\, x_{\mathrm{pa}(i)}) \f]

347 * where \f$\mathrm{pa}(i)\f$ are the parents of node \a i in a DAG.

348 *

349 * The same probability distribution can be represented as a Markov random field:

350 * \dot

351 * graph mrf {

352 * size="1.5,1.5";

353 * x0 [label="0"];

354 * x1 [label="1"];

355 * x2 [label="2"];

356 * x3 [label="3"];

357 * x4 [label="4"];

358 * x0 -- x1;

359 * x0 -- x2;

360 * x1 -- x2;

361 * x1 -- x3;

362 * x1 -- x4;

363 * x2 -- x4;

364 * }

365 * \enddot

366 *

367 * The probability distribution of a Markov random field factorizes as:

368 * \f[ P(\mathbf{x}) = \frac{1}{Z} \prod_{C\in\mathcal{C}} \psi_C(x_C) \f]

369 * where \f$ \mathcal{C} \f$ are the cliques of an undirected graph,

370 * \f$ \psi_C(x_C) \f$ are "potentials" or "compatibility functions", and

371 * \f$ Z \f$ is the partition sum which properly normalizes the probability

372 * distribution.

373 *

374 * Finally, the same probability distribution can be represented as a factor graph:

375 * \dot

376 * graph factorgraph {

377 * size="1.8,1";

378 * x0 [label="0"];

379 * x1 [label="1"];

380 * x2 [label="2"];

381 * x3 [label="3"];

382 * x4 [label="4"];

383 * f01 [shape="box",label=""];

384 * f02 [shape="box",label=""];

385 * f13 [shape="box",label=""];

386 * f124 [shape="box",label=""];

387 * x0 -- f01;

388 * x1 -- f01;

389 * x0 -- f02;

390 * x2 -- f02;

391 * x1 -- f13;

392 * x3 -- f13;

393 * x1 -- f124;

394 * x2 -- f124;

395 * x4 -- f124;

396 * }

397 * \enddot

398 *

399 * The probability distribution of a factor graph factorizes as:

400 * \f[ P(\mathbf{x}) = \frac{1}{Z} \prod_{I\in \mathcal{F}} f_I(x_I) \f]

401 * where \f$ \mathcal{F} \f$ are the factor nodes of a factor graph (a

402 * bipartite graph consisting of variable nodes and factor nodes),

403 * \f$ f_I(x_I) \f$ are the factors, and \f$ Z \f$ is the partition sum

404 * which properly normalizes the probability distribution.

405 *

406 * Looking at the expressions for the joint probability distributions,

407 * it is obvious that Bayesian networks and Markov random fields can

408 * both be easily represented as factor graphs. Factor graphs most

409 * naturally express the factorization structure of a probability

410 * distribution, and hence are a convenient representation for approximate

411 * inference algorithms, which all try to exploit this factorization.

412 * This is why libDAI uses a factor graph as representation of a

413 * graphical model, implemented in the dai::FactorGraph class.

414 *

415 * \section inference-inference Inference tasks

416 *

417 * Given a factor graph, specified by the variable nodes \f$\{x_i\}_{i\in\mathcal{V}}\f$

418 * the factor nodes \f$ \mathcal{F} \f$, the graph structure, and the factors

419 * \f$\{f_I(x_I)\}_{I\in\mathcal{F}}\f$, the following tasks are important:

420 *

421 * - Calculating the partition sum:

422 * \f[ Z = \sum_{\mathbf{x}_{\mathcal{V}}} \prod_{I \in \mathcal{F}} f_I(x_I) \f]

423 * - Calculating the marginal distribution of a subset of variables

424 * \f$\{x_i\}_{i\in A}\f$:

425 * \f[ P(\mathbf{x}_{A}) = \frac{1}{Z} \sum_{\mathbf{x}_{\mathcal{V}\setminus A}} \prod_{I \in \mathcal{F}} f_I(x_I) \f]

426 * - Calculating the MAP state which has the maximum probability mass:

427 * \f[ \mathrm{argmax}_{\mathbf{x}}\,\prod_{I\in\mathcal{F}} f_I(x_I) \f]

428 *

429 * libDAI offers several inference algorithms, which solve (a subset of) these tasks either

430 * approximately or exactly, for factor graphs with discrete variables. The following

431 * algorithms are implemented:

432 *

433 * Exact inference:

434 * - Brute force enumeration: dai::ExactInf

435 * - Junction-tree method: dai::JTree

436 *

437 * Approximate inference:

438 * - Mean Field: dai::MF

439 * - (Loopy) Belief Propagation: dai::BP [\ref KFL01]

440 * - Tree Expectation Propagation: dai::TreeEP [\ref MiQ04]

441 * - Generalized Belief Propagation: dai::HAK [\ref YFW05]

442 * - Double-loop GBP: dai::HAK [\ref HAK03]

443 * - Loop Corrected Belief Propagation: dai::MR [\ref MoR05] and dai::LC [\ref MoK07]

444 * - Gibbs sampling: dai::Gibbs

445 * - Clamped Belief Propagation: dai::CBP [\ref EaG09]

446 *

447 * Not all inference tasks are implemented by each method: calculating MAP states

448 * is only possible with dai::JTree and dai::BP, calculating partition sums is

449 * not possible with dai::MR, dai::LC and dai::Gibbs.

450 *

451 * \section inference-learning Parameter learning

452 *

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

454 * tables by Expectation Maximization (or Maximum Likelihood, if there is no

455 * missing data). This is implemented in dai::EMAlg.

456 *

457 */

460 /** \page fileformats libDAI file formats

461 *

462 * \section fileformats-factorgraph Factor graph (.fg) file format

463 *

464 * This section describes the .fg file format used in libDAI to store factor graphs.

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

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

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

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

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

470 *

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

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

473 * are specified, using one block for each factor, where the blocks are seperated

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

475 * identifier, its label (which should be a nonnegative integer). Comment lines

476 * which start with # are ignored.

477 *

478 * \subsection fileformats-factorgraph-factor Factor block format

479 *

480 * Each block describing a factor starts with a line containing the number of

481 * variables in that factor. The second line contains the labels of these

482 * variables, seperated by spaces (labels are nonnegative integers and to avoid

483 * confusion, it is suggested to start counting at 0). The third line contains

484 * the number of possible values of each of these variables, also seperated by

485 * spaces. Note that there is some redundancy here, since if a variable appears

486 * in more than one factor, the cardinality of that variable appears several

487 * times in the .fg file; obviously, these cardinalities should be consistent.

488 * The fourth line contains the number of nonzero entries

489 * in the factor table. The rest of the lines contain these nonzero entries;

490 * each line consists of a table index, followed by white-space, followed by the

491 * value corresponding to that table index. The most difficult part is getting

492 * the indexing right. The convention that is used is that the left-most

493 * variables cycle through their values the fastest (similar to MatLab indexing

494 * of multidimensional arrays).

495 *

496 * \subsubsection fileformats-factorgraph-factor-example Example

497 *

498 * An example block describing one factor is:

499 *

500 * <pre>

501 * 3

502 * 4 8 7

503 * 3 2 2

504 * 11

505 * 0 0.1

506 * 1 3.5

507 * 2 2.8

508 * 3 6.3

509 * 4 8.4

510 * 6 7.4

511 * 7 2.4

512 * 8 8.9

513 * 9 1.3

514 * 10 1.6

515 * 12 6.4

516 * 11 2.6

517 * </pre>

518 *

519 * which corresponds to the following factor:

520 *

521 * \f[

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

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

524 * \hline

525 * 0 & 0 & 0 & 0.1\\

526 * 1 & 0 & 0 & 3.5\\

527 * 2 & 0 & 0 & 2.8\\

528 * 0 & 1 & 0 & 6.3\\

529 * 1 & 1 & 0 & 8.4\\

530 * 2 & 1 & 0 & 0.0\\

531 * 0 & 0 & 1 & 7.4\\

532 * 1 & 0 & 1 & 2.4\\

533 * 2 & 0 & 1 & 8.9\\

534 * 0 & 1 & 1 & 1.3\\

535 * 1 & 1 & 1 & 1.6\\

536 * 2 & 1 & 1 & 2.6

537 * \end{array}

538 * \f]

539 *

540 * Note that the value of \f$x_4\f$ changes fastest, followed by that of \f$x_8\f$, and \f$x_7\f$

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

542 * Further, \f$x_4\f$ can take on three values, and \f$x_8\f$ and \f$x_7\f$ each have two possible

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

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

545 * eleventh and twelveth entries are interchanged.

546 *

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

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

549 * (i.e., the ordering would be \f$x_4 x_7 x_8\f$) and the values of the table are

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

551 * fastest:

552 *

553 * \f[

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

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

556 * \hline

557 * 0 & 0 & 0 & 0.1\\

558 * 1 & 0 & 0 & 3.5\\

559 * 2 & 0 & 0 & 2.8\\

560 * 0 & 1 & 0 & 7.4\\

561 * 1 & 1 & 0 & 2.4\\

562 * 2 & 1 & 0 & 8.9\\

563 * 0 & 0 & 1 & 6.3\\

564 * 1 & 0 & 1 & 8.4\\

565 * 2 & 0 & 1 & 0.0\\

566 * 0 & 1 & 1 & 1.3\\

567 * 1 & 1 & 1 & 1.6\\

568 * 2 & 1 & 1 & 2.6

569 * \end{array}

570 * \f]

571 *

572 *

573 * \section fileformats-evidence Evidence (.tab) file format

574 *

575 * This section describes the .tab fileformat used in libDAI to store "evidence",

576 * i.e., a data set consisting of multiple samples, where each sample is the

577 * observed joint state of some variables.

578 *

579 * A .tab file is a tabular data file, consisting of a header line, followed by

580 * an empty line, followed by the data points, with one line for each data point.

581 * Each line (apart from the empty one) should have the same number of columns,

582 * where columns are separated by one tab character. Each column corresponds to

583 * a variable. The header line consists of the variable labels (corresponding to

584 * dai::Var::label()). The other lines are observed joint states of the variables, i.e.,

585 * each line corresponds to a joint observation of the variables, and each column

586 * of a line contains the state of the variable associated with that column.

587 * Missing data is handled simply by having two consecutive tab characters,

588 * without any characters in between.

589 *

590 * \subsection fileformats-evidence-example Example

591 *

592 * <pre>

593 * 1 3 2

594 *

595 * 0 0 1

596 * 1 0 1

597 * 1 1

598 * </pre>

599 *

600 * This would correspond to a data set consisting of three observations concerning

601 * the variables with labels 1, 3 and 2; the first observation being

602 * \f$x_1 = 0, x_3 = 0, x_2 = 1\f$, the second observation being

603 * \f$x_1 = 1, x_3 = 0, x_2 = 1\f$, and the third observation being

604 * \f$x_1 = 1, x_2 = 1\f$ (where the state of \f$x_3\f$ is missing).

605 *

606 * \section fileformats-emalg Expectation Maximization (.em) file format

607 *

608 * This section describes the file format of .em files, which are used

609 * to specify a particular EM algorithm. The .em files are complementary

610 * to .fg files; in other words, an .em file without a corresponding .fg

611 * file is useless. Furthermore, one also needs a corresponding .tab file

612 * containing the data used for parameter learning.

613 *

614 * An .em file starts with a line specifying the number of maximization steps,

615 * followed by an empty line. Then, each maximization step is described in a

616 * block, which should satisfy the format described in the next subsection.

617 *

618 * \subsection fileformats-emalg-maximizationstep Maximization Step block format

619 *

620 * A maximization step block of an .em file starts with a single line

621 * describing the number of shared parameters blocks that will follow.

622 * Then, each shared parameters block follows, in the format described in

623 * the next subsection.

624 *

625 * \subsection fileformats-emalg-sharedparameters Shared parameters block format

626 *

627 * A shared parameters block of an .em file starts with a single line

628 * consisting of the name of a ParameterEstimation subclass

629 * and its parameters in the format of a PropertySet. For example:

630 * <pre> CondProbEstimation [target_dim=2,total_dim=4,pseudo_count=1]</pre>

631 * The next line contains the number of factors that share their parameters.

632 * Then, each of these factors is specified on separate lines (possibly

633 * seperated by empty lines), where each line consists of several fields

634 * seperated by a space or a tab character. The first field contains

635 * the index of the factor in the factor graph. The following fields should

636 * contain the variable labels of the variables on which that factor depends,

637 * in a specific ordering. This ordering can be different from the canonical

638 * ordering of the variables used internally in libDAI (which would be sorted

639 * ascendingly according to the variable labels). The ordering of the variables

640 * specifies the implicit ordering of the shared parameters: when iterating

641 * over all shared parameters, the corresponding index of the first variable

642 * changes fastest (in the inner loop), and the corresponding index of the

643 * last variable changes slowest (in the outer loop). By choosing the right

644 * ordering, it is possible to let different factors (depending on different

645 * variables) share parameters in parameter learning using EM. This convention

646 * is similar to the convention used in factor blocks in a factor graph .fg

647 * file (see \ref fileformats-factorgraph-factor).

648 */

650 /** \page bibliography Bibliography

651 * \anchor KFL01 \ref KFL01

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

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

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

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

656 *

657 * \anchor MiQ04 \ref MiQ04

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

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

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

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

662 *

663 * \anchor MoR05 \ref MoR05

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

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

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

667 * 2005(10)-P10011.

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

669 *

670 * \anchor YFW05 \ref YFW05

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

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

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

674 * 51(7):2282-2312.

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

676 *

677 * \anchor HAK03 \ref HAK03

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

679 * "Approximate Inference and Constrained Optimization",

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

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

682 *

683 * \anchor MoK07 \ref MoK07

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

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

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

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

688 *

689 * \anchor MoK07b \ref MoK07b

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

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

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

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

694 *

695 * \anchor EaG09 \ref EaG09

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

697 * "Choosing a Variable to Clamp",

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

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

700 *

701 * \anchor StW99 \ref StW99

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

703 * "Generating Random Regular Graphs Quickly",

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

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

706 *

707 * \anchor EMK06 \ref EMK06

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

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

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

711 * http://uai.sis.pitt.edu/papers/06/UAI2006_0091.pdf

712 *

713 * \anchor WiH03 \ref WiH03

714 * W. Wiegerinck and T. Heskes (2003):

715 * "Fractional Belief Propagation",

716 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 15, pp. 438-445.

717 * http://books.nips.cc/papers/files/nips15/LT16.pdf

718 *

719 * \anchor Min05 \ref Min05

720 * T. Minka (2005):

721 * "Divergence measures and message passing",

722 * <em>MicroSoft Research Technical Report</em> MSR-TR-2005-173,

723 * http://research.microsoft.com/en-us/um/people/minka/papers/message-passing/minka-divergence.pdf

724 */

727 /** \page discussion Ideas not worth exploring

728 * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs

729 *

730 * A FactorGraph and a RegionGraph are often equipped with

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

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

733 * \code

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

735 * class ExtFactorGraph : public FactorGraph {

736 * public:

737 * std::vector<Node1Properties> node1Props;

738 * std::vector<Node2Properties> node2Props;

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

740 * // ...

741 * }

742 * \endcode

743 *

744 * Advantages:

745 * - Less code duplication.

746 * - Easier maintainability.

747 * - Easier to write new inference algorithms.

748 *

749 * Disadvantages:

750 * - Cachability may be worse.

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

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

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

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

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

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

757 * Therefore this is probably a bad idea.

758 *

759 * \section discuss_templates Polymorphism by template parameterization

760 *

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

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

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

764 * \code

765 * template<typename InfAlg>

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

767 * \endcode

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

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

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

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

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

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

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

775 * Therefore this is probably a bad idea.

776 */