libDAI version 0.3.2
[libdai.git] / include / dai / doc.h
index f750e84..b84c21c 100644 (file)
@@ -1,10 +1,8 @@
 /*  This file is part of libDAI - http://www.libdai.org/
  *
- *  libDAI is licensed under the terms of the GNU General Public License version
- *  2, or (at your option) any later version. libDAI is distributed without any
- *  warranty. See the file COPYING for more details.
+ *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
  *
- *  Copyright (C) 2008-2010  Joris Mooij  [joris dot mooij at libdai dot org]
+ *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
  */
 
 
  *  \idea Use boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.
  *  See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
  *  However: I read somewhere that boost::uBLAS concentrates more on correct implementation than on performance.
- *
- *  \idea Introduce naming scheme:
- *  - all Vars should be named v_..., e.g. v_i instead of i
- *  - all VarSets should be named vs_..., e.g. v_i instead of i
- *  - all Factors should be named f_..., e.g. f_I instead of I
- *  - all indices should be named _..., e.g. _k instead of k
- *  - all iterators should be named i_, e.g. i_i is an iterator to i
- *  - all const_iterators should be named ci_, e.g. ci_i is an iterator to i
  **/
 
 
 /** \mainpage Reference manual for libDAI - A free/open source C++ library for Discrete Approximate Inference methods
- *  \author Joris Mooij, Frederik Eaton
- *  \version 0.2.4
- *  \date February 11, 2010
+ *  \author Joris Mooij (with contributions of Frederik Eaton)
+ *  \version 0.3.2
+ *  \date July 17, 2015
  *
  *  <hr size="1">
  *  \section about About libDAI
- *  libDAI is a free/open source C++ library (licensed under GPL 2+) that provides
- *  implementations of various (approximate) inference methods for discrete
- *  graphical models. libDAI supports arbitrary factor graphs with discrete
- *  variables; this includes discrete Markov Random Fields and Bayesian
- *  Networks.
+ *  libDAI is a free/open source C++ library that provides implementations of
+ *  various (approximate) inference methods for discrete graphical models. libDAI
+ *  supports arbitrary factor graphs with discrete variables; this includes
+ *  discrete Markov Random Fields and Bayesian Networks.
  *
  *  The library is targeted at researchers. To be able to use the library, a
  *  good understanding of graphical models is needed.
  *  and to easily compare the accuracy and performance with existing algorithms
  *  that have been implemented already.
  *
+ *  A solver using libDAI was amongst the three winners of the UAI 2010 Approximate
+ *  Inference Challenge (see http://www.cs.huji.ac.il/project/UAI10/ for more 
+ *  information). The full source code is provided as part of the library.
+ *
  *  \section features Features
  *  Currently, libDAI supports the following (approximate) inference methods:
  *  - Exact inference by brute force enumeration;
@@ -80,7 +73,8 @@
  *  - Various variants of Loop Corrected Belief Propagation
  *    [\ref MoK07, \ref MoR05];
  *  - Gibbs sampler;
- *  - Conditioned Belief Propagation [\ref EaG09].
+ *  - Conditioned Belief Propagation [\ref EaG09];
+ *  - Decimation algorithm.
  *
  *  These inference methods can be used to calculate partition sums, marginals
  *  over subsets of variables, and MAP states (the joint state of variables that
  *  \section compatibility Compatibility
  *  
  *  The code has been developed under Debian GNU/Linux with the GCC compiler suite.
- *  libDAI compiles successfully with g++ versions 3.4, 4.1, 4.2 and 4.3.
+ *  libDAI compiles successfully with g++ versions 3.4 up to 4.7 (both 32 and 64 bits).
  *
- *  libDAI has also been successfully compiled with MS Visual Studio 2008 under Windows
- *  (but not all build targets are supported yet) and with Cygwin under Windows.
+ *  libDAI has also been successfully compiled with MS Visual Studio 2008 under Windows,
+ *  MS Visual Studio 2010 under Windows 64, and with Cygwin under Windows.
  *
- *  Finally, libDAI has been compiled successfully on MacOS X.
+ *  Finally, libDAI has been compiled successfully on MacOS X (both 32 and 64 bits).
  *
  *  \section download Downloading libDAI
  *  The libDAI sources and documentation can be downloaded from the libDAI website:
  *  <hr size="1">
  *  \section license-license License
  *
- *  libDAI is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
+ *  libDAI is free software; you can redistribute it and/or modify it under the
+ *  terms of the BSD 2-clause license (also known as the FreeBSD license), which
+ *  can be found in the accompanying LICENSE file.
  *
- *  libDAI is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *  GNU General Public License for more details.
+ *  [Note: up to and including version 0.2.7, libDAI was licensed under the GNU 
+ *  General Public License (GPL) version 2 or higher.]
  *
  *  <hr size="1">
- *  \section license-gpl GNU General Public License version 2
+ *  \section license-freebsd libDAI license (similar to FreeBSD license)
  * 
- *  \verbinclude COPYING
+ *  \verbinclude LICENSE
  */
 
 
  *  \section citations-citations Citing libDAI
  *
  *  If you write a scientific paper describing research that made substantive use
