+++ /dev/null
-This file describes the .fg fileformat used in libDAI to store factor graphs.
-
-Markov Random Fields are special cases of factor graphs, as are Bayesian
-networks. A factor graph can be specified as follows: for each factor, one has
-to specify which variables occur in the factor, what their respective
-cardinalities (i.e., number of possible values) are, and a table listing all
-the values of that factor for all possible configurations of these variables.
-A .fg file is not much more than that. It starts with a line containing the
-number of factors in that graph, followed by an empty line. Then all factors
-are specified, one block for each factor, where the blocks are seperated by
-empty lines. Each variable occurring in the factor graph has a unique
-identifier, its index (which should be a nonnegative integer). Comment lines
-start with #.
-
-Each block starts with a line containing the number of variables in that
-factor. The second line contains the indices of these variables, seperated by
-spaces (indices are nonnegative integers and to avoid confusion, it is
-suggested to start counting at 0). The third line contains the number of
-possible values of each of these variables, also seperated by spaces. Note that
-there is some redundancy here, since if a variable appears in more than one
-factor, the cardinality of that variable appears several times in the .fg file.
-The fourth line contains the number of nonzero entries in the factor table.
-The rest of the lines contain these nonzero entries; each entry consists of a
-table index, followed by white-space, followed by the value corresponding to
-that table index. The most difficult part is getting the indexing right. The
-convention that is used is that the left-most variables cycle through their
-values the fastest (similar to MATLAB indexing of multidimensional arrays). An
-example block describing one factor is:
-
-3
-4 8 7
-3 2 2
-11
-0 0.1
-1 3.5
-2 2.8
-3 6.3
-4 8.4
-6 7.4
-7 2.4
-8 8.9
-9 1.3
-10 1.6
-12 6.4
-11 2.6
-
-which corresponds to the following factor:
-
-x_4 x_8 x_7 | value
- 0 0 0 | 0.1
- 1 0 0 | 3.5
- 2 0 0 | 2.8
- 0 1 0 | 6.3
- 1 1 0 | 8.4
- 2 1 0 | 0.0
- 0 0 1 | 7.4
- 1 0 1 | 2.4
- 2 0 1 | 8.9
- 0 1 1 | 1.3
- 1 1 1 | 1.6
- 2 1 1 | 2.6
-
-Note that the value of x_4 changes fastest, followed by that of x_8, and x_7
-varies the slowest, corresponding to the second line of the block ("4 8 7").
-Further, x_4 can take on three values, and x_8 and x_7 each have two possible
-values, as described in the third line of the block ("3 2 2"). The table
-contains 11 non-zero entries (all except for the fifth entry). Note that the
-eleventh and twelveth entries are interchanged.
-
-A final note: the internal representation in libDAI of the factor above is
-different, because the variables are ordered according to their indices
-(i.e., the ordering would be x_4 x_7 x_8) and the values of the table are
-stored accordingly, with the variable having the smallest index changing
-fastest:
-
-x_4 x_7 x_8 | value
- 0 0 0 | 0.1
- 1 0 0 | 3.5
- 2 0 0 | 2.8
- 0 1 0 | 7.4
- 1 1 0 | 2.4
- 2 1 0 | 8.9
- 0 0 1 | 6.3
- 1 0 1 | 8.4
- 2 0 1 | 0.0
- 0 1 1 | 1.3
- 1 1 1 | 1.6
- 2 1 1 | 2.6
# Flags for the C++ compiler
CCFLAGS=-O3 -Wno-deprecated -Wall -W -Wextra -fpic -Iinclude -Llib
-ifdef DEBUG
-CCFLAGS:=$(CCFLAGS) -g -DDAI_DEBUG
-endif
-
-ifdef WINDOWS
-CCFLAGS:=$(CCFLAGS) -DWINDOWS
-endif
+CCDEBUGFLAGS=-g -DDAI_DEBUG
-OBJECTS:=exactinf$(OE)
-ifdef WITH_BP
-CCFLAGS:=$(CCFLAGS) -DDAI_WITH_BP
-OBJECTS:=$(OBJECTS) bp$(OE)
-endif
-ifdef WITH_MF
-CCFLAGS:=$(CCFLAGS) -DDAI_WITH_MF
-OBJECTS:=$(OBJECTS) mf$(OE)
-endif
-ifdef WITH_HAK
-CCFLAGS:=$(CCFLAGS) -DDAI_WITH_HAK
-OBJECTS:=$(OBJECTS) hak$(OE)
-endif
-ifdef WITH_LC
-CCFLAGS:=$(CCFLAGS) -DDAI_WITH_LC
-OBJECTS:=$(OBJECTS) lc$(OE)
-endif
-ifdef WITH_TREEEP
-CCFLAGS:=$(CCFLAGS) -DDAI_WITH_TREEEP
-OBJECTS:=$(OBJECTS) treeep$(OE)
-endif
-ifdef WITH_JTREE
-CCFLAGS:=$(CCFLAGS) -DDAI_WITH_JTREE
-OBJECTS:=$(OBJECTS) jtree$(OE)
-endif
-ifdef WITH_MR
-CCFLAGS:=$(CCFLAGS) -DDAI_WITH_MR
-OBJECTS:=$(OBJECTS) mr$(OE)
-endif
+# Build targets
+TARGETS=tests utils $(LIB)/libdai$(LE) examples testregression doc
ifdef WITH_MATLAB
-# Replace the following by the directory where Matlab has been installed
-MATLABDIR=/agbs/share/sw/matlab
-MEX=$(MATLABDIR)/bin/mex
-MEXFLAGS=-Iinclude CXX\#$(CC) CXXFLAGS\#'-O3 -Wno-deprecated -Wall -W -Wextra -fpic'
-ifdef DEBUG
-MEXFLAGS:=$(MEXFLAGS) -g -DDAI_DEBUG
+ # Replace the following by the directory where Matlab has been installed
+ MATLABDIR=/agbs/share/sw/matlab
+ MEX=$(MATLABDIR)/bin/mex
+ MEXFLAGS=-Iinclude CXX\#$(CC) CXXFLAGS\#'-O3 -Wno-deprecated -Wall -W -Wextra -fpic'
endif
-ifdef NEW_MATLAB
-MEXFLAGS:=$(MEXFLAGS) -largeArrayDims
-else
-MEXFLAGS:=$(MEXFLAGS) -DSMALLMEM
-endif
-endif
-
-HEADERS=$(INC)/bipgraph.h $(INC)/index.h $(INC)/var.h $(INC)/factor.h $(INC)/varset.h $(INC)/smallset.h $(INC)/prob.h $(INC)/daialg.h $(INC)/properties.h $(INC)/alldai.h $(INC)/enum.h $(INC)/exceptions.h
-TARGETS=tests utils $(LIB)/libdai$(LE) testregression doc examples
-ifdef WITH_MATLAB
-TARGETS:=$(TARGETS) matlabs
-endif
-all : $(TARGETS)
- echo -e "\a"
-examples : examples/example$(EE) examples/example_bipgraph$(EE) examples/example_varset$(EE)
+include Makefile.shared
-matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)
$(LIB)/libdai$(LE) : bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)
-mkdir -p lib
ar rcus $(LIB)/libdai$(LE) bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)
-tests : tests/testdai$(EE)
-
-utils : utils/createfg$(EE) utils/fg2dot$(EE) utils/fginfo$(EE)
-
-testregression : tests/testdai
+testregression : tests/testdai$(EE)
@echo Starting regression test...this can take a minute or so!
cd tests; time ./testregression; cd ..
doc : $(INC)/*.h $(SRC)/*.cpp examples/*.cpp doxygen.conf
- -mkdir -p doc
doxygen doxygen.conf
.PHONY : clean
-rm utils/fg2dot$(EE) utils/createfg$(EE) utils/fginfo$(EE)
-rm -R doc
-rm -R lib
-
-include Makefile.shared
# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ifdef DEBUG
+ CCFLAGS:=$(CCFLAGS) $(CCDEBUGFLAGS)
+endif
+ifdef WINDOWS
+ CCFLAGS:=$(CCFLAGS) -DWINDOWS
+endif
+ifdef WITH_MATLAB
+ TARGETS:=$(TARGETS) matlabs
+ ifdef DEBUG
+ MEXFLAGS:=$(MEXFLAGS) $(CCDEBUGFLAGS)
+ endif
+ ifdef NEW_MATLAB
+ MEXFLAGS:=$(MEXFLAGS) -largeArrayDims
+ else
+ MEXFLAGS:=$(MEXFLAGS) -DSMALLMEM
+ endif
+endif
+
+
+OBJECTS:=exactinf$(OE)
+ifdef WITH_BP
+ CCFLAGS:=$(CCFLAGS) -DDAI_WITH_BP
+ OBJECTS:=$(OBJECTS) bp$(OE)
+endif
+ifdef WITH_MF
+ CCFLAGS:=$(CCFLAGS) -DDAI_WITH_MF
+ OBJECTS:=$(OBJECTS) mf$(OE)
+endif
+ifdef WITH_HAK
+ CCFLAGS:=$(CCFLAGS) -DDAI_WITH_HAK
+ OBJECTS:=$(OBJECTS) hak$(OE)
+endif
+ifdef WITH_LC
+ CCFLAGS:=$(CCFLAGS) -DDAI_WITH_LC
+ OBJECTS:=$(OBJECTS) lc$(OE)
+endif
+ifdef WITH_TREEEP
+ CCFLAGS:=$(CCFLAGS) -DDAI_WITH_TREEEP
+ OBJECTS:=$(OBJECTS) treeep$(OE)
+endif
+ifdef WITH_JTREE
+ CCFLAGS:=$(CCFLAGS) -DDAI_WITH_JTREE
+ OBJECTS:=$(OBJECTS) jtree$(OE)
+endif
+ifdef WITH_MR
+ CCFLAGS:=$(CCFLAGS) -DDAI_WITH_MR
+ OBJECTS:=$(OBJECTS) mr$(OE)
+endif
+
+
+HEADERS=$(INC)/bipgraph.h $(INC)/index.h $(INC)/var.h $(INC)/factor.h $(INC)/varset.h $(INC)/smallset.h $(INC)/prob.h $(INC)/daialg.h $(INC)/properties.h $(INC)/alldai.h $(INC)/enum.h $(INC)/exceptions.h
+
+
+all : $(TARGETS)
+
+examples : examples/example$(EE) examples/example_bipgraph$(EE) examples/example_varset$(EE)
+
+matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)
+
+tests : tests/testdai$(EE)
+
+utils : utils/createfg$(EE) utils/fg2dot$(EE) utils/fginfo$(EE)
+
+
bipgraph$(OE) : $(SRC)/bipgraph.cpp $(HEADERS)
$(CC) $(CCFLAGS) -c $(SRC)/bipgraph.cpp
# Build with debug info?\r
DEBUG=true\r
# Build matlab interface?\r
-#WITH_MATLAB=true\r
+WITH_MATLAB=\r
# New/old matlab version?\r
NEW_MATLAB=true\r
# Windows or linux (default)?\r
# We use the BOOST Program Options library\r
BOOSTLIBS=/LIBPATH:C:\boost_1_36_0\stage\lib\r
\r
-# Compile using GNU C++ Compiler\r
+# Compile using Visual C++ Compiler\r
CC=cl\r
# Output filename option\r
CCO=/Fe\r
\r
# Flags for the C++ compiler\r
CCFLAGS=/Iinclude /IC:\boost_1_36_0 /EHsc /Ox\r
-!IFDEF DEBUG\r
-CCFLAGS=$(CCFLAGS) /Zi /DDAI_DEBUG\r
-!ENDIF\r
-\r
-!IFDEF WINDOWS\r
-CCFLAGS=$(CCFLAGS) /DWINDOWS\r
-!ENDIF\r
-\r
-OBJECTS=exactinf$(OE)\r
-!IFDEF WITH_BP\r
-CCFLAGS=$(CCFLAGS) /DDAI_WITH_BP\r
-OBJECTS=$(OBJECTS) bp$(OE)\r
-!ENDIF\r
-!IFDEF WITH_MF\r
-CCFLAGS=$(CCFLAGS) /DDAI_WITH_MF\r
-OBJECTS=$(OBJECTS) mf$(OE)\r
-!ENDIF\r
-!IFDEF WITH_HAK\r
-CCFLAGS=$(CCFLAGS) /DDAI_WITH_HAK\r
-OBJECTS=$(OBJECTS) hak$(OE)\r
-!ENDIF\r
-!IFDEF WITH_LC\r
-CCFLAGS=$(CCFLAGS) /DDAI_WITH_LC\r
-OBJECTS=$(OBJECTS) lc$(OE)\r
-!ENDIF\r
-!IFDEF WITH_TREEEP\r
-CCFLAGS=$(CCFLAGS) /DDAI_WITH_TREEEP\r
-OBJECTS=$(OBJECTS) treeep$(OE)\r
-!ENDIF\r
-!IFDEF WITH_JTREE\r
-CCFLAGS=$(CCFLAGS) /DDAI_WITH_JTREE\r
-OBJECTS=$(OBJECTS) jtree$(OE)\r
-!ENDIF\r
-!IFDEF WITH_MR\r
-CCFLAGS=$(CCFLAGS) /DDAI_WITH_MR\r
-OBJECTS=$(OBJECTS) mr$(OE)\r
-!ENDIF\r
-\r
-!IFDEF WITH_MATLAB\r
-# Replace the following by the directory where Matlab has been installed\r
-MATLABDIR=c:\matlab\r
-MEX=$(MATLABDIR)\bin\mex\r
-MEXFLAGS=-Iinclude CXX\#$(CC) CXXFLAGS\#"/EHsc /Ox"\r
-!IFDEF DEBUG\r
-MEXFLAGS=$(MEXFLAGS) -g /DDAI_DEBUG\r
-!ENDIF\r
-!IFDEF NEW_MATLAB\r
-MEXFLAGS=$(MEXFLAGS) -largeArrayDims\r
-!ELSE\r
-MEXFLAGS=$(MEXFLAGS) /DSMALLMEM\r
-!ENDIF\r
-!ENDIF\r
-\r
-HEADERS=$(INC)/bipgraph.h $(INC)/index.h $(INC)/var.h $(INC)/factor.h $(INC)/varset.h $(INC)/smallset.h $(INC)/prob.h $(INC)/daialg.h $(INC)/properties.h $(INC)/alldai.h $(INC)/enum.h $(INC)/exceptions.h\r
-\r
-TARGETS=tests utils $(LIB)/libdai$(LE) examples\r
-# testregression disabled, it uses diff\r
-# doc disabled, it uses doxygen, graphviz and latex\r
-!IFDEF WITH_MATLAB\r
-TARGETS = $(TARGETS) matlabs\r
-!ENDIF\r
-all : $(TARGETS)\r
-\r
-examples : examples/example$(EE) examples/example_bipgraph$(EE) examples/example_varset$(EE)\r
-\r
-matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)\r
+CCDEBUGFLAGS=/Zi -DDAI_DEBUG\r
+\r
+# Build targets\r
+TARGETS=tests utils $(LIB)/libdai$(LE) examples # testregression doc\r
+\r
+ifdef WITH_MATLAB\r
+ # Replace the following by the directory where Matlab has been installed\r
+ MATLABDIR=c:\matlab\r
+ MEX=$(MATLABDIR)\bin\mex\r
+ MEXFLAGS=-Iinclude CXX\#$(CC) CXXFLAGS\#"/EHsc /Ox"\r
+endif\r
\r
-$(LIB)/libdai$(LE) : bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)\r
- lib /out:$(LIB)/libdai$(LE) bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)\r
\r
-tests : tests/testdai$(EE)\r
+include Makefile.shared\r
\r
-utils : utils/createfg$(EE) utils/fg2dot$(EE) utils/fginfo$(EE)\r
+\r
+$(LIB)/libdai$(LE) : bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)\r
+ lib /out:$(LIB)/libdai$(LE) bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)\r
\r
testregression : tests/testdai$(EE)\r
echo Starting regression test...this can take a minute or so!\r
doc : $(INC)/*.h $(SRC)/*.cpp examples/*.cpp doxygen.conf\r
doxygen doxygen.conf\r
\r
+.PHONY : clean\r
clean :\r
- del *$(OE) *.ilk *.pdb *$(EE) matlab\*$(ME) examples\*$(EE) tests\testdai$(EE) tests\*.pdb tests\*.ilk utils\*$(EE) utils\*.pdb utils\*.ilk $(LIB)\libdai$(LE)\r
-\r
-!INCLUDE Makefile.shared\r
+ -del *$(OE) *.ilk *.pdb *$(EE) matlab\*$(ME) examples\*$(EE) tests\testdai$(EE) tests\*.pdb tests\*.ilk utils\*$(EE) utils\*.pdb utils\*.ilk $(LIB)\libdai$(LE)\r
+++ /dev/null
-TODO:
-
-- Improve documentation.
- * COPYING
- * FILEFORMAT
- * Merge README with mainpage, removing duplicate text
- * Document examples, tests and utils
-
-- Adapt http://www.boost.org/development/requirements.html#Design_and_Programming
-
-- Use "gcc -MM" to generate dependencies for targets.
- Maybe even better: switch to cmake (see http://lwn.net/Articles/188693/)
- cross-platform build system.
-
-
-OPTIMIZATION:
-
-- BipartiteGraph::isConnected should be optimized using boost::graph
-
-- Replace VarSets by smallSet<size_t> where appropriate, in order to minimize the use of findVar().
-
-- A DAIAlg<T> should not inherit from a FactorGraph/RegionGraph, but should
- store a reference to it. This prevents needless copying of (possibly large)
- data structures. Disadvantage: the caller must not change the data structure
- between calls. (Maybe a smart_ptr would help here?)
- Also, general marginalization functions now copy a complete object. Instead, it
- would make more sense that they construct a new object without copying the
- FactorGraph. Or they can simply be made methods of the general InfAlg class.
-
-
-IDEAS WORTH EXPLORING:
-
-- Use a PropertySet as output of a DAIAlg, instead of functions like maxDiff and Iterations().
-
-- Cache second-order neighborhoods (delta's) in BipGraph?
-
-- If you ever do a rewrite, make sure that the graphical properties are not
- entangled with the probabilistic properties. E.g., a factor graph really
- should be represented as a bipartite graph, with a separate array of variable
- labels and dimensions, and a seperate array of (pointers to) factor tables. In
- this way, each factor could be implemented differently, e.g., we could have
- some sparse factors, some noisy-OR factors, some dense factors, some arbitrary
- precision factors, etc. Or we could make more use of templates to have a more
- generic factor graph.
-
-- Use Boost::uBLAS framework to deal with matrices, especially, with
- 2D sparse matrices.
- See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
- and tests/errorbounds/errorbounds3
-
-- Introduce naming scheme:
- all Vars and VarSets should be named v_..., e.g. v_i instead of i
- all Factors should be named f_..., e.g. f_I instead of I
- all indices should be named _..., e.g. _k instead of k
- all iterators should be named i_, e.g. i_i is an iterator to i
- all const_iterators should be named ci_, e.g. ci_i is an iterator to i
-
-- Define a better fileformat for .fg files (maybe using XML)?
-
-- Alternative implementation of undo factor changes: the only things that have to be
- undone are setting a factor to all ones and setting a factor to a Kronecker delta. This
- could also be implemented in the factor itself, which could maintain its state
- (one/delta/full) and act accordingly.
-
-- Think about the RegionGraph::fac2OR variable: a better implementation of this feature is
- probably possible.
-
-- Optimize GBP with precalculated indices.
-
-- Optimize all indices as follows: keep a cache of all indices that have been
- computed (use a hash). Then, instead of computing on the fly, use the precomputed ones.
-
-- Variable elimination should be implemented generically using a function
- object that tells you which variable to delete.
-
-- Improve general support for graphs and trees.
-
-- Add support for sparse potentials.
-
-- Optimize BP_SEQMAX (it should use a better data structure than a vector for the residuals).
-
-
-BAD IDEAS:
-
-- A FactorGraph and a RegionGraph are often equipped with
- additional properties for nodes and edges. The code to initialize those
- is often quite similar; maybe this can be abstracted to classes
- like ExtFactorGraph and ExtRegionGraph (Ext stands for Extended), e.g.
- template <typename NodeProperties, typename EdgeProperties>
- class ExtFactorGraph : public FactorGraph {
- public:
- std::vector<NodeProperties> nodeProps;
- std::vector<std::vector<EdgeProperties> > edgeProps;
- // blabla
- }
- A disadvantage of this approach may be worse cachability.
- A problem is if there are nog properties for nodes (type 1), nodes (type 2)
- or edges. Maybe this can be solved using specializations, or using variadac
- template arguments or something similar?
- Idea: you could define a "class Empty {}", and add some code that checks for
- the typeid, comparing it with Empty, and doing something special in that case
- (e.g., not allocating memory).
- The main disadvantage of this approach seems to be that it leads to even more
- entanglement.
-
-- Instead of polymorphism by inheritance, use polymorphism by template
- parameterization. For example, the real reason you introduced the complicated
- inheritance scheme was for functions like
- Factor calcMarginal( const InferenceAlgorithm & obj, const VarSet & ns, bool reInit );
- Now instead, you could use a template function:
- template<typename InferenceAlgorithm>
- Factor calcMarginal( const InferenceAlgorithm &obj, const VarSet &ns, bool reInit );
- This would assume that InferenceAlgorithm supports certain methods, like
- clone(), grm(), ...... Ideally, you would use concepts to define different
- classes of inference algorithms with different capabilities, for example the
- ability to calculate logZ, the ability to calculate marginals, the ability to
- calculate bounds, the ability to calculate MAP states, etcetera. Then, use
- traits classes in order to be able to query the capabilities of the model. For
- example, you would be able to query whether the inference algorithm supports
- calculation of logZ. Unfortunately, this is compile-time polymorphism, whereas
- tests/test needs runtime polymorphism.
# will result in a user-defined paragraph with heading "Side Effects:".
# You can put \n's in the value part of an alias to insert newlines.
-ALIASES =
+ALIASES = "idea=\xrefitem ideas \"Idea\" \"Ideas worth exploring\""
# Set the OPTIMIZE_OUTPUT_FOR_C tag to YES if your project consists of C
# sources only. Doxygen will then generate output that is more tailored for C.
# directories like "/usr/src/myproject". Separate the files or directories
# with spaces.
-INPUT = src \
- include/dai
+INPUT = src include/dai
# This tag can be used to specify the character encoding of the source files
# that doxygen parses. Internally doxygen uses the UTF-8 encoding, which is
# should be searched for input files as well. Possible values are YES and NO.
# If left blank NO is used.
-RECURSIVE = NO
+RECURSIVE = YES
# The EXCLUDE tag can be used to specify files and/or directories that should
# excluded from the INPUT source files. This way you can easily exclude a
} // end of namespace dai
-/** \mainpage libDAI reference manual
- * \author Joris Mooij
- * \version git HEAD
- * \date October 8, 2008
- *
- * \section about About libDAI
- * libDAI is a free/open source C++ library (licensed under GPL) that provides
- * implementations of various (approximate) inference methods for discrete
- * graphical models. libDAI supports arbitrary factor graphs with discrete
- * variables; this includes discrete Markov Random Fields and Bayesian
- * Networks.
- *
- * The library is targeted at researchers; to be able to use the library, a
- * good understanding of graphical models is needed.
- *
- * \section limitations Limitations
- * libDAI is not intended to be a complete package for approximate inference.
- * Instead, it should be considered as an "inference engine", providing
- * various inference methods. In particular, it contains no GUI, currently
- * only supports its own file format for input and output (although support
- * for standard file formats may be added later), and provides very limited
- * visualization functionalities.
- *
- * \section features Features
- * Currently, libDAI supports the following (approximate) inference methods:
- * - Exact inference by brute force enumeration;
- * - Exact inference by junction-tree methods;
- * - Mean Field;
- * - Loopy Belief Propagation [\ref KFL01];
- * - Tree Expectation Propagation [\ref MiQ04];
- * - Generalized Belief Propagation [\ref YFW05];
- * - Double-loop GBP [\ref HAK03];
- * - Various variants of Loop Corrected Belief Propagation
- * [\ref MoK07, \ref MoR05].
- *
- * \section language Why C++?
- * Because libDAI is implemented in C++, it is very fast compared with
- * implementations in MatLab (a factor 1000 faster is not uncommon).
- * libDAI does provide a MatLab interface for easy integration with MatLab.
- *
- * \section quickstart Quick start
- * An example program illustrating basic usage of libDAI is given in examples/example.cpp.
- */
-
-/// \example example.cpp
-
-/** \page Bibliography
- * \section Bibliograpy
- * \anchor KFL01 \ref KFL01
- * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
- * "Factor Graphs and the Sum-Product Algorithm",
- * <em>IEEE Transactions on Information Theory</em> 47(2):498-519.
- * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
- *
- * \anchor MiQ04 \ref MiQ04
- * T. Minka and Y. Qi (2004):
- * "Tree-structured Approximations by Expectation Propagation",
- * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.
- * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
- *
- * \anchor MoR05 \ref MoR05
- * A. Montanari and T. Rizzo (2005):
- * "How to Compute Loop Corrections to the Bethe Approximation",
- * <em>Journal of Statistical Mechanics: Theory and Experiment</em>
- * 2005(10)-P10011.
- * http://stacks.iop.org/1742-5468/2005/P10011
- *
- * \anchor YFW05 \ref YFW05
- * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
- * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
- * <em>IEEE Transactions on Information Theory</em>
- * 51(7):2282-2312.
- * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
- *
- * \anchor HAK03 \ref HAK03
- * T. Heskes and C. A. Albers and H. J. Kappen (2003):
- * "Approximate Inference and Constrained Optimization",
- * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.
- * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
- *
- * \anchor MoK07 \ref MoK07
- * J. M. Mooij and H. J. Kappen (2007):
- * "Loop Corrections for Approximate Inference on Factor Graphs",
- * <em>Journal of Machine Learning Research</em> 8:1113-1143.
- * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
- *
- * \anchor MoK07b \ref MoK07b
- * J. M. Mooij and H. J. Kappen (2007):
- * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
- * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.
- * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
- */
-
-
#endif
* neighboring nodes of type 1.
* Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
* Neighbor structures, describing its neighboring nodes of the other type.
+ * \idea Cache second-order neighborhoods in BipartiteGraph.
*/
class BipartiteGraph {
public:
std::vector<size_t> delta2( size_t n2, bool include = false ) const;
/// Returns true if the graph is connected
+ /** \todo Should be optimized by invoking boost::graph library
+ */
bool isConnected() const;
/// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
/// Approximate inference algorithm "(Loopy) Belief Propagation"
+/** \todo Optimize BP_SEQMAX (it should use a better data structure than a vector for the residuals).
+ */
class BP : public DAIAlgFG {
private:
typedef std::vector<size_t> ind_t;
/* the interactions that are created along the way.
* \param ElimSeq A set of outer clusters and an elimination sequence
* \return A set of elimination "cliques"
+ * \todo Variable elimination should be implemented generically using a function
+ * object that tells you which variable to delete.
*/
ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
/// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.
+/** \todo General marginalization functions like calcMarginal now copy a complete InfAlg object. Instead,
+ * it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph.
+ * Or they can simply be made methods of the general InfAlg class.
+ * \idea Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().
+ */
class InfAlg {
public:
/// Virtual desctructor (needed because this class contains virtual functions)
/// Combines an InfAlg and a graphical model, e.g., a FactorGraph or RegionGraph
/** \tparam GRM Should be castable to FactorGraph
+ * \todo A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should
+ * store a reference to the graphical model object. This prevents needless copying
+ * of (possibly large) data structures. Disadvantage: the caller must not change
+ * the graphical model between calls to the inference algorithm (maybe a smart_ptr
+ * or some locking mechanism would help here?).
*/
template <class GRM>
class DAIAlg : public InfAlg, public GRM {
--- /dev/null
+/* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
+ Radboud University Nijmegen, The Netherlands /
+ Max Planck Institute for Biological Cybernetics, Germany
+
+ This file is part of libDAI.
+
+ libDAI is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ libDAI is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with libDAI; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+*/
+
+
+/** \file
+ * \brief Contains additional doxygen documentation
+ *
+ * \todo Merge COPYING into doxygen documentation
+ * \todo Merge README into doxygen documentation
+ * \todo Document examples, tests and utils
+ *
+ * \todo Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming
+ *
+ * \todo Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html
+ * \todo Investigate whether switching to cmake as cross-platform build system would be a good idea.
+ * \todo Switch from nmake to GNU make under Windows http://gnuwin32.sourceforge.net/
+ *
+ * \todo Replace VarSets by SmallSet<size_t> where appropriate, in order to minimize the use of FactorGraph::findVar().
+ *
+ * \idea Disentangle structures. In particular, ensure that graphical properties are not
+ * entangled with probabilistic properties. For example, a FactorGraph contains several
+ * components:
+ * - a BipartiteGraph
+ * - an array of variable labels
+ * - an array of variable state space sizes
+ * - an array of pointers to factor value vectors
+ * In this way, each factor could be implemented differently, e.g., we could have
+ * some sparse factors, some noisy-OR factors, some dense factors, some arbitrary
+ * precision factors, etc.
+ *
+ * \idea Use Boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.
+ * See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
+ *
+ * \idea Introduce naming scheme:
+ * - all Vars should be named v_..., e.g. v_i instead of i
+ * - all VarSets should be named vs_..., e.g. v_i instead of i
+ * - all Factors should be named f_..., e.g. f_I instead of I
+ * - all indices should be named _..., e.g. _k instead of k
+ * - all iterators should be named i_, e.g. i_i is an iterator to i
+ * - all const_iterators should be named ci_, e.g. ci_i is an iterator to i
+ **/
+
+
+/** \page discussion Discussion of possible improvements
+ * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs
+ *
+ * A FactorGraph and a RegionGraph are often equipped with
+ * additional properties for nodes and edges. The code to initialize those
+ * is often quite similar. Maybe one could abstract this, e.g.:
+ * \code
+ * template <typename Node1Properties, typename Node2Properties, typename EdgeProperties>
+ * class ExtFactorGraph : public FactorGraph {
+ * public:
+ * std::vector<Node1Properties> node1Props;
+ * std::vector<Node2Properties> node2Props;
+ * std::vector<std::vector<EdgeProperties> > edgeProps;
+ * // ...
+ * }
+ * \endcode
+ *
+ * Advantages:
+ * - Less code duplication.
+ * - Easier maintainability.
+ * - Easier to write new inference algorithms.
+ *
+ * Disadvantages:
+ * - Cachability may be worse.
+ * - A problem is the case where there are no properties for either type of nodes or for edges.
+ * Maybe this can be solved using specializations, or using variadac template arguments?
+ * Another possible solution would be to define a "class Empty {}", and add some code
+ * that checks for the typeid, comparing it with Empty, and doing something special in that case
+ * (e.g., not allocating memory).
+ * - The main disadvantage of this approach seems to be that it leads to even more entanglement.
+ * Therefore this is probably a bad idea.
+ *
+ * \section discuss_templates Polymorphism by template parameterization
+ * Instead of polymorphism by inheritance, use polymorphism by template parameterization.
+ * For example, the real reason for introducing the complicated inheritance scheme of InfAlg
+ * was for functions like dai::calcMarginal. Instead, one could use a template function:
+ * \code
+ * template<typename InfAlg>
+ * Factor calcMarginal( const InfAlg &obj, const VarSet &ns, bool reInit );
+ * \endcode
+ * This would assume that the type InfAlg supports certain methods. Ideally, one would use
+ * concepts to define different classes of inference algorithms with different capabilities,
+ * for example the ability to calculate logZ, the ability to calculate marginals, the ability to
+ * calculate bounds, the ability to calculate MAP states, etc. Then, one would use traits
+ * classes in order to be able to query the capabilities of the model. For example, one would be
+ * able to query whether the inference algorithm supports calculation of logZ. Unfortunately,
+ * this is compile-time polymorphism, whereas tests/testdai needs runtime polymorphism.
+ * Therefore this is probably a bad idea.
+ */
+
+
+/** \mainpage libDAI reference manual
+ * \author Joris Mooij
+ * \version git HEAD
+ * \date October 10, 2008
+ *
+ * \section about About libDAI
+ * libDAI is a free/open source C++ library (licensed under GPL) that provides
+ * implementations of various (approximate) inference methods for discrete
+ * graphical models. libDAI supports arbitrary factor graphs with discrete
+ * variables; this includes discrete Markov Random Fields and Bayesian
+ * Networks.
+ *
+ * The library is targeted at researchers; to be able to use the library, a
+ * good understanding of graphical models is needed.
+ *
+ * \section limitations Limitations
+ * libDAI is not intended to be a complete package for approximate inference.
+ * Instead, it should be considered as an "inference engine", providing
+ * various inference methods. In particular, it contains no GUI, currently
+ * only supports its own file format for input and output (although support
+ * for standard file formats may be added later), and provides very limited
+ * visualization functionalities.
+ *
+ * \section features Features
+ * Currently, libDAI supports the following (approximate) inference methods:
+ * - Exact inference by brute force enumeration;
+ * - Exact inference by junction-tree methods;
+ * - Mean Field;
+ * - Loopy Belief Propagation [\ref KFL01];
+ * - Tree Expectation Propagation [\ref MiQ04];
+ * - Generalized Belief Propagation [\ref YFW05];
+ * - Double-loop GBP [\ref HAK03];
+ * - Various variants of Loop Corrected Belief Propagation
+ * [\ref MoK07, \ref MoR05].
+ *
+ * \section language Why C++?
+ * Because libDAI is implemented in C++, it is very fast compared with
+ * implementations in MatLab (a factor 1000 faster is not uncommon).
+ * libDAI does provide a MatLab interface for easy integration with MatLab.
+ */
+
+
+/** \example example.cpp
+ */
+
+
+/** \page quickstart Quick start
+ * An example program illustrating basic usage of libDAI is given in examples/example.cpp.
+ */
+
+
+/** \page biboliography Bibliography
+ * \section Bibliograpy
+ * \anchor KFL01 \ref KFL01
+ * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
+ * "Factor Graphs and the Sum-Product Algorithm",
+ * <em>IEEE Transactions on Information Theory</em> 47(2):498-519.
+ * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
+ *
+ * \anchor MiQ04 \ref MiQ04
+ * T. Minka and Y. Qi (2004):
+ * "Tree-structured Approximations by Expectation Propagation",
+ * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.
+ * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
+ *
+ * \anchor MoR05 \ref MoR05
+ * A. Montanari and T. Rizzo (2005):
+ * "How to Compute Loop Corrections to the Bethe Approximation",
+ * <em>Journal of Statistical Mechanics: Theory and Experiment</em>
+ * 2005(10)-P10011.
+ * http://stacks.iop.org/1742-5468/2005/P10011
+ *
+ * \anchor YFW05 \ref YFW05
+ * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
+ * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
+ * <em>IEEE Transactions on Information Theory</em>
+ * 51(7):2282-2312.
+ * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
+ *
+ * \anchor HAK03 \ref HAK03
+ * T. Heskes and C. A. Albers and H. J. Kappen (2003):
+ * "Approximate Inference and Constrained Optimization",
+ * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.
+ * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
+ *
+ * \anchor MoK07 \ref MoK07
+ * J. M. Mooij and H. J. Kappen (2007):
+ * "Loop Corrections for Approximate Inference on Factor Graphs",
+ * <em>Journal of Machine Learning Research</em> 8:1113-1143.
+ * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
+ *
+ * \anchor MoK07b \ref MoK07b
+ * J. M. Mooij and H. J. Kappen (2007):
+ * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
+ * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.
+ * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
+ */
+
+
+/** \page fileformat libDAI factorgraph file format
+ *
+ * This page describes the .fg fileformat used in libDAI to store factor graphs.
+ * Markov Random Fields are special cases of factor graphs, as are Bayesian
+ * networks. A factor graph can be specified as follows: for each factor, one has
+ * to specify which variables occur in the factor, what their respective
+ * cardinalities (i.e., number of possible values) are, and a table listing all
+ * the values of that factor for all possible configurations of these variables.
+ * A .fg file is not much more than that. It starts with a line containing the
+ * number of factors in that graph, followed by an empty line. Then all factors
+ * are specified, one block for each factor, where the blocks are seperated by
+ * empty lines. Each variable occurring in the factor graph has a unique
+ * identifier, its index (which should be a nonnegative integer). Comment lines
+ * start with #.
+ *
+ * Each block starts with a line containing the number of variables in that
+ * factor. The second line contains the indices of these variables, seperated by
+ * spaces (indices are nonnegative integers and to avoid confusion, it is
+ * suggested to start counting at 0). The third line contains the number of
+ * possible values of each of these variables, also seperated by spaces. Note that
+ * there is some redundancy here, since if a variable appears in more than one
+ * factor, the cardinality of that variable appears several times in the .fg file.
+ * The fourth line contains the number of nonzero entries in the factor table.
+ * The rest of the lines contain these nonzero entries; each entry consists of a
+ * table index, followed by white-space, followed by the value corresponding to
+ * that table index. The most difficult part is getting the indexing right. The
+ * convention that is used is that the left-most variables cycle through their
+ * values the fastest (similar to MATLAB indexing of multidimensional arrays). An
+ * example block describing one factor is:
+ *
+ * 3\n
+ * 4 8 7\n
+ * 3 2 2\n
+ * 11\n
+ * 0 0.1\n
+ * 1 3.5\n
+ * 2 2.8\n
+ * 3 6.3\n
+ * 4 8.4\n
+ * 6 7.4\n
+ * 7 2.4\n
+ * 8 8.9\n
+ * 9 1.3\n
+ * 10 1.6\n
+ * 12 6.4\n
+ * 11 2.6\n
+ *
+ * which corresponds to the following factor:
+ *
+ * \f[
+ * \begin{array}{ccc|c}
+ * x_4 & x_8 & x_7 & \mbox{value}\\
+ * \hline
+ * 0 & 0 & 0 & 0.1\\
+ * 1 & 0 & 0 & 3.5\\
+ * 2 & 0 & 0 & 2.8\\
+ * 0 & 1 & 0 & 6.3\\
+ * 1 & 1 & 0 & 8.4\\
+ * 2 & 1 & 0 & 0.0\\
+ * 0 & 0 & 1 & 7.4\\
+ * 1 & 0 & 1 & 2.4\\
+ * 2 & 0 & 1 & 8.9\\
+ * 0 & 1 & 1 & 1.3\\
+ * 1 & 1 & 1 & 1.6\\
+ * 2 & 1 & 1 & 2.6
+ * \end{array}
+ * \f]
+ *
+ * Note that the value of x_4 changes fastest, followed by that of x_8, and x_7
+ * varies the slowest, corresponding to the second line of the block ("4 8 7").
+ * Further, x_4 can take on three values, and x_8 and x_7 each have two possible
+ * values, as described in the third line of the block ("3 2 2"). The table
+ * contains 11 non-zero entries (all except for the fifth entry). Note that the
+ * eleventh and twelveth entries are interchanged.
+ *
+ * A final note: the internal representation in libDAI of the factor above is
+ * different, because the variables are ordered according to their indices
+ * (i.e., the ordering would be x_4 x_7 x_8) and the values of the table are
+ * stored accordingly, with the variable having the smallest index changing
+ * fastest:
+ *
+ * \f[
+ * \begin{array}{ccc|c}
+ * x_4 & x_7 & x_8 & \mbox{value}\\
+ * \hline
+ * 0 & 0 & 0 & 0.1\\
+ * 1 & 0 & 0 & 3.5\\
+ * 2 & 0 & 0 & 2.8\\
+ * 0 & 1 & 0 & 7.4\\
+ * 1 & 1 & 0 & 2.4\\
+ * 2 & 1 & 0 & 8.9\\
+ * 0 & 0 & 1 & 6.3\\
+ * 1 & 0 & 1 & 8.4\\
+ * 2 & 0 & 1 & 0.0\\
+ * 0 & 1 & 1 & 1.3\\
+ * 1 & 1 & 1 & 1.6\\
+ * 2 & 1 & 1 & 2.6
+ * \end{array}
+ * \f]
+ */
+
+
+ /** \page license License
+ * \verbinclude COPYING
+ */
* induced by VarSet::calcState(const std::map<Var,size_t> &).
*
* \tparam T Should be a scalar that is castable from and to double and should support elementary arithmetic operations.
+ * \todo Define a better fileformat for .fg files (maybe using XML)?
+ * \todo Add support for sparse factors.
*/
template <typename T> class TFactor {
private:
*
* Factor graphs explicitly express the factorization structure of the
* corresponding probability distribution.
+ *
+ * \todo Alternative implementation of undo factor changes: the only things that have to be
+ * undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
+ * could also be implemented in the TFactor itself, which could maintain its state
+ * (ones/delta/full) and act accordingly.
*/
class FactorGraph {
public:
/// Approximate inference algorithm: implementation of single-loop ("Generalized Belief Propagation") and double-loop algorithms by Heskes, Albers and Kappen
+/** \todo Optimize HAK with precalculated indices, similarly to BP.
+ */
class HAK : public DAIAlgRG {
private:
std::vector<Factor> _Qa;
* and (long)i is equal to the linear index of the corresponding
* state of indexVars, where the variables in indexVars that are
* not in forVars assume their zero'th value.
+ * \idea Optimize all indices as follows: keep a cache of all (or only
+ * relatively small) indices that have been computed (use a hash). Then,
+ * instead of computing on the fly, use the precomputed ones.
*/
class IndexFor {
private:
*/
+/// \file
+/// \brief Defines some utility functions for interfacing with MatLab
+
+
#ifndef __defined_libdai_matlab_h
#define __defined_libdai_matlab_h
*/
-/// \file
-/// \brief Defines some utility functions for weighted graphs
-/// \todo Improve documentation
+/** \file
+ * \brief Defines some utility functions for weighted graphs
+ * \todo Improve documentation
+ * \todo Improve general support for graphs and trees.
+ */
#ifndef __defined_libdai_weightedgraph_h
}
} else {
update_seq.reserve( nredges );
+ /// \todo Investigate whether performance increases by switching the order of following two loops:
for( size_t i = 0; i < nrVars(); ++i )
foreach( const Neighbor &I, nbV(i) )
update_seq.push_back( Edge( i, I.iter ) );
projects / libdai.git / commitdiff