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