1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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 */
11 /// \file
12 /// \brief Defines class CBP [\ref EaG09]
13 /// \todo Improve documentation
16 #ifndef __defined_libdai_cbp_h
17 #define __defined_libdai_cbp_h
20 #include <fstream>
21 #include <boost/shared_ptr.hpp>
23 #include <dai/daialg.h>
24 #include <dai/bbp.h>
27 namespace dai {
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 );
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;
53 /// Counts number of clampings at each leaf node
54 Real _sum_level;
56 /// Number of leaves of recursion tree
57 size_t _num_leaves;
59 /// Output stream where information about the clampings is written
60 boost::shared_ptr<std::ofstream> _clamp_ofstream;
62 /// Returns BBP cost function used
63 bbp_cfn_t BBP_cost_function() { return props.bbp_cfn; }
65 /// Prints beliefs, variables and partition sum, in case of a debugging build
66 void printDebugInfo();
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 );
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 );
86 /// Return the InfAlg to use at each step of the recursion.
87 /// \todo At present, only returns a BP instance
88 InfAlg* getInfAlg();
90 /// Numer of iterations needed
91 size_t _iters;
92 /// Maximum difference encountered so far
93 Real _maxdiff;
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 );
100 /// Constructor helper function
101 void construct();
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 }
110 /// Name of this inference algorithm
111 static const char *Name;
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 std::vector<Factor> beliefs() const { return concat(_beliefsV, _beliefsF); }
120 virtual Real logZ() const { return _logZ; }
121 virtual void init() {};
122 virtual void init( const VarSet & ) {};
123 virtual Real run();
124 virtual Real maxDiff() const { return _maxdiff; }
125 virtual size_t Iterations() const { return _iters; }
126 //@}
128 Factor beliefV( size_t i ) const { return _beliefsV[i]; }
129 Factor beliefF( size_t I ) const { return _beliefsF[I]; }
131 //----------------------------------------------------------------
133 /// Parameters of this inference algorithm
134 /* PROPERTIES(props,CBP) {
135 /// Enumeration of possible update schedules
136 typedef BP::Properties::UpdateType UpdateType;
137 /// Enumeration of possible methods for deciding when to stop recursing
138 DAI_ENUM(RecurseType,REC_FIXED,REC_LOGZ,REC_BDIFF);
139 /// Enumeration of possible heuristics for choosing clamping variable
140 DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_MAXENT,CHOOSE_BBP,CHOOSE_BP_L1,CHOOSE_BP_CFN);
141 /// Enumeration of possible clampings: variables or factors
142 DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
144 /// Verbosity
145 size_t verbose = 0;
147 /// Tolerance to use in BP
148 Real tol;
149 /// Update style for BP
151 /// Maximum number of iterations for BP
152 size_t maxiter;
154 /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
155 Real rec_tol;
156 /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
157 size_t max_levels = 10;
158 /// If choose==CHOOSE_BBP and maximum adjoint is less than this value, don't recurse
160 /// Heuristic for choosing clamping variable
161 ChooseMethodType choose;
162 /// Method for deciding when to stop recursing
163 RecurseType recursion;
164 /// Whether to clamp variables or factors
165 ClampType clamp;
166 /// Properties to pass to BBP
167 PropertySet bbp_props;
168 /// Cost function to use for BBP
169 bbp_cfn_t bbp_cfn;
170 /// Random seed
171 size_t rand_seed = 0;
173 /// If non-empty, write clamping choices to this file
174 std::string clamp_outfile = "";
175 }
176 */
177 /* {{{ GENERATED CODE: DO NOT EDIT. Created by
178 ./scripts/regenerate-properties include/dai/cbp.h src/cbp.cpp
179 */
180 struct Properties {
181 /// Enumeration of possible update schedules
182 typedef BP::Properties::UpdateType UpdateType;
183 /// Enumeration of possible methods for deciding when to stop recursing
184 DAI_ENUM(RecurseType,REC_FIXED,REC_LOGZ,REC_BDIFF);
185 /// Enumeration of possible heuristics for choosing clamping variable
186 DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_MAXENT,CHOOSE_BBP,CHOOSE_BP_L1,CHOOSE_BP_CFN);
187 /// Enumeration of possible clampings: variables or factors
188 DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
189 /// Verbosity
190 size_t verbose;
191 /// Tolerance to use in BP
192 Real tol;
193 /// Update style for BP
195 /// Maximum number of iterations for BP
196 size_t maxiter;
197 /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
198 Real rec_tol;
199 /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
200 size_t max_levels;
201 /// If choose==CHOOSE_BBP and maximum adjoint is less than this value, don't recurse
203 /// Heuristic for choosing clamping variable
204 ChooseMethodType choose;
205 /// Method for deciding when to stop recursing
206 RecurseType recursion;
207 /// Whether to clamp variables or factors
208 ClampType clamp;
209 /// Properties to pass to BBP
210 PropertySet bbp_props;
211 /// Cost function to use for BBP
212 bbp_cfn_t bbp_cfn;
213 /// Random seed
214 size_t rand_seed;
215 /// If non-empty, write clamping choices to this file
216 std::string clamp_outfile;
218 /// Set members from PropertySet
219 void set(const PropertySet &opts);
220 /// Get members into PropertySet
221 PropertySet get() const;
222 /// Convert to a string which can be parsed as a PropertySet
223 std::string toString() const;
224 } props;
225 /* }}} END OF GENERATED CODE */
227 /// Returns heuristic used for clamping variable
228 Properties::ChooseMethodType ChooseMethod() { return props.choose; }
229 /// Returns method used for deciding when to stop recursing
230 Properties::RecurseType Recursion() { return props.recursion; }
231 /// Returns clamping type used
232 Properties::ClampType Clamping() { return props.clamp; }
233 /// Returns maximum number of levels of recursion
234 size_t maxClampLevel() { return props.max_levels; }
245 /// Computes \f$\frac{\exp(a)}{\exp(a)+\exp(b)}\f$
248 /// Computes log of sum of exponents, i.e., \f$\log\left(\exp(a) + \exp(b)\right)\f$