Fixed typo in doxygen FBP update equation, and removed FBP::_scale_var stuff
[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} \prod_{J\in N_j\setminus\{I\}} m_{J\to j} \right)^{c_I} \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 Add nice way to set scale parameters
52 *
53 * \author Frederik Eaton
54 */
55 class FBP : public BP {
56 protected:
57 /// Factor scale parameters (indexed by factor ID)
58 std::vector<Real> _scale_factor;
59
60 public:
61 /// Name of this inference algorithm
62 static const char *Name;
63
64 public:
65 /// \name Constructors/destructors
66 //@{
67 /// Default constructor
68 FBP() : BP(), _scale_factor() {}
69
70 /// Construct from FactorGraph \a fg and PropertySet \a opts
71 /** \param opts Parameters @see BP::Properties
72 */
73 FBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _scale_factor() {
74 setProperties( opts );
75 construct();
76 }
77 //@}
78
79 /// \name General InfAlg interface
80 //@{
81 virtual FBP* clone() const { return new FBP(*this); }
82 virtual std::string identify() const;
83 //@}
84
85 /// \name FBP accessors/mutators for scale parameters
86 //@{
87 /// Returns scale parameter of the \a I 'th factor
88 Real scaleF( size_t I ) const { return _scale_factor[I]; }
89
90 /// Returns constant reference to vector of all factor scale parameters
91 const std::vector<Real>& scaleFs() const { return _scale_factor; }
92
93 /// Sets the scale parameter of the \a I 'th factor to \a c
94 void setScaleF( size_t I, Real c ) { _scale_factor[I] = c; }
95
96 /// Sets the scale parameters of all factors simultaenously
97 /** \note Faster than calling setScaleF(size_t,Real) for each factor
98 */
99 void setScaleFs( const std::vector<Real> &c ) { _scale_factor = c; }
100
101 protected:
102 // Calculate the updated message from the \a _I 'th neighbor of variable \a i to variable \a i
103 virtual void calcNewMessage( size_t i, size_t _I );
104
105 // Calculates unnormalized belief of factor \a I
106 virtual void calcBeliefF( size_t I, Prob &p ) const;
107
108 // Helper function for constructors
109 virtual void construct();
110 };
111
112
113 } // end of namespace dai
114
115
116 #endif