README

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