Updated copyrights
[libdai.git] / ChangeLog
index 28fe4ae..66326a0 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,11 +1,14 @@
 libDAI-0.2.2 (2008-??-??)
 -------------------------
 
-* Now compiles also under Visual C++.
+* Now compiles also under Visual C++ and cygwin.
 * Added Exceptions framework.
+* Approximate inference methods now report the number of iterations needed.
+* Added damping to various algorithms to improve convergence properties.
 * Replaced ENUM2,ENUM3,ENUM4,ENUM5,ENUM6 by single DAI_ENUM macro.
 * Removed utils/remove_short_loops and matlab/remove_short_loops.
 * Added more features to utils/createfg for creating factor graphs.
+* Replaced sub_nb class in mr.h by boost::dynamic_bitset.
 * 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, 
@@ -20,41 +23,46 @@ libDAI-0.2.2 (2008-??-??)
   - 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
+* 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.
 * Contributions by Peter Gober:
-  - Renamed variable _N in mr.* for compatibility with g++ under cygwin
+  - 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
+  - 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)
+    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:
   - New FactorGraph constructor that constructs from given ranges of factors
-    and variables
+    and variables;
   - Optimization of FactorGraph constructors using tr1::unordered_map.
+* Contributions by Claudio Lima:
+  - Added Max-Product functinoality to BP.
 * 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<Var> instead of a
-  std::set<Var>, which yields a significant speed improvement.
-* Improved MaxSpanningTreePrims algorithm (uses boost::graph)
-* Small optimization in Diffs
+  std::set<Var>, which yields a significant speed improvement. Furthermore,
+  the implementation has been generalized, resulting in the small_set<T> class
+  which can be used to represent sets of small cardinality; VarSet is the
+  specialization with T = Var.
+* 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" :))
+  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
@@ -63,10 +71,11 @@ libDAI-0.2.2 (2008-??-??)
   entangled) code.
 * Improved ClusterGraph implementation, yielding significant speedups
   for the JunctionTree algorithm on large factorgraphs.
-* Improved documetation
+* Improved documetation.
+* Removed x2x.
 * Interface changes:
   - VarSet::
-      stateSpace() -> states()
+      VarSet::stateSpace() -> nrStates(const VarSet &)
       VarSet( const std::set<Var> ) -> VarSet( begin, end, sizeHint=0 )
       VarSet( const std::vector<Var> ) -> VarSet( begin, end, sizeHint=0 )
       removed bool operator||
@@ -97,7 +106,7 @@ libDAI-0.2.2 (2008-??-??)
       nr_IRs() -> nrIRs()
       ORs() -> ORs
       IRs() -> IRs
-  - *::Regenerate() -> *::create()
+  - *::Regenerate() -> *::construct()
   - Renamed Index -> IndexFor
   - Diffs:
       max() -> maxDiff()
@@ -125,3 +134,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<FactorGraph> and for 
+  DAIAlg<RegionGraph> 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<T> inherits. This solves the incompatibility problems of
+  DAIAlg<T> for different T (e.g. DAIAlg<FactorGraph> was incompatible with
+  DAIAlg<RegionGraph>). 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 <loopdepth> 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<FRegion,Region>. 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<Factor>) 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<T> class, which stores a probability vector (without the accompanying indexing
+    and VarSet) and provides functionality for it (which is used by TFactor<T>).
+  o Rewrote the VarSet class. It now caches its statespace(). It now privately inherits from set<Var>.
+    I had to overload the insert methods of set<Var> 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<T> 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<size_t>) by vector<size_t>
+- 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<double>.
+- 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.