1 libDAI - A free/open source C++ library for Discrete Approximate Inference

3 -------------------------------------------------------------------------------

5 Version: git HEAD

6 Date: April 1, 2010 - or later

7 See also: http://www.libdai.org

9 -------------------------------------------------------------------------------

11 License

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.

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.

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/

25 -------------------------------------------------------------------------------

27 Citing libDAI

29 If you write a scientific paper describing research that made substantive use

30 of this program, please:

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.

36 An appropriate citation would be:

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

41 or in BiBTeX format:

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 }

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.

54 -------------------------------------------------------------------------------

56 About libDAI

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.

63 The library is targeted at researchers. To be able to use the library, a good

64 understanding of graphical models is needed.

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

69 * command line interface

70 * (limited) MatLab interface

71 * (experimental) python interface

72 * (experimental) octave interface.

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.

78 Features

80 Currently, libDAI supports the following (approximate) inference methods:

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].

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).

99 In addition, libDAI supports parameter learning of conditional probability

100 tables by Expectation Maximization.

102 Limitations

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.

113 Rationale

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.

126 Language

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).

134 Compatibility

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.

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.

143 Finally, libDAI has been compiled successfully on MacOS X.

145 Downloading libDAI

147 The libDAI sources and documentation can be downloaded from the libDAI website:

148 http://www.libdai.org.

150 Mailing list

152 The Google group "libDAI" (http://groups.google.com/group/libdai) can be used

153 for getting support and discussing development issues.

154 -------------------------------------------------------------------------------

156 Building libDAI under UNIX variants (Linux / Cygwin / Mac OS X)

158 Preparations

160 You need:

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)

170 On Debian/Ubuntu, you can easily install all these packages with a single

171 command:

173 apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev

175 (root permissions needed).

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

181 sudo port install gmake boost doxygen graphviz

183 should be enough to install everything that is needed.

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:

189 ./configure

190 make

191 make install

194 Building libDAI

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

202 make

204 The build includes a regression test, which may take a while to complete.

206 If the build is successful, you can test the example program:

208 examples/example tests/alarm.fg

210 or the more extensive test program:

212 tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX

214 -------------------------------------------------------------------------------

216 Building libDAI under Windows

218 Preparations

220 You need:

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)

226 For the regression test, you need:

228 * GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)

230 Building libDAI

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)

236 make

238 The build includes a regression test, which may take a while to complete.

240 If the build is successful, you can test the example program:

242 examples\example tests\alarm.fg

244 or the more extensive test program:

246 tests\testdai --aliases tests\aliases.conf --filename tests\alarm.fg --methods JTREE_HUGIN BP_SEQMAX

248 -------------------------------------------------------------------------------

250 Building the libDAI MatLab interface

252 You need:

254 * MatLab

255 * The platform-dependent requirements described above

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

261 WITH_MATLAB=true

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

270 make

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.

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:

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]')

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.

291 -------------------------------------------------------------------------------

293 Building the documentation

295 Install doxygen, graphviz and a TeX distribution and use

297 make doc

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.