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