README

   1 libDAI  -  A free/open source C++ library for Discrete Approximate Inference
   2
   3 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
   4
   5 Version:  git HEAD
   6 Date:     November 16, 2009 - or later
   7 See also: http://www.libdai.org
   8
   9 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  10
  11 License
  12
  13 libDAI is free software; you can redistribute it and/or modify it under the
  14 terms of the GNU General Public License as published by the Free Software
  15 Foundation; either version 2 of the License, or (at your option) any later
  16 version.
  17
  18 libDAI is distributed in the hope that it will be useful, but WITHOUT ANY
  19 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  20 PARTICULAR PURPOSE. See the GNU General Public License for more details.
  21
  22 You should have received a copy of the GNU General Public License
  23 along with libDAI in the file COPYING. If not, see http://www.gnu.org/licenses/
  24
  25 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  26
  27 Citing libDAI
  28
  29 If you write a scientific paper describing research that made substantive use
  30 of this program, please:
  31
  32   • mention the fashion in which this software was used, including the version
  33     number, with a citation to the literature, to allow replication;
  34   • mention this software in the Acknowledgements section.
  35
  36 An appropriate citation would be:
  37 J. M. Mooij (2009) "libDAI 0.2.3: A free/open source C++ library for Discrete
  38 Approximate Inference", http://www.libdai.org
  39
  40 Moreover, as a personal note, I would appreciate it if you would email
  41 (citations of) papers referencing this work to joris dot mooij at libdai dot
  42 org.
  43
  44 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  45
  46 About libDAI
  47
  48 libDAI is a free/open source C++ library (licensed under GPL 2+) that provides
  49 implementations of various (approximate) inference methods for discrete
  50 graphical models. libDAI supports arbitrary factor graphs with discrete
  51 variables; this includes discrete Markov Random Fields and Bayesian Networks.
  52
  53 The library is targeted at researchers. To be able to use the library, a good
  54 understanding of graphical models is needed.
  55
  56 The best way to use libDAI is by writing C++ code that invokes the library; in
  57 addition, part of the functionality is accessibly by using the
  58
  59   • command line interface
  60   • (limited) MatLab interface
  61   • (experimental) python interface
  62   • (experimental) octave interface.
  63
  64 libDAI can be used to implement novel (approximate) inference algorithms and to
  65 easily compare the accuracy and performance with existing algorithms that have
  66 been implemented already.
  67
  68 Features
  69
  70 Currently, libDAI supports the following (approximate) inference methods:
  71
  72   • Exact inference by brute force enumeration;
  73   • Exact inference by junction-tree methods;
  74   • Mean Field;
  75   • Loopy Belief Propagation [KFL01];
  76   • Tree Expectation Propagation [MiQ04];
  77   • Generalized Belief Propagation [YFW05];
  78   • Double-loop GBP [HAK03];
  79   • Various variants of Loop Corrected Belief Propagation [MoK07, MoR05];
  80   • Gibbs sampler;
  81   • Clamped Belief Propagation [EaG09].
  82
  83 These inference methods can be used to calculate partition sums, marginals over
  84 subsets of variables, and MAP states (the joint state of variables that has
  85 maximum probability).
  86
  87 In addition, libDAI supports parameter learning of conditional probability
  88 tables by Expectation Maximization.
  89
  90 Limitations
  91
  92 libDAI is not intended to be a complete package for approximate inference.
  93 Instead, it should be considered as an "inference engine", providing various
  94 inference methods. In particular, it contains no GUI, currently only supports
  95 its own file format for input and output (although support for standard file
  96 formats may be added later), and provides very limited visualization
  97 functionalities. The only learning method supported currently is Expectation
  98 Maximization (or Maximum Likelihood if no data is missing) for learning factor
  99 parameters.
 100
 101 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 ways
 106 on various properties of the graphical models. Finding the best approximate
 107 inference method for a particular application therefore often requires
 108 empirical comparisons. However, implementing and debugging these methods takes
 109 a lot of time which could otherwise be spent on research. I hope that this code
 110 will aid researchers to be able to easily compare various (existing as well as
 111 new) approximate inference methods, in this way accelerating research and
 112 stimulating real-world applications of approximate inference.
 113
 114 Language
 115
 116 Because libDAI is implemented in C++, it is very fast compared with
 117 implementations in MatLab (a factor 1000 faster is not uncommon). libDAI does
 118 provide a (limited) MatLab interface for easy integration with MatLab. It also
 119 provides a command line interface and experimental python and octave interfaces
 120 (thanks to Patrick Pletscher).
 121
 122 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, 4.1, 4.2 and 4.3.
 126
 127 libDAI has also been successfully compiled with MS Visual Studio 2008 under
 128 Windows (but not all build targets are supported yet) and with Cygwin under
 129 Windows.
 130
 131 Finally, libDAI has been compiled successfully on MacOS X.
 132
 133 Downloading libDAI
 134
 135 The libDAI sources and documentation can be downloaded from the libDAI website:
 136 http://www.libdai.org.
 137
 138 Mailing list
 139
 140 The Google group "libDAI" (http://groups.google.com/group/libdai) can be used
 141 for getting support and discussing development issues.
 142
 143 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 144
 145 Building libDAI under UNIX variants (Linux / Cygwin / Mac OS X)
 146
 147 You need:
 148
 149   • a recent version of gcc (at least version 3.4)
 150   • GNU make
 151   • doxygen
 152   • graphviz
 153   • recent boost C++ libraries (at least version 1.34, or 1.37 for cygwin;
 154     version 1.37 shipped with Ubuntu 9.04 is known not to work)
 155
 156 On Debian/Ubuntu, you can easily install all these packages with a single
 157 command:
 158
 159   apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev
 160
 161 (root permissions needed).
 162
 163 On Mac OS X (10.4 is known to work), these packages can be installed easily via
 164 MacPorts. If MacPorts is not already installed, install it according to the
 165 instructions at http://www.macports.org/. Then, a simple
 166
 167   sudo port install gmake boost doxygen graphviz
 168
 169 should be enough to install everything that is needed.
 170
 171 On Cygwin, the prebuilt Cygwin package boost-1.33.1-x is known not to work. You
 172 can however obtain the latest boost version (you need at least 1.37.0) from
 173 http://www.boost.org/ and compile/install it with:
 174
 175   ./configure
 176   make
 177   make install
 178
 179
 180 To build the libDAI source, first copy a template Makefile.* to Makefile.conf
 181 (for example, copy Makefile.LINUX to Makefile.conf if you use GNU/Linux). Then,
 182 edit the Makefile.conf template to adapt it to your local setup. Especially
 183 directories may differ from system to system. Finally, run
 184
 185   make
 186
 187 The build includes a regression test, which may take a while to complete.
 188
 189 If the build was successful, you can test the example program:
 190
 191   examples/example tests/alarm.fg
 192
 193 or the more elaborate test program:
 194
 195   tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX
 196
 197 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 198
 199 Building libDAI under Windows
 200
 201 You need:
 202
 203   • A recent version of MicroSoft Visual Studio (2008 works)
 204   • recent boost C++ libraries (version 1.34 or higher)
 205   • GNU make (can be obtained from http://gnuwin32.sourceforge.net)
 206
 207 For the regression test, you need:
 208
 209   • GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)
 210
 211 To build the source, copy Makefile.WINDOWS to Makefile.conf. Then, edit
 212 Makefile.conf to adapt it to your local setup. Finally, run (from the command
 213 line)
 214
 215   make
 216
 217 The build includes a regression test, which may take a while to complete.
 218
 219 If the build was successful, you can test the example program:
 220
 221   example tests\alarm.fg
 222
 223 or the more elaborate test program:
 224
 225   tests\testdai --aliases tests\aliases.conf --filename tests\alarm.fg --methods JTREE_HUGIN BP_SEQMAX
 226
 227 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 228
 229 Building the libDAI MatLab interface
 230
 231 You need:
 232
 233   • MatLab
 234   • The platform-dependent requirements described above
 235
 236 First, you need to build the libDAI source as described above for your
 237 platform. By default, the MatLab interface is disabled, so before compiling the
 238 source, you have to enable it in the Makefile.conf by setting
 239
 240   WITH_MATLAB=true
 241
 242 Also, you have to configure the MatLab-specific parts of Makefile.conf to match
 243 your system (in particular, the Makefile variables ME, MATLABDIR and MEX). The
 244 MEX file extension depends on your platform; for a 64-bit linux x86_64 system
 245 this would be "ME=.mexa64", for a 32-bit linux x86 system "ME=.mexglx". If you
 246 are unsure about your MEX file extension: it needs to be the same as what the
 247 MatLab command "mexext" returns. The required MEX files are built by issuing
 248
 249   make
 250
 251 from the command line. The MatLab interface is much less powerful than using
 252 libDAI from C++. There are two reasons for this: (i) it is boring to write MEX
 253 files; (ii) the large performance penalty paid when large data structures (like
 254 factor graphs) have to be converted between their native C++ data structure to
 255 something that MatLab understands.
 256
 257 A simple example of how to use the MatLab interface is the following (entered
 258 at the MatLab prompt), which performs exact inference by the junction tree
 259 algorithm and approximate inference by belief propagation on the ALARM network:
 260
 261   cd path_to_libdai/matlab
 262   [psi] = dai_readfg ('../examples/alarm.fg');
 263   [logZ,q,md,qv,qf] = dai (psi, 'JTREE', '[updates=HUGIN,verbose=0]')
 264   [logZ,q,md,qv,qf] = dai (psi, 'BP', '[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0]')
 265
 266 where "path_to_libdai" has to be replaced with the directory in which libDAI
 267 was installed. For other algorithms and some default parameters, see the file
 268 tests/aliases.conf.
 269
 270 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 271
 272 Building the documentation
 273
 274 Install doxygen, graphviz and a TeX distribution and use
 275
 276   make doc
 277
 278 to build the documentation. If the documentation is not clear enough, feel free
 279 to send me an email (or even better, to improve the documentation and send a
 280 patch!). The documentation can also be browsed online at http://www.libdai.org.
 281