Moved platform independent build options into Makefile.ALL and documented tests/testdai
[libdai.git] / include / dai / cbp.h
index 370228d..35bc771 100644 (file)
@@ -4,14 +4,12 @@
  *  2, or (at your option) any later version. libDAI is distributed without any
  *  warranty. See the file COPYING for more details.
  *
  *  2, or (at your option) any later version. libDAI is distributed without any
  *  warranty. See the file COPYING for more details.
  *
- *  Copyright (C) 2009  Frederik Eaton [frederik at ofb dot net]
+ *  Copyright (C) 2009  Frederik Eaton  [frederik at ofb dot net]
  */
 
 
 /// \file
  */
 
 
 /// \file
-/// \brief Defines class CBP [\ref EaG09]
-/// \author Frederik Eaton
-/// \todo Improve documentation
+/// \brief Defines class CBP, which implements Clamped Belief Propagation
 
 
 #ifndef __defined_libdai_cbp_h
 
 
 #ifndef __defined_libdai_cbp_h
 namespace dai {
 
 
 namespace dai {
 
 
-/// Find a variable to clamp using BBP (goes with maximum adjoint)
-/// \see BBP
-std::pair<size_t, size_t> bbpFindClampVar( const InfAlg &in_bp, bool clampingVar, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real *maxVarOut );
-
-
-/// Class for CBP (Clamped Belief Propagation)
-/** This algorithm uses configurable heuristics to choose a variable
- *  x_i and a state x_i*. Inference is done with x_i "clamped" to x_i*
- *  (i.e., conditional on x_i == x_i*), and also with the negation of this
- *  condition. Clamping is done recursively up to a fixed number of
- *  levels (other stopping criteria are also implemented, see
- *  \a recursion property). The resulting approximate marginals are
- *  combined using logZ estimates.
+/// Class for CBP (Clamped Belief Propagation) [\ref EaG09]
+/** This approximate inference algorithm uses configurable heuristics to choose a variable
+ *  \f$ x_i \f$ and a state \f$ x_i^* \f$. Inference is done with \f$ x_i \f$ "clamped" to \f$ x_i^* \f$
+ *  (i.e., conditional on \f$ x_i = x_i^* \f$), and also with the negation of this condition. 
+ *  Clamping is done recursively up to a fixed number of levels (other stopping criteria are 
+ *  also implemented, see the CBP::Properties::RecurseType property). The resulting approximate 
+ *  marginals are combined using estimates of the partition sum.
  *
  *  \author Frederik Eaton
  */
  *
  *  \author Frederik Eaton
  */
@@ -50,61 +42,27 @@ class CBP : public DAIAlgFG {
         std::vector<Factor> _beliefsV;
         /// Factor beliefs
         std::vector<Factor> _beliefsF;
         std::vector<Factor> _beliefsV;
         /// Factor beliefs
         std::vector<Factor> _beliefsF;
-        /// Log-partition sum
+        /// Logarithm of partition sum
         Real _logZ;
 
         Real _logZ;
 
-        /// Counts number of clampings at each leaf node
-        Real _sum_level;
+        /// Numer of iterations needed
+        size_t _iters;
+        /// Maximum difference encountered so far
+        Real _maxdiff;
 
 
+        /// Number of clampings at each leaf node
+        Real _sum_level;
         /// Number of leaves of recursion tree
         size_t _num_leaves;
 
         /// Output stream where information about the clampings is written
         boost::shared_ptr<std::ofstream> _clamp_ofstream;
 
         /// Number of leaves of recursion tree
         size_t _num_leaves;
 
         /// Output stream where information about the clampings is written
         boost::shared_ptr<std::ofstream> _clamp_ofstream;
 
-        /// Returns BBP cost function used
-        BBPCostFunction BBP_cost_function() { return props.bbp_cfn; }
-
-        /// Prints beliefs, variables and partition sum, in case of a debugging build
-        void printDebugInfo();
-
-        /// Called by 'run', and by itself. Implements the main algorithm.
-        /** Chooses a variable to clamp, recurses, combines the logZ and
-         *  beliefs estimates of the children, and returns the improved
-         *  estimates in \a lz_out and \a beliefs_out to its parent
-         */
-        void runRecurse( InfAlg *bp, Real orig_logZ, std::vector<size_t> clamped_vars_list, size_t &num_leaves,
-                         size_t &choose_count, Real &sum_level, Real &lz_out, std::vector<Factor> &beliefs_out );
-
-        /// Choose the next variable to clamp
-        /** Choose the next variable to clamp, given a converged InfAlg (\a bp),
-         *  and a vector of variables that are already clamped (\a
-         *  clamped_vars_list). Returns the chosen variable in \a i, and
-         *  the set of states in \a xis. If \a maxVarOut is non-NULL and
-         *  props.choose==CHOOSE_BBP then it is used to store the
-         *  adjoint of the chosen variable
-         */
-        virtual bool chooseNextClampVar( InfAlg* bp, std::vector<size_t> &clamped_vars_list, size_t &i, std::vector<size_t> &xis, Real *maxVarOut );
-
-        /// Return the InfAlg to use at each step of the recursion.
-        /// \todo At present, only returns a BP instance
-        InfAlg* getInfAlg();
-
-        /// Numer of iterations needed
-        size_t _iters;
-        /// Maximum difference encountered so far
-        Real _maxdiff;
-
-        /// Sets variable beliefs, factor beliefs and logZ
-        /** \param bs should be a concatenation of the variable beliefs followed by the factor beliefs
-         */
-        void setBeliefs( const std::vector<Factor> &bs, Real logZ );
-
-        /// Constructor helper function
-        void construct();
 
     public:
 
     public:
-        /// Construct CBP object from FactorGraph fg and PropertySet opts
+        /// Construct CBP object from FactorGraph \a fg and PropertySet \a opts
+        /** \param opts Parameters @see Properties
+         */
         CBP( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg) {
             props.set( opts );
             construct();
         CBP( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg) {
             props.set( opts );
             construct();
@@ -117,8 +75,8 @@ class CBP : public DAIAlgFG {
     //@{
         virtual CBP* clone() const { return new CBP(*this); }
         virtual std::string identify() const { return std::string(Name) + props.toString(); }
     //@{
         virtual CBP* clone() const { return new CBP(*this); }
         virtual std::string identify() const { return std::string(Name) + props.toString(); }
-        virtual Factor belief (const Var &n) const { return _beliefsV[findVar(n)]; }
-        virtual Factor belief (const VarSet &) const { DAI_THROW(NOT_IMPLEMENTED); }
+        virtual Factor belief( const Var &v ) const { return beliefV( findVar( v ) ); }
+        virtual Factor belief( const VarSet & ) const { DAI_THROW(NOT_IMPLEMENTED); }
         virtual Factor beliefV( size_t i ) const { return _beliefsV[i]; }
         virtual Factor beliefF( size_t I ) const { return _beliefsF[I]; }
         virtual std::vector<Factor> beliefs() const { return concat(_beliefsV, _beliefsF); }
         virtual Factor beliefV( size_t i ) const { return _beliefsV[i]; }
         virtual Factor beliefF( size_t I ) const { return _beliefsF[I]; }
         virtual std::vector<Factor> beliefs() const { return concat(_beliefsV, _beliefsF); }
@@ -135,7 +93,7 @@ class CBP : public DAIAlgFG {
 
         //----------------------------------------------------------------
 
 
         //----------------------------------------------------------------
 
-        /// Parameters of this inference algorithm
+        /// Parameters for CBP
         /* PROPERTIES(props,CBP) {
             /// Enumeration of possible update schedules
             typedef BP::Properties::UpdateType UpdateType;
         /* PROPERTIES(props,CBP) {
             /// Enumeration of possible update schedules
             typedef BP::Properties::UpdateType UpdateType;
@@ -146,17 +104,17 @@ class CBP : public DAIAlgFG {
             /// Enumeration of possible clampings: variables or factors
             DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
 
             /// Enumeration of possible clampings: variables or factors
             DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
 
-            /// Verbosity
+            /// Verbosity (amount of output sent to stderr)
             size_t verbose = 0;
 
             size_t verbose = 0;
 
-            /// Tolerance to use in BP
+            /// Tolerance for BP convergence test
             Real tol;
             /// Update style for BP
             UpdateType updates;
             /// Maximum number of iterations for BP
             size_t maxiter;
 
             Real tol;
             /// Update style for BP
             UpdateType updates;
             /// Maximum number of iterations for BP
             size_t maxiter;
 
-            /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
+            /// Tolerance used for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
             Real rec_tol;
             /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
             size_t max_levels = 10;
             Real rec_tol;
             /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
             size_t max_levels = 10;
@@ -191,15 +149,15 @@ class CBP : public DAIAlgFG {
             DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_MAXENT,CHOOSE_BBP,CHOOSE_BP_L1,CHOOSE_BP_CFN);
             /// Enumeration of possible clampings: variables or factors
             DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
             DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_MAXENT,CHOOSE_BBP,CHOOSE_BP_L1,CHOOSE_BP_CFN);
             /// Enumeration of possible clampings: variables or factors
             DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
-            /// Verbosity
+            /// Verbosity (amount of output sent to stderr)
             size_t verbose;
             size_t verbose;
-            /// Tolerance to use in BP
+            /// Tolerance for BP convergence test
             Real tol;
             /// Update style for BP
             UpdateType updates;
             /// Maximum number of iterations for BP
             size_t maxiter;
             Real tol;
             /// Update style for BP
             UpdateType updates;
             /// Maximum number of iterations for BP
             size_t maxiter;
-            /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
+            /// Tolerance used for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
             Real rec_tol;
             /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
             size_t max_levels;
             Real rec_tol;
             /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
             size_t max_levels;
@@ -221,6 +179,9 @@ class CBP : public DAIAlgFG {
             std::string clamp_outfile;
 
             /// Set members from PropertySet
             std::string clamp_outfile;
 
             /// Set members from PropertySet
+            /** \throw UNKNOWN_PROPERTY if a Property key is not recognized
+             *  \throw NOT_ALL_PROPERTIES_SPECIFIED if an expected Property is missing
+             */
             void set(const PropertySet &opts);
             /// Get members into PropertySet
             PropertySet get() const;
             void set(const PropertySet &opts);
             /// Get members into PropertySet
             PropertySet get() const;
@@ -229,32 +190,58 @@ class CBP : public DAIAlgFG {
         } props;
 /* }}} END OF GENERATED CODE */
 
         } props;
 /* }}} END OF GENERATED CODE */
 
-        /// Returns heuristic used for clamping variable
-        Properties::ChooseMethodType ChooseMethod() { return props.choose; }
-        /// Returns method used for deciding when to stop recursing
-        Properties::RecurseType Recursion() { return props.recursion; }
-        /// Returns clamping type used
-        Properties::ClampType Clamping() { return props.clamp; }
-        /// Returns maximum number of levels of recursion
-        size_t maxClampLevel() { return props.max_levels; }
-        /// Returns props.min_max_adj @see CBP::Properties::min_max_adj
-        Real minMaxAdj() { return props.min_max_adj; }
-        /// Returns tolerance used for controlling recursion depth
-        Real recTol() { return props.rec_tol; }
-};
+    private:
+        /// Prints beliefs, variables and partition sum, in case of a debugging build
+        void printDebugInfo();
+
+        /// Called by run(), and by itself. Implements the main algorithm.
+        /** Chooses a variable to clamp, recurses, combines the partition sum 
+         *  and belief estimates of the children, and returns the improved
+         *  estimates in \a lz_out and \a beliefs_out to its parent.
+         */
+        void runRecurse( InfAlg *bp, Real orig_logZ, std::vector<size_t> clamped_vars_list, size_t &num_leaves,
+                         size_t &choose_count, Real &sum_level, Real &lz_out, std::vector<Factor> &beliefs_out );
+
+        /// Choose the next variable to clamp.
+        /** Choose the next variable to clamp, given a converged InfAlg \a bp,
+         *  and a vector of variables that are already clamped (\a
+         *  clamped_vars_list). Returns the chosen variable in \a i, and
+         *  the set of states in \a xis. If \a maxVarOut is non-NULL and
+         *  \a props.choose == \c CHOOSE_BBP then it is used to store the
+         *  adjoint of the chosen variable.
+         */
+        virtual bool chooseNextClampVar( InfAlg* bp, std::vector<size_t> &clamped_vars_list, size_t &i, std::vector<size_t> &xis, Real *maxVarOut );
 
 
+        /// Return the InfAlg to use at each step of the recursion.
+        /** \todo At present, CBP::getInfAlg() only returns a BP instance; 
+         *  it should be possible to select other inference algorithms via a property
+         */
+        InfAlg* getInfAlg();
 
 
-/// Given a sorted vector of states \a xis and total state count \a n_states, return a vector of states not in \a xis
-std::vector<size_t> complement( std::vector<size_t>& xis, size_t n_states );
+        /// Sets variable beliefs, factor beliefs and log partition sum to the specified values
+        /** \param bs should be a concatenation of the variable beliefs followed by the factor beliefs
+         *  \param logZ log partition sum
+         */
+        void setBeliefs( const std::vector<Factor> &bs, Real logZ );
 
 
-/// Computes \f$\frac{\exp(a)}{\exp(a)+\exp(b)}\f$
-Real unSoftMax( Real a, Real b );
+        /// Constructor helper function
+        void construct();
+};
 
 
-/// Computes log of sum of exponents, i.e., \f$\log\left(\exp(a) + \exp(b)\right)\f$
-Real logSumExp( Real a, Real b );
 
 
-/// Compute sum of pairwise L-infinity distances of the first \a nv factors in each vector
-Real dist( const std::vector<Factor>& b1, const std::vector<Factor>& b2, size_t nv );
+/// Find the best variable/factor to clamp using BBP.
+/** Takes a converged inference algorithm as input, runs Gibbs and BP_dual, creates
+ *  and runs a BBP object, finds the best variable/factor (the one with the maximum
+ *  factor adjoint), and returns the corresponding (index,state) pair.
+ *  \param in_bp inference algorithm (compatible with BP) that should have converged;
+ *  \param clampingVar if \c true, finds best variable, otherwise, finds best factor;
+ *  \param bbp_props BBP parameters to use;
+ *  \param cfn BBP cost function to use;
+ *  \param maxVarOut maximum adjoint value (only set if not NULL).
+ *  \see BBP
+ *  \relates CBP
+ */
+std::pair<size_t, size_t> BBPFindClampVar( const InfAlg &in_bp, bool clampingVar, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real *maxVarOut );
 
 
 } // end of namespace dai
 
 
 } // end of namespace dai