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, which implements a variant of Generalized Belief Propagation.
  14 /// \todo Implement Bethe approximation as a standard region graph choice in HAK.
  15 /// \idea Implement more general region graphs and corresponding Generalized Belief Propagation updates as described in [\ref YFW05].
  16
  17
  18 #ifndef __defined_libdai_hak_h
  19 #define __defined_libdai_hak_h
  20
  21
  22 #include <string>
  23 #include <dai/daialg.h>
  24 #include <dai/regiongraph.h>
  25 #include <dai/enum.h>
  26 #include <dai/properties.h>
  27
  28
  29 namespace dai {
  30
  31
  32 /// Approximate inference algorithm: implementation of single-loop ("Generalized Belief Propagation") and double-loop algorithms by Heskes, Albers and Kappen [\ref HAK03]
  33 class HAK : public DAIAlgRG {
  34     private:
  35         /// Outer region beliefs
  36         std::vector<Factor>                _Qa;
  37         /// Inner region beliefs
  38         std::vector<Factor>                _Qb;
  39         /// Messages from outer to inner regions
  40         std::vector<std::vector<Factor> >  _muab;
  41         /// Messages from inner to outer regions
  42         std::vector<std::vector<Factor> >  _muba;
  43         /// Maximum difference encountered so far
  44         Real _maxdiff;
  45         /// Number of iterations needed
  46         size_t _iters;
  47
  48     public:
  49         /// Parameters for HAK
  50         struct Properties {
  51             /// Enumeration of possible cluster choices
  52             /** The following cluster choices are defined:
  53              *   - MIN minimal clusters, i.e., one outer region for each maximal factor
  54              *   - DELTA one outer region for each variable and its Markov blanket
  55              *   - LOOP one cluster for each loop of length at most \a Properties::loopdepth, and in addition one cluster for each maximal factor
  56              */
  57             DAI_ENUM(ClustersType,MIN,DELTA,LOOP);
  58
  59             /// Enumeration of possible message initializations
  60             DAI_ENUM(InitType,UNIFORM,RANDOM);
  61
  62             /// Verbosity (amount of output sent to stderr)
  63             size_t verbose;
  64
  65             /// Maximum number of iterations
  66             size_t maxiter;
  67
  68             /// Tolerance for convergence test
  69             Real tol;
  70
  71             /// Damping constant (0.0 means no damping, 1.0 is maximum damping)
  72             Real damping;
  73
  74             /// How to choose the outer regions
  75             ClustersType clusters;
  76
  77             /// How to initialize the messages
  78             InitType init;
  79
  80             /// Use single-loop (GBP) or double-loop (HAK)
  81             bool doubleloop;
  82
  83             /// Depth of loops (only relevant for \a clusters == \c ClustersType::LOOP)
  84             size_t loopdepth;
  85         } props;
  86
  87         /// Name of this inference algorithm
  88         static const char *Name;
  89
  90     public:
  91     /// \name Constructors/destructors
  92     //@{
  93         /// Default constructor
  94         HAK() : DAIAlgRG(), _Qa(), _Qb(), _muab(), _muba(), _maxdiff(0.0), _iters(0U), props() {}
  95
  96         /// Construct from FactorGraph \a fg and PropertySet \a opts
  97         /** \param opts Parameters @see Properties
  98          */
  99         HAK( const FactorGraph &fg, const PropertySet &opts );
 100
 101         /// Construct from RegionGraph \a rg and PropertySet \a opts
 102         HAK( const RegionGraph &rg, const PropertySet &opts );
 103     //@}
 104
 105
 106     /// \name General InfAlg interface
 107     //@{
 108         virtual HAK* clone() const { return new HAK(*this); }
 109         virtual std::string identify() const;
 110         virtual Factor belief( const VarSet &vs ) const;
 111         virtual std::vector<Factor> beliefs() const;
 112         virtual Real logZ() const;
 113         virtual void init();
 114         virtual void init( const VarSet &vs );
 115         virtual Real run();
 116         virtual Real maxDiff() const { return _maxdiff; }
 117         virtual size_t Iterations() const { return _iters; }
 118         virtual void setProperties( const PropertySet &opts );
 119         virtual PropertySet getProperties() const;
 120         virtual std::string printProperties() const;
 121     //@}
 122
 123
 124     /// \name Additional interface specific for HAK
 125     //@{
 126         /// Returns reference to message from outer region \a alpha to its \a _beta 'th neighboring inner region
 127         Factor & muab( size_t alpha, size_t _beta ) { return _muab[alpha][_beta]; }
 128         /// Returns reference to message the \a _beta 'th neighboring inner region of outer region \a alpha to that outer region
 129         Factor & muba( size_t alpha, size_t _beta ) { return _muba[alpha][_beta]; }
 130         /// Returns belief of outer region \a alpha
 131         const Factor& Qa( size_t alpha ) const { return _Qa[alpha]; };
 132         /// Returns belief of inner region \a beta
 133         const Factor& Qb( size_t beta ) const { return _Qb[beta]; };
 134
 135         /// Runs single-loop algorithm (algorithm 1 in [\ref HAK03])
 136         Real doGBP();
 137         /// Runs double-loop algorithm (as described in section 4.2 of [\ref HAK03]), which always convergences
 138         Real doDoubleLoop();
 139     //@}
 140
 141     private:
 142         /// Helper function for constructors
 143         void construct();
 144         /// Recursive procedure for finding clusters of variables containing loops of length at most \a length
 145         /** \param fg the factor graph
 146          *  \param allcl the clusters found so far
 147          *  \param newcl partial candidate cluster
 148          *  \param root start (and end) point of the loop
 149          *  \param length number of variables that may be added to \a newcl
 150          *  \param vars neighboring variables of \a newcl
 151          *  \return allcl all clusters of variables with loops of length at most \a length passing through root
 152          */
 153         void findLoopClusters( const FactorGraph &fg, std::set<VarSet> &allcl, VarSet newcl, const Var & root, size_t length, VarSet vars );
 154 };
 155
 156
 157 } // end of namespace dai
 158
 159
 160 #endif