Finished a new release: libDAI 0.2.7.
[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 [frederik at ofb dot net]
8 * Copyright (C) 2010 Joris Mooij [joris dot mooij at libdai dot org]
9 */
10
11
12 /// \file
13 /// \brief Defines class FBP, which implements Fractional Belief Propagation
14
15
16 #ifndef __defined_libdai_fbp_h
17 #define __defined_libdai_fbp_h
18
19
20 #include <string>
21 #include <dai/daialg.h>
22 #include <dai/factorgraph.h>
23 #include <dai/properties.h>
24 #include <dai/enum.h>
25 #include <dai/bp.h>
26
27
28 namespace dai {
29
30
31 /// Approximate inference algorithm "Fractional Belief Propagation" [\ref WiH03]
32 /** The Fractional Belief Propagation algorithm is like Belief
33 * Propagation, but associates each factor with a weight (scale parameter)
34 * which controls the divergence measure being minimized. Standard
35 * Belief Propagation corresponds to the case of FBP where each weight
36 * is 1. When cast as an EP algorithm, BP (and EP) minimize
37 * the inclusive KL-divergence, i.e. \f$\min_q KL(p||q)\f$ (note that the
38 * Bethe free energy is typically derived from \f$ KL(q||p) \f$). If each
39 * factor \a I has weight \f$ c_I \f$, then FBP minimizes the
40 * alpha-divergence with \f$ \alpha=1/c_I \f$ for that factor, which also
41 * corresponds to Power EP [\ref Min05].
42 *
43 * The messages \f$m_{I\to i}(x_i)\f$ are passed from factors \f$I\f$ to variables \f$i\f$.
44 * The update equation is given by:
45 * \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]
46 * After convergence, the variable beliefs are calculated by:
47 * \f[ b_i(x_i) \propto \prod_{I\in N_i} m_{I\to i} \f]
48 * and the factor beliefs are calculated by:
49 * \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]
50 * The logarithm of the partition sum is approximated by:
51 * \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]
52 * where the variable weights are defined as
53 * \f[ c_i := \sum_{I \in N_i} c_I \f]
54 *
55 * \todo Add nice way to set weights
56 * \author Frederik Eaton
57 */
58 class FBP : public BP {
59 protected:
60 /// Factor weights (indexed by factor ID)
61 std::vector<Real> _weight;
62
63 public:
64 /// Name of this inference algorithm
65 static const char *Name;
66
67 public:
68 /// \name Constructors/destructors
69 //@{
70 /// Default constructor
71 FBP() : BP(), _weight() {}
72
73 /// Construct from FactorGraph \a fg and PropertySet \a opts
74 /** \param fg Factor graph.
75 * \param opts Parameters @see BP::Properties
76 */
77 FBP( const FactorGraph &fg, const PropertySet &opts ) : BP(fg, opts), _weight() {
78 setProperties( opts );
79 construct();
80 }
81 //@}
82
83 /// \name General InfAlg interface
84 //@{
85 virtual FBP* clone() const { return new FBP(*this); }
86 virtual std::string identify() const;
87 virtual Real logZ() const;
88 //@}
89
90 /// \name FBP accessors/mutators for weights
91 //@{
92 /// Returns weight of the \a I 'th factor
93 Real Weight( size_t I ) const { return _weight[I]; }
94
95 /// Returns constant reference to vector of all factor weights
96 const std::vector<Real>& Weights() const { return _weight; }
97
98 /// Sets the weight of the \a I 'th factor to \a c
99 void setWeight( size_t I, Real c ) { _weight[I] = c; }
100
101 /// Sets the weights of all factors simultaenously
102 /** \note Faster than calling setWeight(size_t,Real) for each factor
103 */
104 void setWeights( const std::vector<Real> &c ) { _weight = c; }
105
106 protected:
107 /// Calculate the product of factor \a I and the incoming messages
108 /** If \a without_i == \c true, the message coming from variable \a i is omitted from the product
109 * \note This function is used by calcNewMessage() and calcBeliefF()
110 */
111 virtual Prob calcIncomingMessageProduct( size_t I, bool without_i, size_t i ) const;
112
113 // Calculate the updated message from the \a _I 'th neighbor of variable \a i to variable \a i
114 virtual void calcNewMessage( size_t i, size_t _I );
115
116 // Calculates unnormalized belief of factor \a I
117 virtual void calcBeliefF( size_t I, Prob &p ) const {
118 p = calcIncomingMessageProduct( I, false, 0 );
119 }
120
121 // Helper function for constructors
122 virtual void construct();
123 };
124
125
126 } // end of namespace dai
127
128
129 #endif