include/dai/hak.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
   2     Radboud University Nijmegen, The Netherlands /
   3     Max Planck Institute for Biological Cybernetics, Germany
   4
   5     This file is part of libDAI.
   6
   7     libDAI is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     libDAI is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with libDAI; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22
  23 #ifndef __defined_libdai_hak_h
  24 #define __defined_libdai_hak_h
  25
  26
  27 #include <string>
  28 #include <dai/daialg.h>
  29 #include <dai/regiongraph.h>
  30 #include <dai/enum.h>
  31 #include <dai/properties.h>
  32
  33
  34 namespace dai {
  35
  36
  37 /// HAK provides an implementation of the single and double-loop algorithms by Heskes, Albers and Kappen
  38 class HAK : public DAIAlgRG {
  39     private:
  40         std::vector<Factor>                _Qa;
  41         std::vector<Factor>                _Qb;
  42         std::vector<std::vector<Factor> >  _muab;
  43         std::vector<std::vector<Factor> >  _muba;
  44         /// Maximum difference encountered so far
  45         double _maxdiff;
  46         /// Number of iterations needed
  47         size_t _iters;
  48
  49     public:
  50         struct Properties {
  51             size_t verbose;
  52             size_t maxiter;
  53             double tol;
  54             double damping;
  55             DAI_ENUM(ClustersType,MIN,DELTA,LOOP)
  56             ClustersType clusters;
  57             bool doubleloop;
  58             size_t loopdepth;
  59         } props;
  60         /// Name of this inference method
  61         static const char *Name;
  62
  63     public:
  64         /// Default constructor
  65         HAK() : DAIAlgRG(), _Qa(), _Qb(), _muab(), _muba(), _maxdiff(0.0), _iters(0U), props() {}
  66
  67         /// Construct from FactorGraph fg and PropertySet opts
  68         HAK( const FactorGraph &fg, const PropertySet &opts );
  69
  70         /// Construct from RegionGraph rg and PropertySet opts
  71         HAK( const RegionGraph &rg, const PropertySet &opts );
  72
  73         /// Copy constructor
  74         HAK( const HAK &x ) : DAIAlgRG(x), _Qa(x._Qa), _Qb(x._Qb), _muab(x._muab), _muba(x._muba), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
  75
  76         /// Clone *this (virtual copy constructor)
  77         virtual HAK* clone() const { return new HAK(*this); }
  78
  79         /// Create (virtual default constructor)
  80         virtual HAK* create() const { return new HAK(); }
  81
  82         /// Assignment operator
  83         HAK& operator=( const HAK &x ) {
  84             if( this != &x ) {
  85                 DAIAlgRG::operator=( x );
  86                 _Qa      = x._Qa;
  87                 _Qb      = x._Qb;
  88                 _muab    = x._muab;
  89                 _muba    = x._muba;
  90                 _maxdiff = x._maxdiff;
  91                 _iters   = x._iters;
  92                 props    = x.props;
  93             }
  94             return *this;
  95         }
  96
  97         /// Identifies itself for logging purposes
  98         virtual std::string identify() const;
  99
 100         /// Get single node belief
 101         virtual Factor belief( const Var &n ) const;
 102
 103         /// Get general belief
 104         virtual Factor belief( const VarSet &ns ) const;
 105
 106         /// Get all beliefs
 107         virtual std::vector<Factor> beliefs() const;
 108
 109         /// Get log partition sum
 110         virtual Real logZ() const;
 111
 112         /// Clear messages and beliefs
 113         virtual void init();
 114
 115         /// Clear messages and beliefs corresponding to the nodes in ns
 116         virtual void init( const VarSet &ns );
 117
 118         /// The actual approximate inference algorithm
 119         virtual double run();
 120
 121         /// Return maximum difference between single node beliefs in the last pass
 122         virtual double maxDiff() const { return _maxdiff; }
 123
 124         /// Return number of passes over the factorgraph
 125         virtual size_t Iterations() const { return _iters; }
 126
 127
 128         Factor & muab( size_t alpha, size_t _beta ) { return _muab[alpha][_beta]; }
 129         Factor & muba( size_t alpha, size_t _beta ) { return _muba[alpha][_beta]; }
 130         const Factor& Qa( size_t alpha ) const { return _Qa[alpha]; };
 131         const Factor& Qb( size_t beta ) const { return _Qb[beta]; };
 132
 133         double doGBP();
 134         double doDoubleLoop();
 135
 136         void setProperties( const PropertySet &opts );
 137         PropertySet getProperties() const;
 138         std::string printProperties() const;
 139
 140     private:
 141         void constructMessages();
 142         void findLoopClusters( const FactorGraph &fg, std::set<VarSet> &allcl, VarSet newcl, const Var & root, size_t length, VarSet vars );
 143 };
 144
 145
 146 } // end of namespace dai
 147
 148
 149 #endif