include/dai/hak.h

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