d0a03d7f820242c415b11ad827e479da8868f87c
[libdai.git] / 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