Merge branch 'master' of git.tuebingen.mpg.de:libdai
[libdai.git] / 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 for JTree
63 struct Properties {
64 /// Enumeration of possible JTree updates
65 /** There are two types of updates:
66 * - HUGIN similar to those in HUGIN
67 * - SHSH Shafer-Shenoy type
68 */
69 DAI_ENUM(UpdateType,HUGIN,SHSH);
70
71 /// Enumeration of inference variants
72 /** There are two inference variants:
73 * - SUMPROD Sum-Product
74 * - MAXPROD Max-Product (equivalent to Min-Sum)
75 */
76 DAI_ENUM(InfType,SUMPROD,MAXPROD);
77
78 /// Enumeration of elimination cost functions used for constructing the junction tree
79 /** The cost of eliminating a variable can be (\see [\ref KoF09], page 314)):
80 * - MINNEIGHBORS the number of neighbors it has in the current adjacency graph;
81 * - MINWEIGHT the product of the number of states of all neighbors in the current adjacency graph;
82 * - MINFILL the number of edges that need to be added to the adjacency graph due to the elimination;
83 * - WEIGHTEDMINFILL the sum of weights of the edges that need to be added to the adjacency graph
84 * due to the elimination, where a weight of an edge is the produt of weights of its constituent
85 * vertices.
86 * The elimination sequence is chosen greedily in order to minimize the cost.
87 */
88 DAI_ENUM(HeuristicType,MINNEIGHBORS,MINWEIGHT,MINFILL,WEIGHTEDMINFILL);
89
90 /// Verbosity (amount of output sent to stderr)
91 size_t verbose;
92
93 /// Type of updates
94 UpdateType updates;
95
96 /// Type of inference
97 InfType inference;
98
99 /// Heuristic to use for constructing the junction tree
100 HeuristicType heuristic;
101 } props;
102
103 /// Name of this inference algorithm
104 static const char *Name;
105
106 public:
107 /// \name Constructors/destructors
108 //@{
109 /// Default constructor
110 JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
111
112 /// Construct from FactorGraph \a fg and PropertySet \a opts
113 /** \param fg factor graph (which has to be connected);
114 ** \param opts Parameters @see Properties
115 * \param automatic if \c true, construct the junction tree automatically, using the heuristic in opts['heuristic'].
116 * \throw FACTORGRAPH_NOT_CONNECTED if \a fg is not connected
117 */
118 JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
119 //@}
120
121
122 /// \name General InfAlg interface
123 //@{
124 virtual JTree* clone() const { return new JTree(*this); }
125 virtual std::string identify() const;
126 virtual Factor belief( const VarSet &vs ) const;
127 virtual std::vector<Factor> beliefs() const;
128 virtual Real logZ() const;
129 virtual void init() {}
130 virtual void init( const VarSet &/*ns*/ ) {}
131 virtual Real run();
132 virtual Real maxDiff() const { return 0.0; }
133 virtual size_t Iterations() const { return 1UL; }
134 virtual void setProperties( const PropertySet &opts );
135 virtual PropertySet getProperties() const;
136 virtual std::string printProperties() const;
137 //@}
138
139
140 /// \name Additional interface specific for JTree
141 //@{
142 /// Constructs a junction tree based on the cliques \a cl (corresponding to some elimination sequence).
143 /** First, constructs a weighted graph, where the nodes are the elements of \a cl, and
144 * each edge is weighted with the cardinality of the intersection of the state spaces of the nodes.
145 * Then, a maximal spanning tree for this weighted graph is calculated.
146 * Subsequently, a corresponding region graph is built:
147 * - the outer regions correspond with the cliques and have counting number 1;
148 * - the inner regions correspond with the seperators, i.e., the intersections of two
149 * cliques that are neighbors in the spanning tree, and have counting number -1;
150 * - inner and outer regions are connected by an edge if the inner region is a
151 * seperator for the outer region.
152 * Finally, Beliefs are constructed.
153 * If \a verify == \c true, checks whether each factor is subsumed by a clique.
154 */
155 void construct( const std::vector<VarSet> &cl, bool verify=false );
156
157 /// Constructs a junction tree based on the cliques \a cl (corresponding to some elimination sequence).
158 /** Invokes construct() and then constructs messages.
159 * \see construct()
160 */
161 void GenerateJT( const std::vector<VarSet> &cl );
162
163 /// Returns constant reference to the message from outer region \a alpha to its \a _beta 'th neighboring inner region
164 const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
165 /// Returns reference to the message from outer region \a alpha to its \a _beta 'th neighboring inner region
166 Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
167
168 /// Runs junction tree algorithm using HUGIN (message-free) updates
169 /** \note The initial messages may be arbitrary; actually they are not used at all.
170 */
171 void runHUGIN();
172
173 /// Runs junction tree algorithm using Shafer-Shenoy updates
174 /** \note The initial messages may be arbitrary.
175 */
176 void runShaferShenoy();
177
178 /// Finds an efficient subtree for calculating the marginal of the variables in \a vs
179 /** First, the current junction tree is reordered such that it gets as root the clique
180 * that has maximal state space overlap with \a vs. Then, the minimal subtree
181 * (starting from the root) is identified that contains all the variables in \a vs
182 * and also the outer region with index \a PreviousRoot (if specified). Finally,
183 * the current junction tree is reordered such that this minimal subtree comes
184 * before the other edges, and the size of the minimal subtree is returned.
185 */
186 size_t findEfficientTree( const VarSet& vs, RootedTree &Tree, size_t PreviousRoot=(size_t)-1 ) const;
187
188 /// Calculates the marginal of a set of variables (using cutset conditioning, if necessary)
189 /** \pre assumes that run() has been called already
190 */
191 Factor calcMarginal( const VarSet& vs );
192
193 /// Calculates the joint state of all variables that has maximum probability
194 /** \pre Assumes that run() has been called and that \a props.inference == \c MAXPROD
195 */
196 std::vector<std::size_t> findMaximum() const;
197 //@}
198 };
199
200
201 /// Calculates upper bound to the treewidth of a FactorGraph, using the specified heuristic
202 /** \relates JTree
203 * \return a pair (number of variables in largest clique, number of states in largest clique)
204 */
205 std::pair<size_t,double> boundTreewidth( const FactorGraph &fg, greedyVariableElimination::eliminationCostFunction fn );
206
207
208 } // end of namespace dai
209
210
211 #endif