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