47ef3eae110f1441951376a615ddecfe5632eaee
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
9 /// \file
10 /// \brief Defines class MF which implements the Mean Field algorithm
13 #ifndef __defined_libdai_mf_h
14 #define __defined_libdai_mf_h
17 #include <string>
18 #include <dai/enum.h>
19 #include <dai/daialg.h>
20 #include <dai/factorgraph.h>
21 #include <dai/properties.h>
24 namespace dai {
27 /// Approximate inference algorithm "Mean Field"
28 /** The Mean Field algorithm iteratively calculates approximations of
29 * single variable marginals (beliefs). The update equation for
30 * a single belief \f$b_i\f$ is given by:
31 * \f[ b_i^{\mathrm{new}}(x_i) \propto \prod_{I\in N_i} \exp \left( \sum_{x_{N_I \setminus \{i\}}} \log f_I(x_I) \prod_{j \in N_I \setminus \{i\}} b_j(x_j) \right) \f]
32 * for naive mean field and by
33 * \f[ b_i^{\mathrm{new}}(x_i) \propto \prod_{I\in N_i} \left( \sum_{x_{N_I \setminus \{i\}}} f_I(x_I) \prod_{j \in N_I \setminus \{i\}} b_j(x_j) \right) \f]
34 * for hard-spin mean field.
35 * These update equations are performed for all variables until convergence.
36 */
37 class MF : public DAIAlgFG {
38 private:
39 /// Current approximations of single variable marginals
40 std::vector<Factor> _beliefs;
41 /// Maximum difference encountered so far
42 Real _maxdiff;
43 /// Number of iterations needed
44 size_t _iters;
46 public:
47 /// Parameters for MF
48 struct Properties {
49 /// Enumeration of possible message initializations
50 DAI_ENUM(InitType,UNIFORM,RANDOM);
52 /// Enumeration of possible update types
53 DAI_ENUM(UpdateType,NAIVE,HARDSPIN);
55 /// Verbosity (amount of output sent to stderr)
56 size_t verbose;
58 /// Maximum number of iterations
59 size_t maxiter;
61 /// Tolerance for convergence test
62 Real tol;
64 /// Damping constant (0.0 means no damping, 1.0 is maximum damping)
65 Real damping;
67 /// How to initialize the messages/beliefs
68 InitType init;
70 /// How to update the messages/beliefs
72 } props;
74 public:
75 /// \name Constructors/destructors
76 //@{
77 /// Default constructor
78 MF() : DAIAlgFG(), _beliefs(), _maxdiff(0.0), _iters(0U), props() {}
80 /// Construct from FactorGraph \a fg and PropertySet \a opts
81 /** \param fg Factor graph.
82 * \param opts Parameters @see Properties
83 */
84 MF( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), _beliefs(), _maxdiff(0.0), _iters(0U), props() {
85 setProperties( opts );
86 construct();
87 }
88 //@}
90 /// \name General InfAlg interface
91 //@{
92 virtual MF* clone() const { return new MF(*this); }
93 virtual MF* construct( const FactorGraph &fg, const PropertySet &opts ) const { return new MF( fg, opts ); }
94 virtual std::string name() const { return "MF"; }
95 virtual Factor belief( const Var &v ) const { return beliefV( findVar( v ) ); }
96 virtual Factor belief( const VarSet &vs ) const;
97 virtual Factor beliefV( size_t i ) const;
98 virtual std::vector<Factor> beliefs() const;
99 virtual Real logZ() const;
100 virtual void init();
101 virtual void init( const VarSet &ns );
102 virtual Real run();
103 virtual Real maxDiff() const { return _maxdiff; }
104 virtual size_t Iterations() const { return _iters; }
105 virtual void setMaxIter( size_t maxiter ) { props.maxiter = maxiter; }
106 virtual void setProperties( const PropertySet &opts );
107 virtual PropertySet getProperties() const;
108 virtual std::string printProperties() const;
109 //@}
111 private:
112 /// Helper function for constructors
113 void construct();
115 /// Calculates an updated belief of variable \a i
116 Factor calcNewBelief( size_t i );
117 };
120 } // end of namespace dai
123 #endif