- *  of this program, please:
- *    - mention the fashion in which this software was
- *      used, including the version number, with a citation to the literature, 
- *      to allow replication; 
- *    - mention this software in the Acknowledgements section. 
+ *  of this library, please cite the following paper describing libDAI:\n
  *
- *  An appropriate citation would be:\n
+ *  Joris M. Mooij;\n
+ *  libDAI: A free & open source C++ library for Discrete Approximate Inference in graphical models;\n
+ *  Journal of Machine Learning Research, 11(Aug):2169-2173, 2010.\n
  *
- *  Joris M. Mooij et al. (2010) "libDAI 0.2.4: A free/open source C++ library for Discrete 
- *  Approximate Inference", http://www.libdai.org
- *
- *  or in BiBTeX format:
+ *  In BiBTeX format (for your convenience):\n
  *  
  *  <pre>
- *  \@misc{mooij2010libdai,
- *    author = "Joris M. Mooij et al.",
- *    title = "lib{DAI} 0.2.4: A free/open source {C}++ library for {D}iscrete {A}pproximate {I}nference",
- *    howpublished = "http://www.libdai.org/",
- *    year = 2010
- *  }
- *  </pre>
- *
- *  Moreover, as a personal note, I would appreciate it if you would email
- *  (citations of) papers referencing this work to joris dot mooij at libdai dot org.
+ *  \@article{Mooij_libDAI_10,
+ *    author    = {Joris M. Mooij},
+ *    title     = {lib{DAI}: A Free and Open Source {C++} Library for Discrete Approximate Inference in Graphical Models},
+ *    journal   = {Journal of Machine Learning Research},
+ *    year      = 2010,
+ *    month     = Aug,
+ *    volume    = 11,
+ *    pages     = {2169-2173},
+ *    url       = "http://www.jmlr.org/papers/volume11/mooij10a/mooij10a.pdf"
+ *  }</pre>
+ *
+ *  Moreover, as a personal note, I would appreciate it to be informed about any
+ *  publications using libDAI at joris dot mooij at libdai dot org.
  */
 
 
  *  You need:
  *    - a recent version of gcc (at least version 3.4)
  *    - GNU make
