Rewrote implementation of response propagation in MR
[libdai.git] / include / dai / lc.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) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 /// \file
13 /// \brief Defines class LC, which implements loop corrections for approximate inference
14
15
16 #ifndef __defined_libdai_lc_h
17 #define __defined_libdai_lc_h
18
19
20 #include <string>
21 #include <dai/daialg.h>
22 #include <dai/enum.h>
23 #include <dai/factorgraph.h>
24 #include <dai/properties.h>
25 #include <dai/exceptions.h>
26
27
28 namespace dai {
29
30
31 /// Approximate inference algorithm "Loop Corrected Belief Propagation" [\ref MoK07]
32 class LC : public DAIAlgFG {
33 private:
34 /// Stores for each variable the approximate cavity distribution multiplied with the omitted factors
35 std::vector<Factor> _pancakes;
36 /// Stores for each variable the approximate cavity distribution
37 std::vector<Factor> _cavitydists;
38 /// _phis[i][_I] corresponds to \f$ \phi^{\setminus i}_I(x_{I \setminus i}) \f$ in the paper
39 std::vector<std::vector<Factor> > _phis;
40 /// Single variable beliefs
41 std::vector<Factor> _beliefs;
42 /// Maximum difference encountered so far
43 Real _maxdiff;
44 /// Number of iterations needed
45 size_t _iters;
46
47 public:
48 /// Parameters for LC
49 struct Properties {
50 /// Enumeration of possible ways to initialize the cavities
51 /** The following initialization methods are defined:
52 * - FULL calculates the marginal using calcMarginal()
53 * - PAIR calculates only second order interactions using calcPairBeliefs() with \a accurate == \c false
54 * - PAIR2 calculates only second order interactions using calcPairBeliefs() with \a accurate == \c true
55 * - UNIFORM uses a uniform distribution
56 */
57 DAI_ENUM(CavityType,FULL,PAIR,PAIR2,UNIFORM);
58
59 /// Enumeration of different update schedules
60 /** The following update schedules are defined:
61 * - SEQFIX sequential fixed schedule
62 * - SEQRND sequential random schedule
63 */
64 DAI_ENUM(UpdateType,SEQFIX,SEQRND);
65
66 /// Verbosity (amount of output sent to stderr)
67 size_t verbose;
68
69 /// Maximum number of iterations
70 size_t maxiter;
71
72 /// Tolerance for convergence test
73 Real tol;
74
75 /// Complete or partial reinitialization of cavity graphs?
76 bool reinit;
77
78 /// Damping constant (0.0 means no damping, 1.0 is maximum damping)
79 Real damping;
80
81 /// How to initialize the cavities
82 CavityType cavity;
83
84 /// What update schedule to use
85 UpdateType updates;
86
87 /// Name of the algorithm used to initialize the cavity distributions
88 std::string cavainame;
89
90 /// Parameters for the algorithm used to initialize the cavity distributions
91 PropertySet cavaiopts;
92 } props;
93
94 /// Name of this inference algorithm
95 static const char *Name;
96
97 public:
98 /// Default constructor
99 LC() : DAIAlgFG(), _pancakes(), _cavitydists(), _phis(), _beliefs(), _maxdiff(), _iters(), props() {}
100
101 /// Construct from FactorGraph \a fg and PropertySet \a opts
102 /** \param opts Parameters @see Properties
103 */
104 LC( const FactorGraph &fg, const PropertySet &opts );
105
106
107 /// \name General InfAlg interface
108 //@{
109 virtual LC* clone() const { return new LC(*this); }
110 virtual std::string identify() const;
111 virtual Factor belief( const Var &v ) const { return beliefV( findVar( v ) ); }
112 virtual Factor belief( const VarSet &/*vs*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
113 virtual Factor beliefV( size_t i ) const { return _beliefs[i]; }
114 virtual std::vector<Factor> beliefs() const { return _beliefs; }
115 virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
116 virtual void init();
117 virtual void init( const VarSet &/*ns*/ ) { init(); }
118 virtual Real run();
119 virtual Real maxDiff() const { return _maxdiff; }
120 virtual size_t Iterations() const { return _iters; }
121 virtual void setProperties( const PropertySet &opts );
122 virtual PropertySet getProperties() const;
123 virtual std::string printProperties() const;
124 //@}
125
126 /// \name Additional interface specific for LC
127 //@{
128 /// Approximates the cavity distribution of variable \a i, using the inference algorithm \a name with parameters \a opts
129 Real CalcCavityDist( size_t i, const std::string &name, const PropertySet &opts );
130 /// Approximates all cavity distributions using inference algorithm \a name with parameters \a opts
131 Real InitCavityDists( const std::string &name, const PropertySet &opts );
132 /// Sets approximate cavity distributions to \a Q
133 long SetCavityDists( std::vector<Factor> &Q );
134 /// Updates the belief of the Markov blanket of variable \a i based upon the information from its \a _I 'th neighboring factor
135 Factor NewPancake (size_t i, size_t _I, bool & hasNaNs);
136 /// Calculates the belief of variable \a i
137 void CalcBelief (size_t i);
138 /// Returns the belief of the Markov blanket of variable \a i (including the variable itself)
139 const Factor &pancake (size_t i) const { return _pancakes[i]; };
140 /// Returns the approximate cavity distribution for variable \a i
141 const Factor &cavitydist (size_t i) const { return _cavitydists[i]; };
142 //@}
143 };
144
145
146 } // end of namespace dai
147
148
149 #endif