Improved documentation
[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-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 */
9
10
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 **/
53
54
55 /** \mainpage Reference manual for libDAI - A free/open source C++ library for Discrete Approximate Inference methods
56 * \author Joris Mooij
57 * \version DAI_VERSION
58 * \date DAI_DATE
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 * - Tree Expectation Propagation [\ref MiQ04];
89 * - Generalized Belief Propagation [\ref YFW05];
90 * - Double-loop GBP [\ref HAK03];
91 * - Various variants of Loop Corrected Belief Propagation
92 * [\ref MoK07, \ref MoR05];
93 * - Gibbs sampler;
94 * - Conditioned BP [\ref EaG09].
95 *
96 * These inference methods can be used to calculate partition sums, marginals
97 * over subsets of variables, and MAP states (the joint state of variables that
98 * has maximum probability).
99 *
100 * In addition, libDAI supports parameter learning of conditional probability
101 * tables by Expectation Maximization.
102 *
103 * \section limitations Limitations
104 * libDAI is not intended to be a complete package for approximate inference.
105 * Instead, it should be considered as an "inference engine", providing
106 * various inference methods. In particular, it contains no GUI, currently
107 * only supports its own file format for input and output (although support
108 * for standard file formats may be added later), and provides very limited
109 * visualization functionalities. The only learning method supported currently
110 * is Expectation Maximization (or Maximum Likelihood if no data is missing)
111 * for learning factor parameters.
112 *
113 * \section rationale Rationale
114 *
115 * In my opinion, the lack of open source "reference" implementations hampers
116 * progress in research on approximate inference. Methods differ widely in terms
117 * of quality and performance characteristics, which also depend in different
118 * ways on various properties of the graphical models. Finding the best
119 * approximate inference method for a particular application therefore often
120 * requires empirical comparisons. However, implementing and debugging these
121 * methods takes a lot of time which could otherwise be spent on research. I hope
122 * that this code will aid researchers to be able to easily compare various
123 * (existing as well as new) approximate inference methods, in this way
124 * accelerating research and stimulating real-world applications of approximate
125 * inference.
126 *
127 * \section language Language
128 * Because libDAI is implemented in C++, it is very fast compared with
129 * implementations in MatLab (a factor 1000 faster is not uncommon).
130 * libDAI does provide a (limited) MatLab interface for easy integration with MatLab.
131 * It also provides a command line interface and experimental python and octave
132 * interfaces (thanks to Patrick Pletscher).
133 *
134 * \section compatibility Compatibility
135 *
136 * The code has been developed under Debian GNU/Linux with the GCC compiler suite.
137 * libDAI compiles successfully with g++ versions 3.4, 4.1, 4.2 and 4.3.
138 *
139 * libDAI has also been successfully compiled with MS Visual Studio 2008 under Windows
140 * (but not all build targets are supported yet) and with Cygwin under Windows.
141 *
142 * Finally, libDAI has been compiled successfully on MacOS X.
143 *
144 * \section download Downloading libDAI
145 * The libDAI sources and documentation can be downloaded from the libDAI website:
146 * http://www.libdai.org.
147 *
148 * \section support Mailing list
149 * The Google group "libDAI" (http://groups.google.com/group/libdai)
150 * can be used for getting support and discussing development issues.
151 */
152
153
154 /** \page license License
155 * <hr size="1">
156 * \section license-license License
157 *
158 * libDAI is free software; you can redistribute it and/or modify
159 * it under the terms of the GNU General Public License as published by
160 * the Free Software Foundation; either version 2 of the License, or
161 * (at your option) any later version.
162 *
163 * libDAI is distributed in the hope that it will be useful,
164 * but WITHOUT ANY WARRANTY; without even the implied warranty of
165 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
166 * GNU General Public License for more details.
167 *
168 * <hr size="1">
169 * \section license-gpl GNU General Public License version 2
170 *
171 * \verbinclude COPYING
172 */
173
174
175 /** \page citations Citing libDAI
176 * <hr size="1">
177 * \section citations-citations Citing libDAI
178 *
179 * If you write a scientific paper describing research that made substantive use
180 * of this program, please:
181 * - mention the fashion in which this software was
182 * used, including the version number, with a citation to the literature,
183 * to allow replication;
184 * - mention this software in the Acknowledgements section.
185 *
186 * An appropriate citation would be:\n
187 * J. M. Mooij (2008) "libDAI 0.2.2: A free/open source C++ library for Discrete
188 * Approximate Inference methods", http://www.libdai.org
189 *
190 * Moreover, as a personal note, I would appreciate it if you would email
191 * (citations of) papers referencing this work to joris dot mooij at libdai dot org.
192 */
193
194
195 /** \page authors Authors
196 * \section authors-authors People who contributed to libDAI
197 *
198 * \verbinclude AUTHORS
199 */
200
201
202 /** \page build Building libDAI
203 * <hr size="1">
204 * \section build-unix Building libDAI under UNIX variants (Linux / Cygwin / Mac OS X)
205 *
206 * You need:
207 * - a recent version of gcc (at least version 3.4)
208 * - GNU make
209 * - doxygen
210 * - graphviz
211 * - recent boost C++ libraries (at least version 1.34, or 1.37 for cygwin;
212 * version 1.37 shipped with Ubuntu 9.04 is known not to work)
213 *
214 * On Debian/Ubuntu, you can easily install all these packages with a single command:
215 * <pre> apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-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 compile/install it with:
227 *
228 * <pre> ./configure
229 * make
230 * make install
231 * </pre>
232 *
233 * To build the libDAI source, first copy a template Makefile.* to Makefile.conf
234 * (for example, copy Makefile.LINUX to Makefile.conf if you use GNU/Linux).
235 * Then, edit the Makefile.conf template to adapt it to your local setup.
236 * Especially directories may differ from system to system. Finally, run
237 * <pre> make</pre>
238 * The build includes a regression test, which may take a while to complete.
239 *
240 * If the build was successful, you can test the example program:
241 * <pre> examples/example tests/alarm.fg</pre>
242 * or the more elaborate test program:
243 * <pre> tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>
244 *
245 *
246 * <hr size="1">
247 * \section build-windows Building libDAI under Windows
248 *
249 * You need:
250 * - A recent version of MicroSoft Visual Studio (2008 works)
251 * - recent boost C++ libraries (version 1.34 or higher)
252 * - GNU make (can be obtained from http://gnuwin32.sourceforge.net)
253 *
254 * For the regression test, you need:
255 * - GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)
256 *
257 * To build the source, copy Makefile.WINDOWS to Makefile.conf. Then, edit
258 * Makefile.conf to adapt it to your local setup. Finally, run (from the command line)
259 * <pre> make</pre>
260 * The build includes a regression test, which may take a while to complete.
261 *
262 * If the build was successful, you can test the example program:
263 * <pre> example tests\alarm.fg</pre>
264 * or the more elaborate test program:
265 * <pre> tests\\testdai --aliases tests\aliases.conf --filename tests\alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>
266 *
267 *
268 * <hr size="1">
269 * \section build-matlab Building the libDAI MatLab interface
270 *
271 * You need:
272 * - MatLab
273 * - The platform-dependent requirements described above
274 *
275 * First, you need to build the libDAI source as described above for your
276 * platform. By default, the MatLab interface is disabled, so before compiling the
277 * source, you have to enable it in the Makefile.conf by setting
278 * <pre> WITH_MATLAB=true</pre>
279 * Also, you have to configure the MatLab-specific parts of
280 * Makefile.conf to match your system (in particular, the Makefile variables ME,
281 * MATLABDIR and MEX). The MEX file extension depends on your platform; for a
282 * 64-bit linux x86_64 system this would be "ME=.mexa64", for a 32-bit linux x86
283 * system "ME=.mexglx". If you are unsure about your MEX file
284 * extension: it needs to be the same as what the MatLab command "mexext" returns.
285 * The required MEX files are built by issuing
286 * <pre> make</pre>
287 * from the command line. The MatLab interface is much less powerful than using
288 * libDAI from C++. There are two reasons for this: (i) it is boring to write MEX
289 * files; (ii) the large performance penalty paid when large data structures (like
290 * factor graphs) have to be converted between their native C++ data structure to
291 * something that MatLab understands.
292 *
293 * A simple example of how to use the MatLab interface is the following (entered
294 * at the MatLab prompt), which performs exact inference by the junction tree
295 * algorithm and approximate inference by belief propagation on the ALARM network:
296 * <pre> cd path_to_libdai/matlab
297 * [psi] = dai_readfg ('../examples/alarm.fg');
298 * [logZ,q,md,qv,qf] = dai (psi, 'JTREE', '[updates=HUGIN,verbose=0]')
299 * [logZ,q,md,qv,qf] = dai (psi, 'BP', '[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0]')</pre>
300 * where "path_to_libdai" has to be replaced with the directory in which libDAI
301 * was installed. For other algorithms and some default parameters, see the file
302 * tests/aliases.conf.
303 *
304 * <hr size="1">
305 * \section build-doxygen Building the documentation
306 *
307 * Install doxygen, graphviz and a TeX distribution and use
308 * <pre> make doc</pre>
309 * to build the documentation. If the documentation is not clear enough, feel free
310 * to send me an email (or even better, to improve the documentation and send a patch!).
311 * The documentation can also be browsed online at http://www.libdai.org.
312 */
313
314
315 /** \page changelog Change Log
316 * \verbinclude ChangeLog
317 */
318
319
320 /** \page inference Graphical models and approximate inference
321 *
322 * \section inference-graphicalmodels Graphical models
323 *
324 * Commonly used graphical models are Bayesian networks and Markov random fields.
325 * In libDAI, both types of graphical models are represented by a slightly more
326 * general type of graphical model: a factor graph [\ref KFL01].
327 *
328 * \dot
329 * digraph bayesnet {
330 * size="1,1";
331 * x0 [label="0"];
332 * x1 [label="1"];
333 * x2 [label="2"];
334 * x3 [label="3"];
335 * x4 [label="4"];
336 * x0 -> x1;
337 * x0 -> x2;
338 * x1 -> x3;
339 * x1 -> x4;
340 * x2 -> x4;
341 * }
342 * \enddot
343 *
344 * \f[ P(\mathbf{x}) = \prod_{i\in\mathcal{V}} P(x_i \,|\, x_{\mathrm{pa}(i)}) \f]
345 * where \f$\mathrm{pa}(i)\f$ are the parents of node \a i in a DAG.
346 *
347 * \dot
348 * graph mrf {
349 * size="1.5,1.5";
350 * x0 [label="0"];
351 * x1 [label="1"];
352 * x2 [label="2"];
353 * x3 [label="3"];
354 * x4 [label="4"];
355 * x0 -- x1;
356 * x0 -- x2;
357 * x1 -- x2;
358 * x1 -- x3;
359 * x1 -- x4;
360 * x2 -- x4;
361 * }
362 * \enddot
363 *
364 * \f[ P(\mathbf{x}) = \frac{1}{Z} \prod_{C\in\mathcal{C}} \psi_C(x_C) \f]
365 * where \f$ \mathcal{C} \f$ are the cliques of an undirected graph,
366 * \f$ \psi_C(x_C) \f$ are "potentials" or "compatibility functions", and
367 * \f$ Z \f$ is the partition sum which properly normalizes the probability
368 * distribution.
369 *
370 * \dot
371 * graph factorgraph {
372 * size="1.8,1";
373 * x0 [label="0"];
374 * x1 [label="1"];
375 * x2 [label="2"];
376 * x3 [label="3"];
377 * x4 [label="4"];
378 * f01 [shape="box",label=""];
379 * f02 [shape="box",label=""];
380 * f13 [shape="box",label=""];
381 * f124 [shape="box",label=""];
382 * x0 -- f01;
383 * x1 -- f01;
384 * x0 -- f02;
385 * x2 -- f02;
386 * x1 -- f13;
387 * x3 -- f13;
388 * x1 -- f124;
389 * x2 -- f124;
390 * x4 -- f124;
391 * }
392 * \enddot
393 *
394 * \f[ P(\mathbf{x}) = \frac{1}{Z} \prod_{I\in \mathcal{F}} f_I(x_I) \f]
395 * where \f$ \mathcal{F} \f$ are the factor nodes of a factor graph (a
396 * bipartite graph consisting of variable nodes and factor nodes),
397 * \f$ f_I(x_I) \f$ are the factors, and \f$ Z \f$ is the partition sum
398 * which properly normalizes the probability distribution.
399 *
400 * Looking at the expressions for the joint probability distributions,
401 * it is obvious that Bayesian networks and Markov random fields can
402 * both be easily represented as factor graphs. Factor graphs most
403 * naturally express the factorization structure of a probability
404 * distribution, and hence are a convenient representation for approximate
405 * inference algorithms, which all try to exploit this factorization.
406 * This is why libDAI uses a factor graph as representation of a
407 * graphical model, implemented in the dai::FactorGraph class.
408 *
409 * \section inference-inference Inference tasks
410 *
411 * Given a factor graph, specified by the variable nodes \f$\{x_i\}_{i\in\mathcal{V}}\f$
412 * the factor nodes \f$ \mathcal{F} \f$, the graph structure, and the factors
413 * \f$\{f_I(x_I)\}_{I\in\mathcal{F}}\f$, the following tasks are important:
414 *
415 * - Calculating the partition sum:
416 * \f[ Z = \sum_{\mathbf{x}_{\mathcal{V}}} \prod_{I \in \mathcal{F}} f_I(x_I) \f]
417 * - Calculating the marginal distribution of a subset of variables
418 * \f$\{x_i\}_{i\in A}\f$:
419 * \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]
420 * - Calculating the MAP state which has the maximum probability mass:
421 * \f[ \mathrm{argmax}_{\mathbf{x}}\,\prod_{I\in\mathcal{F}} f_I(x_I) \f]
422 *
423 * libDAI offers several inference algorithms, which solve (a subset of) these tasks either
424 * approximately or exactly, for factor graphs with discrete variables. The following
425 * algorithms are implemented:
426 *
427 * Exact inference:
428 * - Brute force enumeration: dai::ExactInf
429 * - Junction-tree method: dai::JTree
430 *
431 * Approximate inference:
432 * - Mean Field: dai::MF
433 * - (Loopy) Belief Propagation: dai::BP [\ref KFL01]
434 * - Tree Expectation Propagation: dai::TreeEP [\ref MiQ04]
435 * - Generalized Belief Propagation: dai::HAK [\ref YFW05]
436 * - Double-loop GBP: dai::HAK [\ref HAK03]
437 * - Loop Corrected Belief Propagation: dai::MR [\ref MoR05] and dai::LC [\ref MoK07]
438 * - Gibbs sampling: dai::Gibbs
439 * - Conditioned BP: dai::CBP [\ref EaG09]
440 *
441 * Not all inference tasks are implemented by each method: calculating MAP states
442 * is only possible with dai::JTree and dai::BP, calculating partition sums is
443 * not possible with dai::MR, dai::LC and dai::Gibbs.
444 *
445 * \section inference-learning Parameter learning
446 *
447 * In addition, libDAI supports parameter learning of conditional probability
448 * tables by Expectation Maximization (or Maximum Likelihood, if there is no
449 * missing data). This is implemented in dai::EMAlg.
450 *
451 */
452
453
454 /** \page fileformats libDAI file formats
455 *
456 * \section fileformats-factorgraph Factor graph (.fg) file format
457 *
458 * This section describes the .fg file format used in libDAI to store factor graphs.
459 * Markov Random Fields are special cases of factor graphs, as are Bayesian
460 * networks. A factor graph can be specified as follows: for each factor, one has
461 * to specify which variables occur in the factor, what their respective
462 * cardinalities (i.e., number of possible values) are, and a table listing all
463 * the values of that factor for all possible configurations of these variables.
464 *
465 * A .fg file is not much more than that. It starts with a line containing the
466 * number of factors in that graph, followed by an empty line. Then all factors
467 * are specified, using one block for each factor, where the blocks are seperated
468 * by empty lines. Each variable occurring in the factor graph has a unique
469 * identifier, its label (which should be a nonnegative integer). Comment lines
470 * which start with # are ignored.
471 *
472 * \subsection fileformats-factorgraph-factor Factor block format
473 *
474 * Each block describing a factor starts with a line containing the number of
475 * variables in that factor. The second line contains the labels of these
476 * variables, seperated by spaces (labels are nonnegative integers and to avoid
477 * confusion, it is suggested to start counting at 0). The third line contains
478 * the number of possible values of each of these variables, also seperated by
479 * spaces. Note that there is some redundancy here, since if a variable appears
480 * in more than one factor, the cardinality of that variable appears several
481 * times in the .fg file; obviously, these cardinalities should be consistent.
482 * The fourth line contains the number of nonzero entries
483 * in the factor table. The rest of the lines contain these nonzero entries;
484 * each line consists of a table index, followed by white-space, followed by the
485 * value corresponding to that table index. The most difficult part is getting
486 * the indexing right. The convention that is used is that the left-most
487 * variables cycle through their values the fastest (similar to MatLab indexing
488 * of multidimensional arrays).
489 *
490 * \subsubsection fileformats-factorgraph-factor-example Example
491 *
492 * An example block describing one factor is:
493 *
494 * <pre>
495 * 3
496 * 4 8 7
497 * 3 2 2
498 * 11
499 * 0 0.1
500 * 1 3.5
501 * 2 2.8
502 * 3 6.3
503 * 4 8.4
504 * 6 7.4
505 * 7 2.4
506 * 8 8.9
507 * 9 1.3
508 * 10 1.6
509 * 12 6.4
510 * 11 2.6
511 * </pre>
512 *
513 * which corresponds to the following factor:
514 *
515 * \f[
516 * \begin{array}{ccc|c}
517 * x_4 & x_8 & x_7 & \mbox{value}\\
518 * \hline
519 * 0 & 0 & 0 & 0.1\\
520 * 1 & 0 & 0 & 3.5\\
521 * 2 & 0 & 0 & 2.8\\
522 * 0 & 1 & 0 & 6.3\\
523 * 1 & 1 & 0 & 8.4\\
524 * 2 & 1 & 0 & 0.0\\
525 * 0 & 0 & 1 & 7.4\\
526 * 1 & 0 & 1 & 2.4\\
527 * 2 & 0 & 1 & 8.9\\
528 * 0 & 1 & 1 & 1.3\\
529 * 1 & 1 & 1 & 1.6\\
530 * 2 & 1 & 1 & 2.6
531 * \end{array}
532 * \f]
533 *
534 * Note that the value of \f$x_4\f$ changes fastest, followed by that of \f$x_8\f$, and \f$x_7\f$
535 * varies the slowest, corresponding to the second line of the block ("4 8 7").
536 * Further, \f$x_4\f$ can take on three values, and \f$x_8\f$ and \f$x_7\f$ each have two possible
537 * values, as described in the third line of the block ("3 2 2"). The table
538 * contains 11 non-zero entries (all except for the fifth entry). Note that the
539 * eleventh and twelveth entries are interchanged.
540 *
541 * A final note: the internal representation in libDAI of the factor above is
542 * different, because the variables are ordered according to their indices
543 * (i.e., the ordering would be \f$x_4 x_7 x_8\f$) and the values of the table are
544 * stored accordingly, with the variable having the smallest index changing
545 * fastest:
546 *
547 * \f[
548 * \begin{array}{ccc|c}
549 * x_4 & x_7 & x_8 & \mbox{value}\\
550 * \hline
551 * 0 & 0 & 0 & 0.1\\
552 * 1 & 0 & 0 & 3.5\\
553 * 2 & 0 & 0 & 2.8\\
554 * 0 & 1 & 0 & 7.4\\
555 * 1 & 1 & 0 & 2.4\\
556 * 2 & 1 & 0 & 8.9\\
557 * 0 & 0 & 1 & 6.3\\
558 * 1 & 0 & 1 & 8.4\\
559 * 2 & 0 & 1 & 0.0\\
560 * 0 & 1 & 1 & 1.3\\
561 * 1 & 1 & 1 & 1.6\\
562 * 2 & 1 & 1 & 2.6
563 * \end{array}
564 * \f]
565 *
566 *
567 * \section fileformats-evidence Evidence (.tab) file format
568 *
569 * This section describes the .tab fileformat used in libDAI to store "evidence",
570 * i.e., a data set consisting of multiple samples, where each sample is the
571 * observed joint state of some variables.
572 *
573 * A .tab file is a tabular data file, consisting of a header line, followed by
574 * an empty line, followed by the data points, with one line for each data point.
575 * Each line (apart from the empty one) should have the same number of columns,
576 * where columns are separated by one tab character. Each column corresponds to
577 * a variable. The header line consists of the variable labels (corresponding to
578 * dai::Var::label()). The other lines are observed joint states of the variables, i.e.,
579 * each line corresponds to a joint observation of the variables, and each column
580 * of a line contains the state of the variable associated with that column.
581 * Missing data is handled simply by having two consecutive tab characters,
582 * without any characters in between.
583 *
584 * \subsection fileformats-evidence-example Example
585 *
586 * <pre>
587 * 1 3 2
588 *
589 * 0 0 1
590 * 1 0 1
591 * 1 1
592 * </pre>
593 *
594 * This would correspond to a data set consisting of three observations concerning
595 * the variables with labels 1, 3 and 2; the first observation being
596 * \f$x_1 = 0, x_3 = 0, x_2 = 1\f$, the second observation being
597 * \f$x_1 = 1, x_3 = 0, x_2 = 1\f$, and the third observation being
598 * \f$x_1 = 1, x_2 = 1\f$ (where the state of \f$x_3\f$ is missing).
599 *
600 * \section fileformats-emalg Expectation Maximization (.em) file format
601 *
602 * This section describes the file format of .em files, which are used
603 * to specify a particular EM algorithm. The .em files are complementary
604 * to .fg files; in other words, an .em file without a corresponding .fg
605 * file is useless. Furthermore, one also needs a corresponding .tab file
606 * containing the data used for parameter learning.
607 *
608 * An .em file starts with a line specifying the number of maximization steps,
609 * followed by an empty line. Then, each maximization step is described in a
610 * block, which should satisfy the format described in the next subsection.
611 *
612 * \subsection fileformats-emalg-maximizationstep Maximization Step block format
613 *
614 * A maximization step block of an .em file starts with a single line
615 * describing the number of shared parameters blocks that will follow.
616 * Then, each shared parameters block follows, in the format described in
617 * the next subsection.
618 *
619 * \subsection fileformats-emalg-sharedparameters Shared parameters block format
620 *
621 * A shared parameters block of an .em file starts with a single line
622 * consisting of the name of a ParameterEstimation subclass
623 * and its parameters in the format of a PropertySet. For example:
624 * <pre> CondProbEstimation [target_dim=2,total_dim=4,pseudo_count=1]</pre>
625 * The next line contains the number of factors that share their parameters.
626 * Then, each of these factors is specified on separate lines (possibly
627 * seperated by empty lines), where each line consists of several fields
628 * seperated by a space or a tab character. The first field contains
629 * the index of the factor in the factor graph. The following fields should
630 * contain the variable labels of the variables on which that factor depends,
631 * in a specific ordering. This ordering can be different from the canonical
632 * ordering of the variables used internally in libDAI (which would be sorted
633 * ascendingly according to the variable labels). The odering of the variables
634 * specifies the implicit ordering of the shared parameters: when iterating
635 * over all shared parameters, the corresponding index of the first variable
636 * changes fastest (in the inner loop), and the corresponding index of the
637 * last variable changes slowest (in the outer loop). By choosing the right
638 * ordering, it is possible to let different factors (depending on different
639 * variables) share parameters in parameter learning using EM. This convention
640 * is similar to the convention used in factor blocks in a factor graph .fg
641 * file (see \ref fileformats-factorgraph-factor).
642 */
643
644 /** \page bibliography Bibliography
645 * \anchor KFL01 \ref KFL01
646 * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
647 * "Factor Graphs and the Sum-Product Algorithm",
648 * <em>IEEE Transactions on Information Theory</em> 47(2):498-519.
649 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
650 *
651 * \anchor MiQ04 \ref MiQ04
652 * T. Minka and Y. Qi (2004):
653 * "Tree-structured Approximations by Expectation Propagation",
654 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.
655 * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
656 *
657 * \anchor MoR05 \ref MoR05
658 * A. Montanari and T. Rizzo (2005):
659 * "How to Compute Loop Corrections to the Bethe Approximation",
660 * <em>Journal of Statistical Mechanics: Theory and Experiment</em>
661 * 2005(10)-P10011.
662 * http://stacks.iop.org/1742-5468/2005/P10011
663 *
664 * \anchor YFW05 \ref YFW05
665 * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
666 * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
667 * <em>IEEE Transactions on Information Theory</em>
668 * 51(7):2282-2312.
669 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
670 *
671 * \anchor HAK03 \ref HAK03
672 * T. Heskes and C. A. Albers and H. J. Kappen (2003):
673 * "Approximate Inference and Constrained Optimization",
674 * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.
675 * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
676 *
677 * \anchor MoK07 \ref MoK07
678 * J. M. Mooij and H. J. Kappen (2007):
679 * "Loop Corrections for Approximate Inference on Factor Graphs",
680 * <em>Journal of Machine Learning Research</em> 8:1113-1143.
681 * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
682 *
683 * \anchor MoK07b \ref MoK07b
684 * J. M. Mooij and H. J. Kappen (2007):
685 * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
686 * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.
687 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
688 *
689 * \anchor EaG09 \ref EaG09
690 * F. Eaton and Z. Ghahramani (2009):
691 * "Choosing a Variable to Clamp",
692 * <em>Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS 2009)</em> 5:145-152
693 * http://jmlr.csail.mit.edu/proceedings/papers/v5/eaton09a/eaton09a.pdf
694 *
695 * \anchor StW99 \ref StW99
696 * A. Steger and N. C. Wormald (1999):
697 * "Generating Random Regular Graphs Quickly",
698 * <em>Combinatorics, Probability and Computing</em> Vol 8, Issue 4, pp. 377-396
699 * http://www.math.uwaterloo.ca/~nwormald/papers/randgen.pdf
700 *
701 * \anchor EMK06 \ref EMK06
702 * G. Elidan and I. McGraw and D. Koller (2006):
703 * "Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing",
704 * <em>Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)</em>
705 * http://uai.sis.pitt.edu/papers/06/UAI2006_0091.pdf
706 */
707
708
709 /** \page discussion Ideas not worth exploring
710 * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs
711 *
712 * A FactorGraph and a RegionGraph are often equipped with
713 * additional properties for nodes and edges. The code to initialize those
714 * is often quite similar. Maybe one could abstract this, e.g.:
715 * \code
716 * template <typename Node1Properties, typename Node2Properties, typename EdgeProperties>
717 * class ExtFactorGraph : public FactorGraph {
718 * public:
719 * std::vector<Node1Properties> node1Props;
720 * std::vector<Node2Properties> node2Props;
721 * std::vector<std::vector<EdgeProperties> > edgeProps;
722 * // ...
723 * }
724 * \endcode
725 *
726 * Advantages:
727 * - Less code duplication.
728 * - Easier maintainability.
729 * - Easier to write new inference algorithms.
730 *
731 * Disadvantages:
732 * - Cachability may be worse.
733 * - A problem is the case where there are no properties for either type of nodes or for edges.
734 * Maybe this can be solved using specializations, or using variadac template arguments?
735 * Another possible solution would be to define a "class Empty {}", and add some code
736 * that checks for the typeid, comparing it with Empty, and doing something special in that case
737 * (e.g., not allocating memory).
738 * - The main disadvantage of this approach seems to be that it leads to even more entanglement.
739 * Therefore this is probably a bad idea.
740 *
741 * \section discuss_templates Polymorphism by template parameterization
742 *
743 * Instead of polymorphism by inheritance, use polymorphism by template parameterization.
744 * For example, the real reason for introducing the complicated inheritance scheme of dai::InfAlg
745 * was for functions like dai::calcMarginal. Instead, one could use a template function:
746 * \code
747 * template<typename InfAlg>
748 * Factor calcMarginal( const InfAlg &obj, const VarSet &ns, bool reInit );
749 * \endcode
750 * This would assume that the type InfAlg supports certain methods. Ideally, one would use
751 * concepts to define different classes of inference algorithms with different capabilities,
752 * for example the ability to calculate logZ, the ability to calculate marginals, the ability to
753 * calculate bounds, the ability to calculate MAP states, etc. Then, one would use traits
754 * classes in order to be able to query the capabilities of the model. For example, one would be
755 * able to query whether the inference algorithm supports calculation of logZ. Unfortunately,
756 * this is compile-time polymorphism, whereas tests/testdai needs runtime polymorphism.
757 * Therefore this is probably a bad idea.
758 */