include/dai/treeep.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 TreeEP
  14 /// \todo Improve documentation
  15
  16
  17 #ifndef __defined_libdai_treeep_h
  18 #define __defined_libdai_treeep_h
  19
  20
  21 #include <vector>
  22 #include <string>
  23 #include <dai/daialg.h>
  24 #include <dai/varset.h>
  25 #include <dai/regiongraph.h>
  26 #include <dai/factorgraph.h>
  27 #include <dai/clustergraph.h>
  28 #include <dai/weightedgraph.h>
  29 #include <dai/jtree.h>
  30 #include <dai/properties.h>
  31 #include <dai/enum.h>
  32
  33
  34 namespace dai {
  35
  36
  37 /// Approximate inference algorithm "TreeEP" by Minka and Qi
  38 class TreeEP : public JTree {
  39     private:
  40         /// Maximum difference encountered so far
  41         double                  _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 choices for the tree
  49             DAI_ENUM(TypeType,ORG,ALT)
  50
  51             /// Verbosity
  52             size_t verbose;
  53
  54             /// Maximum number of iterations
  55             size_t maxiter;
  56
  57             /// Tolerance
  58             double tol;
  59
  60             /// How to choose the tree
  61             TypeType type;
  62         } props; // FIXME: should be props2 because of conflict with JTree::props?
  63
  64         /// Name of this inference method
  65         static const char *Name;
  66
  67     private:
  68         class TreeEPSubTree {
  69             private:
  70                 std::vector<Factor>  _Qa;
  71                 std::vector<Factor>  _Qb;
  72                 DEdgeVec             _RTree;
  73                 std::vector<size_t>  _a;        // _Qa[alpha]  <->  superTree.Qa[_a[alpha]]
  74                 std::vector<size_t>  _b;        // _Qb[beta]   <->  superTree.Qb[_b[beta]]
  75                                                 // _Qb[beta]   <->  _RTree[beta]
  76                 const Factor *       _I;
  77                 VarSet               _ns;
  78                 VarSet               _nsrem;
  79                 double               _logZ;
  80
  81
  82             public:
  83                 TreeEPSubTree() : _Qa(), _Qb(), _RTree(), _a(), _b(), _I(NULL), _ns(), _nsrem(), _logZ(0.0) {}
  84                 TreeEPSubTree( const TreeEPSubTree &x) : _Qa(x._Qa), _Qb(x._Qb), _RTree(x._RTree), _a(x._a), _b(x._b), _I(x._I), _ns(x._ns), _nsrem(x._nsrem), _logZ(x._logZ) {}
  85                 TreeEPSubTree & operator=( const TreeEPSubTree& x ) {
  86                     if( this != &x ) {
  87                         _Qa         = x._Qa;
  88                         _Qb         = x._Qb;
  89                         _RTree      = x._RTree;
  90                         _a          = x._a;
  91                         _b          = x._b;
  92                         _I          = x._I;
  93                         _ns         = x._ns;
  94                         _nsrem      = x._nsrem;
  95                         _logZ       = x._logZ;
  96                     }
  97                     return *this;
  98                 }
  99
 100                 TreeEPSubTree( const DEdgeVec &subRTree, const DEdgeVec &jt_RTree, const std::vector<Factor> &jt_Qa, const std::vector<Factor> &jt_Qb, const Factor *I );
 101                 void init();
 102                 void InvertAndMultiply( const std::vector<Factor> &Qa, const std::vector<Factor> &Qb );
 103                 void HUGIN_with_I( std::vector<Factor> &Qa, std::vector<Factor> &Qb );
 104                 double logZ( const std::vector<Factor> &Qa, const std::vector<Factor> &Qb ) const;
 105                 const Factor *& I() { return _I; }
 106         };
 107
 108         std::map<size_t, TreeEPSubTree>  _Q;
 109
 110     public:
 111         /// Default constructor
 112         TreeEP() : JTree(), _maxdiff(0.0), _iters(0), props(), _Q() {}
 113
 114         /// Copy constructor
 115         TreeEP( const TreeEP &x ) : JTree(x), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props), _Q(x._Q) {
 116             for( size_t I = 0; I < nrFactors(); I++ )
 117                 if( offtree( I ) )
 118                     _Q[I].I() = &factor(I);
 119         }
 120
 121         /// Assignment operator
 122         TreeEP& operator=( const TreeEP &x ) {
 123             if( this != &x ) {
 124                 JTree::operator=( x );
 125                 _maxdiff = x._maxdiff;
 126                 _iters   = x._iters;
 127                 props    = x.props;
 128                 _Q       = x._Q;
 129                 for( size_t I = 0; I < nrFactors(); I++ )
 130                     if( offtree( I ) )
 131                         _Q[I].I() = &factor(I);
 132             }
 133             return *this;
 134         }
 135
 136         /// Construct from FactorGraph fg and PropertySet opts
 137         TreeEP( const FactorGraph &fg, const PropertySet &opts );
 138
 139
 140         /// @name General InfAlg interface
 141         //@{
 142         virtual TreeEP* clone() const { return new TreeEP(*this); }
 143         virtual std::string identify() const;
 144         virtual Real logZ() const;
 145         virtual void init();
 146         virtual void init( const VarSet &/*ns*/ ) { init(); }
 147         virtual double run();
 148         virtual double maxDiff() const { return _maxdiff; }
 149         virtual size_t Iterations() const { return _iters; }
 150         //@}
 151
 152
 153         /// @name Additional interface specific for TreeEP
 154         //@{
 155         //@}
 156
 157     private:
 158         void ConstructRG( const DEdgeVec &tree );
 159         bool offtree( size_t I ) const { return (fac2OR[I] == -1U); }
 160
 161         void setProperties( const PropertySet &opts );
 162         PropertySet getProperties() const;
 163         std::string printProperties() const;
 164 };
 165
 166
 167 } // end of namespace dai
 168
 169
 170 #endif