Multiple changes: changes in build system, one workaround and one bug fix
[libdai.git] / src / decmap.cpp
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
7
8
9 #include <dai/dai_config.h>
10 #ifdef DAI_WITH_DECMAP
11
12
13 #include <dai/alldai.h>
14
15
16 namespace dai {
17
18
19 using namespace std;
20
21
22 void DecMAP::setProperties( const PropertySet &opts ) {
23 DAI_ASSERT( opts.hasKey("ianame") );
24 DAI_ASSERT( opts.hasKey("iaopts") );
25
26 props.ianame = opts.getStringAs<string>("ianame");
27 props.iaopts = opts.getStringAs<PropertySet>("iaopts");
28 if( opts.hasKey("verbose") )
29 props.verbose = opts.getStringAs<size_t>("verbose");
30 else
31 props.verbose = 0;
32 if( opts.hasKey("reinit") )
33 props.reinit = opts.getStringAs<bool>("reinit");
34 else
35 props.reinit = true;
36 }
37
38
39 PropertySet DecMAP::getProperties() const {
40 PropertySet opts;
41 opts.set( "verbose", props.verbose );
42 opts.set( "reinit", props.reinit );
43 opts.set( "ianame", props.ianame );
44 opts.set( "iaopts", props.iaopts );
45 return opts;
46 }
47
48
49 string DecMAP::printProperties() const {
50 stringstream s( stringstream::out );
51 s << "[";
52 s << "verbose=" << props.verbose << ",";
53 s << "reinit=" << props.reinit << ",";
54 s << "ianame=" << props.ianame << ",";
55 s << "iaopts=" << props.iaopts << "]";
56 return s.str();
57 }
58
59
60 DecMAP::DecMAP( const FactorGraph& fg, const PropertySet& opts ) : DAIAlgFG(fg), _state(), _logp(), _maxdiff(), _iters(), props() {
61 setProperties( opts );
62
63 _state = vector<size_t>( nrVars(), 0 );
64 _logp = -INFINITY;
65 }
66
67
68 Factor DecMAP::belief( const VarSet& vs ) const {
69 if( vs.size() == 0 )
70 return Factor();
71 else {
72 map<Var, size_t> state;
73 for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
74 state[*v] = _state[findVar(*v)];
75 return createFactorDelta( vs, calcLinearState( vs, state ) );
76 }
77 }
78
79
80 Factor DecMAP::beliefV( size_t i ) const {
81 return createFactorDelta( var(i), _state[i] );
82 }
83
84
85 vector<Factor> DecMAP::beliefs() const {
86 vector<Factor> result;
87 for( size_t i = 0; i < nrVars(); ++i )
88 result.push_back( beliefV(i) );
89 for( size_t I = 0; I < nrFactors(); ++I )
90 result.push_back( beliefF(I) );
91 return result;
92 }
93
94
95 Real DecMAP::run() {
96 if( props.verbose >= 1 )
97 cerr << "Starting " << identify() << "...";
98 if( props.verbose >= 2 )
99 cerr << endl;
100
101 // the variables which have not been clamped yet
102 SmallSet<size_t> freeVars;
103 for( size_t i = 0; i < nrVars(); i++ )
104 freeVars |= i;
105
106 // prepare the inference algorithm object
107 InfAlg *clamped = newInfAlg( props.ianame, fg(), props.iaopts );
108
109 // decimate until no free variables remain
110 while( freeVars.size() ) {
111 Real md = clamped->run();
112 if( md > _maxdiff )
113 _maxdiff = md;
114 _iters += clamped->Iterations();
115
116 // store the variables that need initialization
117 VarSet varsToInit;
118 SmallSet<size_t> varsToClamp;
119
120 // schedule clamping for the free variables with zero entropy
121 for( SmallSet<size_t>::const_iterator it = freeVars.begin(); it != freeVars.end(); ) {
122 if( clamped->beliefV( *it ).entropy() == 0.0 ) {
123 // this variable should be clamped
124 varsToInit |= var( *it );
125 varsToClamp |= *it;
126 _state[*it] = clamped->beliefV( *it ).p().argmax().first;
127 freeVars.erase( *it );
128 } else
129 it++;
130 }
131
132 // find the free factor with lowest entropy
133 size_t bestI = 0;
134 Real bestEnt = INFINITY;
135 for( size_t I = 0; I < nrFactors(); I++ ) {
136 // check if the factor is still free
137 if( freeVars.intersects( bipGraph().nb2Set(I) ) ) {
138 Real EntI = clamped->beliefF(I).entropy();
139 if( EntI < bestEnt ) {
140 bestI = I;
141 bestEnt = EntI;
142 }
143 }
144 }
145
146 // schedule clamping for the factor with lowest entropy
147 vector<size_t> Istate(1,0);
148 Istate[0] = clamped->beliefF(bestI).p().argmax().first;
149 map<Var, size_t> Istatemap = calcState( factor(bestI).vars(), Istate[0] );
150 bforeach( size_t i, bipGraph().nb2Set(bestI) & freeVars ) {
151 varsToInit |= var(i);
152 varsToClamp |= i;
153 _state[i] = Istatemap[var(i)];
154 freeVars.erase(i);
155 }
156
157 // clamp all variables scheduled for clamping
158 bforeach( size_t i, varsToClamp )
159 clamped->clamp( i, _state[i], false );
160
161 // initialize clamped for the next run
162 if( props.reinit )
163 clamped->init();
164 else
165 clamped->init( varsToInit );
166 }
167
168 // calculate MAP state
169 map<Var, size_t> state;
170 for( size_t i = 0; i < nrVars(); i++ )
171 state[var(i)] = _state[i];
172 _logp = 0.0;
173 for( size_t I = 0; I < nrFactors(); I++ )
174 _logp += dai::log( factor(I)[calcLinearState( factor(I).vars(), state )] );
175
176 // clean up
177 delete clamped;
178
179 return _maxdiff;
180 }
181
182
183 } // end of namespace dai
184
185
186 #endif