[Frederik Eaton] Added Fractional Belief Propagation
[libdai.git] / include / dai / fbp.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) 2009 Frederik Eaton
8 */
9
10
11 /// \file
12 /// \brief Defines class FBP, which implements Fractional Belief Propagation
13
14
15 #ifndef __defined_libdai_fbp_h
16 #define __defined_libdai_fbp_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 "Fractional Belief Propagation" [\ref WiH03]
31 /** The Fractional Belief Propagation algorithm is like Belief
32 * Propagation, but associates each factor with a scale parameter
33 * which controls the divergence measure being minimized. Standard
34 * Belief Propagation corresponds to the case of FBP where each scale
35 * parameter is 1. When cast as an EP algorithm, BP (and EP) minimize
36 * the inclusive KL-divergence, i.e. \f$\min_q KL(p||q)\f$ (note that the
37 * Bethe free energy is typically derived from \f$ KL(q||p) \f$). If each
38 * factor \a I has scale parameter \f$ c_I \f$, then FBP minimizes the
39 * alpha-divergence with \f$ \alpha=1/c_I \f$ for that factor, which also
40 * corresponds to Power EP [\ref Min05].
41 *
42 * The messages \f$m_{I\to i}(x_i)\f$ are passed from factors \f$I\f$ to variables \f$i\f$.
43 * The update equation is given by:
44 * \f[ m_{I\to i}(x_i) \propto \left( \sum_{x_{N_I\setminus\{i\}}} f_I(x_I)^{1/c_I} \prod_{j\in N_I\setminus\{i\}} m_{I\to j}^{1-1/c_I}\right)^{c_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j} \f]
45 * After convergence, the variable beliefs are calculated by:
46 * \f[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i} \f]
47 * and the factor beliefs are calculated by:
48 * \f[ b_I(x_I) \propto f_I(x_I)^{1/c_I} \prod_{j \in N_I} m_{I\to j}^{1-1/c_I} \prod_{J\in N_j\setminus\{I\}} m_{J\to j} \f]
49 *
50 * \todo Implement logZ
51 * \todo Why are the _scale_var necessary?
52 * \todo Add nice way to set scale parameters
53 *
54 * \author Frederik Eaton
55 */
56 class FBP : public BP {
57 protected:
58 /// Factor scale parameters (indexed by factor ID)
59 std::vector<Real> _scale_factor;
60 /// Variable scale parameters (indexed by variable ID)
61 /** \note Equal to sum of scale parameters of neighboring factors
62 */
63 std::vector<Real> _scale_var;
64
65 public:
66 /// Name of this inference algorithm
67 static const char *Name;
68
69 public:
70 /// \name Constructors/destructors
71 //@{
72 /// Default constructor
73 FBP() : BP(), _scale_factor(), _scale_var() {}
74
75 /// Construct from FactorGraph \a fg and PropertySet \a opts
76 /** \param opts Parameters @see BP::Properties
77 */
78 FBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _scale_factor(), _scale_var() {
79 setProperties( opts );
80 construct();
81 }
82 //@}
83
84 /// \name General InfAlg interface
85 //@{
86 virtual FBP* clone() const { return new FBP(*this); }
87 virtual std::string identify() const;
88 //@}
89
90 /// \name FBP accessors/mutators for scale parameters
91 //@{
92 /// Returns scale parameter of the \a I 'th factor
93 Real scaleF( size_t I ) const { return _scale_factor[I]; }
94
95 /// Returns constant reference to vector of all factor scale parameters
96 const std::vector<Real>& scaleFs() const { return _scale_factor; }
97
98 /// Returns scale parameter of the \a i 'th variable
99 Real scaleV( size_t i ) const { return _scale_var[i]; }
100
101 /// Returns constant reference to vector of all variable scale parameters
102 const std::vector<Real>& scaleVs() const { return _scale_var; }
103
104 /// Sets the scale parameter of the \a I 'th factor to \a c
105 void setScaleF( size_t I, Real c ) {
106 _scale_factor[I] = c;
107 foreach( const Neighbor &i, nbF(I) )
108 recalcScaleV(i);
109 }
110
111 /// Sets the scale parameters of all factors simultaenously
112 /** \note Faster than calling setScaleF(size_t,Real) for each factor
113 */
114 void setScaleFs( const std::vector<Real> &c ) {
115 _scale_factor = c;
116 recalcScaleVs();
117 }
118
119 /// Recalculates all variable scale parameters
120 /** \note For each variable, its scale parameter is set to
121 * the sum of the scale parameters of its neighboring factors.
122 */
123 void recalcScaleVs() {
124 for( size_t i = 0; i < nrVars(); i++ )
125 recalcScaleV(i);
126 }
127
128 /// Recalculates the scale parameter of the \a i 'th variable
129 /** \note The scale parameter is set to the sum of the scale parameters of its neighboring factors.
130 */
131 void recalcScaleV( size_t i ) {
132 // Set _scale_var[i] to the sum of its neighbors
133 Real c_i = 0.0;
134 foreach( const Neighbor &I, nbV(i) )
135 c_i += scaleF(I);
136 _scale_var[i] = c_i;
137 }
138
139 protected:
140 // Calculate the updated message from the \a _I 'th neighbor of variable \a i to variable \a i
141 virtual void calcNewMessage( size_t i, size_t _I );
142
143 // Calculates unnormalized belief of factor \a I
144 virtual void calcBeliefF( size_t I, Prob &p ) const;
145
146 // Helper function for constructors
147 virtual void construct();
148
149 /// (Re)constructs the scale parameters data structures
150 void constructScaleParams() {
151 _scale_factor.resize( nrFactors(), 1.0 );
152 _scale_var.resize( nrVars() );
153 recalcScaleVs();
154 }
155 };
156
157
158 } // end of namespace dai
159
160
161 #endif