- *    - doxygen
- *    - graphviz
- *    - recent boost C++ libraries (at least version 1.34 if you have
- *      a recent version of GCC, otherwise at least version 1.37; however,
+ *    - recent boost C++ libraries (at least version 1.37; however,
  *      version 1.37 shipped with Ubuntu 9.04 is known not to work)
+ *    - GMP library (or the Windows port called MPIR, for 64 bits builds MPIR 2.5.0 or higher is needed)
+ *    - doxygen (only for building the documentation)
+ *    - graphviz (only for using some of the libDAI command line utilities)
+ *    - CImg library (only for building the image segmentation example)
  * 
- *  On Debian/Ubuntu, you can easily install all these packages with a single command:
- *  <pre>  apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev</pre>
+ *  On Debian/Ubuntu, you can easily install the required packages with a single command:
+ *  <pre>  apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev libboost-test-dev libgmp-dev cimg-dev</pre>
  *  (root permissions needed).
  *
  *  On Mac OS X (10.4 is known to work), these packages can be installed easily via MacPorts.
  *  If MacPorts is not already installed, install it according to the instructions at http://www.macports.org/.
  *  Then, a simple 
- *    <pre>  sudo port install gmake boost doxygen graphviz</pre>
+ *    <pre>  sudo port install gmake boost gmp doxygen graphviz</pre>
  *  should be enough to install everything that is needed.
  *  
  *  On Cygwin, the prebuilt Cygwin package boost-1.33.1-x is known not to work.
  *  You can however obtain the latest boost version (you need at least 1.37.0)
- *  from http://www.boost.org/ and compile/install it with:
+ *  from http://www.boost.org/ and build it as described in the next subsection.
+ *
+ *  \subsubsection build-unix-boost Building boost under Cygwin
+ *
+ *  - Download the latest boost libraries from http://www.boost.org
+ *  - Build the required boost libraries using:
+ *    <pre>
+ *    ./bootstrap.sh --with-libraries=program_options,math,graph,test --prefix=/boost_root/
+ *    ./bjam</pre>
+ *  - In order to use dynamic linking, the boost .dll's should be somewhere in the path. 
+ *    This can be achieved by a command like:
+ *    <pre>
+ *    export PATH=$PATH:/boost_root/stage/lib</pre>
  *
- *  <pre>  ./configure
- *  make
- *  make install
- *  </pre>
  *
  *  \subsection build-unix-libdai Building libDAI
  *
  *  To build the libDAI source, first copy a template Makefile.* to Makefile.conf
  *  (for example, copy Makefile.LINUX to Makefile.conf if you use GNU/Linux). 
- *  Then, edit the Makefile.conf template to adapt it to your local setup.
- *  Especially directories may differ from system to system. Platform independent
- *  build options can be set in Makefile.ALL. Finally, run
+ *  Then, edit the Makefile.conf template to adapt it to your local setup. In case
+ *  you want to use Boost libraries which are installed in non-standard locations,
+ *  you have to tell the compiler and linker about their locations (using the
+ *  -I, -L flags for GCC; also you may need to set the LD_LIBRARY_PATH environment 
+ *  variable correctly before running libDAI binaries). Platform independent build
+ *  options can be set in Makefile.ALL. Finally, run
  *  <pre>  make</pre>
  *  The build includes a regression test, which may take a while to complete.
  *
  *  You need:
  *  - A recent version of MicroSoft Visual Studio (2008 is known to work)
  *  - recent boost C++ libraries (version 1.37 or higher)
+ *  - GMP or MPIR library (for 64-bits builds, MPIR 2.5.0 or higher is needed)
  *  - GNU make (can be obtained from http://gnuwin32.sourceforge.net)
+ *  - CImg library (only for building the image segmentation example)
  *
  *  For the regression test, you need:
  *  - GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)
  *
+ *  \subsubsection build-windows-boost Building boost under Windows
+ *
+ *  Because building boost under Windows is tricky, I provide some guidance here.
+ *
+ *  - Download the boost zip file from http://www.boost.org/users/download
+ *    and unpack it somewhere.
+ *  - Download the bjam executable from http://www.boost.org/users/download
+ *    and unpack it somewhere else.
+ *  - Download Boost.Build (v2) from http://www.boost.org/docs/tools/build/index.html
+ *    and unpack it yet somewhere else.
+ *  - Edit the file \c boost-build.jam in the main boost directory to change the
+ *    \c BOOST_BUILD directory to the place where you put Boost.Build (use UNIX
+ *    / instead of Windows \ in pathnames).
+ *  - Copy the \c bjam.exe executable into the main boost directory.
+ *    Now if you issue <tt>"bjam --version"</tt> you should get a version and no errors.
+ *    Issueing <tt>"bjam --show-libraries"</tt> will show the libraries that will be built.
+ *  - The following command builds the boost libraries that are relevant for libDAI:
+ *    <pre>
+ *    bjam --with-graph --with-math --with-program_options --with-test link=static runtime-link=shared</pre>
+ *
+ *  \subsection build-windows-gmp Building GMP or MPIR under Windows
+ *  
+ *  Information about how to build GPR or MPIR under Windows can be found on the internet.
+ *  The user has to update Makefile.WINDOWS in order to link with the GPR/MPIR libraries.
+ *  Note that for 64-bit builds, MPIR 2.5.0 or higher is needed.
+ *
  *  \subsection build-windows-libdai Building libDAI
  *
  *  To build the source, copy Makefile.WINDOWS to Makefile.conf. Then, edit 
  *  at the MatLab prompt), which performs exact inference by the junction tree
  *  algorithm and approximate inference by belief propagation on the ALARM network:
  *  <pre>  cd path_to_libdai/matlab
