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