Improved TreeEP (added 'maxtime' property)
[libdai.git] / include / dai / trwbp.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) 2010 Joris Mooij [joris dot mooij at libdai dot org]
8 */
9
10
11 /// \file
12 /// \brief Defines class TRWBP, which implements Tree-Reweighted Belief Propagation
13
14
15 #ifndef __defined_libdai_trwbp_h
16 #define __defined_libdai_trwbp_h
17
18
19 #include <string>
20 #include <dai/daialg.h>
21 #include <dai/factorgraph.h>
22 #include <dai/properties.h>
23 #include <dai/enum.h>
24 #include <dai/bp.h>
25
26
27 namespace dai {
28
29
30 /// Approximate inference algorithm "Tree-Reweighted Belief Propagation" [\ref WJW03]
31 /** The Tree-Reweighted Belief Propagation algorithm is like Belief
32 * Propagation, but associates each factor with a scale parameter.
33 * which controls the divergence measure being minimized.
34 *
35 * The messages \f$m_{I\to i}(x_i)\f$ are passed from factors \f$I\f$ to variables \f$i\f$.
36 * The update equation is given by:
37 * \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]
38 * After convergence, the variable beliefs are calculated by:
39 * \f[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i}^{c_I} \f]
40 * and the factor beliefs are calculated by:
41 * \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]
42 * The logarithm of the partition sum is approximated by:
43 * \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]
44 * where the variable weights are defined as
45 * \f[ c_i := \sum_{I \in N_i} c_I \f]
46 *
47 * \note TRWBP is actually equivalent to FBP
48 * \todo Merge code of FBP and TRWBP
49 */
50 class TRWBP : public BP {
51 protected:
52 /// "Edge weights" (indexed by factor ID)
53 /** In [\ref WJW03], only unary or pairwise factors are considered.
54 * Here we are more general by having a weight for each factor in the
55 * factor graph. If unary factors have weight 1, and higher-order factors
56 * are absent, then we have the special case considered in [\ref WJW03].
57 */
58 std::vector<Real> _weight;
59
60 public:
61 /// Size of sample of trees used to set the weights
62 /** \todo See if there is a way to wrap TRWBP::nrtrees in a props struct
63 * together with the other properties currently in TRWBP::props
64 * (without copying al lot of BP code literally)
65 */
66 size_t nrtrees;
67
68 /// Name of this inference algorithm
69 static const char *Name;
70
71 public:
72 /// \name Constructors/destructors
73 //@{
74 /// Default constructor
75 TRWBP() : BP(), _weight() {}
76
77 /// Construct from FactorGraph \a fg and PropertySet \a opts.
78 /** There is an additional property "nrtrees" which allows to specify the
79 * number of random spanning trees used to set the scale parameters.
80 * \param fg Factor graph.
81 * \param opts Parameters @see BP::Properties.
82 */
83 TRWBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _weight() {
84 setProperties( opts );
85 construct();
86 }
87 //@}
88
89 /// \name General InfAlg interface
90 //@{
91 virtual TRWBP* clone() const { return new TRWBP(*this); }
92 virtual std::string identify() const;
93 virtual Real logZ() const;
94 virtual void setProperties( const PropertySet &opts );
95 virtual PropertySet getProperties() const;
96 virtual std::string printProperties() const;
97 //@}
98
99 /// \name TRWBP accessors/mutators for scale parameters
100 //@{
101 /// Returns weight corresponding to the \a I 'th factor
102 Real Weight( size_t I ) const { return _weight[I]; }
103
104 /// Returns constant reference to vector of all weights
105 const std::vector<Real>& Weights() const { return _weight; }
106
107 /// Sets the weight of the \a I 'th factor to \a c
108 void setWeight( size_t I, Real c ) { _weight[I] = c; }
109
110 /// Sets the weights of all factors simultaenously
111 /** \note Faster than calling setWeight(size_t,Real) for each factor
112 */
113 void setWeights( const std::vector<Real> &c ) { _weight = c; }
114
115 /// Increases weights corresponding to pairwise factors in \a tree with 1
116 void addTreeToWeights( const RootedTree &tree );
117
118 /// Samples weights from a sample of \a nrTrees random spanning trees
119 void sampleWeights( size_t nrTrees );
120
121 protected:
122 /// Calculate the product of factor \a I and the incoming messages
123 /** If \a without_i == \c true, the message coming from variable \a i is omitted from the product
124 * \note This function is used by calcNewMessage() and calcBeliefF()
125 */
126 virtual Prob calcIncomingMessageProduct( size_t I, bool without_i, size_t i ) const;
127
128 /// Calculates unnormalized belief of variable \a i
129 virtual void calcBeliefV( size_t i, Prob &p ) const;
130
131 // Calculates unnormalized belief of factor \a I
132 virtual void calcBeliefF( size_t I, Prob &p ) const {
133 p = calcIncomingMessageProduct( I, false, 0 );
134 }
135
136 // Helper function for constructors
137 virtual void construct();
138 };
139
140
141 } // end of namespace dai
142
143
144 #endif