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