include/dai/cbp.h

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