Merge branch 'pletscher'
[libdai.git] / ChangeLog
index 28fe4ae..a53c029 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
-libDAI-0.2.2 (2008-??-??)
+* Added init parameter to HAK/GBP to allow for random initialization
+* Replaced the standard assert() macro by DAI_ASSERT, which throws a
+  dai::Exception and is even active if NDEBUG is defined
+* Added a constructor TProb<T>::TProb<T>( const std::vector<S> &v )
+* Introduced CCNODEBUGFLAGS in Makefile
+* Updated copyright headers
+* Added max-product functionality to JTree
+* [Charlie Vaske] EM bugfix (was using abs() instead of fabs() in 
+  determining EM termination, which caused a loss of precision).
+* [Charlie Vaske] New constructor in Permute for canonical variable ordering
+* [Charlie Vaske] New constructor in Factor that reorders variables to canonical ordering
+* [Charlie Vaske] New accessor in Properties for getting all keys
+* [Charlie Vaske] New function for getting inferred parameters
+* Cleaned up error handling by introducing the DAI_THROWE macro
+* Introduced DAI_DEBASSERT macro to abbreviate a common pattern
+* Changed FactorGraph::clamp and DAIAlg::clamp interfaces (the variable to be
+  clamped is now indicated by its index, not as a Var) and marked the old
+  interface as obsolete
+* [Patrick Pletscher] Fixed performance issue in FactorGraph::clamp
+* [Sebastian Nowozin] MEX file dai now also optionally returns the MAP state
+  (only for BP)
+* [Sebastian Nowozin] Fixed memory leak in MEX file dai
+
+git ae0fc30e10be6683cbfc209dcee56f34234a6cb8
+--------------------------------------------
+* Added work-around for bug in Boost Graph Library
+* Improvements of TFactor<T>:
+  - Extended functionality of TFactor<T>::operators +,-,+=,-= to handle different VarSets
+  - Added TFactor<T>::maxMarginal (similar to marginal but with max instead of sum)
+* Added BipartiteGraph::eraseEdge
+* Removed all the virtual default constructors *::create(), as they are not used.
+* Fixed bug in MaxSpanningTree (it wrongly assumed that the tree was not empty).
+* [Charlie Vaske] Added Expectation Maximization code.
+* Added MatLab QuickStart to README.
+* MEX file dai now also returns variable and factor beliefs.
+* Cleanups and extra documentation of the code contributed by Frederik Eaton
+* Removed erroneous 'inline' directives in gibbs.cpp
+* [Frederik Eaton] Added script for automatically generating properties code (used by CBP and BBP)
+* [Frederik Eaton] Updated doxygen.conf to version 1.5.9
+* [Frederik Eaton] Added newInfAlgFromString to alldai.h/cpp
+* [Frederik Eaton] Added FactorGraph::clampVar and FactorGraph::clampFactor
+* [Frederik Eaton] Changed BP to be able to record order in which messages are sent (for use by BBP)
+* [Frederik Eaton] Improved documentation of BipartiteGraph::Neighbor
+* [Frederik Eaton]: Extended InfAlg interface with beliefV() and beliefF() methods;
+* [Frederik Eaton]: Improved PropertySet class:
+  - Added default constructor
+  - Allow construction from string
+  - Added method allKeys() to produce list of keys
+  - In getStringAs(), check for typeid(ValueType) before typeid(std::string)
+    (this fixes a strange bug for empty string property)
+* [Frederik Eaton]: Added some utility macros (DAI_PV, DAI_DMSG, DAI_ACCMUT, DAI_IFVERB)
+  and functions (concat(),rnd()) to include/dai/util.h
+* [Frederik Eaton] Added backwards compatibility layer for edge interface to
+  BipartiteGraph and FactorGraph (which will be obsoleted soon)
+* [Frederik Eaton] Added BP_dual, BBP and CBP algorithms
+* [Frederik Eaton] Added Gibbs::state() accessors/mutators
+* [Frederik Eaton] Fixed Gibbs::getVarDist(size_t) to return uniform
+  distribution if no state is allowed
+* [Frederik Eaton] Improved parsing code in tests/testdai to allow recursive
+  alias substitutions
+* Interface changes:
+    TProb<T>::minVal()     -> TProb<T>::min()
+    TFactor<T>::minVal()   -> TFactor<T>::min()
+    TProb<T>::maxVal()     -> TProb<T>::max()
+    TFactor<T>::maxVal()   -> TFactor<T>::max()
+    TProb<T>::totalSum()   -> TProb<T>sum()
+    TFactor<T>::totalSum() -> TFactor<T>::sum()
+* [Frederik Eaton] Added methods setUniform (), sumAbs(), argmax() to TProb<T>
+* [Frederik Eaton] Added TAGS, lib targets to Makefile
+* [Frederik Eaton] Add useful aliases to aliases.conf
+* [Frederik Eaton] Removed unnecessary copy constructors and assignment
+  operators
+* [Frederik Eaton] Change cout to cerr in warnings and error messages
+* [Giuseppe Passino] Optimised maximum-residual BP by using a reversed ordered
+  set instead of the linear search (which can yield enormous speedups - a
+  factor 500 has been measured on a binary Ising grid with 128x128 variables!)
+* Added debug assertions to Var which check for inconsistent dimensions of
+  variables with the same labels
+* [Giuseppe Passino] Added prefix ++ operator to State (State::operator++())
+* [Giuseppe Passino] Added iterators to FactorGraph (FactorGraph::begin,
+  FactorGraph::end)
+* [Giuseppe Passino] Added iterators to TFactor (TFactor::begin, TFactor::end)
+* [Giuseppe Passino] Added iterators to TProb (TProb::begin, TProb::end)
+* [Giuseppe Passino] Added BP::findMaximum(), which can be used after running
+  max-product BP to construct a global state with maximum probability
+* Improved Makefile (libDAI now also builds out-of-the-box on MacOSX,
+  thanks to Dan Preston; merged Makefile.win and Makefile.shared into Makefile)
+* Fixed bug in calcMarginal, calcPairBeliefs, calcPairBeliefsNew where
+  states with zero probability mass were clamped, leading to NaNs or assertion
+  errors (thanks to Dan Preston for reporting this)
+* toc() now returns POSIX system time with maximum accuracy of microseconds
+* Exception objects now remember their error code
+* Added examples/example_sprinkler.cpp
+* [Peter Gober] Made libDAI build out-of-the-box on Cygwin.
+* [Frederik Eaton] Added Gibbs sampler to algorithms
+* Improved documentation of include/dai/{bipgraph.h, prob.h, smallset.h,
+  var.h, varset.h, factor.h, enum.h} and of examples/example.cpp
+  Merged TODO and FILEFORMAT into doxygen documentation
+* examples/
+  - Moved example.cpp to examples/
+  - Added examples/example_bipgraph.cpp
+  - Added examples/example_varset.cpp
+* Interface changes:
+  - Replaced TProb<T>::log0() by TProb<T>::log(true)
+  - Replaced TProb<T>::takeLog0() by TProb<T>::takeLog(true)
+  - Replaced TFactor<T>::log0() by TFactor<T>::log(true)
+  - Removed TProb<T>::hasNonPositives()
+  - Renamed smallSet<T> to SmallSet<T>
+  - Removed TFactor<T>::divided_by, use operator/ instead
+  - Removed TFactor<T>::divide, use operator/= instead
+  - Removed TFactor<T>::partSum(const VarSet&), use marginal(const VarSet&,true) instead
+  - Improved constructors of TProb and TFactor to use iterators instead of pointers
+* Miscellaneous small changes and cleanups:
+  - Changed regression test so that it also works under Windows
+  - Changed output stream operator<< for Var and VarSet
+  - Added TProb::draw() function, which draws a random index
+  - Cleanup of matlab interface code
+  - Small improvement of utils/fginfo
+  - Small cleanup of BP code
+  - Switched Makefile.win to GNU Make syntax
+
+
+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, 
-  nor an edge list. Instead, it stores the graph structure as lists of 
-  neighboring nodes. This yields a significant memory/speed improvement for 
+  Giuseppe Passino). BipartiteGraph no longer stores the node properties
+  (former _V1 and _V2), nor does it store a dense adjacency matrix anymore,
+  nor an edge list. Instead, it stores the graph structure as lists of
+  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<Var> instead of a
+  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 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 
+  - 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
-  - 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:
+  - 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);
+* 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 
+  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
-* 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<Var> ) -> VarSet( begin, end, sizeHint=0 )
-      VarSet( const std::vector<Var> ) -> 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<Var> ) -> VarSet( begin, end, sizeHint=0 )
+  - VarSet( const std::vector<Var> ) -> 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 +263,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.