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