Fixed regression in scripts/regenerate-properties
[libdai.git] / src / mf.cpp
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 #include <iostream>
13 #include <sstream>
14 #include <map>
15 #include <set>
16 #include <dai/mf.h>
17 #include <dai/util.h>
18
19
20 namespace dai {
21
22
23 using namespace std;
24
25
26 const char *MF::Name = "MF";
27
28
29 void MF::setProperties( const PropertySet &opts ) {
30 DAI_ASSERT( opts.hasKey("tol") );
31 DAI_ASSERT( opts.hasKey("maxiter") );
32
33 props.tol = opts.getStringAs<Real>("tol");
34 props.maxiter = opts.getStringAs<size_t>("maxiter");
35 if( opts.hasKey("verbose") )
36 props.verbose = opts.getStringAs<size_t>("verbose");
37 else
38 props.verbose = 0U;
39 if( opts.hasKey("damping") )
40 props.damping = opts.getStringAs<Real>("damping");
41 else
42 props.damping = 0.0;
43 }
44
45
46 PropertySet MF::getProperties() const {
47 PropertySet opts;
48 opts.Set( "tol", props.tol );
49 opts.Set( "maxiter", props.maxiter );
50 opts.Set( "verbose", props.verbose );
51 opts.Set( "damping", props.damping );
52 return opts;
53 }
54
55
56 string MF::printProperties() const {
57 stringstream s( stringstream::out );
58 s << "[";
59 s << "tol=" << props.tol << ",";
60 s << "maxiter=" << props.maxiter << ",";
61 s << "verbose=" << props.verbose << ",";
62 s << "damping=" << props.damping << "]";
63 return s.str();
64 }
65
66
67 void MF::construct() {
68 // create beliefs
69 _beliefs.clear();
70 _beliefs.reserve( nrVars() );
71 for( size_t i = 0; i < nrVars(); ++i )
72 _beliefs.push_back( Factor( var(i) ) );
73 }
74
75
76 string MF::identify() const {
77 return string(Name) + printProperties();
78 }
79
80
81 void MF::init() {
82 for( vector<Factor>::iterator qi = _beliefs.begin(); qi != _beliefs.end(); qi++ )
83 qi->fill(1.0);
84 }
85
86
87 Factor MF::calcNewBelief( size_t i ) {
88 Factor result;
89 foreach( const Neighbor &I, nbV(i) ) {
90 Factor henk;
91 foreach( const Neighbor &j, nbF(I) ) // for all j in I \ i
92 if( j != i )
93 henk *= _beliefs[j];
94 Factor piet = factor(I).log(true);
95 piet *= henk;
96 piet = piet.marginal(var(i), false);
97 piet = piet.exp();
98 result *= piet;
99 }
100 result.normalize();
101 return result;
102 }
103
104
105 Real MF::run() {
106 if( props.verbose >= 1 )
107 cerr << "Starting " << identify() << "...";
108
109 double tic = toc();
110 vector<Real> diffs( nrVars(), INFINITY );
111 Real maxDiff = INFINITY;
112
113 vector<size_t> update_seq;
114 update_seq.reserve( nrVars() );
115 for( size_t i = 0; i < nrVars(); i++ )
116 update_seq.push_back( i );
117
118 // do several passes over the network until maximum number of iterations has
119 // been reached or until the maximum belief difference is smaller than tolerance
120 for( _iters = 0; _iters < props.maxiter && maxDiff > props.tol; _iters++ ) {
121 random_shuffle( update_seq.begin(), update_seq.end() );
122
123 foreach( const size_t &i, update_seq ) {
124 Factor nb = calcNewBelief( i );
125
126 if( nb.hasNaNs() ) {
127 cerr << Name << "::run(): ERROR: new belief of variable " << var(i) << " has NaNs!" << endl;
128 return 1.0;
129 }
130
131 if( props.damping != 0.0 )
132 nb = (nb^(1.0 - props.damping)) * (_beliefs[i]^props.damping);
133 diffs[i] = dist( nb, _beliefs[i], Prob::DISTLINF );
134
135 _beliefs[i] = nb;
136 }
137 maxDiff = max( diffs );
138
139 if( props.verbose >= 3 )
140 cerr << Name << "::run: maxdiff " << maxDiff << " after " << _iters+1 << " passes" << endl;
141 }
142
143 if( maxDiff > _maxdiff )
144 _maxdiff = maxDiff;
145
146 if( props.verbose >= 1 ) {
147 if( maxDiff > props.tol ) {
148 if( props.verbose == 1 )
149 cerr << endl;
150 cerr << Name << "::run: WARNING: not converged within " << props.maxiter << " passes (" << toc() - tic << " seconds)...final maxdiff:" << maxDiff << endl;
151 } else {
152 if( props.verbose >= 3 )
153 cerr << Name << "::run: ";
154 cerr << "converged in " << _iters << " passes (" << toc() - tic << " seconds)." << endl;
155 }
156 }
157
158 return maxDiff;
159 }
160
161
162 Factor MF::beliefV( size_t i ) const {
163 Factor piet;
164 piet = _beliefs[i];
165 piet.normalize();
166 return(piet);
167 }
168
169
170 Factor MF::belief (const VarSet &ns) const {
171 if( ns.size() == 1 )
172 return belief( *(ns.begin()) );
173 else {
174 DAI_ASSERT( ns.size() == 1 );
175 return Factor();
176 }
177 }
178
179
180 Factor MF::belief (const Var &n) const {
181 return( beliefV( findVar( n ) ) );
182 }
183
184
185 vector<Factor> MF::beliefs() const {
186 vector<Factor> result;
187 for( size_t i = 0; i < nrVars(); i++ )
188 result.push_back( beliefV(i) );
189 return result;
190 }
191
192
193 Real MF::logZ() const {
194 Real s = 0.0;
195
196 for(size_t i=0; i < nrVars(); i++ )
197 s -= beliefV(i).entropy();
198 for(size_t I=0; I < nrFactors(); I++ ) {
199 Factor henk;
200 foreach( const Neighbor &j, nbF(I) ) // for all j in I
201 henk *= _beliefs[j];
202 henk.normalize();
203 Factor piet;
204 piet = factor(I).log(true);
205 piet *= henk;
206 s -= piet.sum();
207 }
208
209 return -s;
210 }
211
212
213 void MF::init( const VarSet &ns ) {
214 for( size_t i = 0; i < nrVars(); i++ ) {
215 if( ns.contains(var(i) ) )
216 _beliefs[i].fill( 1.0 );
217 }
218 }
219
220
221 } // end of namespace dai