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