Improved documentation of include/dai/bp.h
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 5 Nov 2009 13:10:00 +0000 (14:10 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 5 Nov 2009 13:10:00 +0000 (14:10 +0100)
TODO
include/dai/bipgraph.h
include/dai/bp.h
include/dai/daialg.h
include/dai/doc.h
include/dai/factor.h
include/dai/factorgraph.h
include/dai/index.h
include/dai/prob.h
include/dai/regiongraph.h
include/dai/util.h

diff --git a/TODO b/TODO
index ac86592..86e6181 100644 (file)
--- a/TODO
+++ b/TODO
@@ -2,7 +2,6 @@ To do for the next release (0.2.3):
 
 Improve documentation:
 
-       bp.h
        jtree.h
        hak.h
        treeep.h
@@ -15,6 +14,7 @@ Improve documentation:
        evidence.h
        emalg.h
        doc.h
+               - add http to reference about maximum-residual BP
 
 Write a concept/notations page for the documentation,
 explaining the concepts of "state" (index into a 
index 4c68d13..feff3c8 100644 (file)
@@ -137,16 +137,22 @@ class BipartiteGraph {
             std::vector<size_t> ind2;       // indices of nodes of type 2
         };
 
-        // OBSOLETE
-        /// \name Backwards compatibility layer (to be removed soon)
+    // OBSOLETE
+    /// \name Backwards compatibility layer (to be removed soon)
         //@{
         /// Enable backwards compatibility layer?
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         bool _edge_indexed;
         /// Call indexEdges() first to initialize these members
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         std::vector<Edge> _edges;
         /// Call indexEdges() first to initialize these members
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         hash_map<Edge,size_t> _vv2e;
-        //@}
+    //@}
 
     public:
     /// \name Constructors and destructors
@@ -346,6 +352,9 @@ class BipartiteGraph {
         // OBSOLETE
     /// \name Backwards compatibility layer (to be removed soon)
     //@{
+        /// Prepare backwards compatibility layer for indexed edges
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         void indexEdges() {
             std::cerr << "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl;
             _edges.clear();
@@ -368,15 +377,24 @@ class BipartiteGraph {
             _edge_indexed = true;
         }
 
+        /// Returns edge with index \a e
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         const Edge& edge(size_t e) const {
             DAI_ASSERT(_edge_indexed);
             return _edges[e];
         }
 
+        /// Returns all edges
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         const std::vector<Edge>& edges() const {
             return _edges;
         }
 
+        /// Converts a pair of node indices to an edge index
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         size_t VV2E(size_t n1, size_t n2) const {
             DAI_ASSERT(_edge_indexed);
             Edge e(n1,n2);
@@ -385,6 +403,9 @@ class BipartiteGraph {
             return i->second;
         }
 
+        /// Returns number of edges
+        /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+         */
         size_t nr_edges() const {
             DAI_ASSERT(_edge_indexed);
             return _edges.size();
index c88b2e0..536164f 100644 (file)
@@ -10,8 +10,7 @@
 
 
 /// \file
-/// \brief Defines class BP
-/// \todo Improve documentation
+/// \brief Defines class BP, which implements (Loopy) Belief Propagation
 
 
 #ifndef __defined_libdai_bp_h
@@ -29,24 +28,70 @@ namespace dai {
 
 
 /// Approximate inference algorithm "(Loopy) Belief Propagation"
+/** The Loopy Belief Propagation algorithm uses message passing
+ *  to approximate marginal probability distributions ("beliefs") for variables
+ *  and factors (more precisely, for the subset of variables depending on the factor).
+ *  There are two variants, the sum-product algorithm (corresponding to 
+ *  finite temperature) and the max-product algorithm (corresponding to 
+ *  zero temperature).
+ *
+ *  The messages \f$m_{I\to i}(x_i)\f$ are passed from factors \f$I\f$ to variables \f$i\f$. 
+ *  In case of the sum-product algorith, the update equation is: 
+ *    \f[ m_{I\to i}(x_i) \propto \sum_{x_{I\setminus\{i\}}} f_I(x_I) \prod_{j\in N_I\setminus\{i\}} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}\f]
+ *  and in case of the max-product algorithm:
+ *    \f[ m_{I\to i}(x_i) \propto \max_{x_{I\setminus\{i\}}} f_I(x_I) \prod_{j\in N_I\setminus\{i\}} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}\f]
+ *  In order to improve convergence, the updates can be damped. For improved numerical stability,
+ *  the updates can be done in the log-domain alternatively.
+ *
+ *  After convergence, the variable beliefs are calculated by:
+ *    \f[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i}(x_i)\f]
+ *  and the factor beliefs are calculated by:
+ *    \f[ b_I(x_I) \propto f_I(x_I) \prod_{j\in N_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}(x_j) \f]
+ *  The logarithm of the partition sum is calculated by:
+ *    \f[ \log Z = \sum_i (1 - |N_i|) \sum_{x_i} b_i(x_i) \log b_i(x_i) - \sum_I \sum_{x_I} b_I(x_I) \log \frac{b_I(x_I)}{f_I(x_I)} \f]
+ *
+ *  There are several predefined update schedules:
+ *    - PARALL parallel updates
+ *    - SEQFIX sequential updates using a fixed sequence
+ *    - SEQRND sequential updates using a random sequence
+ *    - SEQMAX maximum-residual updates [\ref EMK06]
+ *
+ *  For the max-product algorithm, a heuristic way of finding the MAP state (the 
+ *  joint configuration of all variables which has maximum probability) is provided
+ *  by the findMaximum() method, which can be called after convergence.
+ *
+ *  \note There are two implementations, an optimized one (the default) which caches IndexFor objects,
+ *  and a slower, less complicated one which is easier to maintain/understand. The slower one can be 
+ *  enabled by defining DAI_BP_FAST as false in the source file.
+ */
 class BP : public DAIAlgFG {
     private:
+        /// Type used for index cache
         typedef std::vector<size_t> ind_t;
-        typedef std::multimap<Real, std::pair<std::size_t, std::size_t> > LutType;
+        /// Type used for storing edge properties
         struct EdgeProp {
+            /// Index cached for this edge
             ind_t  index;
+            /// Old message living on this edge
             Prob   message;
+            /// New message living on this edge
             Prob   newMessage;
+            /// Residual for this edge
             Real   residual;
         };
+        /// Stores all edge properties
         std::vector<std::vector<EdgeProp> > _edges;
+        /// Type of lookup table (only used for maximum-residual BP)
+        typedef std::multimap<Real, std::pair<std::size_t, std::size_t> > LutType;
+        /// Lookup table (only used for maximum-residual BP)
         std::vector<std::vector<LutType::iterator> > _edge2lut;
+        /// Lookup table (only used for maximum-residual BP)
         LutType _lut;
-        /// Maximum difference encountered so far
+        /// Maximum difference between variable beliefs encountered so far
         Real _maxdiff;
         /// Number of iterations needed
         size_t _iters;
-        /// The history of message updates (only recorded if recordSentMessages is true)
+        /// The history of message updates (only recorded if \a recordSentMessages is \c true)
         std::vector<std::pair<std::size_t, std::size_t> > _sentMessages;
 
     public:
@@ -64,16 +109,16 @@ class BP : public DAIAlgFG {
             /// Maximum number of iterations
             size_t maxiter;
 
-            /// Tolerance
+            /// Tolerance for convergence test
             Real tol;
 
-            /// Do updates in logarithmic domain?
+            /// Whether updates should be done in logarithmic domain or not
             bool logdomain;
 
-            /// Damping constant
+            /// Damping constant (0.0 means no damping, 1.0 is maximum damping)
             Real damping;
 
-            /// Update schedule
+            /// Message update schedule
             UpdateType updates;
 
             /// Type of inference: sum-product or max-product?
@@ -87,9 +132,17 @@ class BP : public DAIAlgFG {
         bool recordSentMessages;
 
     public:
+    /// \name Constructors/destructors
+    //@{
         /// Default constructor
         BP() : DAIAlgFG(), _edges(), _edge2lut(), _lut(), _maxdiff(0.0), _iters(0U), _sentMessages(), props(), recordSentMessages(false) {}
 
+        /// Construct from FactorGraph \a fg and PropertySet \a opts
+        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), _sentMessages(), props(), recordSentMessages(false) {
+            setProperties( opts );
+            construct();
+        }
+
         /// Copy constructor
         BP( const BP &x ) : DAIAlgFG(x), _edges(x._edges), _edge2lut(x._edge2lut),
             _lut(x._lut), _maxdiff(x._maxdiff), _iters(x._iters), _sentMessages(x._sentMessages),
@@ -115,12 +168,7 @@ class BP : public DAIAlgFG {
             }
             return *this;
         }
-
-        /// Construct from FactorGraph fg and PropertySet opts
-        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), _sentMessages(), props(), recordSentMessages(false) {
-            setProperties( opts );
-            construct();
-        }
+    //@}
 
     /// \name General InfAlg interface
     //@{
@@ -145,40 +193,51 @@ class BP : public DAIAlgFG {
     /// \name Additional interface specific for BP
     //@{
         /// Calculates the joint state of all variables that has maximum probability
-        /** Assumes that run() has been called and that props.inference == MAXPROD
+        /** \pre Assumes that run() has been called and that \a props.inference == \c MAXPROD
          */
         std::vector<std::size_t> findMaximum() const;
 
-        /// Returns history of sent messages
+        /// Returns history of which messages have been updated
         const std::vector<std::pair<std::size_t, std::size_t> >& getSentMessages() const {
             return _sentMessages;
         }
 
-        /// Clears history of sent messages
-        void clearSentMessages() {
-            _sentMessages.clear();
-        }
+        /// Clears history of which messages have been updated
+        void clearSentMessages() { _sentMessages.clear(); }
     //@}
 
     private:
+        /// Returns constant reference to message from the \a _I 'th neighbor of variable \a i to variable \a i
         const Prob & message(size_t i, size_t _I) const { return _edges[i][_I].message; }
+        /// Returns reference to message from the \a _I 'th neighbor of variable \a i to variable \a i
         Prob & message(size_t i, size_t _I) { return _edges[i][_I].message; }
-        Prob & newMessage(size_t i, size_t _I) { return _edges[i][_I].newMessage; }
+        /// Returns constant reference to updated message from the \a _I 'th neighbor of variable \a i to variable \a i
         const Prob & newMessage(size_t i, size_t _I) const { return _edges[i][_I].newMessage; }
-        ind_t & index(size_t i, size_t _I) { return _edges[i][_I].index; }
+        /// Returns reference to updated message from the \a _I 'th neighbor of variable \a i to variable \a i
+        Prob & newMessage(size_t i, size_t _I) { return _edges[i][_I].newMessage; }
+        /// Returns constant reference to cached index for the edge between variable \a i and its \a _I 'th neighbor
         const ind_t & index(size_t i, size_t _I) const { return _edges[i][_I].index; }
-        Real & residual(size_t i, size_t _I) { return _edges[i][_I].residual; }
+        /// Returns reference to cached index for the edge between variable \a i and its \a _I 'th neighbor
+        ind_t & index(size_t i, size_t _I) { return _edges[i][_I].index; }
+        /// Returns constant reference to residual for the edge between variable \a i and its \a _I 'th neighbor
         const Real & residual(size_t i, size_t _I) const { return _edges[i][_I].residual; }
+        /// Returns reference to residual for the edge between variable \a i and its \a _I 'th neighbor
+        Real & residual(size_t i, size_t _I) { return _edges[i][_I].residual; }
 
+        /// Calculate the updated message from the \a _I 'th neighbor of variable \a i to variable \a i
         void calcNewMessage( size_t i, size_t _I );
+        /// Replace the "old" message from the \a _I 'th neighbor of variable \a i to variable \a i by the "new" (updated) message
         void updateMessage( size_t i, size_t _I );
+        /// Set the residual (difference between new and old message) for the edge between variable \a i and its \a _I 'th neighbor to \a r
         void updateResidual( size_t i, size_t _I, Real r );
+        /// Finds the edge which has the maximum residual (difference between new and old message)
         void findMaxResidual( size_t &i, size_t &_I );
-        /// Calculates unnormalized belief of variable
+        /// Calculates unnormalized belief of variable \a i
         void calcBeliefV( size_t i, Prob &p ) const;
-        /// Calculates unnormalized belief of factor
+        /// Calculates unnormalized belief of factor \a I
         void calcBeliefF( size_t I, Prob &p ) const;
 
+        /// Helper function for constructors
         void construct();
 };
 
index 86d633e..205b74d 100644 (file)
@@ -127,7 +127,9 @@ class InfAlg {
         virtual void clamp( size_t i, size_t x, bool backup = false ) = 0;
 
         // OBSOLETE
-        /// Only for backwards compatibility (to be removed soon)
+        /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v, x}\f$)
+        /** \deprecated Please use dai::InfAlg::clamp(size_t,size_t,bool) instead
+         */
         virtual void clamp( const Var &v, size_t x, bool backup = false ) = 0;
 
         /// Sets all factors interacting with variable with index \a i to one.
@@ -204,7 +206,9 @@ class DAIAlg : public InfAlg, public GRM {
         void clamp( size_t i, size_t x, bool backup = false ) { GRM::clamp( i, x, backup ); }
 
         // OBSOLETE
-        /// Only for backwards compatibility (to be removed soon)
+        /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v, x}\f$)
+        /** \deprecated Please use dai::DAIAlg<>::clamp(size_t,size_t,bool) instead
+         */
         void clamp( const Var &v, size_t x, bool backup = false ) {
             GRM::clamp( v, x, backup );
             std::cerr << "Warning: this DAIAlg<...>::clamp(const Var&,...) interface is obsolete!" << std::endl;
@@ -262,11 +266,15 @@ Factor calcMarginal( const InfAlg& obj, const VarSet& vs, bool reInit );
 std::vector<Factor> calcPairBeliefs( const InfAlg& obj, const VarSet& vs, bool reInit, bool accurate=false );
 
 // OBSOLETE
-/// Only for backwards compatibility (to be removed soon)
+/// Calculates beliefs for all pairs of variables in \a vs using inference algorithm \a obj.
+/** \deprecated Please use dai::calcPairBeliefs() instead with \a accurate == \c true
+ */
 std::vector<Factor> calcPairBeliefsNew( const InfAlg& obj, const VarSet& vs, bool reInit );
 
 // OBSOLETE
-/// Only for backwards compatibility (to be removed soon)
+/// Calculates marginal probability distribution for \a vs up to second order interactions using inference algorithm \a obj
+/** \deprecated Functionality is not widely used
+ */
 Factor calcMarginal2ndO( const InfAlg& obj, const VarSet& vs, bool reInit );
 
 
index 7d2cd70..1789619 100644 (file)
  *  "Generating Random Regular Graphs Quickly",
  *  <em>Combinatorics, Probability and Computing</em> Vol 8, Issue 4, pp. 377-396
  *  http://www.math.uwaterloo.ca/~nwormald/papers/randgen.pdf
+ *
+ *  \anchor EMK06 \ref EMK06
+ *  G. Elidan and I. McGraw and D. Koller (2006):
+ *  "Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing",
+ *  <em>Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)</em>
  */
 
 
index 749a699..b976b22 100644 (file)
@@ -225,13 +225,13 @@ template <typename T> class TFactor {
 
         // OBSOLETE
         /// Sets values that are smaller (in absolute value) than \a epsilon to 0
-        /** \note Obsolete, to be removed soon
+        /** \deprecated Functionality was not widely used
          */
         TFactor<T>& makeZero( T epsilon ) { _p.makeZero( epsilon ); return *this; }
 
         // OBSOLETE
         /// Sets values that are smaller than \a epsilon to \a epsilon
-        /** \note Obsolete, to be removed soon
+        /** \deprecated Functionality was not widely used
          */
         TFactor<T>& makePositive( T epsilon ) { _p.makePositive( epsilon ); return *this; }
 
index b0551d0..87d1c0e 100644 (file)
@@ -269,14 +269,16 @@ class FactorGraph {
         /// Returns a copy of \c *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
         FactorGraph maximalFactors() const;
 
-        /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_v,x}\f$);
+        /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i,x}\f$);
         /** \note This version changes the factor graph structure and thus returns a newly constructed FactorGraph
          *  and keeps the current one constant, contrary to clamp()
          */
         FactorGraph clamped( size_t i, size_t x ) const;
 
         // OBSOLETE
-        /// Only for backwards compatibility (to be removed soon)
+        /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v,x}\f$);
+        /** \deprecated Please use dai::FactorGraph::clamped(size_t,size_t) instead
+         */
         FactorGraph clamped( const Var &v, size_t x ) const {
             std::cerr << "Warning: this FactorGraph::clamped(const Var&,...) interface is obsolete!" << std::endl;
             return clamped( findVar(v), x );
@@ -291,7 +293,9 @@ class FactorGraph {
         virtual void clamp( size_t i, size_t x, bool backup = false );
 
         // OBSOLETE
-        /// Only for backwards compatibility (to be removed soon)
+        /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v, x}\f$)
+        /** \deprecated Please use dai::FactorGraph::clamp(size_t,size_t,bool) instead
+         */
         virtual void clamp( const Var &v, size_t x, bool backup = false ) {
             std::cerr << "Warning: this FactorGraph::clamp(const Var&,...) interface is obsolete!" << std::endl;
             clamp( findVar(v), x, backup );
@@ -342,11 +346,26 @@ class FactorGraph {
         // OBSOLETE
     /// \name Backwards compatibility layer (to be removed soon)
     //@{
-        size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
-        const Edge& edge(size_t e) const { return G.edge(e); }
+        /// Prepare backwards compatibility layer for indexed edges
+        /** \deprecated Please use FactorGraph::Neighbor interface instead
+         */
         void indexEdges() { G.indexEdges(); }
-        size_t nr_edges() const { return G.nr_edges(); }
+        /// Returns edge with index \a e
+        /** \deprecated Please use FactorGraph::Neighbor interface instead
+         */
+        const Edge& edge(size_t e) const { return G.edge(e); }
+        /// Returns all edges
+        /** \deprecated Please use FactorGraph::Neighbor interface instead
+         */
         const std::vector<Edge>& edges() const { return G.edges(); }
+        /// Converts a pair of node indices to an edge index
+        /** \deprecated Please use FactorGraph::Neighbor interface instead
+         */
+        size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
+        /// Returns number of edges
+        /** \deprecated Please use FactorGraph::Neighbor interface instead
+         */
+        size_t nr_edges() const { return G.nr_edges(); }
     //@}
 
     private:
index 733afd8..ee4c081 100644 (file)
@@ -98,6 +98,8 @@ class IndexFor {
 
         // OBSOLETE
         /// Conversion to \c long: returns linear index of the current state of indexVars
+        /** \deprecated Will be replaced by an operator size_t()
+         */
         operator long () const {
             return( _index );
         }
@@ -205,7 +207,9 @@ class Permute {
         }
 
         // OBSOLETE
-        /// For backwards compatibility (to be removed soon)
+        /// Calculates a permuted linear index
+        /** \deprecated Renamed into dai::Permute::convertLinearIndex()
+         */
         size_t convert_linear_index( size_t li ) const { return convertLinearIndex(li); }
 
         /// Returns const reference to the permutation
index 5140e1c..d382478 100644 (file)
@@ -381,7 +381,7 @@ template <typename T> class TProb {
 
         // OBSOLETE
         /// Returns pointwise signum
-        /** \note Obsolete, to be removed soon
+        /** \deprecated Functionality was not widely used
          */
         TProb<T> sgn() const {
             TProb<T> x;
@@ -499,7 +499,7 @@ template <typename T> class TProb {
 
         // OBSOLETE
         /// Sets entries that are smaller (in absolute value) than \a epsilon to 0
-        /** \note Obsolete, to be removed soon
+        /** \deprecated Functionality was not widely used
          */
         TProb<T>& makeZero( T epsilon ) {
             for( size_t i = 0; i < size(); i++ )
@@ -510,7 +510,7 @@ template <typename T> class TProb {
         
         // OBSOLETE
         /// Sets entries that are smaller than \a epsilon to \a epsilon
-        /** \note Obsolete, to be removed soon
+        /** \deprecated Functionality was not widely used
          */
         TProb<T>& makePositive( T epsilon ) {
             for( size_t i = 0; i < size(); i++ )
index 07ffbaf..46690e7 100644 (file)
@@ -162,7 +162,9 @@ class RegionGraph : public FactorGraph {
         bool checkCountingNumbers() const;
 
         // OBSOLETE
-        /// For backwards compatibility (to be removed soon)
+        /// Check whether the counting numbers are valid
+        /** \deprecated Renamed into dai::RegionGraph::checkCountingNumbers()
+         */
         bool Check_Counting_Numbers() { return checkCountingNumbers(); }
     //@}
 
@@ -208,7 +210,9 @@ class RegionGraph : public FactorGraph {
         void calcCountingNumbers();
 
         // OBSOLETE
-        /// For backwards compatibility (to be removed soon)
+        /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
+        /** \deprecated Renamed into dai::RegionGraph::calcCountingNumbers()
+         */
         void Calc_Counting_Numbers() { calcCountingNumbers(); }
     //@}
 
index 05c55f8..3e02d41 100644 (file)
@@ -196,7 +196,7 @@ void tokenizeString( const std::string& s, std::vector<std::string>& outTokens,
 
 // OBSOLETE
 /// Used to keep track of the progress made by iterative algorithms.
-/** \note Obsolete, to be removed soon
+/** \deprecated Superfluous, because a simple std::vector<Real> provides the same functionality
  */
 class Diffs : public std::vector<Real> {
     private: