067eb1350fb5c067301728549b4d95167742d657
[libdai.git] / include / dai / daialg.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 abstract base class InfAlg, its descendants DAIAlg<>, the specializations DAIAlgFG and DAIAlgRG and some generic inference methods.
14 /// \todo Improve documentation
15
16
17 #ifndef __defined_libdai_daialg_h
18 #define __defined_libdai_daialg_h
19
20
21 #include <string>
22 #include <iostream>
23 #include <vector>
24 #include <dai/factorgraph.h>
25 #include <dai/regiongraph.h>
26
27
28 namespace dai {
29
30
31 /// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.
32 /** \todo General marginalization functions like calcMarginal now copy a complete InfAlg object. Instead,
33 * it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph.
34 * Or they can simply be made methods of the general InfAlg class.
35 * \idea Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().
36 */
37 class InfAlg {
38 public:
39 /// Virtual desctructor (needed because this class contains virtual functions)
40 virtual ~InfAlg() {}
41
42 public:
43 /// Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor)
44 virtual InfAlg* clone() const = 0;
45
46 /// Identifies itself for logging purposes
47 virtual std::string identify() const = 0;
48
49 /// Returns the "belief" (i.e., approximate marginal probability distribution) of a variable
50 virtual Factor belief( const Var &n ) const = 0;
51
52 /// Returns the "belief" (i.e., approximate marginal probability distribution) of a set of variables
53 virtual Factor belief( const VarSet &n ) const = 0;
54
55 /// Returns marginal for a variable.
56 /** Sometimes preferred to belief() for performance reasons.
57 * Faster implementations exist in e.g. BP.
58 */
59 virtual Factor beliefV( size_t i ) const { return belief( fg().var(i) ); }
60
61 /// Returns marginal for a factor.
62 /** Sometimes preferred to belief() for performance reasons.
63 * Faster implementations exist in e.g. BP.
64 */
65 virtual Factor beliefF( size_t I ) const { return belief( fg().factor(I).vars() ); }
66
67 /// Returns all "beliefs" (i.e., approximate marginal probability distribution) calculated by the algorithm
68 virtual std::vector<Factor> beliefs() const = 0;
69
70 /// Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph)
71 virtual Real logZ() const = 0;
72
73 /// Initializes all data structures of the approximate inference algorithm
74 /** This method should be called at least once before run() is called
75 */
76 virtual void init() = 0;
77
78 /// Initializes all data structures corresponding to some set of variables
79 /** This method can be used to do a partial initialization after a part of the factor graph has changed.
80 * Instead of initializing all data structures, it only initializes those involving the variables in ns.
81 */
82 virtual void init( const VarSet &ns ) = 0;
83
84 /// Runs the approximate inference algorithm
85 /* Before run() is called the first time, init() should be called.
86 * If run() returns successfully, the results can be queried using the methods belief(), beliefs() and logZ().
87 */
88 virtual double run() = 0;
89
90 /// Clamp variable with index i to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
91 /** If backup == true, make a backup of all factors that are changed
92 */
93 virtual void clamp( size_t i, size_t x, bool backup = false ) = 0;
94
95 // OBSOLETE
96 /// Only for backwards compatibility (to be removed soon)
97 virtual void clamp( const Var &v, size_t x, bool backup = false ) = 0;
98
99 /// Set all factors interacting with var(i) to 1
100 virtual void makeCavity( size_t i, bool backup = false ) = 0;
101
102 /// Return maximum difference between single node beliefs in the last pass
103 /// \throw Exception if not implemented/supported
104 virtual double maxDiff() const = 0;
105
106 /// Return number of passes over the factorgraph
107 /// \throw Exception if not implemented/supported
108 virtual size_t Iterations() const = 0;
109
110
111 /// Get reference to underlying FactorGraph
112 virtual FactorGraph &fg() = 0;
113
114 /// Get const reference to underlying FactorGraph
115 virtual const FactorGraph &fg() const = 0;
116
117 /// Save factor I
118 virtual void backupFactor( size_t I ) = 0;
119 /// Save Factors involving ns
120 virtual void backupFactors( const VarSet &ns ) = 0;
121
122 /// Restore factor I
123 virtual void restoreFactor( size_t I ) = 0;
124 /// Restore Factors involving ns
125 virtual void restoreFactors( const VarSet &ns ) = 0;
126 };
127
128
129 /// Combines an InfAlg and a graphical model, e.g., a FactorGraph or RegionGraph
130 /** \tparam GRM Should be castable to FactorGraph
131 * \todo A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should
132 * store a reference to the graphical model object. This prevents needless copying
133 * of (possibly large) data structures. Disadvantage: the caller must not change
134 * the graphical model between calls to the inference algorithm (maybe a smart_ptr
135 * or some locking mechanism would help here?).
136 */
137 template <class GRM>
138 class DAIAlg : public InfAlg, public GRM {
139 public:
140 /// Default constructor
141 DAIAlg() : InfAlg(), GRM() {}
142
143 /// Construct from GRM
144 DAIAlg( const GRM &grm ) : InfAlg(), GRM(grm) {}
145
146 /// Save factor I
147 void backupFactor( size_t I ) { GRM::backupFactor( I ); }
148 /// Save Factors involving ns
149 void backupFactors( const VarSet &ns ) { GRM::backupFactors( ns ); }
150
151 /// Restore factor I
152 void restoreFactor( size_t I ) { GRM::restoreFactor( I ); }
153 /// Restore Factors involving ns
154 void restoreFactors( const VarSet &ns ) { GRM::restoreFactors( ns ); }
155
156 /// Clamp variable with index i to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
157 void clamp( size_t i, size_t x, bool backup = false ) { GRM::clamp( i, x, backup ); }
158
159 // OBSOLETE
160 /// Only for backwards compatibility (to be removed soon)
161 void clamp( const Var &v, size_t x, bool backup = false ) {
162 GRM::clamp( v, x, backup );
163 std::cerr << "Warning: this DAIAlg<...>::clamp(const Var&,...) interface is obsolete!" << std::endl;
164 }
165
166 /// Set all factors interacting with var(i) to 1
167 void makeCavity( size_t i, bool backup = false ) { GRM::makeCavity( i, backup ); }
168
169 /// Get reference to underlying FactorGraph
170 FactorGraph &fg() { return (FactorGraph &)(*this); }
171
172 /// Get const reference to underlying FactorGraph
173 const FactorGraph &fg() const { return (const FactorGraph &)(*this); }
174 };
175
176
177 /// Base class for inference algorithms that operate on a FactorGraph
178 typedef DAIAlg<FactorGraph> DAIAlgFG;
179
180 /// Base class for inference algorithms that operate on a RegionGraph
181 typedef DAIAlg<RegionGraph> DAIAlgRG;
182
183
184 Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit );
185 std::vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reInit );
186 std::vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool reInit );
187 Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit );
188
189
190 } // end of namespace dai
191
192
193 #endif