1 /* This file is part of libDAI - http://www.libdai.org/
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.
7 * Copyright (C) 2009 Frederik Eaton [frederik at ofb dot net]
12 /// \brief Defines class CBP [\ref EaG09]
13 /// \todo Improve documentation
16 #ifndef __defined_libdai_cbp_h
17 #define __defined_libdai_cbp_h
21 #include <boost/shared_ptr.hpp>
23 #include <dai/daialg.h>
30 /// Find a variable to clamp using BBP (goes with maximum adjoint)
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.
44 class CBP
: public DAIAlgFG
{
47 std::vector
<Factor
> _beliefsV
;
49 std::vector
<Factor
> _beliefsF
;
53 /// Counts number of clampings at each leaf node
56 /// Number of leaves of recursion tree
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
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
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
90 /// Numer of iterations needed
92 /// Maximum difference encountered so far
95 /// Sets variable beliefs, factor beliefs and logZ
96 /** \param bs should be a concatenation of the variable beliefs followed by the factor beliefs
98 void setBeliefs( const std::vector
<Factor
> &bs
, Real logZ
);
100 /// Constructor helper function
104 /// Construct CBP object from FactorGraph fg and PropertySet opts
105 CBP( const FactorGraph
&fg
, const PropertySet
&opts
) : DAIAlgFG(fg
) {
110 /// Name of this inference algorithm
111 static const char *Name
;
113 /// \name General InfAlg interface
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 Factor
beliefV( size_t i
) const { return _beliefsV
[i
]; }
120 virtual Factor
beliefF( size_t I
) const { return _beliefsF
[I
]; }
121 virtual std::vector
<Factor
> beliefs() const { return concat(_beliefsV
, _beliefsF
); }
122 virtual Real
logZ() const { return _logZ
; }
123 virtual void init() {};
124 virtual void init( const VarSet
& ) {};
126 virtual Real
maxDiff() const { return _maxdiff
; }
127 virtual size_t Iterations() const { return _iters
; }
128 virtual void setProperties( const PropertySet
&opts
) { props
.set( opts
); }
129 virtual PropertySet
getProperties() const { return props
.get(); }
130 virtual std::string
printProperties() const { return props
.toString(); }
133 //----------------------------------------------------------------
135 /// Parameters of this inference algorithm
136 /* PROPERTIES(props,CBP) {
137 /// Enumeration of possible update schedules
138 typedef BP::Properties::UpdateType UpdateType;
139 /// Enumeration of possible methods for deciding when to stop recursing
140 DAI_ENUM(RecurseType,REC_FIXED,REC_LOGZ,REC_BDIFF);
141 /// Enumeration of possible heuristics for choosing clamping variable
142 DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_MAXENT,CHOOSE_BBP,CHOOSE_BP_L1,CHOOSE_BP_CFN);
143 /// Enumeration of possible clampings: variables or factors
144 DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
149 /// Tolerance to use in BP
151 /// Update style for BP
153 /// Maximum number of iterations for BP
156 /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
158 /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
159 size_t max_levels = 10;
160 /// If choose==CHOOSE_BBP and maximum adjoint is less than this value, don't recurse
162 /// Heuristic for choosing clamping variable
163 ChooseMethodType choose;
164 /// Method for deciding when to stop recursing
165 RecurseType recursion;
166 /// Whether to clamp variables or factors
168 /// Properties to pass to BBP
169 PropertySet bbp_props;
170 /// Cost function to use for BBP
173 size_t rand_seed = 0;
175 /// If non-empty, write clamping choices to this file
176 std::string clamp_outfile = "";
179 /* {{{ GENERATED CODE: DO NOT EDIT. Created by
180 ./scripts/regenerate-properties include/dai/cbp.h src/cbp.cpp
183 /// Enumeration of possible update schedules
184 typedef BP::Properties::UpdateType UpdateType
;
185 /// Enumeration of possible methods for deciding when to stop recursing
186 DAI_ENUM(RecurseType
,REC_FIXED
,REC_LOGZ
,REC_BDIFF
);
187 /// Enumeration of possible heuristics for choosing clamping variable
188 DAI_ENUM(ChooseMethodType
,CHOOSE_RANDOM
,CHOOSE_MAXENT
,CHOOSE_BBP
,CHOOSE_BP_L1
,CHOOSE_BP_CFN
);
189 /// Enumeration of possible clampings: variables or factors
190 DAI_ENUM(ClampType
,CLAMP_VAR
,CLAMP_FACTOR
);
193 /// Tolerance to use in BP
195 /// Update style for BP
197 /// Maximum number of iterations for BP
199 /// Tolerance to use for controlling recursion depth (\a recurse is REC_LOGZ or REC_BDIFF)
201 /// Maximum number of levels of recursion (\a recurse is REC_FIXED)
203 /// If choose==CHOOSE_BBP and maximum adjoint is less than this value, don't recurse
205 /// Heuristic for choosing clamping variable
206 ChooseMethodType choose
;
207 /// Method for deciding when to stop recursing
208 RecurseType recursion
;
209 /// Whether to clamp variables or factors
211 /// Properties to pass to BBP
212 PropertySet bbp_props
;
213 /// Cost function to use for BBP
217 /// If non-empty, write clamping choices to this file
218 std::string clamp_outfile
;
220 /// Set members from PropertySet
221 void set(const PropertySet
&opts
);
222 /// Get members into PropertySet
223 PropertySet
get() const;
224 /// Convert to a string which can be parsed as a PropertySet
225 std::string
toString() const;
227 /* }}} END OF GENERATED CODE */
229 /// Returns heuristic used for clamping variable
230 Properties::ChooseMethodType
ChooseMethod() { return props
.choose
; }
231 /// Returns method used for deciding when to stop recursing
232 Properties::RecurseType
Recursion() { return props
.recursion
; }
233 /// Returns clamping type used
234 Properties::ClampType
Clamping() { return props
.clamp
; }
235 /// Returns maximum number of levels of recursion
236 size_t maxClampLevel() { return props
.max_levels
; }
237 /// Returns props.min_max_adj @see CBP::Properties::min_max_adj
238 Real
minMaxAdj() { return props
.min_max_adj
; }
239 /// Returns tolerance used for controlling recursion depth
240 Real
recTol() { return props
.rec_tol
; }
244 /// Given a sorted vector of states \a xis and total state count \a n_states, return a vector of states not in \a xis
245 std::vector
<size_t> complement( std::vector
<size_t>& xis
, size_t n_states
);
247 /// Computes \f$\frac{\exp(a)}{\exp(a)+\exp(b)}\f$
248 Real
unSoftMax( Real a
, Real b
);
250 /// Computes log of sum of exponents, i.e., \f$\log\left(\exp(a) + \exp(b)\right)\f$
251 Real
logSumExp( Real a
, Real b
);
253 /// Compute sum of pairwise L-infinity distances of the first \a nv factors in each vector
254 Real
dist( const std::vector
<Factor
>& b1
, const std::vector
<Factor
>& b2
, size_t nv
);
257 } // end of namespace dai