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

3 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

5 Version: git commit 76cf77837c617f54202590125c7a566ae443d0ab

6 Date: Thu Nov 12 10:52:51 2009 +0100

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. An appropriate

35 citation would be:

36 J. M. Mooij (2008) "libDAI 0.2.2: A free/open source C++ library for

37 Discrete Approximate Inference methods", http://www.libdai.org

39 Moreover, as a personal note, I would appreciate it if you would email

40 (citations of) papers referencing this work to joris dot mooij at libdai dot

41 org.

43 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

45 About libDAI

47 libDAI is a free/open source C++ library (licensed under GPLv2+) that provides

48 implementations of various (approximate) inference methods for discrete

49 graphical models. libDAI supports arbitrary factor graphs with discrete

50 variables; this includes discrete Markov Random Fields and Bayesian Networks.

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

53 understanding of graphical models is needed.

55 Features

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

59 • Exact inference by brute force enumeration;

60 • Exact inference by junction-tree methods;

61 • Mean Field;

62 • Loopy Belief Propagation [KFL01];

63 • Tree Expectation Propagation [MiQ04];

64 • Generalized Belief Propagation [YFW05];

65 • Double-loop GBP [HAK03];

66 • Various variants of Loop Corrected Belief Propagation [MoK07, MoR05];

67 • Gibbs sampler;

68 • Conditioned BP [EaG09].

70 These inference methods can be used to calculate partition sums, marginals over

71 subsets of variables, and MAP states (the joint state of variables that has

72 maximum probability).

74 In addition, libDAI supports parameter learning of conditional probability

75 tables by Expectation Maximization.

77 Limitations

79 libDAI is not intended to be a complete package for approximate inference.

80 Instead, it should be considered as an "inference engine", providing various

81 inference methods. In particular, it contains no GUI, currently only supports

82 its own file format for input and output (although support for standard file

83 formats may be added later), and provides very limited visualization

84 functionalities. The only learning method supported currently is Expectation

85 Maximization (or Maximum Likelihood if no data is missing) for learning factor

86 parameters.

88 Why C++?

90 Because libDAI is implemented in C++, it is very fast compared with

91 implementations in MatLab (a factor 1000 faster is not uncommon). libDAI does

92 provide a (limited) MatLab interface for easy integration with MatLab.

94 Compatibility

96 The code has been developed under Debian GNU/Linux with the GCC compiler suite.

97 libDAI compiles successfully with g++ versions 3.4, 4.1, 4.2 and 4.3.

99 libDAI has also been successfully compiled with MS Visual Studio 2008 under

100 Windows (but not all build targets are supported yet) and with Cygwin under

101 Windows.

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

105 Downloading libDAI

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

108 http://www.libdai.org.

110 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

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

114 You need:

116 • a recent version of gcc (at least version 3.4)

117 • GNU make

118 • doxygen

119 • graphviz

120 • recent boost C++ libraries (at least version 1.34, or 1.37 for cygwin;

121 version 1.37 shipped with Ubuntu 9.04 is known not to work)

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

124 command:

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

128 (root permissions needed).

130 On Mac OS X (10.4 is known to work), these packages can be installed easily via

131 MacPorts. If MacPorts is not already installed, install it according to the

132 instructions at http://www.macports.org/. Then, a simple

134 sudo port install gmake boost doxygen graphviz

136 should be enough to install everything that is needed.

138 On Cygwin, the prebuilt Cygwin package boost-1.33.1-x is known not to work. You

139 can however obtain the latest boost version (you need at least 1.37.0) from

140 http://www.boost.org/ and compile/install it with:

142 ./configure

143 make

144 make install

147 To build the libDAI source, first copy a template Makefile.* to Makefile.conf

148 (for example, copy Makefile.LINUX to Makefile.conf if you use GNU/Linux). Then,

149 edit the Makefile.conf template to adapt it to your local setup. Especially

150 directories may differ from system to system. Finally, run

152 make

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

156 If the build was successful, you can test the example program:

158 examples/example tests/alarm.fg

160 or the more elaborate test program:

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

164 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

166 Building libDAI under Windows

168 You need:

170 • A recent version of MicroSoft Visual Studio (2008 works)

171 • recent boost C++ libraries (version 1.34 or higher)

172 • GNU make (can be obtained from http://gnuwin32.sourceforge.net)

174 For the regression test, you need:

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

178 To build the source, copy Makefile.WINDOWS to Makefile.conf. Then, edit

179 Makefile.conf to adapt it to your local setup. Finally, run (from the command

180 line)

182 make

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

186 If the build was successful, you can test the example program:

188 example tests\alarm.fg

190 or the more elaborate test program:

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

194 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

196 Building the libDAI MatLab interface

198 You need:

200 • MatLab

201 • The platform-dependent requirements described above

203 First, you need to build the libDAI source as described above for your

204 platform. By default, the MatLab interface is disabled, so before compiling the

205 source, you have to enable it in the Makefile.conf by setting

207 WITH_MATLAB=true

209 Also, you have to configure the MatLab-specific parts of Makefile.conf to match

210 your system (in particular, the Makefile variables ME, MATLABDIR and MEX). The

211 MEX file extension depends on your platform; for a 64-bit linux x86_64 system

212 this would be "ME=.mexa64", for a 32-bit linux x86 system "ME=.mexglx". If you

213 are unsure about your MEX file extension: it needs to be the same as what the

214 MatLab command "mexext" returns. The required MEX files are built by issuing

216 make

218 from the command line. The MatLab interface is much less powerful than using

219 libDAI from C++. There are two reasons for this: (i) it is boring to write MEX

220 files; (ii) the large performance penalty paid when large data structures (like

221 factor graphs) have to be converted between their native C++ data structure to

222 something that MatLab understands.

224 A simple example of how to use the MatLab interface is the following (entered

225 at the MatLab prompt), which performs exact inference by the junction tree

226 algorithm and approximate inference by belief propagation on the ALARM network:

228 cd path_to_libdai/matlab

229 [psi] = dai_readfg ('../examples/alarm.fg');

230 [logZ,q,md,qv,qf] = dai (psi, 'JTREE', '[updates=HUGIN,verbose=0]')

231 [logZ,q,md,qv,qf] = dai (psi, 'BP', '[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0]')

233 where "path_to_libdai" has to be replaced with the directory in which libDAI

234 was installed. For other algorithms and some default parameters, see the file

235 tests/aliases.conf.

237 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

239 Building the documentation

241 Install doxygen and use

243 make doc

245 to build the documentation. If the documentation is not clear enough, feel free

246 to send me an email (or even better, to improve the documentation and send a

247 patch!).