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