README

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