Implementing TRWBP
[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
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 *
43 * \todo Fix documentation
44 */
45 class TRWBP : public BP {
46 protected:
47 /// Factor scale parameters (indexed by factor ID)
48 std::vector<Real> _edge_weight;
49
50 public:
51 /// Name of this inference algorithm
52 static const char *Name;
53
54 public:
55 /// \name Constructors/destructors
56 //@{
57 /// Default constructor
58 TRWBP() : BP(), _edge_weight() {}
59
60 /// Construct from FactorGraph \a fg and PropertySet \a opts
61 /** \param opts Parameters @see BP::Properties
62 */
63 TRWBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _edge_weight() {
64 setProperties( opts );
65 construct();
66 }
67 //@}
68
69 /// \name General InfAlg interface
70 //@{
71 virtual TRWBP* clone() const { return new TRWBP(*this); }
72 virtual std::string identify() const;
73 virtual Real logZ() const;
74 //@}
75
76 /// \name TRWBP accessors/mutators for scale parameters
77 //@{
78 /// Returns scale parameter of edge corresponding to the \a I 'th factor
79 Real edgeWeight( size_t I ) const { return _edge_weight[I]; }
80
81 /// Returns constant reference to vector of all factor scale parameters
82 const std::vector<Real>& edgeWeights() const { return _edge_weight; }
83
84 /// Sets the scale parameter of the \a I 'th factor to \a c
85 void setEdgeWeight( size_t I, Real c ) { _edge_weight[I] = c; }
86
87 /// Sets the scale parameters of all factors simultaenously
88 /** \note Faster than calling setScaleF(size_t,Real) for each factor
89 */
90 void setEdgeWeights( const std::vector<Real> &c ) { _edge_weight = c; }
91
92 protected:
93 // Calculate the updated message from the \a _I 'th neighbor of variable \a i to variable \a i
94 virtual void calcNewMessage( size_t i, size_t _I );
95
96 /// Calculates unnormalized belief of variable \a i
97 virtual void calcBeliefV( size_t i, Prob &p ) const;
98
99 // Calculates unnormalized belief of factor \a I
100 virtual void calcBeliefF( size_t I, Prob &p ) const;
101
102 // Helper function for constructors
103 virtual void construct();
104 };
105
106
107 } // end of namespace dai
108
109
110 #endif