Updated copyright headers
[libdai.git] / include / dai / doc.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2008-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 */
9
10
11 /** \file
12 * \brief Contains additional doxygen documentation
13 *
14 * \todo Merge COPYING into doxygen documentation
15 * \todo Merge README into doxygen documentation
16 * \todo Document examples, tests and utils
17 *
18 * \todo Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming
19 *
20 * \todo Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html
21 * \todo Investigate whether switching to cmake as cross-platform build system would be a good idea.
22 * \todo Switch from nmake to GNU make under Windows http://gnuwin32.sourceforge.net/
23 *
24 * \todo Replace VarSets by SmallSet<size_t> where appropriate, in order to minimize the use of FactorGraph::findVar().
25 *
26 * \idea Disentangle structures. In particular, ensure that graphical properties are not
27 * entangled with probabilistic properties. For example, a FactorGraph contains several
28 * components:
29 * - a BipartiteGraph
30 * - an array of variable labels
31 * - an array of variable state space sizes
32 * - an array of pointers to factor value vectors
33 * In this way, each factor could be implemented differently, e.g., we could have
34 * some sparse factors, some noisy-OR factors, some dense factors, some arbitrary
35 * precision factors, etc.
36 *
37 * \idea Use Boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.
38 * See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
39 *
40 * \idea Introduce naming scheme:
41 * - all Vars should be named v_..., e.g. v_i instead of i
42 * - all VarSets should be named vs_..., e.g. v_i instead of i
43 * - all Factors should be named f_..., e.g. f_I instead of I
44 * - all indices should be named _..., e.g. _k instead of k
45 * - all iterators should be named i_, e.g. i_i is an iterator to i
46 * - all const_iterators should be named ci_, e.g. ci_i is an iterator to i
47 **/
48
49
50 /** \page discussion Discussion of possible improvements
51 * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs
52 *
53 * A FactorGraph and a RegionGraph are often equipped with
54 * additional properties for nodes and edges. The code to initialize those
55 * is often quite similar. Maybe one could abstract this, e.g.:
56 * \code
57 * template <typename Node1Properties, typename Node2Properties, typename EdgeProperties>
58 * class ExtFactorGraph : public FactorGraph {
59 * public:
60 * std::vector<Node1Properties> node1Props;
61 * std::vector<Node2Properties> node2Props;
62 * std::vector<std::vector<EdgeProperties> > edgeProps;
63 * // ...
64 * }
65 * \endcode
66 *
67 * Advantages:
68 * - Less code duplication.
69 * - Easier maintainability.
70 * - Easier to write new inference algorithms.
71 *
72 * Disadvantages:
73 * - Cachability may be worse.
74 * - A problem is the case where there are no properties for either type of nodes or for edges.
75 * Maybe this can be solved using specializations, or using variadac template arguments?
76 * Another possible solution would be to define a "class Empty {}", and add some code
77 * that checks for the typeid, comparing it with Empty, and doing something special in that case
78 * (e.g., not allocating memory).
79 * - The main disadvantage of this approach seems to be that it leads to even more entanglement.
80 * Therefore this is probably a bad idea.
81 *
82 * \section discuss_templates Polymorphism by template parameterization
83 * Instead of polymorphism by inheritance, use polymorphism by template parameterization.
84 * For example, the real reason for introducing the complicated inheritance scheme of dai::InfAlg
85 * was for functions like dai::calcMarginal. Instead, one could use a template function:
86 * \code
87 * template<typename InfAlg>
88 * Factor calcMarginal( const InfAlg &obj, const VarSet &ns, bool reInit );
89 * \endcode
90 * This would assume that the type InfAlg supports certain methods. Ideally, one would use
91 * concepts to define different classes of inference algorithms with different capabilities,
92 * for example the ability to calculate logZ, the ability to calculate marginals, the ability to
93 * calculate bounds, the ability to calculate MAP states, etc. Then, one would use traits
94 * classes in order to be able to query the capabilities of the model. For example, one would be
95 * able to query whether the inference algorithm supports calculation of logZ. Unfortunately,
96 * this is compile-time polymorphism, whereas tests/testdai needs runtime polymorphism.
97 * Therefore this is probably a bad idea.
98 */
99
100
101 /** \mainpage libDAI reference manual
102 * \author Joris Mooij
103 * \version git HEAD
104 * \date October 10, 2008
105 *
106 * \section about About libDAI
107 * libDAI is a free/open source C++ library (licensed under GPLv2+) that provides
108 * implementations of various (approximate) inference methods for discrete
109 * graphical models. libDAI supports arbitrary factor graphs with discrete
110 * variables; this includes discrete Markov Random Fields and Bayesian
111 * Networks.
112 *
113 * The library is targeted at researchers. To be able to use the library, a
114 * good understanding of graphical models is needed.
115 *
116 * \section limitations Limitations
117 * libDAI is not intended to be a complete package for approximate inference.
118 * Instead, it should be considered as an "inference engine", providing
119 * various inference methods. In particular, it contains no GUI, currently
120 * only supports its own file format for input and output (although support
121 * for standard file formats may be added later), and provides very limited
122 * visualization functionalities. The only learning method supported currently
123 * is EM for learning factor parameters.
124 *
125 * \section features Features
126 * Currently, libDAI supports the following (approximate) inference methods:
127 * - Exact inference by brute force enumeration;
128 * - Exact inference by junction-tree methods;
129 * - Mean Field;
130 * - Loopy Belief Propagation [\ref KFL01];
131 * - Tree Expectation Propagation [\ref MiQ04];
132 * - Generalized Belief Propagation [\ref YFW05];
133 * - Double-loop GBP [\ref HAK03];
134 * - Various variants of Loop Corrected Belief Propagation
135 * [\ref MoK07, \ref MoR05];
136 * - Gibbs sampler;
137 * - Conditioned BP [\ref EaG09];
138 *
139 * In addition, libDAI supports parameter learning of conditional probability
140 * tables by Expectation Maximization.
141 *
142 * \section language Why C++?
143 * Because libDAI is implemented in C++, it is very fast compared with
144 * implementations in MatLab (a factor 1000 faster is not uncommon).
145 * libDAI does provide a MatLab interface for easy integration with MatLab.
146 */
147
148
149 /** \example example.cpp
150 */
151
152
153 /** \page quickstart Quick start
154 * An example program illustrating basic usage of libDAI is given in examples/example.cpp.
155 */
156
157
158 /** \page bibliography Bibliography
159 * \section Bibliograpy
160 * \anchor KFL01 \ref KFL01
161 * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
162 * "Factor Graphs and the Sum-Product Algorithm",
163 * <em>IEEE Transactions on Information Theory</em> 47(2):498-519.
164 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
165 *
166 * \anchor MiQ04 \ref MiQ04
167 * T. Minka and Y. Qi (2004):
168 * "Tree-structured Approximations by Expectation Propagation",
169 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.
170 * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
171 *
172 * \anchor MoR05 \ref MoR05
173 * A. Montanari and T. Rizzo (2005):
174 * "How to Compute Loop Corrections to the Bethe Approximation",
175 * <em>Journal of Statistical Mechanics: Theory and Experiment</em>
176 * 2005(10)-P10011.
177 * http://stacks.iop.org/1742-5468/2005/P10011
178 *
179 * \anchor YFW05 \ref YFW05
180 * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
181 * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
182 * <em>IEEE Transactions on Information Theory</em>
183 * 51(7):2282-2312.
184 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
185 *
186 * \anchor HAK03 \ref HAK03
187 * T. Heskes and C. A. Albers and H. J. Kappen (2003):
188 * "Approximate Inference and Constrained Optimization",
189 * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.
190 * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
191 *
192 * \anchor MoK07 \ref MoK07
193 * J. M. Mooij and H. J. Kappen (2007):
194 * "Loop Corrections for Approximate Inference on Factor Graphs",
195 * <em>Journal of Machine Learning Research</em> 8:1113-1143.
196 * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
197 *
198 * \anchor MoK07b \ref MoK07b
199 * J. M. Mooij and H. J. Kappen (2007):
200 * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
201 * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.
202 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
203 *
204 * \anchor EaG09 \ref EaG09
205 * F. Eaton and Z. Ghahramani (2009):
206 * "Choosing a Variable to Clamp",
207 * <em>Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS 2009)</em> 5:145-152
208 * http://jmlr.csail.mit.edu/proceedings/papers/v5/eaton09a/eaton09a.pdf
209 */
210
211
212 /** \page fileformat libDAI factorgraph file format
213 *
214 * This page describes the .fg fileformat used in libDAI to store factor graphs.
215 * Markov Random Fields are special cases of factor graphs, as are Bayesian
216 * networks. A factor graph can be specified as follows: for each factor, one has
217 * to specify which variables occur in the factor, what their respective
218 * cardinalities (i.e., number of possible values) are, and a table listing all
219 * the values of that factor for all possible configurations of these variables.
220 * A .fg file is not much more than that. It starts with a line containing the
221 * number of factors in that graph, followed by an empty line. Then all factors
222 * are specified, one block for each factor, where the blocks are seperated by
223 * empty lines. Each variable occurring in the factor graph has a unique
224 * identifier, its index (which should be a nonnegative integer). Comment lines
225 * start with #.
226 *
227 * Each block starts with a line containing the number of variables in that
228 * factor. The second line contains the indices of these variables, seperated by
229 * spaces (indices are nonnegative integers and to avoid confusion, it is
230 * suggested to start counting at 0). The third line contains the number of
231 * possible values of each of these variables, also seperated by spaces. Note that
232 * there is some redundancy here, since if a variable appears in more than one
233 * factor, the cardinality of that variable appears several times in the .fg file.
234 * The fourth line contains the number of nonzero entries in the factor table.
235 * The rest of the lines contain these nonzero entries; each entry consists of a
236 * table index, followed by white-space, followed by the value corresponding to
237 * that table index. The most difficult part is getting the indexing right. The
238 * convention that is used is that the left-most variables cycle through their
239 * values the fastest (similar to MATLAB indexing of multidimensional arrays). An
240 * example block describing one factor is:
241 *
242 * 3\n
243 * 4 8 7\n
244 * 3 2 2\n
245 * 11\n
246 * 0 0.1\n
247 * 1 3.5\n
248 * 2 2.8\n
249 * 3 6.3\n
250 * 4 8.4\n
251 * 6 7.4\n
252 * 7 2.4\n
253 * 8 8.9\n
254 * 9 1.3\n
255 * 10 1.6\n
256 * 12 6.4\n
257 * 11 2.6\n
258 *
259 * which corresponds to the following factor:
260 *
261 * \f[
262 * \begin{array}{ccc|c}
263 * x_4 & x_8 & x_7 & \mbox{value}\\
264 * \hline
265 * 0 & 0 & 0 & 0.1\\
266 * 1 & 0 & 0 & 3.5\\
267 * 2 & 0 & 0 & 2.8\\
268 * 0 & 1 & 0 & 6.3\\
269 * 1 & 1 & 0 & 8.4\\
270 * 2 & 1 & 0 & 0.0\\
271 * 0 & 0 & 1 & 7.4\\
272 * 1 & 0 & 1 & 2.4\\
273 * 2 & 0 & 1 & 8.9\\
274 * 0 & 1 & 1 & 1.3\\
275 * 1 & 1 & 1 & 1.6\\
276 * 2 & 1 & 1 & 2.6
277 * \end{array}
278 * \f]
279 *
280 * Note that the value of x_4 changes fastest, followed by that of x_8, and x_7
281 * varies the slowest, corresponding to the second line of the block ("4 8 7").
282 * Further, x_4 can take on three values, and x_8 and x_7 each have two possible
283 * values, as described in the third line of the block ("3 2 2"). The table
284 * contains 11 non-zero entries (all except for the fifth entry). Note that the
285 * eleventh and twelveth entries are interchanged.
286 *
287 * A final note: the internal representation in libDAI of the factor above is
288 * different, because the variables are ordered according to their indices
289 * (i.e., the ordering would be x_4 x_7 x_8) and the values of the table are
290 * stored accordingly, with the variable having the smallest index changing
291 * fastest:
292 *
293 * \f[
294 * \begin{array}{ccc|c}
295 * x_4 & x_7 & x_8 & \mbox{value}\\
296 * \hline
297 * 0 & 0 & 0 & 0.1\\
298 * 1 & 0 & 0 & 3.5\\
299 * 2 & 0 & 0 & 2.8\\
300 * 0 & 1 & 0 & 7.4\\
301 * 1 & 1 & 0 & 2.4\\
302 * 2 & 1 & 0 & 8.9\\
303 * 0 & 0 & 1 & 6.3\\
304 * 1 & 0 & 1 & 8.4\\
305 * 2 & 0 & 1 & 0.0\\
306 * 0 & 1 & 1 & 1.3\\
307 * 1 & 1 & 1 & 1.6\\
308 * 2 & 1 & 1 & 2.6
309 * \end{array}
310 * \f]
311 */
312
313
314 /** \page license License
315 * \verbinclude COPYING
316 */