c5794177ee36f201d6d02b9495aa8cf3fd547a3d
1 /* This file is part of libDAI - http://www.libdai.org/
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
10 /// \brief Defines class TRWBP, which implements Tree-Reweighted Belief Propagation
13 #ifndef __defined_libdai_trwbp_h
14 #define __defined_libdai_trwbp_h
18 #include <dai/daialg.h>
19 #include <dai/factorgraph.h>
20 #include <dai/properties.h>
28 /// Approximate inference algorithm "Tree-Reweighted Belief Propagation" [\ref WJW03]
29 /** The Tree-Reweighted Belief Propagation algorithm is like Belief
30 * Propagation, but associates each factor with a scale parameter.
31 * which controls the divergence measure being minimized.
33 * The messages \f$m_{I\to i}(x_i)\f$ are passed from factors \f$I\f$ to variables \f$i\f$.
34 * The update equation is given by:
35 * \f[ m_{I\to i}(x_i) \propto \sum_{x_{N_I\setminus\{i\}}} f_I(x_I)^{1/c_I} \prod_{j\in N_I\setminus\{i\}} m_{I\to j}^{c_I-1} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}^{c_J} \f]
36 * After convergence, the variable beliefs are calculated by:
37 * \f[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i}^{c_I} \f]
38 * and the factor beliefs are calculated by:
39 * \f[ b_I(x_I) \propto f_I(x_I)^{1/c_I} \prod_{j \in N_I} m_{I\to j}^{c_I-1} \prod_{J\in N_j\setminus\{I\}} m_{J\to j}^{c_J} \f]
40 * The logarithm of the partition sum is approximated by:
41 * \f[ \log Z = \sum_{I} \sum_{x_I} b_I(x_I) \big( \log f_I(x_I) - c_I \log b_I(x_I) \big) + \sum_{i} (c_i - 1) \sum_{x_i} b_i(x_i) \log b_i(x_i) \f]
42 * where the variable weights are defined as
43 * \f[ c_i := \sum_{I \in N_i} c_I \f]
45 * \note TRWBP is actually equivalent to FBP
46 * \todo Merge code of FBP and TRWBP
48 class TRWBP
: public BP
{
50 /// "Edge weights" (indexed by factor ID)
51 /** In [\ref WJW03], only unary or pairwise factors are considered.
52 * Here we are more general by having a weight for each factor in the
53 * factor graph. If unary factors have weight 1, and higher-order factors
54 * are absent, then we have the special case considered in [\ref WJW03].
56 std::vector
<Real
> _weight
;
59 /// Size of sample of trees used to set the weights
60 /** \todo See if there is a way to wrap TRWBP::nrtrees in a props struct
61 * together with the other properties currently in TRWBP::props
62 * (without copying al lot of BP code literally)
67 /// \name Constructors/destructors
69 /// Default constructor
70 TRWBP() : BP(), _weight() {}
72 /// Construct from FactorGraph \a fg and PropertySet \a opts.
73 /** There is an additional property "nrtrees" which allows to specify the
74 * number of random spanning trees used to set the scale parameters.
75 * \param fg Factor graph.
76 * \param opts Parameters @see BP::Properties.
78 TRWBP( const FactorGraph
&fg
, const PropertySet
&opts
) : BP(fg
, opts
), _weight() {
79 setProperties( opts
);
84 /// \name General InfAlg interface
86 virtual TRWBP
* clone() const { return new TRWBP(*this); }
87 virtual TRWBP
* construct( const FactorGraph
&fg
, const PropertySet
&opts
) const { return new TRWBP( fg
, opts
); }
88 virtual std::string
name() const { return "TRWBP"; }
89 virtual Real
logZ() const;
90 virtual void setProperties( const PropertySet
&opts
);
91 virtual PropertySet
getProperties() const;
92 virtual std::string
printProperties() const;
95 /// \name TRWBP accessors/mutators for scale parameters
97 /// Returns weight corresponding to the \a I 'th factor
98 Real
Weight( size_t I
) const { return _weight
[I
]; }
100 /// Returns constant reference to vector of all weights
101 const std::vector
<Real
>& Weights() const { return _weight
; }
103 /// Sets the weight of the \a I 'th factor to \a c
104 void setWeight( size_t I
, Real c
) { _weight
[I
] = c
; }
106 /// Sets the weights of all factors simultaenously
107 /** \note Faster than calling setWeight(size_t,Real) for each factor
109 void setWeights( const std::vector
<Real
> &c
) { _weight
= c
; }
111 /// Increases weights corresponding to pairwise factors in \a tree with 1
112 void addTreeToWeights( const RootedTree
&tree
);
114 /// Samples weights from a sample of \a nrTrees random spanning trees
115 void sampleWeights( size_t nrTrees
);
118 /// Calculate the product of factor \a I and the incoming messages
119 /** If \a without_i == \c true, the message coming from variable \a i is omitted from the product
120 * \note This function is used by calcNewMessage() and calcBeliefF()
122 virtual Prob
calcIncomingMessageProduct( size_t I
, bool without_i
, size_t i
) const;
124 /// Calculates unnormalized belief of variable \a i
125 virtual void calcBeliefV( size_t i
, Prob
&p
) const;
127 // Calculates unnormalized belief of factor \a I
128 virtual void calcBeliefF( size_t I
, Prob
&p
) const {
129 p
= calcIncomingMessageProduct( I
, false, 0 );
132 // Helper function for constructors
133 virtual void construct();
137 } // end of namespace dai