f5e28fd522e9e324279ea442ac59bf6d4307c9ad
[libdai.git] / README
1 libDAI - A free/open source C++ library for Discrete Approximate Inference
2
3 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
4
5 Version: git commit 7982eafde7cecc6ee4105461337667980203e4d2
6 Date: Thu Nov 12 16:36:54 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. 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
38
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.
42
43 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
44
45 About libDAI
46
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.
51
52 The library is targeted at researchers. To be able to use the library, a good
53 understanding of graphical models is needed.
54
55 Features
56
57 Currently, libDAI supports the following (approximate) inference methods:
58
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].
69
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).
73
74 In addition, libDAI supports parameter learning of conditional probability
75 tables by Expectation Maximization.
76
77 Limitations
78
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.
87
88 Why C++?
89
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.
93
94 Compatibility
95
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.
98
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.
102
103 Finally, libDAI has been compiled successfully on MacOS X.
104
105 Downloading libDAI
106
107 The libDAI sources and documentation can be downloaded from the libDAI website:
108 http://www.libdai.org.
109
110 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
111
112 Building libDAI under UNIX variants (Linux / Cygwin / Mac OS X)
113
114 You need:
115
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)
122
123 On Debian/Ubuntu, you can easily install all these packages with a single
124 command:
125
126 apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev
127
128 (root permissions needed).
129
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
133
134 sudo port install gmake boost doxygen graphviz
135
136 should be enough to install everything that is needed.
137
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:
141
142 ./configure
143 make
144 make install
145
146
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
151
152 make
153
154 The build includes a regression test, which may take a while to complete.
155
156 If the build was successful, you can test the example program:
157
158 examples/example tests/alarm.fg
159
160 or the more elaborate test program:
161
162 tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX
163
164 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
165
166 Building libDAI under Windows
167
168 You need:
169
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)
173
174 For the regression test, you need:
175
176 • GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)
177
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)
181
182 make
183
184 The build includes a regression test, which may take a while to complete.
185
186 If the build was successful, you can test the example program:
187
188 example tests\alarm.fg
189
190 or the more elaborate test program:
191
192 tests\testdai --aliases tests\aliases.conf --filename tests\alarm.fg --methods JTREE_HUGIN BP_SEQMAX
193
194 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
195
196 Building the libDAI MatLab interface
197
198 You need:
199
200 • MatLab
201 • The platform-dependent requirements described above
202
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
206
207 WITH_MATLAB=true
208
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
215
216 make
217
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.
223
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:
227
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]')
232
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.
236
237 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
238
239 Building the documentation
240
241 Install doxygen and use
242
243 make doc
244
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!).
248