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