1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
4 This file is part of libDAI.
6 libDAI is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 libDAI is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with libDAI; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 #include <dai/diffs.h>
37 const char *MF::Name
= "MF";
40 void MF::setProperties( const PropertySet
&opts
) {
41 assert( opts
.hasKey("tol") );
42 assert( opts
.hasKey("maxiter") );
44 props
.tol
= opts
.getStringAs
<double>("tol");
45 props
.maxiter
= opts
.getStringAs
<size_t>("maxiter");
46 if( opts
.hasKey("verbose") )
47 props
.verbose
= opts
.getStringAs
<size_t>("verbose");
50 if( opts
.hasKey("damping") )
51 props
.damping
= opts
.getStringAs
<double>("damping");
57 PropertySet
MF::getProperties() const {
59 opts
.Set( "tol", props
.tol
);
60 opts
.Set( "maxiter", props
.maxiter
);
61 opts
.Set( "verbose", props
.verbose
);
62 opts
.Set( "damping", props
.damping
);
67 string
MF::printProperties() const {
68 stringstream
s( stringstream::out
);
70 s
<< "tol=" << props
.tol
<< ",";
71 s
<< "maxiter=" << props
.maxiter
<< ",";
72 s
<< "verbose=" << props
.verbose
<< ",";
73 s
<< "damping=" << props
.damping
<< "]";
78 void MF::construct() {
81 _beliefs
.reserve( nrVars() );
82 for( size_t i
= 0; i
< nrVars(); ++i
)
83 _beliefs
.push_back( Factor( var(i
) ) );
87 string
MF::identify() const {
88 return string(Name
) + printProperties();
93 for( vector
<Factor
>::iterator qi
= _beliefs
.begin(); qi
!= _beliefs
.end(); qi
++ )
101 if( props
.verbose
>= 1 )
102 cout
<< "Starting " << identify() << "...";
104 size_t pass_size
= _beliefs
.size();
105 Diffs
diffs(pass_size
* 3, 1.0);
108 for( t
=0; t
< (props
.maxiter
*pass_size
) && diffs
.maxDiff() > props
.tol
; t
++ ) {
109 // choose random Var i
110 size_t i
= (size_t) (nrVars() * rnd_uniform());
114 foreach( const Neighbor
&I
, nbV(i
) ) {
116 foreach( const Neighbor
&j
, nbF(I
) ) // for all j in I \ i
119 piet
= factor(I
).log0();
121 piet
= piet
.partSum(var(i
));
128 if( jan
.hasNaNs() ) {
129 cout
<< Name
<< "::run(): ERROR: jan has NaNs!" << endl
;
133 if( props
.damping
!= 0.0 )
134 jan
= (jan
^(1.0 - props
.damping
)) * (_beliefs
[i
]^props
.damping
);
135 diffs
.push( dist( jan
, _beliefs
[i
], Prob::DISTLINF
) );
140 _iters
= t
/ pass_size
;
141 if( diffs
.maxDiff() > _maxdiff
)
142 _maxdiff
= diffs
.maxDiff();
144 if( props
.verbose
>= 1 ) {
145 if( diffs
.maxDiff() > props
.tol
) {
146 if( props
.verbose
== 1 )
148 cout
<< Name
<< "::run: WARNING: not converged within " << props
.maxiter
<< " passes (" << toc() - tic
<< " seconds)...final maxdiff:" << diffs
.maxDiff() << endl
;
150 if( props
.verbose
>= 2 )
151 cout
<< Name
<< "::run: ";
152 cout
<< "converged in " << t
/ pass_size
<< " passes (" << toc() - tic
<< " seconds)." << endl
;
156 return diffs
.maxDiff();
160 Factor
MF::beliefV( size_t i
) const {
168 Factor
MF::belief (const VarSet
&ns
) const {
170 return belief( *(ns
.begin()) );
172 assert( ns
.size() == 1 );
178 Factor
MF::belief (const Var
&n
) const {
179 return( beliefV( findVar( n
) ) );
183 vector
<Factor
> MF::beliefs() const {
184 vector
<Factor
> result
;
185 for( size_t i
= 0; i
< nrVars(); i
++ )
186 result
.push_back( beliefV(i
) );
191 Real
MF::logZ() const {
194 for(size_t i
=0; i
< nrVars(); i
++ )
195 sum
-= beliefV(i
).entropy();
196 for(size_t I
=0; I
< nrFactors(); I
++ ) {
198 foreach( const Neighbor
&j
, nbF(I
) ) // for all j in I
202 piet
= factor(I
).log0();
204 sum
-= piet
.totalSum();
211 void MF::init( const VarSet
&ns
) {
212 for( size_t i
= 0; i
< nrVars(); i
++ ) {
213 if( ns
.contains(var(i
) ) )
214 _beliefs
[i
].fill( 1.0 );
219 } // end of namespace dai