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 /// \file
  24 /// \brief Defines class HAK.
  25 /// \todo Improve documentation
  26
  27
  28 #ifndef __defined_libdai_hak_h
  29 #define __defined_libdai_hak_h
  30
  31
  32 #include <string>
  33 #include <dai/daialg.h>
  34 #include <dai/regiongraph.h>
  35 #include <dai/enum.h>
  36 #include <dai/properties.h>
  37
  38
  39 namespace dai {
  40
  41
  42 /// Approximate inference algorithm: implementation of single-loop ("Generalized Belief Propagation") and double-loop algorithms by Heskes, Albers and Kappen
  43 /** \todo Optimize HAK with precalculated indices, similarly to BP.
  44  */
  45 class HAK : public DAIAlgRG {
  46     private:
  47         std::vector<Factor>                _Qa;
  48         std::vector<Factor>                _Qb;
  49         std::vector<std::vector<Factor> >  _muab;
  50         std::vector<std::vector<Factor> >  _muba;
  51         /// Maximum difference encountered so far
  52         double _maxdiff;
  53         /// Number of iterations needed
  54         size_t _iters;
  55
  56     public:
  57         /// Parameters of this inference algorithm
  58         struct Properties {
  59             /// Enumeration of possible cluster choices
  60             DAI_ENUM(ClustersType,MIN,DELTA,LOOP)
  61
  62             /// Verbosity
  63             size_t verbose;
  64
  65             /// Maximum number of iterations
  66             size_t maxiter;
  67
  68             /// Tolerance
  69             double tol;
  70
  71             /// Damping constant
  72             double damping;
  73
  74             /// How to choose the clusters
  75             ClustersType clusters;
  76
  77             /// Use single-loop (GBP) or double-loop (HAK)
  78             bool doubleloop;
  79
  80             /// Depth of loops (only relevant for clusters == ClustersType::LOOP)
  81             size_t loopdepth;
  82         } props;
  83
  84         /// Name of this inference algorithm
  85         static const char *Name;
  86
  87     public:
  88         /// Default constructor
  89         HAK() : DAIAlgRG(), _Qa(), _Qb(), _muab(), _muba(), _maxdiff(0.0), _iters(0U), props() {}
  90
  91         /// Copy constructor
  92         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) {}
  93
  94         /// Assignment operator
  95         HAK& operator=( const HAK &x ) {
  96             if( this != &x ) {
  97                 DAIAlgRG::operator=( x );
  98                 _Qa      = x._Qa;
  99                 _Qb      = x._Qb;
 100                 _muab    = x._muab;
 101                 _muba    = x._muba;
 102                 _maxdiff = x._maxdiff;
 103                 _iters   = x._iters;
 104                 props    = x.props;
 105             }
 106             return *this;
 107         }
 108
 109         /// Construct from FactorGraph fg and PropertySet opts
 110         HAK( const FactorGraph &fg, const PropertySet &opts );
 111
 112         /// Construct from RegionGraph rg and PropertySet opts
 113         HAK( const RegionGraph &rg, const PropertySet &opts );
 114
 115
 116         /// @name General InfAlg interface
 117         //@{
 118         virtual HAK* clone() const { return new HAK(*this); }
 119         virtual HAK* create() const { return new HAK(); }
 120         virtual std::string identify() const;
 121         virtual Factor belief( const Var &n ) const;
 122         virtual Factor belief( const VarSet &ns ) const;
 123         virtual std::vector<Factor> beliefs() const;
 124         virtual Real logZ() const;
 125         virtual void init();
 126         virtual void init( const VarSet &ns );
 127         virtual double run();
 128         virtual double maxDiff() const { return _maxdiff; }
 129         virtual size_t Iterations() const { return _iters; }
 130         //@}
 131
 132
 133         /// @name Additional interface specific for HAK
 134         //@{
 135         Factor & muab( size_t alpha, size_t _beta ) { return _muab[alpha][_beta]; }
 136         Factor & muba( size_t alpha, size_t _beta ) { return _muba[alpha][_beta]; }
 137         const Factor& Qa( size_t alpha ) const { return _Qa[alpha]; };
 138         const Factor& Qb( size_t beta ) const { return _Qb[beta]; };
 139
 140         double doGBP();
 141         double doDoubleLoop();
 142         //@}
 143
 144     private:
 145         void constructMessages();
 146         void findLoopClusters( const FactorGraph &fg, std::set<VarSet> &allcl, VarSet newcl, const Var & root, size_t length, VarSet vars );
 147
 148         void setProperties( const PropertySet &opts );
 149         PropertySet getProperties() const;
 150         std::string printProperties() const;
 151 };
 152
 153
 154 } // end of namespace dai
 155
 156
 157 #endif