2 Copyright 2009 Charles Vaske <cvaske@soe.ucsc.edu>
3 University of California Santa Cruz
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 #ifndef __defined_libdai_emalg_h
20 #define __defined_libdai_emalg_h
25 #include <dai/factor.h>
26 #include <dai/daialg.h>
27 #include <dai/evidence.h>
28 #include <dai/index.h>
29 #include <dai/properties.h>
33 /** \brief Defines classes related to Expectation Maximization:
34 * EMAlg, ParameterEstimate, and FactorOrientations
39 ///Interface for a parameter estimation method.
40 /** This parameter estimation interface is based on sufficient statistics.
41 * Implementations are responsible for collecting data from a probability
42 * vector passed to it from a SharedParameters container object.
44 * Implementations of this interface should register a factory function
45 * via the static ParameterEstimation::registerMethod function.
47 class ParameterEstimation
{
49 /// A pointer to a factory function.
50 typedef ParameterEstimation
* (*ParamEstFactory
)(const PropertySet
&);
52 /// General factory method for construction of ParameterEstimation subclasses.
53 static ParameterEstimation
* construct(const std::string
& method
,
54 const PropertySet
& p
);
55 /// Register a subclass with ParameterEstimation::construct.
56 static void registerMethod(const std::string method
,
57 const ParamEstFactory f
) {
58 if (_registry
== NULL
) {
59 loadDefaultRegistry();
61 (*_registry
)[method
] = f
;
63 /// Virtual destructor for deleting pointers to derived classes.
64 virtual ~ParameterEstimation() {}
65 /// Estimate the factor using the accumulated sufficient statistics and reset.
66 virtual Prob
estimate() = 0;
67 /// Accumulate the sufficient statistics for p.
68 virtual void addSufficientStatistics(Prob
& p
) = 0;
69 /// Returns the size of the Prob that is passed to addSufficientStatistics.
70 virtual size_t probSize() const = 0;
71 /// A virtual copy constructor.
72 virtual ParameterEstimation
* clone() const= 0;
74 static std::map
< std::string
, ParamEstFactory
>* _registry
;
75 static void loadDefaultRegistry();
78 /// Estimates the parameters of a conditional probability, using pseudocounts.
79 class CondProbEstimation
: private ParameterEstimation
{
85 /** For a conditional probability \f$ Pr( X | Y ) \f$,
86 * \param target_dimension should equal \f$ | X | \f$
87 * \param pseudocounts has length \f$ |X| \cdot |Y| \f$
89 CondProbEstimation(size_t target_dimension
, Prob pseudocounts
);
91 /// Virtual constructor, using a PropertySet.
92 /** Some keys in the PropertySet are required:
93 * - target_dimension, which should be equal to \f$ | X | \f$
94 * - total_dimension, which sholud be equal to \f$ |X| \cdot |Y| \f$
97 * - pseudo_count which specifies the initial counts (defaults to 1)
99 static ParameterEstimation
* factory(const PropertySet
& p
);
100 /// Virtual destructor
101 virtual ~CondProbEstimation() {}
102 /// Returns an estimate of the conditional probability distribution.
103 /** The format of the resulting Prob keeps all the values for
104 * \f$ P(X | Y=a) \f$ sequential in teh array.
106 virtual Prob
estimate();
107 /// Accumulate sufficient statistics from the expectations in p.
108 virtual void addSufficientStatistics(Prob
& p
);
109 /// Returns the required size for arguments to addSufficientStatistics
110 virtual size_t probSize() const { return _stats
.size(); }
111 /// Virtual copy constructor.
112 virtual ParameterEstimation
* clone() const {
113 return new CondProbEstimation(_target_dim
, _initial_stats
);
117 /** A single factor or set of factors whose parameters should be
118 * estimated. Each factor's values are reordered to match a
119 * canonical variable ordering. This canonical variable ordering
120 * will likely not be the order of variables required to make two
121 * factors parameters isomorphic. Therefore, this ordering of the
122 * variables must be specified for ever factor to ensure that
123 * parameters can be shared between different factors during EM.
125 class SharedParameters
{
127 /// Convenience label for an index into a FactorGraph to a factor.
128 typedef size_t FactorIndex
;
129 /// Convenience label for a grouping of factor orientations.
130 typedef std::map
< FactorIndex
, std::vector
< Var
> > FactorOrientations
;
132 std::map
< FactorIndex
, VarSet
> _varsets
;
133 std::map
< FactorIndex
, Permute
> _perms
;
134 FactorOrientations _varorders
;
135 ParameterEstimation
* _estimation
;
136 bool _deleteEstimation
;
138 static Permute
calculatePermutation(const std::vector
< Var
>& varorder
,
139 const std::vector
< size_t >& dims
,
141 void setPermsAndVarSetsFromVarOrders();
144 SharedParameters(const SharedParameters
& sp
);
145 /// Constructor useful in programmatic settings
146 /** \param varorders all the factor orientations for this parameter
147 \param estimation a pointer to the parameter estimation method
149 SharedParameters(const FactorOrientations
& varorders
,
150 ParameterEstimation
* estimation
);
152 /// Constructor for making an object from a stream
153 SharedParameters(std::istream
& is
, const FactorGraph
& fg_varlookup
);
156 ~SharedParameters() { if (_deleteEstimation
) delete _estimation
; }
158 /// Collect the necessary statistics from expected values
159 void collectSufficientStatistics(InfAlg
& alg
);
161 /// Estimate and set the shared parameters
162 void setParameters(FactorGraph
& fg
);
165 /** A maximization step groups together several parameter estimation
166 * tasks into a single unit.
168 class MaximizationStep
{
170 std::vector
< SharedParameters
> _params
;
172 MaximizationStep() : _params() {}
174 /// Construct an step object taht contains all these estimation probelms
175 MaximizationStep(std::vector
< SharedParameters
>& maximizations
) :
176 _params(maximizations
) {}
178 /// Construct a step from an input stream
179 MaximizationStep(std::istream
& is
, const FactorGraph
& fg_varlookup
);
181 /** Collect the beliefs from this InfAlg as expectations for
182 * the next Maximization step.
184 void addExpectations(InfAlg
& alg
);
186 /** Using all of the currently added expectations, make new factors
187 * with maximized parameters and set them in the FactorGraph.
189 void maximize(FactorGraph
& fg
);
192 /// EMAlg performs Expectation Maximization to learn factor parameters.
193 /** This requires specifying:
194 * - Evidence (instances of observations from the graphical model),
195 * - InfAlg for performing the E-step, which includes the factor graph
196 * - a vector of MaximizationSteps steps to be performed
198 * This implementation can peform incremental EM by using multiple
199 * MaximizationSteps. An expectation step is performed between execution
200 * of each MaximizationStep. A call to iterate() will cycle through all
205 /// All the data samples used during learning
206 const Evidence
& _evidence
;
208 /// How to do the expectation step
211 /// The maximization steps to take
212 std::vector
<MaximizationStep
> _msteps
;
214 std::vector
<Real
> _lastLogZ
;
220 /// Key for setting maximum iterations @see setTermConditions
221 static const std::string MAX_ITERS_KEY
;//("max_iters");
222 /// Default maximum iterations
223 static const size_t MAX_ITERS_DEFAULT
;
224 /// Key for setting likelihood termination condition @see setTermConditions
225 static const std::string LOG_Z_TOL_KEY
;
226 /// Default log_z_tol
227 static const Real LOG_Z_TOL_DEFAULT
;
229 /// Construct an EMAlg from all these objects
230 EMAlg(const Evidence
& evidence
, InfAlg
& estep
,
231 std::vector
<MaximizationStep
>& msteps
,
232 PropertySet
* termconditions
=NULL
)
233 : _evidence(evidence
),
238 _max_iters(MAX_ITERS_DEFAULT
),
239 _log_z_tol(LOG_Z_TOL_DEFAULT
) {
240 setTermConditions(termconditions
);
243 /// Construct an EMAlg from an input stream
244 EMAlg(const Evidence
& evidence
, InfAlg
& estep
, std::istream
& mstep_file
);
246 /// Change the coditions for termination
247 /** There are two possible parameters in the PropertySety
248 * - max_iters maximum number of iterations (default 30)
249 * - log_z_tol proportion of increase in logZ (default 0.01)
251 * \see hasSatisifiedTermConditions()
253 void setTermConditions(const PropertySet
* p
);
255 /// Determine if the termination conditions have been met.
256 /** There are two sufficient termination conditions:
257 * -# the maximum number of iterations has been performed
258 * -# the ratio of logZ increase over previous logZ is less than the
260 \f$ \frac{\log(Z_{current}) - \log(Z_{previous})}
261 {| \log(Z_{previous}) | } < tol \f$.
263 bool hasSatisfiedTermConditions() const;
265 size_t getCurrentIters() const { return _iters
; }
267 /// Perform an iteration over all maximization steps
270 /// Performs an iteration over a single MaximizationStep
271 Real
iterate(MaximizationStep
& mstep
);
273 /// Iterate until termination conditions satisfied