- *  [psi] = dai_readfg ('../examples/alarm.fg');
+ *  [psi] = dai_readfg ('../tests/alarm.fg');
  *  [logZ,q,md,qv,qf] = dai (psi, 'JTREE', '[updates=HUGIN,verbose=0]')
  *  [logZ,q,md,qv,qf] = dai (psi, 'BP', '[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0]')</pre>
  *  where "path_to_libdai" has to be replaced with the directory in which libDAI
  *  - Loop Corrected Belief Propagation: dai::MR [\ref MoR05] and dai::LC [\ref MoK07]
  *  - Gibbs sampling: dai::Gibbs
  *  - Conditioned Belief Propagation: dai::CBP [\ref EaG09]
+ *  - Decimation algorithm: dai::DecMAP
  *
  *  Not all inference tasks are implemented by each method: calculating MAP states
- *  is only possible with dai::JTree and dai::BP, calculating partition sums is
+ *  is only possible with dai::JTree, dai::BP and dai::DECMAP; calculating partition sums is
  *  not possible with dai::MR, dai::LC and dai::Gibbs.
  *
  *  \section terminology-learning Parameter learning
  *  8 8.9
  *  9 1.3
  *  10 1.6
- *  12 6.4
  *  11 2.6
  *  </pre>
  *
  *  <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437,
  *  http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
  *
+ *  \anchor Moo08 \ref Moo08
+ *  J. M. Mooij (2008):
+ *  "Understanding and Improving Belief Propagation",
+ *  <em>Ph.D. Thesis</em> Radboud University Nijmegen
+ *  http://webdoc.ubn.ru.nl/mono/m/mooij_j/undeanimb.pdf
+ *
  *  \anchor MoR05 \ref MoR05
  *  A. Montanari and T. Rizzo (2005):
  *  "How to Compute Loop Corrections to the Bethe Approximation",
  *  <em>Journal of Statistical Mechanics: Theory and Experiment</em> 2005(10)-P10011,
  *  http://stacks.iop.org/1742-5468/2005/P10011
  *
+ *  \anchor RYG12 \ref RYG12
+ *  S. Ravanbakhsh, C.-N. Yu, R. Greiner (2012):
+ *  "A Generalized Loop Correction Method for Approximate Inference in Graphical Models",
+ *  <em>29th International Conference on Machine Learning (ICML 2012)</em>,
+ *  http://www.icml.cc/2012/papers/#paper-304
+ *
  *  \anchor StW99 \ref StW99
  *  A. Steger and N. C. Wormald (1999):
  *  "Generating Random Regular Graphs Quickly",