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