1 /* This file is part of libDAI - http://www.libdai.org/
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
9 #include <dai/dai_config.h>
27 void MF::setProperties( const PropertySet
&opts
) {
28 DAI_ASSERT( opts
.hasKey("tol") );
29 DAI_ASSERT( opts
.hasKey("maxiter") );
31 props
.tol
= opts
.getStringAs
<Real
>("tol");
32 props
.maxiter
= opts
.getStringAs
<size_t>("maxiter");
33 if( opts
.hasKey("verbose") )
34 props
.verbose
= opts
.getStringAs
<size_t>("verbose");
37 if( opts
.hasKey("damping") )
38 props
.damping
= opts
.getStringAs
<Real
>("damping");
41 if( opts
.hasKey("init") )
42 props
.init
= opts
.getStringAs
<Properties::InitType
>("init");
44 props
.init
= Properties::InitType::UNIFORM
;
45 if( opts
.hasKey("updates") )
46 props
.updates
= opts
.getStringAs
<Properties::UpdateType
>("updates");
48 props
.updates
= Properties::UpdateType::NAIVE
;
52 PropertySet
MF::getProperties() const {
54 opts
.set( "tol", props
.tol
);
55 opts
.set( "maxiter", props
.maxiter
);
56 opts
.set( "verbose", props
.verbose
);
57 opts
.set( "damping", props
.damping
);
58 opts
.set( "init", props
.init
);
59 opts
.set( "updates", props
.updates
);
64 string
MF::printProperties() const {
65 stringstream
s( stringstream::out
);
67 s
<< "tol=" << props
.tol
<< ",";
68 s
<< "maxiter=" << props
.maxiter
<< ",";
69 s
<< "verbose=" << props
.verbose
<< ",";
70 s
<< "init=" << props
.init
<< ",";
71 s
<< "updates=" << props
.updates
<< ",";
72 s
<< "damping=" << props
.damping
<< "]";
77 void MF::construct() {
80 _beliefs
.reserve( nrVars() );
81 for( size_t i
= 0; i
< nrVars(); ++i
)
82 _beliefs
.push_back( Factor( var(i
) ) );
87 if( props
.init
== Properties::InitType::UNIFORM
)
88 for( size_t i
= 0; i
< nrVars(); i
++ )
89 _beliefs
[i
].fill( 1.0 );
91 for( size_t i
= 0; i
< nrVars(); i
++ )
92 _beliefs
[i
].randomize();
96 Factor
MF::calcNewBelief( size_t i
) {
98 bforeach( const Neighbor
&I
, nbV(i
) ) {
99 Factor belief_I_minus_i
;
100 bforeach( const Neighbor
&j
, nbF(I
) ) // for all j in I \ i
102 belief_I_minus_i
*= _beliefs
[j
];
103 Factor f_I
= factor(I
);
104 if( props
.updates
== Properties::UpdateType::NAIVE
)
106 Factor msg_I_i
= (belief_I_minus_i
* f_I
).marginal( var(i
), false );
107 if( props
.updates
== Properties::UpdateType::NAIVE
)
108 result
*= msg_I_i
.exp();
118 if( props
.verbose
>= 1 )
119 cerr
<< "Starting " << identify() << "...";
123 vector
<size_t> update_seq
;
124 update_seq
.reserve( nrVars() );
125 for( size_t i
= 0; i
< nrVars(); i
++ )
126 update_seq
.push_back( i
);
128 // do several passes over the network until maximum number of iterations has
129 // been reached or until the maximum belief difference is smaller than tolerance
130 Real maxDiff
= INFINITY
;
131 for( _iters
= 0; _iters
< props
.maxiter
&& maxDiff
> props
.tol
; _iters
++ ) {
132 random_shuffle( update_seq
.begin(), update_seq
.end(), rnd
);
135 bforeach( const size_t &i
, update_seq
) {
136 Factor nb
= calcNewBelief( i
);
139 cerr
<< name() << "::run(): ERROR: new belief of variable " << var(i
) << " has NaNs!" << endl
;
143 if( props
.damping
!= 0.0 )
144 nb
= (nb
^(1.0 - props
.damping
)) * (_beliefs
[i
]^props
.damping
);
146 maxDiff
= std::max( maxDiff
, dist( nb
, _beliefs
[i
], DISTLINF
) );
150 if( props
.verbose
>= 3 )
151 cerr
<< name() << "::run: maxdiff " << maxDiff
<< " after " << _iters
+1 << " passes" << endl
;
154 if( maxDiff
> _maxdiff
)
157 if( props
.verbose
>= 1 ) {
158 if( maxDiff
> props
.tol
) {
159 if( props
.verbose
== 1 )
161 cerr
<< name() << "::run: WARNING: not converged within " << props
.maxiter
<< " passes (" << toc() - tic
<< " seconds)...final maxdiff:" << maxDiff
<< endl
;
163 if( props
.verbose
>= 3 )
164 cerr
<< name() << "::run: ";
165 cerr
<< "converged in " << _iters
<< " passes (" << toc() - tic
<< " seconds)." << endl
;
173 Factor
MF::beliefV( size_t i
) const {
174 return _beliefs
[i
].normalized();
178 Factor
MF::belief (const VarSet
&ns
) const {
181 else if( ns
.size() == 1 )
182 return beliefV( findVar( *(ns
.begin()) ) );
184 DAI_THROW(BELIEF_NOT_AVAILABLE
);
190 vector
<Factor
> MF::beliefs() const {
191 vector
<Factor
> result
;
192 for( size_t i
= 0; i
< nrVars(); i
++ )
193 result
.push_back( beliefV(i
) );
198 Real
MF::logZ() const {
201 for( size_t i
= 0; i
< nrVars(); i
++ )
202 s
-= beliefV(i
).entropy();
203 for( size_t I
= 0; I
< nrFactors(); I
++ ) {
205 bforeach( const Neighbor
&j
, nbF(I
) ) // for all j in I
209 piet
= factor(I
).log(true);
218 void MF::init( const VarSet
&ns
) {
219 for( size_t i
= 0; i
< nrVars(); i
++ )
220 if( ns
.contains(var(i
) ) ) {
221 if( props
.init
== Properties::InitType::UNIFORM
)
222 _beliefs
[i
].fill( 1.0 );
224 _beliefs
[i
].randomize();
229 } // end of namespace dai