X-Git-Url: http://git.tuebingen.mpg.de/?p=libdai.git;a=blobdiff_plain;f=ChangeLog;h=aae4a8c5b5bd0df8295dd4fb0d1abf8a891b6aff;hp=28fe4ae6eaa074edd857e4c150a5e5a92c8838e7;hb=5462dc0b1d6ddfdf1bee861873873c85c48af34d;hpb=4c750bf8a4fd204f4ca38a1483765285e4e70412 diff --git a/ChangeLog b/ChangeLog index 28fe4ae..aae4a8c 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,11 +1,20 @@ -libDAI-0.2.2 (2008-??-??) +libDAI-0.2.2 (2008-09-30) ------------------------- -* Now compiles also under Visual C++. -* Added Exceptions framework. -* Replaced ENUM2,ENUM3,ENUM4,ENUM5,ENUM6 by single DAI_ENUM macro. -* Removed utils/remove_short_loops and matlab/remove_short_loops. +New features: +* Approximate inference methods now report the number of iterations needed. +* Added damping to various algorithms to improve convergence properties. * Added more features to utils/createfg for creating factor graphs. +* Added ExactInf class for brute force exact inference. +* [Giuseppe Pasino] Added "logdomain" property to BP, a boolean that controls + whether calculations are done in the log-domain or in the linear domain; + doing calculations in the log-domain may help if the numerical range + of a double is too small. +* [Claudio Lima] Added Max-Product functionality to BP. +* Improved documentation. + +Improved architecture: +* Added Exceptions framework. * Pervasive change of BipartiteGraph implementation (based on an idea by Giuseppe Passino). BipartiteGraph no longer stores the node properties (former _V1 and _V2), nor does it store a dense adjacency matrix anymore, @@ -13,102 +22,109 @@ libDAI-0.2.2 (2008-??-??) neighboring nodes. This yields a significant memory/speed improvement for large factor graphs, and is more elegant as well. Iterating over neighbors is made easy by using boost::foreach. -* Improved index.h (merged from SVN head): +* Added conditional compilation of inference methods. +* VarSet is now implemented using a std::vector instead of a + std::set, which yields a significant speed improvement. Furthermore, + the implementation has been generalized, resulting in the small_set class + which can be used to represent sets of small cardinality; VarSet is the + specialization with T = Var. +* Improved ClusterGraph implementation, yielding significant speedups + for the JunctionTree algorithm on large factorgraphs. + +Code cleanup: +* Moved everything into namespace "dai". +* Renamed DEBUG to DAI_DEBUG to avoid conflicts. +* Replaced ENUM2,ENUM3,ENUM4,ENUM5,ENUM6 by single DAI_ENUM macro. +* Removed utils/remove_short_loops and matlab/remove_short_loops. +* Replaced sub_nb class in mr.h by boost::dynamic_bitset. +* Improved index.h: - Renamed Index -> IndexFor - Added some .reserve()'s to IndexFor methods which yields a 25% speedup of testregression - Replaced multind by Permute - Added MultiFor - Added State -* Improved factor.h (merged from SVN head): mainly new functionality -* Moved everything into namespace "dai" -* Added ExactInf class for brute force exact inference -* Renamed DEBUG to DAI_DEBUG to avoid conflicts -* Added conditional compilation of inference methods +* New funcstionality of factor.h. +* Moved Properties and MaxDiff frameworks from InfAlg to each individual + inference algorithm, because the Properties framework was not as + convenient as I hoped, and not every inference algorithm needs a maxdiff + variable. Also, replaced some FactorGraph functionality in InfAlg by a + function that returns the FactorGraph. The result is cleaner (less + entangled) code. +* Removed x2x. +* Replaced Complex with real numbers (negative potentials are just too rare + to warrant the additional "complexity" :)). + +Miscellaneous improvements: +* Now compiles also with MS Visual C++ (thanks to Jiuxiang Hu) and with + GCC under cygwin. * Contributions by Peter Gober: - - Renamed variable _N in mr.* for compatibility with g++ under cygwin -* Contributions by Giuseppe Passino: - - removed "using namespace std;" from header files - bad practice - - moved header files in include/dai and sources in src - - changed #ifndefs to GNU style - - added extra warning checks (-W -Wextra) and fixed resulting warnings + - Renamed variable _N in mr.* for compatibility with g++ under cygwin. +* Misc contributions by Giuseppe Passino: + - removed "using namespace std;" from header files - bad practice; + - moved header files in include/dai and sources in src; + - changed #ifndefs to GNU style; + - added extra warning checks (-W -Wextra) and fixed resulting warnings; - dai::TProb: - o removed copy constructor and assignment operators (redundant) - o implementation of some methods via STL algorithms - o added methods takeExp, takeLog, takeLog0 for transformation in-place - o explicit constructor (prevents implicit conversion from size_t to TProb) - o added operator+,+=,-,-=, with argument T (for calculations in log-scale) - - Added "logdomain" property to BP, a boolean that controls whether - calculations are done in the log-domain or in the linear domain; - doing calculations in the log-domain may help if the numerical range - of a double is too small. -* Contributions by Christian Wojek: + o removed copy constructor and assignment operators (redundant); + o implementation of some methods via STL algorithms; + o added methods takeExp, takeLog, takeLog0 for transformation in-place; + o explicit constructor (prevents implicit conversion from size_t to TProb); + o added operator+,+=,-,-=, with argument T (for calculations in log-scale); +* Misc contributions by Christian Wojek: - New FactorGraph constructor that constructs from given ranges of factors - and variables + and variables; - Optimization of FactorGraph constructors using tr1::unordered_map. * FactorGraph constructors no longer check for short loops (huge speed increase for large factor graphs), nor for negative entries. Also, the normtype is now Prob::NORMPROB by default. -* VarSet is now implemented using a std::vector instead of a - std::set, which yields a significant speed improvement. -* Improved MaxSpanningTreePrims algorithm (uses boost::graph) -* Small optimization in Diffs -* Replaced Complex with real numbers (negative potentials is just not - used enough to warrant the additional "complexity" :)) -* Moved Properties and MaxDiff frameworks from InfAlg to each individual - inference algorithm, because the Properties framework was not as - convenient as I hoped, and not every inference algorithm needs a maxdiff - variable. Also, replaced some FactorGraph functionality in InfAlg by a - function that returns the FactorGraph. The result is cleaner (less - entangled) code. -* Improved ClusterGraph implementation, yielding significant speedups - for the JunctionTree algorithm on large factorgraphs. -* Improved documetation -* Interface changes: - - VarSet:: - stateSpace() -> states() - VarSet( const std::set ) -> VarSet( begin, end, sizeHint=0 ) - VarSet( const std::vector ) -> VarSet( begin, end, sizeHint=0 ) - removed bool operator|| - operator&&(const VarSet&) -> intersects(const VarSet&) - operator&&(const Var&) -> contains(const Var&) - - FactorGraph:: - delta(const Var &) -> delta(size_t) - Delta(const Var &) -> Delta(size_t) - makeCavity(const Var &) -> makeCavity(size_t) - vars() -> vars - factors() -> factors - removed MakeFactorCavity(size_t) - removed ExactMarginal(const VarSet &) - removed ExactlogZ() - removed updatedFactor(size_t) - removed _normtype and NormType() - removed hasShortLoops(...) and removeShortLoops(...) - WriteToDotFile(const char *filename) -> printDot( std::ostream& os ) - undoProb(size_t) -> restoreFactor(size_t) - saveProb(size_t) -> backupFactor(size_t) - undoProbs(const VarSet &) -> restoreFactors(const VarSet &) - saveProbs(const VarSet &) -> backupFactors(const VarSet &) - ReadFromFile(const char*) returns void (throws on error) - WriteToFile(const char*) returns void (throws on error) - removed hasNegatives() - - RegionGraph:: - nr_ORs() -> nrORs() - nr_IRs() -> nrIRs() - ORs() -> ORs - IRs() -> IRs - - *::Regenerate() -> *::create() - - Renamed Index -> IndexFor - - Diffs: - max() -> maxDiff() - max_size() -> maxSize() - - Prob::max() -> Prob::maxVal() - - Factor:: - max() -> maxVal() - part_sum() -> partSum() - - toc() in util.h now returns seconds as a double - - VarSet::operator&& - - Properties -> PropertySet +* Improved MaxSpanningTreePrims algorithm (uses boost::graph). + +Interface changes: +* VarSet:: + - VarSet::stateSpace() -> nrStates(const VarSet &) + - VarSet( const std::set ) -> VarSet( begin, end, sizeHint=0 ) + - VarSet( const std::vector ) -> VarSet( begin, end, sizeHint=0 ) + - removed bool operator|| + - operator&&(const VarSet&) -> intersects(const VarSet&) + - operator&&(const Var&) -> contains(const Var&) +* FactorGraph:: + - delta(const Var &) -> delta(size_t) + - Delta(const Var &) -> Delta(size_t) + - makeCavity(const Var &) -> makeCavity(size_t) + - vars() -> vars + - factors() -> factors + - removed MakeFactorCavity(size_t) + - removed ExactMarginal(const VarSet &) + - removed ExactlogZ() + - removed updatedFactor(size_t) + - removed _normtype and NormType() + - removed hasShortLoops(...) and removeShortLoops(...) + - WriteToDotFile(const char *filename) -> printDot( std::ostream& os ) + - undoProb(size_t) -> restoreFactor(size_t) + - saveProb(size_t) -> backupFactor(size_t) + - undoProbs(const VarSet &) -> restoreFactors(const VarSet &) + - saveProbs(const VarSet &) -> backupFactors(const VarSet &) + - ReadFromFile(const char*) returns void (throws on error) + - WriteToFile(const char*) returns void (throws on error) + - removed hasNegatives() +* RegionGraph:: + - nr_ORs() -> nrORs() + - nr_IRs() -> nrIRs() + - ORs() -> ORs + - IRs() -> IRs +* *::Regenerate() -> *::construct() +* Renamed Index -> IndexFor +* Diffs: + - max() -> maxDiff() + - max_size() -> maxSize() +* Prob::max() -> Prob::maxVal() +* Factor:: + - max() -> maxVal() + - part_sum() -> partSum() +* toc() in util.h now returns seconds as a double +* VarSet::operator&& +* Properties -> PropertySet libDAI-0.2.1 (2008-05-26) @@ -125,3 +141,310 @@ libDAI-0.2.0 (2006-11-30) ------------------------- First public release. + + +0.1.5 (2006-11-30) +------------------ + +Regressions + +- tests/testlcbp and tests/testlcbp are broken. +- EXACT method does not work anymore. +- The Properties framework gives a speed penalty because of the lookup + costs involved; inner loops should be optimized. + +General framework + +- DAIAlg is now a template class; typedefs for DAIAlg and for + DAIAlg are provided. In this way, we do not have to write "wrapper" + functions to forward functionality from either FactorGraph or RegionGraph + to DAIAlg. Functionality like clamping can be implemented in FactorGraph + and in RegionGraph and no explicit interface is needed in descendants. +- New abstract base class InfAlg added, representing an inference algorithm, + from which DAIAlg inherits. This solves the incompatibility problems of + DAIAlg for different T (e.g. DAIAlg was incompatible with + DAIAlg). More work is required to reduce code duplication + (make FactorGraph part of InfAlg). +- Added generic interface (nrVars(), Vars(), nrFactors(), factor(size_t), + beliefs(), belief(VarSet &), ...) to InfAlg and descendants. +- Added a saveProbs/undoProbs interface to InfAlg and descendants that enables + one to save a few factors, modify them (e.g. clamp them), and then restore them + to their old values. Undo should also init the corresponding messages / beliefs. + This can be used if a given factor graph repeatedly needs to be clamped in + different ways and an approximation method is run for each clamping; using the + saveProbs/undoProbs can give a significant speed increase. +- Switched to a general Properties framework that handles the parameters of + all inference methods in a uniform manner. The Properties class is a map of + several properties in boost::any objects, indexed by their names (strings). + It can read from a stream and write to a stream. It is recursive, in the sense + that a Properties object can hold a variable of type Properties as well. +- Added a generic way of constructing inference algorithms from a factor graph, + name and properties object. Added the newInfAlg function which constructs + the requested object. This is used by LCBP, the Matlab interface and the + command line (test) interface. +- Added a generic enum framework for enum parameters. Although implemented as a + hack, it is quite useful in that it drastically simplifies and reduces the + amount of code for handling enum parameters. +- Provided generic functions for calculating marginals in different ways that + work for all approximate inference methods. + +Bugfixes + +- Fixed GBP free energy. +- Fixed bug in junctiontree (it didn't init the _vars variable). +- Corrected two bugs in operator&& and operator|| in VarSet (they returned + the logical NOT of what they should return). +- Fixed bug in RegionGraph::RecomputeOR(s). +- Fixed bug in utils/create_dreg_fg: + graph structure was not random for given parameters (forgot to call srand()). +- TreeEP bug workaround: use the complete junction tree instead of a subtree. +- Fixed bug in JTree::HUGIN() and JTree:ShaferShenoy() in case of junction tree + that consists of one outer region only. +- Fixed INIT bug in LCBP2::UpdatePancake(). +- Fixed MaxDiffs flow (except for MR). + +New functionality + +- HAK supports several default cluster choices: + minimal (only factors) + delta (Markov blankets) + loop (all loops consisting of loops consisting of or less variables) + Only the maximal clusters are used as outer clusters. +- Implemented TreeEP. It generalizes the heuristic method described in the + Minka & Qi paper for obtaining a tree with the most relevant interactions to + higher order interactions. Almost all optimizations described in the Minka & Qi + paper are used, except that evidence is passed over the whole tree instead of + relevant subsets (the latter is almost implemented but buggy). Also added + alternative (worst-case) algorithm that uses a maximum spanning tree on the + weighted graph where the weight between neighbours i and j is given by + N(psi,i,j), where psi is the product of all the factors involving both i and j + (which is an upper bound on the effective interaction between i and j). +- Implemented MR (MontanariRizzo) based on Bastian's code, but extended it + to be able to handle connectivities larger than 3 (in principle, up to 32). + It supports different initialization methods (the original RESPPROP, + the CLAMPING method and EXACT which uses JTree) and different update methods + (FULL and LINEAR). +- Implemented LCBP2, an analogon of LCBP which represents pancakes as little + networks and uses some approximate inference method on them for calculating + marginals. +- Now there are several LCBP variants (LCBP, LCBPI, LCBPJ, LCBPK, LCBPL); + LCBPJ works only for pairwise, LCBPK is LCBP improved for higher order + interactions and LCBPL is LCBPI improved for higher-order interactions. +- Wrote one single program utils/createfg for creating various types of + random factor graphs. +- Wrote utility to visualize factor graphs using graphviz. + (it uses the BOOST Program Options library) +- Added fginfo utility that displays some info about a .fg file. +- Implemented Factor::strength function that calculates the potential strength + N(psi,i,j) between variables i and j as described in cs.IT:0504030 +- Wrote a general MatLab interface matlab/dai (similar to tests/test); + this unified the matlab functions dai, dai_bp, dai_mf, dai_jt, dai_tep, dai_cvm. +- Added MATLAB routine that returns contraction matrix A for BP convergence analysis. +- Implemented a MATLAB interface ai_potstrength for Factor::strength +- Added Martijn's x2x + +Improvements of existing code + +- Reimplemented RegionGraph and descendants: a RegionGraph ISA FactorGraph + and also a BipartiteGraph. It now also keeps a map that + associates outer region indices to factor indices (no powers yet, this + is deemed superfluous) and provides functions to recompute (some of) the + outer regions from the factors. +- InfAlg descendants run() methods now stop immediately and return NAN in case + they detect NANs. Only BP does not do NAN checking for performance reasons. +- LCBP now works with factors containing zeroes (by defining x/0 = 0). +- HAK, GBP and DoubleLoop now conform to the standards for verbose reporting, + timing and convergence criteria. +- Implemented logZ() for JTree. It does the calculation during message-passing. +- Marginal2ndO now optionally divides by the single node beliefs (to the power n-2); + hopefully this will give more accurate approximations. +- Marginal and Marginal2ndO (optionally) use the new saveProbs/undoProbs functionality + for a faster way of calculating marginals, which does not require a call to init() + nor cloning the whole object for each clamping. This leads to a significant speedup. +- LCBP (and LCBP2) now have complete flexibility in the specification of the + inner method, i.e. the method used to generate the initial cavity approximations. + One can pass two strings, a name and a properties string, and LCBP simply invokes + newInfAlg to construct the corresponding inference algorithm and uses the generic + marginal functions to approximate cavity marginals. +- Replaced the global "method" variable by local properties and removed ai.h +- Added some methods to Factor (operators *, *=, /, /= with doubles as + second argument, operators -, +=, -= with other Factors as second + arguments, randomize(), RemoveFirstOrderInteractions) and similar + operations to Prob +- Moving towards boost::program_options for handling command line arguments + (tests/test is done). +- Renamed some FactorGraph methods: + nr_vars -> nrVars + nr_factors -> nrFactors + varind -> findVar + factorind -> findFactor + makeFacCavity -> makeFactorCavity +- LCBP_SEQMAXRES has been removed because it did strange things. +- Implemented RandomDRegularGraph +- Implemented JTree::calcMarginal for marginals that are not confined + within one cluster (using cut-set conditioning). +- Added isConnected() method to FactorGraph (some methods do not work with + disconnected factor graphs). +- Pair beliefs are now calculated in a symmetrical way by calcPairBeliefs +- Removed single node interaction "correction" code from clamping methods +- Removed calcCavityDist and calcCavityDist2ndO +- No longer depends on GSL. +- Increased portability by combining platform dependant utility functions + in util.{h,cpp}. +- Wrote *.m files providing help + +Testing framework + +- Made a new and significantly improved testing framework that provides most + functionality from the command line. +- The basis is provided by tests/test, which uses the newInfAlg functionality + and enables the user to easily compare from the command line different + inference methods on a given factorgraph. All parameters can be specified. + Output consists of CPU time, average and maximum single variable marginal + errors, relative logZ error and MaxDiff(). +- tests/aliases.conf contains aliases for standard combinations of methods + and their options (which can be used in tests/test). +- tests/large contains several bash/python scripts that create random factor + graphs, compare several approximate inference algorithms (using tests/test) and + allow for easy visualization of the results using PyX. +- Added several .fg files for test purposes to /tests (e.g. two ALARM versions + alarm.fg and alarm_bnt.fg; testfast.fg, a 4x4 periodic Ising grid for + regression testing). +- Added a regression test to the Makefile which is included in the standard + target. It compares all inference methods on tests/testfast.fg with the + results stored in tests/testfast.out + +Miscellaneous + +- Expanded all tabs to spaces (":set tabstop 4\n:set expandtab\n:retab" in vim) +- Experimental MATLAB code added for StarEP approximation on cavity +- Renamed project to libDAI and changed directory name accordingly. +- Renamed JunctionTree to JTree. +- Fixed licensing (now it's officially GPL). +- Improved README + + +revision 252 +------------ + +Functionality +- Added RegionGraph, GBP, CVM and HAK (double-loop). +- Added JunctionTree (with two update algorithms, HUGIN and Shafer-Shenoy), which is a + RegionGraph. +- NormType is now chosen automatically (in case of negative factors, Prob::NORMLINF is used, + otherwise the default Prob::NORMPROB is used). Also, in case of negative factors, the + RegionGraph constructors assign each Factor to a unique outer region instead of dividing + it over all subsuming outer regions. See README for when negative factors are known to work + and when not. +- FactorGraph::FactorGraph(const vector) only gives a warning in case of short loops, + it does not automatically merge factors anymore. +- Removed BP_SEQMAXRESNOCLEAR (all cavity initialization methods now are implicitly NOCLEAR) +- Added MATLAB interface functions ai_readfg, ai_removeshortloops and ai_bp +- Added LCBP-III type that should be equivalent to LCBP-II, but can handle zeroes + in potentials. Note that it is significantly slower than LCBP-II (and has to be reimplemented + such that it does not store the complete pancakes, but represents them as little factor graphs). + +Implementation / code +- Made a seperate type WeightedGraph, which until now only implements Prim's + maximal spanning tree algorithm and is only used by the junction tree code. It might + be good to make it a class somewhere in the future and extend it's interface. +- Made a seperate class ClusterGraph, which is only used by the junction tree + code. It's main purpose is a graph-theoretical variable elimination algorithm. +- Implemented the heuristic "minimum-new-edges-in-clique-graph" for variable elimination. +- Massive code cleanup, moving towards "generic" programming style, using + multiple inheritance and polymorphism. + o BP, LCBP, MF, HAK and JunctionTree now inherit from a common DAIAlg class + o Made generic functions Marginal, Marginal2ndO, calcCavityDist, calcCavityDist2ndO, clamp + that can be used by FactorGraph-based DAIAlgs. + o Created TProb class, which stores a probability vector (without the accompanying indexing + and VarSet) and provides functionality for it (which is used by TFactor). + o Rewrote the VarSet class. It now caches its statespace(). It now privately inherits from set. + I had to overload the insert methods of set so that they calculate the new statespace. + o Rewrote the TFactor class. The TFactor class now HAS a TProb and HAS a VarSet. +- Rewrote BP to use the new TProb interface. Performance of BP improved up to a factor 6 by: + o using Prob's instead of Factor's; + o splitting the multiplication of the messages into two parts (thanks to Vicenc!); + o optimizing the calculation of the beliefs (only the message calculations were optimized till now). + o replacing FactorGraph::_nb1 and _nb2 (which were set) by vector +- LCBP now seperately stores cavitydists and pancakes. Added InitPancakes() method + that takes the cavitydists and multiplies them with the relevant factors. This + resulted in an API change in AI which now accepts and returns initial cavitydists + instead of initial pancakes. + +Minor changes +- Started writing DoxyGen documentation +- Renamed lcptab2fg.m matlab/ai_writefg.m +- Moved all matlab stuff to matlab/ +- More detailed reporting (also reports clocks used). +- Marginal and Marginal2ndO now use *differences* in logZ to avoid NaNs. +- Improved testing suite. +- Removed logreal support. +- FactorGraph now also supports input streams and ignores comment lines in .fg files. +- Added tests/create_full_fg.cpp and tests/create_ising_fg.cpp which create + full and periodic 2D Ising networks according to some command line parameters. +- Now logZ really returns logZ instead of -logZ. +- Added FactorGraph::WriteToDotFile + + +0.1.4 (2006-04-13) +------------------ +- Added file IO routines to read and write factorgraphs. +- Added L-infinity normalization for use with (partially) negative factors. +- Renamed BetheF, MFF to logZ, which now use complex numbers to be able to +handle (partially) negative factors. +- Added test suite. +- All probabilities are now represented using double instead of LogReal. +- Combined Alg and Alg3 into LCBP. Several update schemes possible. +- Combined several variants of BP into doBP. Several update schemes possible. +Now uses precalculated indices for optimization. +- Renamed Node -> Var and Potential -> Factor. +- Extensive code cleanup. More use of OO techniques. Changed API. +- MaxIter now means maximum number of passes (corresponding to number of +_parallel_ updates). +- MaxDiff now means the maximum L-infinity distance between the updated and +original single variable beliefs, for all AI methods. +- Implemented RBP which converges faster than BP for difficult problems. +- Now uses method parameter which is a bitmask combining outmethod and inmethod +(see ai.h). + + +0.1.3 (2006-03-22) +-------------------- +- All AI methods now return maxdiff +- ai.cpp: + o Now returns maxdiffinner and maxdiffouter + o New BP2ndO innermethod (estimate only 2nd order cavity interactions) + o New InitCav outermethod (only create initial cavity distributions) +- bp.cpp: + o New CavityDist2ndO which estimates 2nd order cavity interactions +- Makefile: + o Bugfix: removed dependencies on algwim.* + + +0.1.2 (2006-02-28) +-------------------- +- Cleaned up alg.cpp (removed Alg2 and its corresponding data structures). +- Added the possibility to provide initial cavity distributions as an input +argument to ai (not much error checking is done, so be careful). +- Potentials2mx now correctly sets the dimensions of the P field (i.e. for +the output arguments Q, Q0 of ai). +- Removed algwim.* since it does not work. + + +0.1.1 (2006-02-28) +-------------------- +- The constructors of (Log)FactorGraph and LogFactorGraph from a +vector<(Log)Potential> now merge potentials to prevent short loops (of length +4) in the factor graph. These are used in ai to construct the factor graphs +from the psi argument. If compiled with DEBUG defined, the method calc_nb() +of BipGraph checks for the existence of short loops. +- Changed calling syntax of ai (now the actual syntax *does* correspond to its +description in the help). +- ai does not hook cout anymore (which caused weird segfaults). +- Fixed a bug in an assert statement in the matlab interface code in ai.cpp. +- Removed network.* since it is not useful. + + +0.1.0 (2006-02-28) +-------------------- +First version worthy a version number.