Finished a new release: libDAI v0.2.6
[libdai.git] / include / dai / doc.h
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-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 */
9
10
11 /** \file
12 * \brief Contains additional doxygen documentation
13 *
14 * \todo Replace all Name members by virtual functions (or add virtual functions returning the Name)
15 *
16 * \idea Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming
17 *
18 * \idea Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html
19 *
20 * \idea Disentangle structures. In particular, ensure that graphical properties are not
21 * entangled with probabilistic properties. For example, a FactorGraph contains several components:
22 * - a BipartiteGraph
23 * - an array of variable labels
24 * - an array of variable state space sizes
25 * - an array of pointers to factor value vectors
26 * In this way, each factor could be implemented differently, e.g., we could have
27 * some sparse factors, some noisy-OR factors, some dense factors, some arbitrary
28 * precision factors, etcetera.
29 *
30 * \idea Use boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.
31 * See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
32 * However: I read somewhere that boost::uBLAS concentrates more on correct implementation than on performance.
33 **/
34
35
36 /** \mainpage Reference manual for libDAI - A free/open source C++ library for Discrete Approximate Inference methods
37 * \author Joris Mooij (with contributions of Frederik Eaton)
38 * \version 0.2.6
39 * \date August 5, 2010
40 *
41 * <hr size="1">
42 * \section about About libDAI
43 * libDAI is a free/open source C++ library (licensed under GPL 2+) that provides
44 * implementations of various (approximate) inference methods for discrete
45 * graphical models. libDAI supports arbitrary factor graphs with discrete
46 * variables; this includes discrete Markov Random Fields and Bayesian
47 * Networks.
48 *
49 * The library is targeted at researchers. To be able to use the library, a
50 * good understanding of graphical models is needed.
51 *
52 * The best way to use libDAI is by writing C++ code that invokes the library;
53 * in addition, part of the functionality is accessibly by using the
54 * - command line interface
55 * - (limited) MatLab interface
56 * - (experimental) python interface
57 * - (experimental) octave interface.
58 *
59 * libDAI can be used to implement novel (approximate) inference algorithms
60 * and to easily compare the accuracy and performance with existing algorithms
61 * that have been implemented already.
62 *
63 * A solver using libDAI was amongst the three winners of the UAI 2010 Approximate
64 * Inference Challenge (see http://www.cs.huji.ac.il/project/UAI10/ for more
65 * information). The full source code is provided as part of the library.
66 *
67 * \section features Features
68 * Currently, libDAI supports the following (approximate) inference methods:
69 * - Exact inference by brute force enumeration;
70 * - Exact inference by junction-tree methods;
71 * - Mean Field;
72 * - Loopy Belief Propagation [\ref KFL01];
73 * - Fractional Belief Propagation [\ref WiH03];
74 * - Tree-Reweighted Belief Propagation [\ref WJW03];
75 * - Tree Expectation Propagation [\ref MiQ04];
76 * - Generalized Belief Propagation [\ref YFW05];
77 * - Double-loop GBP [\ref HAK03];
78 * - Various variants of Loop Corrected Belief Propagation
79 * [\ref MoK07, \ref MoR05];
80 * - Gibbs sampler;
81 * - Conditioned Belief Propagation [\ref EaG09];
82 * - Decimation algorithm.
83 *
84 * These inference methods can be used to calculate partition sums, marginals
85 * over subsets of variables, and MAP states (the joint state of variables that
86 * has maximum probability).
87 *
88 * In addition, libDAI supports parameter learning of conditional probability
89 * tables by Expectation Maximization.
90 *
91 * \section limitations Limitations
92 * libDAI is not intended to be a complete package for approximate inference.
93 * Instead, it should be considered as an "inference engine", providing
94 * various inference methods. In particular, it contains no GUI, currently
95 * only supports its own file format for input and output (although support
96 * for standard file formats may be added later), and provides very limited
97 * visualization functionalities. The only learning method supported currently
98 * is Expectation Maximization (or Maximum Likelihood if no data is missing)
99 * for learning factor parameters.
100 *
101 * \section rationale Rationale
102 *
103 * In my opinion, the lack of open source "reference" implementations hampers
104 * progress in research on approximate inference. Methods differ widely in terms
105 * of quality and performance characteristics, which also depend in different
106 * ways on various properties of the graphical models. Finding the best
107 * approximate inference method for a particular application therefore often
108 * requires empirical comparisons. However, implementing and debugging these
109 * methods takes a lot of time which could otherwise be spent on research. I hope
110 * that this code will aid researchers to be able to easily compare various
111 * (existing as well as new) approximate inference methods, in this way
112 * accelerating research and stimulating real-world applications of approximate
113 * inference.
114 *
115 * \section language Language
116 * Because libDAI is implemented in C++, it is very fast compared with
117 * implementations in MatLab (a factor 1000 faster is not uncommon).
118 * libDAI does provide a (limited) MatLab interface for easy integration with MatLab.
119 * It also provides a command line interface and experimental python and octave
120 * interfaces (thanks to Patrick Pletscher).
121 *
122 * \section compatibility Compatibility
123 *
124 * The code has been developed under Debian GNU/Linux with the GCC compiler suite.
125 * libDAI compiles successfully with g++ versions 3.4 up to 4.4.
126 *
127 * libDAI has also been successfully compiled with MS Visual Studio 2008 under Windows
128 * (but not all build targets are supported yet) and with Cygwin under Windows.
129 *
130 * Finally, libDAI has been compiled successfully on MacOS X.
131 *
132 * \section download Downloading libDAI
133 * The libDAI sources and documentation can be downloaded from the libDAI website:
134 * http://www.libdai.org.
135 *
136 * \section support Mailing list
137 * The Google group "libDAI" (http://groups.google.com/group/libdai)
138 * can be used for getting support and discussing development issues.
139 */
140
141
142 /** \page license License
143 * <hr size="1">
144 * \section license-license License
145 *
146 * libDAI is free software; you can redistribute it and/or modify
147 * it under the terms of the GNU General Public License as published by
148 * the Free Software Foundation; either version 2 of the License, or
149 * (at your option) any later version.
150 *
151 * libDAI is distributed in the hope that it will be useful,
152 * but WITHOUT ANY WARRANTY; without even the implied warranty of
153 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
154 * GNU General Public License for more details.
155 *
156 * <hr size="1">
157 * \section license-gpl GNU General Public License version 2
158 *
159 * \verbinclude COPYING
160 */
161
162
163 /** \page citations Citing libDAI
164 * <hr size="1">
165 * \section citations-citations Citing libDAI
166 *
167 * If you write a scientific paper describing research that made substantive use
168 * of this program, please cite the software appropriately, by mentioning the
169 * fashion in which this software was used, including the version number.
170 *
171 * An appropriate citation would be:\n
172 *
173 * Joris M. Mooij et al. (2010) "libDAI 0.2.6: A free/open source C++ library for Discrete
174 * Approximate Inference", http://www.libdai.org
175 *
176 * or in BiBTeX format:
177 *
178 * <pre>
179 * \@misc{mooij2010libdai,
180 * author = "Joris M. Mooij et al.",
181 * title = "lib{DAI} 0.2.6: A free/open source {C}++ library for {D}iscrete {A}pproximate {I}nference",
182 * howpublished = "http://www.libdai.org/",
183 * year = 2010
184 * }
185 * </pre>
186 *
187 * Moreover, as a personal note, I would appreciate it to be informed about any
188 * publications using libDAI at joris dot mooij at libdai dot org.
189 */
190
191
192 /** \page authors Authors
193 * \section authors-authors People who contributed to libDAI
194 *
195 * \verbinclude AUTHORS
196 */
197
198
199 /** \page build Building libDAI
200 * <hr size="1">
201 * \section build-unix Building libDAI under UNIX variants (Linux / Cygwin / Mac OS X)
202 *
203 * \subsection build-unix-preparations Preparations
204 *
205 * You need:
206 * - a recent version of gcc (at least version 3.4)
207 * - GNU make
208 * - recent boost C++ libraries (at least version 1.37; however,
209 * version 1.37 shipped with Ubuntu 9.04 is known not to work)
210 * - doxygen (only for building the documentation)
211 * - graphviz (only for using some of the libDAI command line utilities)
212 * - CImg library (only for building the image segmentation example)
213 *
214 * On Debian/Ubuntu, you can easily install the required packages with a single command:
215 * <pre> apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev libboost-test-dev cimg-dev</pre>
216 * (root permissions needed).
217 *
218 * On Mac OS X (10.4 is known to work), these packages can be installed easily via MacPorts.
219 * If MacPorts is not already installed, install it according to the instructions at http://www.macports.org/.
220 * Then, a simple
221 * <pre> sudo port install gmake boost doxygen graphviz</pre>
222 * should be enough to install everything that is needed.
223 *
224 * On Cygwin, the prebuilt Cygwin package boost-1.33.1-x is known not to work.
225 * You can however obtain the latest boost version (you need at least 1.37.0)
226 * from http://www.boost.org/ and build it as described in the next subsection.
227 *
228 * \subsubsection build-unix-boost Building boost under Cygwin
229 *
230 * - Download the latest boost libraries from http://www.boost.org
231 * - Build the required boost libraries using:
232 * <pre>
233 * ./bootstrap.sh --with-libraries=program_options,math,graph,test --prefix=/boost_root/
234 * ./bjam</pre>
235 * - In order to use dynamic linking, the boost .dll's should be somewhere in the path.
236 * This can be achieved by a command like:
237 * <pre>
238 * export PATH=$PATH:/boost_root/stage/lib</pre>
239 *
240 *
241 * \subsection build-unix-libdai Building libDAI
242 *
243 * To build the libDAI source, first copy a template Makefile.* to Makefile.conf
244 * (for example, copy Makefile.LINUX to Makefile.conf if you use GNU/Linux).
245 * Then, edit the Makefile.conf template to adapt it to your local setup.
246 * Especially directories may differ from system to system. Platform independent
247 * build options can be set in Makefile.ALL. Finally, run
248 * <pre> make</pre>
249 * The build includes a regression test, which may take a while to complete.
250 *
251 * If the build is successful, you can test the example program:
252 * <pre> examples/example tests/alarm.fg</pre>
253 * or the more extensive test program:
254 * <pre> tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>
255 *
256 *
257 * <hr size="1">
258 * \section build-windows Building libDAI under Windows
259 *
260 * \subsection build-windows-preparations Preparations
261 *
262 * You need:
263 * - A recent version of MicroSoft Visual Studio (2008 is known to work)
264 * - recent boost C++ libraries (version 1.37 or higher)
265 * - GNU make (can be obtained from http://gnuwin32.sourceforge.net)
266 * - CImg library (only for building the image segmentation example)
267 *
268 * For the regression test, you need:
269 * - GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)
270 *
271 * \subsubsection build-windows-boost Building boost under Windows
272 *
273 * Because building boost under Windows is tricky, I provide some guidance here.
274 *
275 * - Download the boost zip file from http://www.boost.org/users/download
276 * and unpack it somewhere.
277 * - Download the bjam executable from http://www.boost.org/users/download
278 * and unpack it somewhere else.
279 * - Download Boost.Build (v2) from http://www.boost.org/docs/tools/build/index.html
280 * and unpack it yet somewhere else.
281 * - Edit the file \c boost-build.jam in the main boost directory to change the
282 * \c BOOST_BUILD directory to the place where you put Boost.Build (use UNIX
283 * / instead of Windows \ in pathnames).
284 * - Copy the \c bjam.exe executable into the main boost directory.
285 * Now if you issue <tt>"bjam --version"</tt> you should get a version and no errors.
286 * Issueing <tt>"bjam --show-libraries"</tt> will show the libraries that will be built.
287 * - The following command builds the boost libraries that are relevant for libDAI:
288 * <pre>
289 * bjam --with-graph --with-math --with-program_options --with-test link=static runtime-link=shared</pre>
290 *
291 * \subsection build-windows-libdai Building libDAI
292 *
293 * To build the source, copy Makefile.WINDOWS to Makefile.conf. Then, edit
294 * Makefile.conf to adapt it to your local setup. Platform independent
295 * build options can be set in Makefile.ALL. Finally, run (from the command line)
296 * <pre> make</pre>
297 * The build includes a regression test, which may take a while to complete.
298 *
299 * If the build is successful, you can test the example program:
300 * <pre> examples\\example tests\\alarm.fg</pre>
301 * or the more extensive test program:
302 * <pre> tests\\testdai --aliases tests\\aliases.conf --filename tests\\alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>
303 *
304 *
305 * <hr size="1">
306 * \section build-matlab Building the libDAI MatLab interface
307 *
308 * You need:
309 * - MatLab
310 * - The platform-dependent requirements described above
311 *
312 * First, you need to build the libDAI source as described above for your
313 * platform. By default, the MatLab interface is disabled, so before compiling the
314 * source, you have to enable it in Makefile.ALL by setting
315 * <pre> WITH_MATLAB=true</pre>
316 * Also, you have to configure the MatLab-specific parts of
317 * Makefile.conf to match your system (in particular, the Makefile variables ME,
318 * MATLABDIR and MEX). The MEX file extension depends on your platform; for a
319 * 64-bit linux x86_64 system this would be "ME=.mexa64", for a 32-bit linux x86
320 * system "ME=.mexglx". If you are unsure about your MEX file
321 * extension: it needs to be the same as what the MatLab command "mexext" returns.
322 * The required MEX files are built by issuing
323 * <pre> make</pre>
324 * from the command line. The MatLab interface is much less powerful than using
325 * libDAI from C++. There are two reasons for this: (i) it is boring to write MEX
326 * files; (ii) the large performance penalty paid when large data structures (like
327 * factor graphs) have to be converted between their native C++ data structure to
328 * something that MatLab understands.
329 *
330 * A simple example of how to use the MatLab interface is the following (entered
331 * at the MatLab prompt), which performs exact inference by the junction tree
332 * algorithm and approximate inference by belief propagation on the ALARM network:
333 * <pre> cd path_to_libdai/matlab
334 * [psi] = dai_readfg ('../tests/alarm.fg');
335 * [logZ,q,md,qv,qf] = dai (psi, 'JTREE', '[updates=HUGIN,verbose=0]')
336 * [logZ,q,md,qv,qf] = dai (psi, 'BP', '[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0]')</pre>
337 * where "path_to_libdai" has to be replaced with the directory in which libDAI
338 * was installed. For other algorithms and some default parameters, see the file
339 * tests/aliases.conf.
340 *
341 * <hr size="1">
342 * \section build-doxygen Building the documentation
343 *
344 * Install doxygen, graphviz and a TeX distribution and use
345 * <pre> make doc</pre>
346 * to build the documentation. If the documentation is not clear enough, feel free
347 * to send me an email (or even better, to improve the documentation and send a patch!).
348 * The documentation can also be browsed online at http://www.libdai.org.
349 */
350
351
352 /** \page changelog Change Log
353 * \verbinclude ChangeLog
354 */
355
356
357 /** \page terminology Terminology and conventions
358 *
359 * \section terminology-graphicalmodels Graphical models
360 *
361 * Commonly used graphical models are Bayesian networks and Markov random fields.
362 * In libDAI, both types of graphical models are represented by a slightly more
363 * general type of graphical model: a factor graph [\ref KFL01].
364 *
365 * An example of a Bayesian network is:
366 * \dot
367 * digraph bayesnet {
368 * size="1,1";
369 * x0 [label="0"];
370 * x1 [label="1"];
371 * x2 [label="2"];
372 * x3 [label="3"];
373 * x4 [label="4"];
374 * x0 -> x1;
375 * x0 -> x2;
376 * x1 -> x3;
377 * x1 -> x4;
378 * x2 -> x4;
379 * }
380 * \enddot
381 * The probability distribution of a Bayesian network factorizes as:
382 * \f[ P(\mathbf{x}) = \prod_{i\in\mathcal{V}} P(x_i \,|\, x_{\mathrm{pa}(i)}) \f]
383 * where \f$\mathrm{pa}(i)\f$ are the parents of node \a i in a DAG.
384 *
385 * The same probability distribution can be represented as a Markov random field:
386 * \dot
387 * graph mrf {
388 * size="1.5,1.5";
389 * x0 [label="0"];
390 * x1 [label="1"];
391 * x2 [label="2"];
392 * x3 [label="3"];
393 * x4 [label="4"];
394 * x0 -- x1;
395 * x0 -- x2;
396 * x1 -- x2;
397 * x1 -- x3;
398 * x1 -- x4;
399 * x2 -- x4;
400 * }
401 * \enddot
402 *
403 * The probability distribution of a Markov random field factorizes as:
404 * \f[ P(\mathbf{x}) = \frac{1}{Z} \prod_{C\in\mathcal{C}} \psi_C(x_C) \f]
405 * where \f$ \mathcal{C} \f$ are the cliques of an undirected graph,
406 * \f$ \psi_C(x_C) \f$ are "potentials" or "compatibility functions", and
407 * \f$ Z \f$ is the partition sum which properly normalizes the probability
408 * distribution.
409 *
410 * Finally, the same probability distribution can be represented as a factor graph:
411 * \dot
412 * graph factorgraph {
413 * size="1.8,1";
414 * x0 [label="0"];
415 * x1 [label="1"];
416 * x2 [label="2"];
417 * x3 [label="3"];
418 * x4 [label="4"];
419 * f01 [shape="box",label=""];
420 * f02 [shape="box",label=""];
421 * f13 [shape="box",label=""];
422 * f124 [shape="box",label=""];
423 * x0 -- f01;
424 * x1 -- f01;
425 * x0 -- f02;
426 * x2 -- f02;
427 * x1 -- f13;
428 * x3 -- f13;
429 * x1 -- f124;
430 * x2 -- f124;
431 * x4 -- f124;
432 * }
433 * \enddot
434 *
435 * The probability distribution of a factor graph factorizes as:
436 * \f[ P(\mathbf{x}) = \frac{1}{Z} \prod_{I\in \mathcal{F}} f_I(x_I) \f]
437 * where \f$ \mathcal{F} \f$ are the factor nodes of a factor graph (a
438 * bipartite graph consisting of variable nodes and factor nodes),
439 * \f$ f_I(x_I) \f$ are the factors, and \f$ Z \f$ is the partition sum
440 * which properly normalizes the probability distribution.
441 *
442 * Looking at the expressions for the joint probability distributions,
443 * it is obvious that Bayesian networks and Markov random fields can
444 * both be easily represented as factor graphs. Factor graphs most
445 * naturally express the factorization structure of a probability
446 * distribution, and hence are a convenient representation for approximate
447 * inference algorithms, which all try to exploit this factorization.
448 * This is why libDAI uses a factor graph as representation of a
449 * graphical model, implemented in the dai::FactorGraph class.
450 *
451 * \section terminology-inference Inference tasks
452 *
453 * Given a factor graph, specified by the variable nodes \f$\{x_i\}_{i\in\mathcal{V}}\f$
454 * the factor nodes \f$ \mathcal{F} \f$, the graph structure, and the factors
455 * \f$\{f_I(x_I)\}_{I\in\mathcal{F}}\f$, the following tasks are important:
456 *
457 * - Calculating the partition sum:
458 * \f[ Z = \sum_{\mathbf{x}_{\mathcal{V}}} \prod_{I \in \mathcal{F}} f_I(x_I) \f]
459 * - Calculating the marginal distribution of a subset of variables
460 * \f$\{x_i\}_{i\in A}\f$:
461 * \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]
462 * - Calculating the MAP state which has the maximum probability mass:
463 * \f[ \mathrm{argmax}_{\mathbf{x}}\,\prod_{I\in\mathcal{F}} f_I(x_I) \f]
464 *
465 * libDAI offers several inference algorithms, which solve (a subset of) these tasks either
466 * approximately or exactly, for factor graphs with discrete variables. The following
467 * algorithms are implemented:
468 *
469 * Exact inference:
470 * - Brute force enumeration: dai::ExactInf
471 * - Junction-tree method: dai::JTree
472 *
473 * Approximate inference:
474 * - Mean Field: dai::MF
475 * - (Loopy) Belief Propagation: dai::BP [\ref KFL01]
476 * - Fractional Belief Propagation: dai::FBP [\ref WiH03]
477 * - Tree-Reweighted Belief Propagation: dai::TRWBP [\ref WJW03]
478 * - Tree Expectation Propagation: dai::TreeEP [\ref MiQ04]
479 * - Generalized Belief Propagation: dai::HAK [\ref YFW05]
480 * - Double-loop GBP: dai::HAK [\ref HAK03]
481 * - Loop Corrected Belief Propagation: dai::MR [\ref MoR05] and dai::LC [\ref MoK07]
482 * - Gibbs sampling: dai::Gibbs
483 * - Conditioned Belief Propagation: dai::CBP [\ref EaG09]
484 * - Decimation algorithm: dai::DecMAP
485 *
486 * Not all inference tasks are implemented by each method: calculating MAP states
487 * is only possible with dai::JTree, dai::BP and dai::DECMAP; calculating partition sums is
488 * not possible with dai::MR, dai::LC and dai::Gibbs.
489 *
490 * \section terminology-learning Parameter learning
491 *
492 * In addition, libDAI supports parameter learning of conditional probability
493 * tables by Expectation Maximization (or Maximum Likelihood, if there is no
494 * missing data). This is implemented in dai::EMAlg.
495 *
496 * \section terminology-variables-states Variables and states
497 *
498 * Linear states are a concept that is used often in libDAI, for example for storing
499 * and accessing factors, which are functions mapping from states of a set of variables
500 * to the real numbers. Internally, a factor is stored as an array, and the array index
501 * of an entry corresponds with the linear state of the set of variables. Below we will
502 * define variables, states and linear states of (sets of) variables.
503 *
504 * \subsection terminology-variables Variables
505 *
506 * Each (random) \a variable has a unique identifier, its \a label (which has
507 * a non-negative integer value). If two variables have the same
508 * label, they are considered as identical. A variable can take on a finite
509 * number of different values or \a states.
510 *
511 * We use the following notational conventions. The discrete
512 * random variable with label \f$l\f$ is denoted as \f$x_l\f$, and the number
513 * of possible values of this variable as \f$S_{x_l}\f$ or simply \f$S_l\f$.
514 * The set of possible values of variable \f$x_l\f$ is denoted
515 * \f$X_l := \{0,1,\dots,S_l-1\}\f$ and called its \a state \a space.
516 *
517 * \subsection terminology-variable-sets Sets of variables and the canonical ordering
518 *
519 * Let \f$A := \{x_{l_1},x_{l_2},\dots,x_{l_n}\}\f$ be a set of variables.
520 *
521 * The \a canonical \a ordering of the variables in \a A is induced by their labels.
522 * That is: if \f$l_1 < l_2\f$, then \f$x_{l_1}\f$ occurs before \f$x_{l_2}\f$ in the
523 * canonical ordering. Below, we will assume that \f$(l_i)_{i=1}^n\f$ is
524 * ordered according to the canonical ordering, i.e., \f$l_1 < l_2 < \dots < l_n\f$.
525 *
526 * \subsection terminology-variable-states States and linear states of sets of variables
527 *
528 * A \a state of the variables in \a A refers to a joint assignment of the
529 * variables, or in other words, to an element of the Cartesian product
530 * \f$ \prod_{i=1}^n X_{l_i}\f$ of the state spaces of the variables in \a A.
531 * Note that a state can also be interpreted as a mapping from variables (or
532 * variable labels) to the natural numbers, which assigns to a variable (or its
533 * label) the corresponding state of the variable.
534 *
535 * A state of \a n variables can be represented as an n-tuple of
536 * non-negative integers: \f$(s_1,s_2,\dots,s_n)\f$ corresponds to the
537 * joint assignment \f$x_{l_1} = s_1, \dots, x_{l_n} = s_n\f$.
538 * Alternatively, a state can be represented compactly as one non-negative integer;
539 * this representation is called a \a linear \a state. The linear state
540 * \a s corresponding to the state \f$(s_1,s_2,\dots,s_n)\f$ would be:
541 * \f[
542 * s := \sum_{i=1}^n s_i \prod_{j=1}^{i-1} S_{l_j}
543 * = s_1 + s_2 S_{l_1} + s_3 S_{l_1} S_{l_2} + \dots + s_n S_{l_1} \cdots S_{l_{n-1}}.
544 * \f]
545 *
546 * Vice versa, given a linear state \a s for the variables \a A, the
547 * corresponding state \f$s_i\f$ of the \a i 'th variable \f$x_{l_i}\f$ (according to
548 * the canonical ordering of the variables in \a A) is given by
549 * \f[
550 * s_i = \left\lfloor\frac{s \mbox { mod } \prod_{j=1}^i S_{l_j}}{\prod_{j=1}^{i-1} S_{l_j}}\right\rfloor.
551 * \f]
552 *
553 * Finally, the \a number \a of \a states of the set of variables \a A is simply the
554 * number of different joint assignments of the variables, that is, \f$\prod_{i=1}^n S_{l_i}\f$.
555 */
556
557
558 /** \page fileformats libDAI file formats
559 *
560 * \section fileformats-factorgraph Factor graph (.fg) file format
561 *
562 * This section describes the .fg file format used in libDAI to store factor graphs.
563 * Markov Random Fields are special cases of factor graphs, as are Bayesian
564 * networks. A factor graph can be specified as follows: for each factor, one has
565 * to specify which variables occur in the factor, what their respective
566 * cardinalities (i.e., number of possible values) are, and a table listing all
567 * the values of that factor for all possible configurations of these variables.
568 *
569 * A .fg file is not much more than that. It starts with a line containing the
570 * number of factors in that graph, followed by an empty line. Then all factors
571 * are specified, using one block for each factor, where the blocks are seperated
572 * by empty lines. Each variable occurring in the factor graph has a unique
573 * identifier, its label (which should be a nonnegative integer). Comment lines
574 * which start with # are ignored.
575 *
576 * \subsection fileformats-factorgraph-factor Factor block format
577 *
578 * Each block describing a factor starts with a line containing the number of
579 * variables in that factor. The second line contains the labels of these
580 * variables, seperated by spaces (labels are nonnegative integers and to avoid
581 * confusion, it is suggested to start counting at 0). The third line contains
582 * the number of possible values of each of these variables, also seperated by
583 * spaces. Note that there is some redundancy here, since if a variable appears
584 * in more than one factor, the cardinality of that variable appears several
585 * times in the .fg file; obviously, these cardinalities should be consistent.
586 * The fourth line contains the number of nonzero entries
587 * in the factor table. The rest of the lines contain these nonzero entries;
588 * each line consists of a table index, followed by white-space, followed by the
589 * value corresponding to that table index. The most difficult part is getting
590 * the indexing right. The convention that is used is that the left-most
591 * variables cycle through their values the fastest (similar to MatLab indexing
592 * of multidimensional arrays).
593 *
594 * \subsubsection fileformats-factorgraph-factor-example Example
595 *
596 * An example block describing one factor is:
597 *
598 * <pre>
599 * 3
600 * 4 8 7
601 * 3 2 2
602 * 11
603 * 0 0.1
604 * 1 3.5
605 * 2 2.8
606 * 3 6.3
607 * 4 8.4
608 * 6 7.4
609 * 7 2.4
610 * 8 8.9
611 * 9 1.3
612 * 10 1.6
613 * 11 2.6
614 * </pre>
615 *
616 * which corresponds to the following factor:
617 *
618 * \f[
619 * \begin{array}{ccc|c}
620 * x_4 & x_8 & x_7 & \mbox{value}\\
621 * \hline
622 * 0 & 0 & 0 & 0.1\\
623 * 1 & 0 & 0 & 3.5\\
624 * 2 & 0 & 0 & 2.8\\
625 * 0 & 1 & 0 & 6.3\\
626 * 1 & 1 & 0 & 8.4\\
627 * 2 & 1 & 0 & 0.0\\
628 * 0 & 0 & 1 & 7.4\\
629 * 1 & 0 & 1 & 2.4\\
630 * 2 & 0 & 1 & 8.9\\
631 * 0 & 1 & 1 & 1.3\\
632 * 1 & 1 & 1 & 1.6\\
633 * 2 & 1 & 1 & 2.6
634 * \end{array}
635 * \f]
636 *
637 * Note that the value of \f$x_4\f$ changes fastest, followed by that of \f$x_8\f$, and \f$x_7\f$
638 * varies the slowest, corresponding to the second line of the block ("4 8 7").
639 * Further, \f$x_4\f$ can take on three values, and \f$x_8\f$ and \f$x_7\f$ each have two possible
640 * values, as described in the third line of the block ("3 2 2"). The table
641 * contains 11 non-zero entries (all except for the fifth entry). Note that the
642 * eleventh and twelveth entries are interchanged.
643 *
644 * A final note: the internal representation in libDAI of the factor above is
645 * different, because the variables are ordered according to their indices
646 * (i.e., the ordering would be \f$x_4 x_7 x_8\f$) and the values of the table are
647 * stored accordingly, with the variable having the smallest index changing
648 * fastest:
649 *
650 * \f[
651 * \begin{array}{ccc|c}
652 * x_4 & x_7 & x_8 & \mbox{value}\\
653 * \hline
654 * 0 & 0 & 0 & 0.1\\
655 * 1 & 0 & 0 & 3.5\\
656 * 2 & 0 & 0 & 2.8\\
657 * 0 & 1 & 0 & 7.4\\
658 * 1 & 1 & 0 & 2.4\\
659 * 2 & 1 & 0 & 8.9\\
660 * 0 & 0 & 1 & 6.3\\
661 * 1 & 0 & 1 & 8.4\\
662 * 2 & 0 & 1 & 0.0\\
663 * 0 & 1 & 1 & 1.3\\
664 * 1 & 1 & 1 & 1.6\\
665 * 2 & 1 & 1 & 2.6
666 * \end{array}
667 * \f]
668 *
669 *
670 * \section fileformats-evidence Evidence (.tab) file format
671 *
672 * This section describes the .tab fileformat used in libDAI to store "evidence",
673 * i.e., a data set consisting of multiple samples, where each sample is the
674 * observed joint state of some variables.
675 *
676 * A .tab file is a tabular data file, consisting of a header line, followed by
677 * an empty line, followed by the data points, with one line for each data point.
678 * Each line (apart from the empty one) should have the same number of columns,
679 * where columns are separated by one tab character. Each column corresponds to
680 * a variable. The header line consists of the variable labels (corresponding to
681 * dai::Var::label()). The other lines are observed joint states of the variables, i.e.,
682 * each line corresponds to a joint observation of the variables, and each column
683 * of a line contains the state of the variable associated with that column.
684 * Missing data is handled simply by having two consecutive tab characters,
685 * without any characters in between.
686 *
687 * \subsection fileformats-evidence-example Example
688 *
689 * <pre>
690 * 1 3 2
691 *
692 * 0 0 1
693 * 1 0 1
694 * 1 1
695 * </pre>
696 *
697 * This would correspond to a data set consisting of three observations concerning
698 * the variables with labels 1, 3 and 2; the first observation being
699 * \f$x_1 = 0, x_3 = 0, x_2 = 1\f$, the second observation being
700 * \f$x_1 = 1, x_3 = 0, x_2 = 1\f$, and the third observation being
701 * \f$x_1 = 1, x_2 = 1\f$ (where the state of \f$x_3\f$ is missing).
702 *
703 * \section fileformats-emalg Expectation Maximization (.em) file format
704 *
705 * This section describes the file format of .em files, which are used
706 * to specify a particular EM algorithm. The .em files are complementary
707 * to .fg files; in other words, an .em file without a corresponding .fg
708 * file is useless. Furthermore, one also needs a corresponding .tab file
709 * containing the data used for parameter learning.
710 *
711 * An .em file starts with a line specifying the number of maximization steps,
712 * followed by an empty line. Then, each maximization step is described in a
713 * block, which should satisfy the format described in the next subsection.
714 *
715 * \subsection fileformats-emalg-maximizationstep Maximization Step block format
716 *
717 * A maximization step block of an .em file starts with a single line
718 * describing the number of shared parameters blocks that will follow.
719 * Then, each shared parameters block follows, in the format described in
720 * the next subsection.
721 *
722 * \subsection fileformats-emalg-sharedparameters Shared parameters block format
723 *
724 * A shared parameters block of an .em file starts with a single line
725 * consisting of the name of a ParameterEstimation subclass
726 * and its parameters in the format of a PropertySet. For example:
727 * <pre> CondProbEstimation [target_dim=2,total_dim=4,pseudo_count=1]</pre>
728 * The next line contains the number of factors that share their parameters.
729 * Then, each of these factors is specified on separate lines (possibly
730 * seperated by empty lines), where each line consists of several fields
731 * seperated by a space or a tab character. The first field contains
732 * the index of the factor in the factor graph. The following fields should
733 * contain the variable labels of the variables on which that factor depends,
734 * in a specific ordering. This ordering can be different from the canonical
735 * ordering of the variables used internally in libDAI (which would be sorted
736 * ascendingly according to the variable labels). The ordering of the variables
737 * specifies the implicit ordering of the shared parameters: when iterating
738 * over all shared parameters, the corresponding index of the first variable
739 * changes fastest (in the inner loop), and the corresponding index of the
740 * last variable changes slowest (in the outer loop). By choosing the right
741 * ordering, it is possible to let different factors (depending on different
742 * variables) share parameters in parameter learning using EM. This convention
743 * is similar to the convention used in factor blocks in a factor graph .fg
744 * file (see \ref fileformats-factorgraph-factor).
745 *
746 * \section fileformats-aliases Aliases file format
747 *
748 * An aliases file is basically a list of "macros" and the strings that they
749 * should be substituted with.
750 *
751 * Each line of the aliases file can be either empty, contain a comment
752 * (if the first character is a '#') or contain an alias. In the latter case,
753 * the line should contain a colon; the part before the colon contains the
754 * name of the alias, the part after the colon the string that it should be
755 * substituted with. Any whitespace before and after the colon is ignored.
756 *
757 * For example, the following line would define the alias \c BP_SEQFIX
758 * as a shorthand for "BP[updates=SEQFIX,tol=1e-9,maxiter=10000,logdomain=0]":
759 * <pre>
760 * BP_SEQFIX: BP[updates=SEQFIX,tol=1e-9,maxiter=10000,logdomain=0]
761 * </pre>
762 *
763 * Aliases files can be used to store default options for algorithms.
764 */
765
766 /** \page bibliography Bibliography
767 * \anchor EaG09 \ref EaG09
768 * F. Eaton and Z. Ghahramani (2009):
769 * "Choosing a Variable to Clamp",
770 * <em>Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS 2009)</em> 5:145-152,
771 * http://jmlr.csail.mit.edu/proceedings/papers/v5/eaton09a/eaton09a.pdf
772 *
773 * \anchor EMK06 \ref EMK06
774 * G. Elidan and I. McGraw and D. Koller (2006):
775 * "Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing",
776 * <em>Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)</em>,
777 * http://uai.sis.pitt.edu/papers/06/UAI2006_0091.pdf
778 *
779 * \anchor HAK03 \ref HAK03
780 * T. Heskes and C. A. Albers and H. J. Kappen (2003):
781 * "Approximate Inference and Constrained Optimization",
782 * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320,
783 * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
784 *
785 * \anchor KFL01 \ref KFL01
786 * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
787 * "Factor Graphs and the Sum-Product Algorithm",
788 * <em>IEEE Transactions on Information Theory</em> 47(2):498-519,
789 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
790 *
791 * \anchor KoF09 \ref KoF09
792 * D. Koller and N. Friedman (2009):
793 * <em>Probabilistic Graphical Models - Principles and Techniques</em>,
794 * The MIT Press, Cambridge, Massachusetts, London, England.
795
796 * \anchor Min05 \ref Min05
797 * T. Minka (2005):
798 * "Divergence measures and message passing",
799 * <em>MicroSoft Research Technical Report</em> MSR-TR-2005-173,
800 * http://research.microsoft.com/en-us/um/people/minka/papers/message-passing/minka-divergence.pdf
801 *
802 * \anchor MiQ04 \ref MiQ04
803 * T. Minka and Y. Qi (2004):
804 * "Tree-structured Approximations by Expectation Propagation",
805 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16,
806 * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
807 *
808 * \anchor MoK07 \ref MoK07
809 * J. M. Mooij and H. J. Kappen (2007):
810 * "Loop Corrections for Approximate Inference on Factor Graphs",
811 * <em>Journal of Machine Learning Research</em> 8:1113-1143,
812 * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
813 *
814 * \anchor MoK07b \ref MoK07b
815 * J. M. Mooij and H. J. Kappen (2007):
816 * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
817 * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437,
818 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
819 *
820 * \anchor Moo08 \ref Moo08
821 * J. M. Mooij (2008):
822 * "Understanding and Improving Belief Propagation",
823 * <em>Ph.D. Thesis</em> Radboud University Nijmegen
824 * http://webdoc.ubn.ru.nl/mono/m/mooij_j/undeanimb.pdf
825 *
826 * \anchor MoR05 \ref MoR05
827 * A. Montanari and T. Rizzo (2005):
828 * "How to Compute Loop Corrections to the Bethe Approximation",
829 * <em>Journal of Statistical Mechanics: Theory and Experiment</em> 2005(10)-P10011,
830 * http://stacks.iop.org/1742-5468/2005/P10011
831 *
832 * \anchor StW99 \ref StW99
833 * A. Steger and N. C. Wormald (1999):
834 * "Generating Random Regular Graphs Quickly",
835 * <em>Combinatorics, Probability and Computing</em> Vol 8, Issue 4, pp. 377-396,
836 * http://www.math.uwaterloo.ca/~nwormald/papers/randgen.pdf
837 *
838 * \anchor WiH03 \ref WiH03
839 * W. Wiegerinck and T. Heskes (2003):
840 * "Fractional Belief Propagation",
841 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 15, pp. 438-445,
842 * http://books.nips.cc/papers/files/nips15/LT16.pdf
843 *
844 * \anchor WJW03 \ref WJW03
845 * M. J. Wainwright, T. S. Jaakkola and A. S. Willsky (2003):
846 * "Tree-reweighted belief propagation algorithms and approximate ML estimation by pseudo-moment matching",
847 * <em>9th Workshop on Artificial Intelligence and Statistics</em>,
848 * http://www.eecs.berkeley.edu/~wainwrig/Papers/WJW_AIStat03.pdf
849 *
850 * \anchor YFW05 \ref YFW05
851 * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
852 * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
853 * <em>IEEE Transactions on Information Theory</em> 51(7):2282-2312,
854 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
855 */
856
857
858 /** \page discussion Ideas not worth exploring
859 * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs
860 *
861 * A FactorGraph and a RegionGraph are often equipped with
862 * additional properties for nodes and edges. The code to initialize those
863 * is often quite similar. Maybe one could abstract this, e.g.:
864 * \code
865 * template <typename Node1Properties, typename Node2Properties, typename EdgeProperties>
866 * class ExtFactorGraph : public FactorGraph {
867 * public:
868 * std::vector<Node1Properties> node1Props;
869 * std::vector<Node2Properties> node2Props;
870 * std::vector<std::vector<EdgeProperties> > edgeProps;
871 * // ...
872 * }
873 * \endcode
874 *
875 * Advantages:
876 * - Less code duplication.
877 * - Easier maintainability.
878 * - Easier to write new inference algorithms.
879 *
880 * Disadvantages:
881 * - Cachability may be worse.
882 * - A problem is the case where there are no properties for either type of nodes or for edges.
883 * Maybe this can be solved using specializations, or using variadac template arguments?
884 * Another possible solution would be to define a "class Empty {}", and add some code
885 * that checks for the typeid, comparing it with Empty, and doing something special in that case
886 * (e.g., not allocating memory).
887 * - The main disadvantage of this approach seems to be that it leads to even more entanglement.
888 * Therefore this is probably a bad idea.
889 *
890 * \section discuss_templates Polymorphism by template parameterization
891 *
892 * Instead of polymorphism by inheritance, use polymorphism by template parameterization.
893 * For example, the real reason for introducing the complicated inheritance scheme of dai::InfAlg
894 * was for functions like dai::calcMarginal. Instead, one could use a template function:
895 * \code
896 * template<typename InfAlg>
897 * Factor calcMarginal( const InfAlg &obj, const VarSet &ns, bool reInit );
898 * \endcode
899 * This would assume that the type InfAlg supports certain methods. Ideally, one would use
900 * concepts to define different classes of inference algorithms with different capabilities,
901 * for example the ability to calculate logZ, the ability to calculate marginals, the ability to
902 * calculate bounds, the ability to calculate MAP states, etc. Then, one would use traits
903 * classes in order to be able to query the capabilities of the model. For example, one would be
904 * able to query whether the inference algorithm supports calculation of logZ. Unfortunately,
905 * this is compile-time polymorphism, whereas tests/testdai needs runtime polymorphism.
906 * Therefore this is probably a bad idea.
907 */