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          */
  94         JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
  95     //@}
  96
  97
  98     /// \name General InfAlg interface
  99     //@{
 100         virtual JTree* clone() const { return new JTree(*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 Real run();
 109         virtual Real maxDiff() const { return 0.0; }
 110         virtual size_t Iterations() const { return 1UL; }
 111         virtual void setProperties( const PropertySet &opts );
 112         virtual PropertySet getProperties() const;
 113         virtual std::string printProperties() const;
 114     //@}
 115
 116
 117     /// \name Additional interface specific for JTree
 118     //@{
 119         /// Constructs a junction tree based on the cliques \a cl (corresponding to some elimination sequence).
 120         /** First, constructs a weighted graph, where the nodes are the elements of \a cl, and
 121          *  each edge is weighted with the cardinality of the intersection of the state spaces of the nodes.
 122          *  Then, a maximal spanning tree for this weighted graph is calculated.
 123          *  Finally, a corresponding region graph is built:
 124          *    - the outer regions correspond with the cliques and have counting number 1;
 125          *    - the inner regions correspond with the seperators, i.e., the intersections of two
 126          *      cliques that are neighbors in the spanning tree, and have counting number -1;
 127          *    - inner and outer regions are connected by an edge if the inner region is a
 128          *      seperator for the outer region.
 129          */
 130         void GenerateJT( const std::vector<VarSet> &cl );
 131
 132         /// Returns constant reference to the message from outer region \a alpha to its \a _beta 'th neighboring inner region
 133         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
 134         /// Returns reference to the message from outer region \a alpha to its \a _beta 'th neighboring inner region
 135         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
 136
 137         /// Runs junction tree algorithm using HUGIN updates
 138         /** \note The initial messages may be arbitrary.
 139          */
 140         void runHUGIN();
 141
 142         /// Runs junction tree algorithm using Shafer-Shenoy updates
 143         /** \note The initial messages may be arbitrary.
 144          */
 145         void runShaferShenoy();
 146
 147         /// Finds an efficient subtree for calculating the marginal of the variables in \a vs
 148         /** First, the current junction tree is reordered such that it gets as root the clique
 149          *  that has maximal state space overlap with \a vs. Then, the minimal subtree
 150          *  (starting from the root) is identified that contains all the variables in \a vs
 151          *  and also the outer region with index \a PreviousRoot (if specified). Finally,
 152          *  the current junction tree is reordered such that this minimal subtree comes
 153          *  before the other edges, and the size of the minimal subtree is returned.
 154          */
 155         size_t findEfficientTree( const VarSet& vs, RootedTree &Tree, size_t PreviousRoot=(size_t)-1 ) const;
 156
 157         /// Calculates the marginal of a set of variables (using cutset conditioning, if necessary)
 158         /** \pre assumes that run() has been called already
 159          */
 160         Factor calcMarginal( const VarSet& vs );
 161
 162         /// Calculates the joint state of all variables that has maximum probability
 163         /** \pre Assumes that run() has been called and that \a props.inference == \c MAXPROD
 164          */
 165         std::vector<std::size_t> findMaximum() const;
 166     //@}
 167 };
 168
 169
 170 /// Calculates upper bound to the treewidth of a FactorGraph, using the MinFill heuristic
 171 /** \relates JTree
 172  *  \return a pair (number of variables in largest clique, number of states in largest clique)
 173  */
 174 std::pair<size_t,size_t> boundTreewidth( const FactorGraph & fg );
 175
 176
 177 /// Calculates upper bound to the treewidth of a FactorGraph, using the MinFill heuristic
 178 /** \deprecated Renamed into boundTreewidth()
 179  */
 180 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 181
 182
 183 } // end of namespace dai
 184
 185
 186 #endif