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         /// Construct from FactorGraph fg and PropertySet opts
  92         HAK( const FactorGraph &fg, const PropertySet &opts );
  93
  94         /// Construct from RegionGraph rg and PropertySet opts
  95         HAK( const RegionGraph &rg, const PropertySet &opts );
  96
  97
  98         /// @name General InfAlg interface
  99         //@{
 100         virtual HAK* clone() const { return new HAK(*this); }
 101         virtual std::string identify() const;
 102         virtual Factor belief( const Var &n ) const;
 103         virtual Factor belief( const VarSet &ns ) const;
 104         virtual std::vector<Factor> beliefs() const;
 105         virtual Real logZ() const;
 106         virtual void init();
 107         virtual void init( const VarSet &ns );
 108         virtual double run();
 109         virtual double maxDiff() const { return _maxdiff; }
 110         virtual size_t Iterations() const { return _iters; }
 111         //@}
 112
 113
 114         /// @name Additional interface specific for HAK
 115         //@{
 116         Factor & muab( size_t alpha, size_t _beta ) { return _muab[alpha][_beta]; }
 117         Factor & muba( size_t alpha, size_t _beta ) { return _muba[alpha][_beta]; }
 118         const Factor& Qa( size_t alpha ) const { return _Qa[alpha]; };
 119         const Factor& Qb( size_t beta ) const { return _Qb[beta]; };
 120
 121         double doGBP();
 122         double doDoubleLoop();
 123         //@}
 124
 125     private:
 126         void constructMessages();
 127         void findLoopClusters( const FactorGraph &fg, std::set<VarSet> &allcl, VarSet newcl, const Var & root, size_t length, VarSet vars );
 128
 129         void setProperties( const PropertySet &opts );
 130         PropertySet getProperties() const;
 131         std::string printProperties() const;
 132 };
 133
 134
 135 } // end of namespace dai
 136
 137
 138 #endif