include/dai/jtree.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 JTree, which implements the junction tree algorithm
  14
  15
  16 #ifndef __defined_libdai_jtree_h
  17 #define __defined_libdai_jtree_h
  18
  19
  20 #include <vector>
  21 #include <string>
  22 #include <dai/daialg.h>
  23 #include <dai/varset.h>
  24 #include <dai/regiongraph.h>
  25 #include <dai/factorgraph.h>
  26 #include <dai/clustergraph.h>
  27 #include <dai/weightedgraph.h>
  28 #include <dai/enum.h>
  29 #include <dai/properties.h>
  30
  31
  32 namespace dai {
  33
  34
  35 /// Exact inference algorithm using junction tree
  36 /** The junction tree algorithm uses message passing on a junction tree to calculate
  37  *  exact marginal probability distributions ("beliefs") for specified cliques
  38  *  (outer regions) and separators (intersections of pairs of cliques).
  39  *
  40  *  There are two variants, the sum-product algorithm (corresponding to
  41  *  finite temperature) and the max-product algorithm (corresponding to
  42  *  zero temperature).
  43  */
  44 class JTree : public DAIAlgRG {
  45     private:
  46         /// Stores the messages
  47         std::vector<std::vector<Factor> >  _mes;
  48
  49         /// Stores the logarithm of the partition sum
  50         Real _logZ;
  51
  52     public:
  53         /// The junction tree (stored as a rooted tree)
  54         RootedTree RTree;
  55
  56         /// Outer region beliefs
  57         std::vector<Factor> Qa;
  58
  59         /// Inner region beliefs
  60         std::vector<Factor> Qb;
  61
  62         /// Parameters of this inference algorithm
  63         struct Properties {
  64             /// Enumeration of possible JTree updates
  65             DAI_ENUM(UpdateType,HUGIN,SHSH);
  66
  67             /// Enumeration of inference variants
  68             DAI_ENUM(InfType,SUMPROD,MAXPROD);
  69
  70             /// Verbosity
  71             size_t verbose;
  72
  73             /// Type of updates: HUGIN or Shafer-Shenoy
  74             UpdateType updates;
  75
  76             /// Type of inference: sum-product or max-product
  77             InfType inference;
  78         } props;
  79
  80         /// Name of this inference algorithm
  81         static const char *Name;
  82
  83     public:
  84     /// \name Constructors/destructors
  85     //@{
  86         /// Default constructor
  87         JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
  88
  89         /// Construct from FactorGraph \a fg and PropertySet \a opts
  90         /** \param fg factor graph (which has to be connected);
  91          *  \param opts parameters;
  92          *  \param automatic if \c true, construct the junction tree automatically, using the MinFill heuristic.
  93          *  \throw FACTORGRAPH_NOT_CONNECTED if \a fg is not connected
  94          */
  95         JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
  96     //@}
  97
  98
  99     /// \name General InfAlg interface
 100     //@{
 101         virtual JTree* clone() const { return new JTree(*this); }
 102         virtual std::string identify() const;
 103         virtual Factor belief( const Var &n ) const;
 104         virtual Factor belief( const VarSet &ns ) const;
 105         virtual std::vector<Factor> beliefs() const;
 106         virtual Real logZ() const;
 107         virtual void init() {}
 108         virtual void init( const VarSet &/*ns*/ ) {}
 109         virtual Real run();
 110         virtual Real maxDiff() const { return 0.0; }
 111         virtual size_t Iterations() const { return 1UL; }
 112         virtual void setProperties( const PropertySet &opts );
 113         virtual PropertySet getProperties() const;
 114         virtual std::string printProperties() const;
 115     //@}
 116
 117
 118     /// \name Additional interface specific for JTree
 119     //@{
 120         /// Constructs a junction tree based on the cliques \a cl (corresponding to some elimination sequence).
 121         /** First, constructs a weighted graph, where the nodes are the elements of \a cl, and
 122          *  each edge is weighted with the cardinality of the intersection of the state spaces of the nodes.
 123          *  Then, a maximal spanning tree for this weighted graph is calculated.
 124          *  Finally, a corresponding region graph is built:
 125          *    - the outer regions correspond with the cliques and have counting number 1;
 126          *    - the inner regions correspond with the seperators, i.e., the intersections of two
 127          *      cliques that are neighbors in the spanning tree, and have counting number -1;
 128          *    - inner and outer regions are connected by an edge if the inner region is a
 129          *      seperator for the outer region.
 130          */
 131         void GenerateJT( const std::vector<VarSet> &cl );
 132
 133         /// Returns constant reference to the message from outer region \a alpha to its \a _beta 'th neighboring inner region
 134         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
 135         /// Returns reference to the message from outer region \a alpha to its \a _beta 'th neighboring inner region
 136         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
 137
 138         /// Runs junction tree algorithm using HUGIN updates
 139         /** \note The initial messages may be arbitrary.
 140          */
 141         void runHUGIN();
 142
 143         /// Runs junction tree algorithm using Shafer-Shenoy updates
 144         /** \note The initial messages may be arbitrary.
 145          */
 146         void runShaferShenoy();
 147
 148         /// Finds an efficient subtree for calculating the marginal of the variables in \a vs
 149         /** First, the current junction tree is reordered such that it gets as root the clique
 150          *  that has maximal state space overlap with \a vs. Then, the minimal subtree
 151          *  (starting from the root) is identified that contains all the variables in \a vs
 152          *  and also the outer region with index \a PreviousRoot (if specified). Finally,
 153          *  the current junction tree is reordered such that this minimal subtree comes
 154          *  before the other edges, and the size of the minimal subtree is returned.
 155          */
 156         size_t findEfficientTree( const VarSet& vs, RootedTree &Tree, size_t PreviousRoot=(size_t)-1 ) const;
 157
 158         /// Calculates the marginal of a set of variables (using cutset conditioning, if necessary)
 159         /** \pre assumes that run() has been called already
 160          */
 161         Factor calcMarginal( const VarSet& vs );
 162
 163         /// Calculates the joint state of all variables that has maximum probability
 164         /** \pre Assumes that run() has been called and that \a props.inference == \c MAXPROD
 165          */
 166         std::vector<std::size_t> findMaximum() const;
 167     //@}
 168 };
 169
 170
 171 /// Calculates upper bound to the treewidth of a FactorGraph, using the MinFill heuristic
 172 /** \relates JTree
 173  *  \return a pair (number of variables in largest clique, number of states in largest clique)
 174  */
 175 std::pair<size_t,size_t> boundTreewidth( const FactorGraph & fg );
 176
 177
 178 /// Calculates upper bound to the treewidth of a FactorGraph, using the MinFill heuristic
 179 /** \deprecated Renamed into boundTreewidth()
 180  */
 181 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 182
 183
 184 } // end of namespace dai
 185
 186
 187 #endif