include/dai/cbp.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2009  Frederik Eaton [frederik at ofb dot net]
   8  */
   9
  10
  11 /// \file
  12 /// \brief Defines class CBP [\ref EaG09]
  13 /// \todo Improve documentation
  14
  15
  16 #ifndef __defined_libdai_cbp_h
  17 #define __defined_libdai_cbp_h
  18
  19
  20 #include <fstream>
  21 #include <boost/shared_ptr.hpp>
  22
  23 #include <dai/daialg.h>
  24 #include <dai/cbp.h>
  25 #include <dai/bbp.h>
  26
  27
  28 namespace dai {
  29
  30
  31 /// Find a variable to clamp using BBP (goes with maximum adjoint)
  32 /// \see BBP
  33 std::pair<size_t, size_t> bbpFindClampVar( const InfAlg &in_bp, bool clampingVar, const PropertySet &bbp_props, bbp_cfn_t cfn, Real *maxVarOut );
  34
  35
  36 /// Class for CBP (Clamped Belief Propagation)
  37 /** This algorithm uses configurable heuristics to choose a variable
  38  *  x_i and a state x_i*. Inference is done with x_i "clamped" to x_i*
  39  *  (i.e., conditional on x_i == x_i*), and also with the negation of this
  40  *  condition. Clamping is done recursively up to a fixed number of
  41  *  levels (other stopping criteria are also implemented, see
  42  *  \a recursion property). The resulting approximate marginals are
  43  *  combined using logZ estimates.
  44  */
  45 class CBP : public DAIAlgFG {
  46     private:
  47         /// Variable beliefs
  48         std::vector<Factor> _beliefsV;
  49         /// Factor beliefs
  50         std::vector<Factor> _beliefsF;
  51         /// Log-partition sum
  52         double _logZ;
  53
  54         /// Counts number of clampings at each leaf node
  55         double _sum_level;
  56
  57         /// Number of leaves of recursion tree
  58         size_t _num_leaves;
  59
  60         /// Output stream where information about the clampings is written
  61         boost::shared_ptr<std::ofstream> _clamp_ofstream;
  62
  63         /// Returns BBP cost function used
  64         bbp_cfn_t BBP_cost_function() { return props.bbp_cfn; }
  65
  66         /// Prints beliefs, variables and partition sum, in case of a debugging build
  67         void printDebugInfo();
  68
  69         /// Called by 'run', and by itself. Implements the main algorithm.
  70         /** Chooses a variable to clamp, recurses, combines the logZ and
  71          *  beliefs estimates of the children, and returns the improved
  72          *  estimates in \a lz_out and \a beliefs_out to its parent
  73          */
  74         void runRecurse( InfAlg *bp, double orig_logZ, std::vector<size_t> clamped_vars_list, size_t &num_leaves,
  75                          size_t &choose_count, double &sum_level, Real &lz_out, std::vector<Factor> &beliefs_out );
  76
  77         /// Choose the next variable to clamp
  78         /** Choose the next variable to clamp, given a converged InfAlg (\a bp),
  79          *  and a vector of variables that are already clamped (\a
  80          *  clamped_vars_list). Returns the chosen variable in \a i, and
  81          *  the set of states in \a xis. If \a maxVarOut is non-NULL and
  82          *  props.choose==CHOOSE_BBP then it is used to store the
  83          *  adjoint of the chosen variable
  84          */
  85         virtual bool chooseNextClampVar( InfAlg* bp, std::vector<size_t> &clamped_vars_list, size_t &i, std::vector<size_t> &xis, Real *maxVarOut );
  86
  87         /// Return the InfAlg to use at each step of the recursion.
  88         /// \todo At present, only returns a BP instance
  89         InfAlg* getInfAlg();
  90
  91         /// Numer of iterations needed
  92         size_t _iters;
  93         /// Maximum difference encountered so far
  94         double _maxdiff;
  95
  96         /// Sets variable beliefs, factor beliefs and logZ
  97         /** \param bs should be a concatenation of the variable beliefs followed by the factor beliefs
  98          */
  99         void setBeliefs( const std::vector<Factor> &bs, double logZ );
 100
 101         /// Constructor helper function
 102         void construct();
 103
 104     public:
 105         /// Construct CBP object from FactorGraph fg and PropertySet opts
 106         CBP( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg) {
 107             props.set( opts );
 108             construct();
 109         }
 110
 111         /// Name of this inference algorithm
 112         static const char *Name;
 113
 114         /// @name General InfAlg interface
 115         //@{
 116         virtual CBP* clone() const { return new CBP(*this); }
 117         virtual std::string identify() const { return std::string(Name) + props.toString(); }
 118         virtual Factor belief (const Var &n) const { return _beliefsV[findVar(n)]; }
 119         virtual Factor belief (const VarSet &) const { DAI_THROW(NOT_IMPLEMENTED); }
 120         virtual std::vector<Factor> beliefs() const { return concat(_beliefsV, _beliefsF); }
 121         virtual Real logZ() const { return _logZ; }
 122         virtual void init() {};
 123         virtual void init( const VarSet & ) {};
 124         virtual double run();
 125         virtual double maxDiff() const { return _maxdiff; }
 126         virtual size_t Iterations() const { return _iters; }
 127         //@}
 128
 129         Factor beliefV( size_t i ) const { return _beliefsV[i]; }
 130         Factor beliefF( size_t I ) const { return _beliefsF[I]; }
 131
 132         //----------------------------------------------------------------
 133
 134         /// Parameters of this inference algorithm
 135         /* PROPERTIES(props,CBP) {
 136             /// Enumeration of possible update schedules
 137             typedef BP::Properties::UpdateType UpdateType;
 138             /// Enumeration of possible methods for deciding when to stop recursing
 139             DAI_ENUM(RecurseType,REC_FIXED,REC_LOGZ,REC_BDIFF);
 140             /// Enumeration of possible heuristics for choosing clamping variable
 141             DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_MAXENT,CHOOSE_BBP,CHOOSE_BP_L1,CHOOSE_BP_CFN);
 142             /// Enumeration of possible clampings: variables or factors
 143             DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
 144
 145             /// Verbosity
 146             size_t verbose = 0;
 147
 148             /// Tolerance to use in BP
 149             double tol;
 150             /// Update style for BP
 151             UpdateType updates;
 152             /// Maximum number of iterations for BP
 153             size_t maxiter;
 154
 155             /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
 156             double rec_tol;
 157             /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
 158             size_t max_levels = 10;
 159             /// If choose==CHOOSE_BBP and maximum adjoint is less than this value, don't recurse
 160             double min_max_adj;
 161             /// Heuristic for choosing clamping variable
 162             ChooseMethodType choose;
 163             /// Method for deciding when to stop recursing
 164             RecurseType recursion;
 165             /// Whether to clamp variables or factors
 166             ClampType clamp;
 167             /// Properties to pass to BBP
 168             PropertySet bbp_props;
 169             /// Cost function to use for BBP
 170             bbp_cfn_t bbp_cfn;
 171             /// Random seed
 172             size_t rand_seed = 0;
 173
 174             /// If non-empty, write clamping choices to this file
 175             std::string clamp_outfile = "";
 176         }
 177         */
 178 /* {{{ GENERATED CODE: DO NOT EDIT. Created by
 179     ./scripts/regenerate-properties include/dai/cbp.h src/cbp.cpp
 180 */
 181         struct Properties {
 182             /// Enumeration of possible update schedules
 183             typedef BP::Properties::UpdateType UpdateType;
 184             /// Enumeration of possible methods for deciding when to stop recursing
 185             DAI_ENUM(RecurseType,REC_FIXED,REC_LOGZ,REC_BDIFF);
 186             /// Enumeration of possible heuristics for choosing clamping variable
 187             DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_MAXENT,CHOOSE_BBP,CHOOSE_BP_L1,CHOOSE_BP_CFN);
 188             /// Enumeration of possible clampings: variables or factors
 189             DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
 190             /// Verbosity
 191             size_t verbose;
 192             /// Tolerance to use in BP
 193             double tol;
 194             /// Update style for BP
 195             UpdateType updates;
 196             /// Maximum number of iterations for BP
 197             size_t maxiter;
 198             /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
 199             double rec_tol;
 200             /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
 201             size_t max_levels;
 202             /// If choose==CHOOSE_BBP and maximum adjoint is less than this value, don't recurse
 203             double min_max_adj;
 204             /// Heuristic for choosing clamping variable
 205             ChooseMethodType choose;
 206             /// Method for deciding when to stop recursing
 207             RecurseType recursion;
 208             /// Whether to clamp variables or factors
 209             ClampType clamp;
 210             /// Properties to pass to BBP
 211             PropertySet bbp_props;
 212             /// Cost function to use for BBP
 213             bbp_cfn_t bbp_cfn;
 214             /// Random seed
 215             size_t rand_seed;
 216             /// If non-empty, write clamping choices to this file
 217             std::string clamp_outfile;
 218
 219             /// Set members from PropertySet
 220             void set(const PropertySet &opts);
 221             /// Get members into PropertySet
 222             PropertySet get() const;
 223             /// Convert to a string which can be parsed as a PropertySet
 224             std::string toString() const;
 225         } props;
 226 /* }}} END OF GENERATED CODE */
 227
 228         /// Returns heuristic used for clamping variable
 229         Properties::ChooseMethodType ChooseMethod() { return props.choose; }
 230         /// Returns method used for deciding when to stop recursing
 231         Properties::RecurseType Recursion() { return props.recursion; }
 232         /// Returns clamping type used
 233         Properties::ClampType Clamping() { return props.clamp; }
 234         /// Returns maximum number of levels of recursion
 235         size_t maxClampLevel() { return props.max_levels; }
 236         /// Returns props.min_max_adj @see CBP::Properties::min_max_adj
 237         double minMaxAdj() { return props.min_max_adj; }
 238         /// Returns tolerance used for controlling recursion depth
 239         double recTol() { return props.rec_tol; }
 240 };
 241
 242
 243 /// Given a sorted vector of states \a xis and total state count \a n_states, return a vector of states not in \a xis
 244 std::vector<size_t> complement( std::vector<size_t>& xis, size_t n_states );
 245
 246 /// Computes \f$\frac{\exp(a)}{\exp(a)+\exp(b)}\f$
 247 Real unSoftMax( Real a, Real b );
 248
 249 /// Computes log of sum of exponents, i.e., \f$\log\left(\exp(a) + \exp(b)\right)\f$
 250 Real logSumExp( Real a, Real b );
 251
 252 /// Compute sum of pairwise L-infinity distances of the first \a nv factors in each vector
 253 Real dist( const std::vector<Factor>& b1, const std::vector<Factor>& b2, size_t nv );
 254
 255
 256 } // end of namespace dai
 257
 258
 259 #endif