Improved documentation of include/dai/treeep.h
[libdai.git] / 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, which implements Tree Expectation Propagation
14
15
16 #ifndef __defined_libdai_treeep_h
17 #define __defined_libdai_treeep_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/jtree.h>
29 #include <dai/properties.h>
30 #include <dai/enum.h>
31
32
33 namespace dai {
34
35
36 /// Approximate inference algorithm "Tree Expectation Propagation" [\ref MiQ04]
37 class TreeEP : public JTree {
38 private:
39 /// Maximum difference encountered so far
40 Real _maxdiff;
41 /// Number of iterations needed
42 size_t _iters;
43
44 public:
45 /// Parameters of this inference algorithm
46 struct Properties {
47 /// Enumeration of possible choices for the tree
48 /** The two possibilities are:
49 * - \c ORG: take the maximum spanning tree where the weights are crude
50 * estimates of the mutual information between the nodes;
51 * - \c ALT: take the maximum spanning tree where the weights are upper
52 * bounds on the effective interaction strengths between pairs of nodes.
53 */
54 DAI_ENUM(TypeType,ORG,ALT);
55
56 /// Verbosity
57 size_t verbose;
58
59 /// Maximum number of iterations
60 size_t maxiter;
61
62 /// Tolerance
63 Real tol;
64
65 /// How to choose the tree
66 TypeType type;
67 } props;
68
69 /// Name of this inference method
70 static const char *Name;
71
72 private:
73 /// Stores the data structures needed to efficiently update the approximation of an off-tree factor
74 class TreeEPSubTree {
75 private:
76 std::vector<Factor> _Qa;
77 std::vector<Factor> _Qb;
78 RootedTree _RTree;
79 std::vector<size_t> _a; // _Qa[alpha] <-> superTree.Qa[_a[alpha]]
80 std::vector<size_t> _b; // _Qb[beta] <-> superTree.Qb[_b[beta]]
81 // _Qb[beta] <-> _RTree[beta]
82 const Factor * _I;
83 VarSet _ns;
84 VarSet _nsrem;
85 Real _logZ;
86
87
88 public:
89 TreeEPSubTree() : _Qa(), _Qb(), _RTree(), _a(), _b(), _I(NULL), _ns(), _nsrem(), _logZ(0.0) {}
90 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) {}
91 TreeEPSubTree & operator=( const TreeEPSubTree& x ) {
92 if( this != &x ) {
93 _Qa = x._Qa;
94 _Qb = x._Qb;
95 _RTree = x._RTree;
96 _a = x._a;
97 _b = x._b;
98 _I = x._I;
99 _ns = x._ns;
100 _nsrem = x._nsrem;
101 _logZ = x._logZ;
102 }
103 return *this;
104 }
105
106 TreeEPSubTree( const RootedTree &subRTree, const RootedTree &jt_RTree, const std::vector<Factor> &jt_Qa, const std::vector<Factor> &jt_Qb, const Factor *I );
107 void init();
108 void InvertAndMultiply( const std::vector<Factor> &Qa, const std::vector<Factor> &Qb );
109 void HUGIN_with_I( std::vector<Factor> &Qa, std::vector<Factor> &Qb );
110 Real logZ( const std::vector<Factor> &Qa, const std::vector<Factor> &Qb ) const;
111 const Factor *& I() { return _I; }
112 };
113
114 /// Stores a TreeEPSubTree object for each off-tree factor
115 std::map<size_t, TreeEPSubTree> _Q;
116
117 public:
118 /// Default constructor
119 TreeEP() : JTree(), _maxdiff(0.0), _iters(0), props(), _Q() {}
120
121 /// Copy constructor
122 TreeEP( const TreeEP &x ) : JTree(x), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props), _Q(x._Q) {
123 for( size_t I = 0; I < nrFactors(); I++ )
124 if( offtree( I ) )
125 _Q[I].I() = &factor(I);
126 }
127
128 /// Assignment operator
129 TreeEP& operator=( const TreeEP &x ) {
130 if( this != &x ) {
131 JTree::operator=( x );
132 _maxdiff = x._maxdiff;
133 _iters = x._iters;
134 props = x.props;
135 _Q = x._Q;
136 for( size_t I = 0; I < nrFactors(); I++ )
137 if( offtree( I ) )
138 _Q[I].I() = &factor(I);
139 }
140 return *this;
141 }
142
143 /// Construct from FactorGraph \a fg and PropertySet \a opts
144 TreeEP( const FactorGraph &fg, const PropertySet &opts );
145
146
147 /// \name General InfAlg interface
148 //@{
149 virtual TreeEP* clone() const { return new TreeEP(*this); }
150 virtual std::string identify() const;
151 virtual Real logZ() const;
152 virtual void init();
153 virtual void init( const VarSet &/*ns*/ ) { init(); }
154 virtual Real run();
155 virtual Real maxDiff() const { return _maxdiff; }
156 virtual size_t Iterations() const { return _iters; }
157 virtual void setProperties( const PropertySet &opts );
158 virtual PropertySet getProperties() const;
159 virtual std::string printProperties() const;
160 //@}
161
162
163 private:
164 /// Helper function for constructors
165 void construct( const RootedTree &tree );
166 /// Returns \c true if factor \a I is not part of the tree
167 bool offtree( size_t I ) const { return (fac2OR[I] == -1U); }
168 };
169
170
171 } // end of namespace dai
172
173
174 #endif