* [\ref MoK07, \ref MoR05];
* - Gibbs sampler.
*
+ * In addition, libDAI supports parameter learning of conditional probability
+ * tables by Expectation Maximization.
+ *
* \section language Why C++?
* Because libDAI is implemented in C++, it is very fast compared with
* implementations in MatLab (a factor 1000 faster is not uncommon).
*/
-/** \page biboliography Bibliography
+/** \page bibliography Bibliography
* \section Bibliograpy
* \anchor KFL01 \ref KFL01
* F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
#include <dai/properties.h>
-/// \file
-/** \brief Defines classes related to Expectation Maximization:
- * EMAlg, ParameterEstimation, CondProbEstimation and SharedParameters
- */
+/// \file
+/// \brief Defines classes related to Expectation Maximization: EMAlg, ParameterEstimation, CondProbEstimation and SharedParameters
+/// \todo Describe EM file format
namespace dai {
*
* Implementations of this interface should register a factory function
* via the static ParameterEstimation::registerMethod function.
+ * The default registry only contains CondProbEstimation, named
+ * "ConditionalProbEstimation".
*/
class ParameterEstimation {
public:
/// A pointer to a factory function.
- typedef ParameterEstimation* (*ParamEstFactory)(const PropertySet&);
+ typedef ParameterEstimation* (*ParamEstFactory)( const PropertySet& );
+
+ /// Virtual destructor for deleting pointers to derived classes.
+ virtual ~ParameterEstimation() {}
+ /// Virtual copy constructor.
+ virtual ParameterEstimation* clone() const = 0;
/// General factory method for construction of ParameterEstimation subclasses.
- static ParameterEstimation* construct( const std::string& method, const PropertySet& p );
- /// Register a subclass with ParameterEstimation::construct.
- static void registerMethod( const std::string method, const ParamEstFactory f ) {
+ static ParameterEstimation* construct( const std::string &method, const PropertySet &p );
+
+ /// Register a subclass so that it can be used with ParameterEstimation::construct.
+ static void registerMethod( const std::string &method, const ParamEstFactory &f ) {
if( _registry == NULL )
loadDefaultRegistry();
(*_registry)[method] = f;
}
- /// Virtual destructor for deleting pointers to derived classes.
- virtual ~ParameterEstimation() {}
+
/// Estimate the factor using the accumulated sufficient statistics and reset.
virtual Prob estimate() = 0;
+
/// Accumulate the sufficient statistics for p.
- virtual void addSufficientStatistics( Prob& p ) = 0;
- /// Returns the size of the Prob that is passed to addSufficientStatistics.
+ virtual void addSufficientStatistics( const Prob &p ) = 0;
+
+ /// Returns the size of the Prob that should be passed to addSufficientStatistics.
virtual size_t probSize() const = 0;
- /// A virtual copy constructor.
- virtual ParameterEstimation* clone() const = 0;
private:
- static std::map<std::string, ParamEstFactory>* _registry;
+ /// A static registry containing all methods registered so far.
+ static std::map<std::string, ParamEstFactory> *_registry;
+
+ /// Registers default ParameterEstimation subclasses (currently, only CondProbEstimation).
static void loadDefaultRegistry();
};
-/// Estimates the parameters of a conditional probability, using pseudocounts.
+/// Estimates the parameters of a conditional probability table, using pseudocounts.
class CondProbEstimation : private ParameterEstimation {
private:
+ /// Number of states of the variable of interest
size_t _target_dim;
+ /// Current pseudocounts
Prob _stats;
+ /// Initial pseudocounts
Prob _initial_stats;
+
public:
- /** For a conditional probability \f$ Pr( X | Y ) \f$,
+ /// Constructor
+ /** For a conditional probability \f$ P( X | Y ) \f$,
* \param target_dimension should equal \f$ | X | \f$
* \param pseudocounts has length \f$ |X| \cdot |Y| \f$
*/
- CondProbEstimation( size_t target_dimension, Prob pseudocounts );
+ CondProbEstimation( size_t target_dimension, const Prob &pseudocounts );
/// Virtual constructor, using a PropertySet.
- /** Some keys in the PropertySet are required:
- * - target_dimension, which should be equal to \f$ | X | \f$
- * - total_dimension, which should be equal to \f$ |X| \cdot |Y| \f$
+ /** Some keys in the PropertySet are required.
+ * For a conditional probability \f$ P( X | Y ) \f$,
+ * - target_dimension should be equal to \f$ | X | \f$
+ * - total_dimension should be equal to \f$ |X| \cdot |Y| \f$
*
* An optional key is:
* - pseudo_count, which specifies the initial counts (defaults to 1)
*/
- static ParameterEstimation* factory( const PropertySet& p );
+ static ParameterEstimation* factory( const PropertySet &p );
+
+ /// Virtual copy constructor
+ virtual ParameterEstimation* clone() const { return new CondProbEstimation( _target_dim, _initial_stats ); }
+
/// Virtual destructor
virtual ~CondProbEstimation() {}
+
/// Returns an estimate of the conditional probability distribution.
/** The format of the resulting Prob keeps all the values for
- * \f$ P(X | Y=a) \f$ sequential in the array.
+ * \f$ P(X | Y=y) \f$ in sequential order in the array.
*/
virtual Prob estimate();
+
/// Accumulate sufficient statistics from the expectations in p.
- virtual void addSufficientStatistics( Prob& p );
- /// Returns the required size for arguments to addSufficientStatistics
- virtual size_t probSize() const {
- return _stats.size();
- }
- /// Virtual copy constructor.
- virtual ParameterEstimation* clone() const {
- return new CondProbEstimation( _target_dim, _initial_stats );
- }
+ virtual void addSufficientStatistics( const Prob &p );
+
+ /// Returns the required size for arguments to addSufficientStatistics.
+ virtual size_t probSize() const { return _stats.size(); }
};
-/** A single factor or set of factors whose parameters should be
- * estimated. Each factor's values are reordered to match a
- * canonical variable ordering. This canonical variable ordering
- * will likely not be the order of variables required to make two
- * factors parameters isomorphic. Therefore, this ordering of the
- * variables must be specified for each factory to ensure that
- * parameters can be shared between different factors during EM.
+/// A single factor or set of factors whose parameters should be estimated.
+/** To ensure that parameters can be shared between different factors during
+ * EM learning, each factor's values are reordered to match a desired variable
+ * ordering. The ordering of the variables in a factor may therefore differ
+ * from the canonical ordering used in libDAI. The SharedParameters
+ * class couples one or more factors (together with the specified orderings
+ * of the variables) with a ParameterEstimation object, taking care of the
+ * necessary permutations of the factor entries / parameters.
*/
class SharedParameters {
public:
- /// Convenience label for an index into a FactorGraph to a factor.
+ /// Convenience label for an index into a factor in a FactorGraph.
typedef size_t FactorIndex;
/// Convenience label for a grouping of factor orientations.
- typedef std::map< FactorIndex, std::vector< Var > > FactorOrientations;
+ typedef std::map<FactorIndex, std::vector<Var> > FactorOrientations;
+
private:
+ /// Maps factor indices to the corresponding VarSets
std::map<FactorIndex, VarSet> _varsets;
+ /// Maps factor indices to the corresponding Permute objects that permute the desired ordering into the canonical ordering
std::map<FactorIndex, Permute> _perms;
+ /// Maps factor indices to the corresponding desired variable orderings
FactorOrientations _varorders;
- ParameterEstimation* _estimation;
+ /// Parameter estimation method to be used
+ ParameterEstimation *_estimation;
+ /// Indicates whether the object pointed to by _estimation should be deleted upon destruction
bool _deleteEstimation;
/// Calculates the permutation that permutes the variables in varorder into the canonical ordering
- static Permute calculatePermutation( const std::vector<Var>& varorder, VarSet& outVS );
+ static Permute calculatePermutation( const std::vector<Var> &varorder, VarSet &outVS );
+
/// Initializes _varsets and _perms from _varorders
void setPermsAndVarSetsFromVarOrders();
public:
/// Copy constructor
- SharedParameters( const SharedParameters& sp );
- /// Constructor useful in programmatic settings
+ SharedParameters( const SharedParameters &sp );
+
+ /// Constructor
/** \param varorders all the factor orientations for this parameter
* \param estimation a pointer to the parameter estimation method
*/
- SharedParameters( const FactorOrientations& varorders, ParameterEstimation* estimation );
+ SharedParameters( const FactorOrientations &varorders, ParameterEstimation *estimation );
- /// Constructor for making an object from a stream
- SharedParameters( std::istream& is, const FactorGraph& fg_varlookup );
+ /// Constructor for making an object from a stream and a factor graph
+ SharedParameters( std::istream &is, const FactorGraph &fg_varlookup );
/// Destructor
~SharedParameters() {
}
/// Collect the necessary statistics from expected values
- void collectSufficientStatistics( InfAlg& alg );
+ void collectSufficientStatistics( InfAlg &alg );
/// Estimate and set the shared parameters
- void setParameters( FactorGraph& fg );
+ void setParameters( FactorGraph &fg );
};
-/** A maximization step groups together several parameter estimation
- * tasks into a single unit.
- */
+/// A MaximizationStep groups together several parameter estimation tasks into a single unit.
class MaximizationStep {
private:
std::vector<SharedParameters> _params;
+
public:
/// Default constructor
MaximizationStep() : _params() {}
- /// Construct a step object that contains all these estimation problems
- MaximizationStep( std::vector<SharedParameters>& maximizations ) : _params(maximizations) {}
+ /// Constructor from a vector of SharedParameters objects
+ MaximizationStep( std::vector<SharedParameters> &maximizations ) : _params(maximizations) {}
- /// Construct a step from an input stream
- MaximizationStep( std::istream& is, const FactorGraph& fg_varlookup );
+ /// Constructor from an input stream and a corresponding factor graph
+ MaximizationStep( std::istream &is, const FactorGraph &fg_varlookup );
- /** Collect the beliefs from this InfAlg as expectations for
- * the next Maximization step.
- */
- void addExpectations( InfAlg& alg );
+ /// Collect the beliefs from this InfAlg as expectations for the next Maximization step.
+ void addExpectations( InfAlg &alg );
- /** Using all of the currently added expectations, make new factors
- * with maximized parameters and set them in the FactorGraph.
- */
- void maximize( FactorGraph& fg );
+ /// Using all of the currently added expectations, make new factors with maximized parameters and set them in the FactorGraph.
+ void maximize( FactorGraph &fg );
};
/// EMAlg performs Expectation Maximization to learn factor parameters.
/** This requires specifying:
* - Evidence (instances of observations from the graphical model),
- * - InfAlg for performing the E-step, which includes the factor graph
- * - a vector of MaximizationSteps steps to be performed
+ * - InfAlg for performing the E-step, which includes the factor graph,
+ * - a vector of MaximizationSteps steps to be performed.
*
* This implementation can perform incremental EM by using multiple
* MaximizationSteps. An expectation step is performed between execution
class EMAlg {
private:
/// All the data samples used during learning
- const Evidence& _evidence;
+ const Evidence &_evidence;
/// How to do the expectation step
- InfAlg& _estep;
+ InfAlg &_estep;
/// The maximization steps to take
std::vector<MaximizationStep> _msteps;
public:
/// Key for setting maximum iterations @see setTermConditions
- static const std::string MAX_ITERS_KEY; //("max_iters");
- /// Default maximum iterations
+ static const std::string MAX_ITERS_KEY;
+ /// Default maximum iterations @see setTermConditions
static const size_t MAX_ITERS_DEFAULT;
/// Key for setting likelihood termination condition @see setTermConditions
static const std::string LOG_Z_TOL_KEY;
- /// Default log_z_tol
+ /// Default likelihood tolerance @see setTermConditions
static const Real LOG_Z_TOL_DEFAULT;
/// Construct an EMAlg from all these objects
- EMAlg( const Evidence& evidence, InfAlg& estep, std::vector<MaximizationStep>& msteps, const PropertySet &termconditions ) :
- _evidence(evidence), _estep(estep), _msteps(msteps), _iters(0), _lastLogZ(), _max_iters(MAX_ITERS_DEFAULT), _log_z_tol(LOG_Z_TOL_DEFAULT) {
+ EMAlg( const Evidence &evidence, InfAlg &estep, std::vector<MaximizationStep> &msteps, const PropertySet &termconditions )
+ : _evidence(evidence), _estep(estep), _msteps(msteps), _iters(0), _lastLogZ(), _max_iters(MAX_ITERS_DEFAULT), _log_z_tol(LOG_Z_TOL_DEFAULT)
+ {
setTermConditions( termconditions );
}
- /// Construct an EMAlg from an input stream
- EMAlg( const Evidence& evidence, InfAlg& estep, std::istream& mstep_file );
+ /// Construct an EMAlg from an Evidence object, an InfAlg object, and an input stream
+ EMAlg( const Evidence &evidence, InfAlg &estep, std::istream &mstep_file );
/// Change the conditions for termination
/** There are two possible parameters in the PropertySet
- * - max_iters maximum number of iterations (default 30)
- * - log_z_tol proportion of increase in logZ (default 0.01)
+ * - max_iters maximum number of iterations
+ * - log_z_tol proportion of increase in logZ
*
* \see hasSatisifiedTermConditions()
*/
/** There are two sufficient termination conditions:
* -# the maximum number of iterations has been performed
* -# the ratio of logZ increase over previous logZ is less than the
- * tolerance. I.e.
- \f$ \frac{\log(Z_{current}) - \log(Z_{previous})}
- {| \log(Z_{previous}) | } < tol \f$.
+ * tolerance, i.e.,
+ * \f$ \frac{\log(Z_t) - \log(Z_{t-1})}{| \log(Z_{t-1}) | } < \mathrm{tol} \f$.
*/
bool hasSatisfiedTermConditions() const;
/// Returns number of iterations done so far
- size_t getCurrentIters() const {
- return _iters;
- }
+ size_t getCurrentIters() const { return _iters; }
/// Perform an iteration over all maximization steps
Real iterate();
- /// Performs an iteration over a single MaximizationStep
- Real iterate( MaximizationStep& mstep );
+ /// Perform an iteration over a single MaximizationStep
+ Real iterate( MaximizationStep &mstep );
- /// Iterate until termination conditions satisfied
+ /// Iterate until termination conditions are satisfied
void run();
};
/// \file
/// \brief Defines classes Evidence and Observation
-/// \todo Improve documentation
+/// \todo Describe tabular data file format
#ifndef __defined_libdai_evidence_h
/// Stores observed values of a subset of variables
class Observation {
private:
+ /// Used to store the state of some variables
std::map<Var, size_t> _obs;
public:
/// Default constructor
Observation() : _obs() {}
+
/// Get all observations
const std::map<Var, size_t>& observations() const { return _obs; }
+
/// Add an observation
void addObservation( Var node, size_t setting );
- /// Clamp variables to observed values
+
+ /// Clamp variables in the graphical model to their observed values
void applyEvidence( InfAlg& alg ) const;
};
-/// Stores multiple observations of variables
-/** The Evidence class contains multiple samples, where a sample is the joint
+/// Stores multiple joint observations of sets of variables.
+/** The Evidence class stores multiple samples, where each sample is the joint
* observation of the states of some variables.
*/
class Evidence {
private:
+ /// Each sample is the joint observation of the states of some variables
std::vector<Observation> _samples;
public:
/// Default constructor
Evidence() : _samples() {}
- /** Read in tab-data from a stream. Each line contains one sample, and
- * the first line is a header line with names.
+ /// Read in tabular data from a stream.
+ /** Each line contains one sample, and the first line is a header line with names.
*/
- void addEvidenceTabFile(std::istream& is, std::map<std::string, Var>& varMap);
+ void addEvidenceTabFile( std::istream& is, std::map<std::string, Var> &varMap );
- /** Read in tab-data from a stream. Each line contains one sample,
- * and the first line is a header line with variable labels.
+ /// Read in tabular data from a stream.
+ /** Each line contains one sample, and the first line is a header line with
+ * variable labels which should correspond with a subset of the variables in fg.
*/
- void addEvidenceTabFile(std::istream& is, FactorGraph& fg);
+ void addEvidenceTabFile( std::istream& is, FactorGraph& fg );
- /// Returns total number of samples
+ /// Returns number of stored samples
size_t nrSamples() const { return _samples.size(); }
- /// @name iterator interface
+ /// @name Iterator interface
//@{
+ /// Iterator over the elements
typedef std::vector<Observation>::iterator iterator;
+ /// Constant iterator over the elements
typedef std::vector<Observation>::const_iterator const_iterator;
+ /// Returns iterator that points to the first element
iterator begin() { return _samples.begin(); }
+ /// Returns constant iterator that points to the first element
const_iterator begin() const { return _samples.begin(); }
+ /// Returns iterator that points beyond the last element
iterator end() { return _samples.end(); }
+ /// Returns constant iterator that points beyond the last element
const_iterator end() const { return _samples.end(); }
//@}
};
void ParameterEstimation::loadDefaultRegistry() {
- _registry = new std::map< std::string, ParamEstFactory>();
+ _registry = new std::map<std::string, ParamEstFactory>();
(*_registry)["ConditionalProbEstimation"] = CondProbEstimation::factory;
}
-ParameterEstimation* ParameterEstimation::construct( const std::string& method, const PropertySet& p ) {
- if (_registry == NULL)
+ParameterEstimation* ParameterEstimation::construct( const std::string &method, const PropertySet &p ) {
+ if( _registry == NULL )
loadDefaultRegistry();
- std::map< std::string, ParamEstFactory>::iterator i = _registry->find(method);
- if (i == _registry->end())
+ std::map<std::string, ParamEstFactory>::iterator i = _registry->find(method);
+ if( i == _registry->end() )
DAI_THROW(UNKNOWN_PARAMETER_ESTIMATION_METHOD);
ParamEstFactory factory = i->second;
return factory(p);
}
-ParameterEstimation* CondProbEstimation::factory( const PropertySet& p ) {
- size_t target_dimension = p.getStringAs<size_t>("target_dim");
+ParameterEstimation* CondProbEstimation::factory( const PropertySet &p ) {
+ size_t target_dimension = p.getStringAs<size_t>("target_dim");
size_t total_dimension = p.getStringAs<size_t>("total_dim");
Real pseudo_count = 1;
- if (p.hasKey("pseudo_count"))
+ if( p.hasKey("pseudo_count") )
pseudo_count = p.getStringAs<Real>("pseudo_count");
- Prob counts_vec(total_dimension, pseudo_count);
- return new CondProbEstimation(target_dimension, counts_vec);
+ return new CondProbEstimation( target_dimension, Prob( total_dimension, pseudo_count ) );
}
-CondProbEstimation::CondProbEstimation( size_t target_dimension, Prob pseudocounts )
+CondProbEstimation::CondProbEstimation( size_t target_dimension, const Prob &pseudocounts )
: _target_dim(target_dimension), _stats(pseudocounts), _initial_stats(pseudocounts)
{
- if (_stats.size() % _target_dim)
+ if( _stats.size() % _target_dim )
DAI_THROW(MALFORMED_PROPERTY);
}
-void CondProbEstimation::addSufficientStatistics( Prob& p ) {
+void CondProbEstimation::addSufficientStatistics( const Prob &p ) {
_stats += p;
}
Prob CondProbEstimation::estimate() {
- for (size_t parent = 0; parent < _stats.size(); parent += _target_dim) {
- Real norm = 0;
+ // normalize pseudocounts
+ for( size_t parent = 0; parent < _stats.size(); parent += _target_dim ) {
+ // calculate norm
+ Real norm = 0.0;
size_t top = parent + _target_dim;
- for (size_t i = parent; i < top; ++i)
+ for( size_t i = parent; i < top; ++i )
norm += _stats[i];
- if (norm != 0)
- norm = 1 / norm;
- for (size_t i = parent; i < top; ++i)
+ if( norm != 0.0 )
+ norm = 1.0 / norm;
+ // normalize
+ for( size_t i = parent; i < top; ++i )
_stats[i] *= norm;
}
+ // reset _stats to _initial_stats
Prob result = _stats;
_stats = _initial_stats;
return result;
}
-Permute SharedParameters::calculatePermutation( const std::vector< Var >& varorder, VarSet& outVS ) {
- std::vector<size_t> dims;
- std::vector<long> labels;
-
+Permute SharedParameters::calculatePermutation( const std::vector<Var> &varorder, VarSet &outVS ) {
// Collect all labels and dimensions, and order them in vs
+ std::vector<size_t> dims;
dims.reserve( varorder.size() );
+ std::vector<long> labels;
labels.reserve( varorder.size() );
for( size_t i = 0; i < varorder.size(); i++ ) {
dims.push_back( varorder[i].states() );
// Construct the sigma array for the permutation object
std::vector<size_t> sigma;
sigma.reserve( dims.size() );
- for (VarSet::iterator set_iterator = outVS.begin(); sigma.size() < dims.size(); ++set_iterator)
+ for( VarSet::iterator set_iterator = outVS.begin(); sigma.size() < dims.size(); ++set_iterator )
sigma.push_back( find(labels.begin(), labels.end(), set_iterator->label()) - labels.begin() );
- return Permute(dims, sigma);
+ return Permute( dims, sigma );
}
void SharedParameters::setPermsAndVarSetsFromVarOrders() {
- if (_varorders.size() == 0)
+ if( _varorders.size() == 0 )
return;
if( _estimation == NULL )
DAI_THROW(INVALID_SHARED_PARAMETERS_ORDER);
// Construct the permutation objects and the varsets
for( FactorOrientations::const_iterator foi = _varorders.begin(); foi != _varorders.end(); ++foi ) {
VarSet vs;
- _perms[foi->first] = calculatePermutation(foi->second, vs);
+ _perms[foi->first] = calculatePermutation( foi->second, vs );
_varsets[foi->first] = vs;
if( _estimation->probSize() != vs.nrStates() )
DAI_THROW(INVALID_SHARED_PARAMETERS_ORDER);
}
-SharedParameters::SharedParameters(std::istream& is, const FactorGraph& fg_varlookup)
+SharedParameters::SharedParameters( std::istream &is, const FactorGraph &fg_varlookup )
: _varsets(), _perms(), _varorders(), _estimation(NULL), _deleteEstimation(true)
{
+ // Read the desired parameter estimation method from the stream
std::string est_method;
PropertySet props;
is >> est_method;
is >> props;
- _estimation = ParameterEstimation::construct(est_method, props);
+ // Construct a corresponding object
+ _estimation = ParameterEstimation::construct( est_method, props );
+ // Read in the factors that are to be estimated
size_t num_factors;
is >> num_factors;
for( size_t sp_i = 0; sp_i < num_factors; ++sp_i ) {
std::string line;
- while(line.size() == 0 && getline(is, line))
+ while( line.size() == 0 && getline(is, line) )
;
- std::vector< std::string > fields;
+ std::vector<std::string> fields;
tokenizeString(line, fields, " \t");
// Lookup the factor in the factorgraph
- if (fields.size() < 1)
+ if( fields.size() < 1 )
DAI_THROW(INVALID_SHARED_PARAMETERS_INPUT_LINE);
std::istringstream iss;
- iss.str(fields[0]);
+ iss.str( fields[0] );
size_t factor;
iss >> factor;
- const VarSet& vs = fg_varlookup.factor(factor).vars();
- if (fields.size() != vs.size() + 1)
+ const VarSet &vs = fg_varlookup.factor(factor).vars();
+ if( fields.size() != vs.size() + 1 )
DAI_THROW(INVALID_SHARED_PARAMETERS_INPUT_LINE);
// Construct the vector of Vars
- std::vector< Var > var_order;
+ std::vector<Var> var_order;
var_order.reserve( vs.size() );
- for (size_t fi = 1; fi < fields.size(); ++fi) {
+ for( size_t fi = 1; fi < fields.size(); ++fi ) {
// Lookup a single variable by label
long label;
- std::istringstream labelparse(fields[fi]);
+ std::istringstream labelparse( fields[fi] );
labelparse >> label;
VarSet::const_iterator vsi = vs.begin();
- for ( ; vsi != vs.end(); ++vsi)
- if (vsi->label() == label)
+ for( ; vsi != vs.end(); ++vsi )
+ if( vsi->label() == label )
break;
- if (vsi == vs.end())
+ if( vsi == vs.end() )
DAI_THROW(INVALID_SHARED_PARAMETERS_INPUT_LINE);
- var_order.push_back(*vsi);
+ var_order.push_back( *vsi );
}
_varorders[factor] = var_order;
}
+
+ // Calculate the necessary permutations
setPermsAndVarSetsFromVarOrders();
}
-SharedParameters::SharedParameters( const SharedParameters& sp )
+SharedParameters::SharedParameters( const SharedParameters &sp )
: _varsets(sp._varsets), _perms(sp._perms), _varorders(sp._varorders), _estimation(sp._estimation), _deleteEstimation(sp._deleteEstimation)
{
- if (_deleteEstimation)
+ // If sp owns its _estimation object, we should clone it instead
+ if( _deleteEstimation )
_estimation = _estimation->clone();
}
-SharedParameters::SharedParameters( const FactorOrientations& varorders, ParameterEstimation* estimation )
+SharedParameters::SharedParameters( const FactorOrientations &varorders, ParameterEstimation *estimation )
: _varsets(), _perms(), _varorders(varorders), _estimation(estimation), _deleteEstimation(false)
{
+ // Calculate the necessary permutations
setPermsAndVarSetsFromVarOrders();
}
-void SharedParameters::collectSufficientStatistics(InfAlg& alg) {
- for ( std::map< FactorIndex, Permute >::iterator i = _perms.begin(); i != _perms.end(); ++i) {
- Permute& perm = i->second;
- VarSet& vs = _varsets[i->first];
+void SharedParameters::collectSufficientStatistics( InfAlg &alg ) {
+ for( std::map< FactorIndex, Permute >::iterator i = _perms.begin(); i != _perms.end(); ++i ) {
+ Permute &perm = i->second;
+ VarSet &vs = _varsets[i->first];
Factor b = alg.belief(vs);
- Prob p(b.states(), 0.0);
- for (size_t entry = 0; entry < b.states(); ++entry)
+ Prob p( b.states(), 0.0 );
+ for( size_t entry = 0; entry < b.states(); ++entry )
p[entry] = b[perm.convert_linear_index(entry)];
- _estimation->addSufficientStatistics(p);
+ _estimation->addSufficientStatistics( p );
}
}
-void SharedParameters::setParameters(FactorGraph& fg) {
+void SharedParameters::setParameters( FactorGraph &fg ) {
Prob p = _estimation->estimate();
- for ( std::map< FactorIndex, Permute >::iterator i = _perms.begin(); i != _perms.end(); ++i) {
- Permute& perm = i->second;
- VarSet& vs = _varsets[i->first];
+ for( std::map<FactorIndex, Permute>::iterator i = _perms.begin(); i != _perms.end(); ++i ) {
+ Permute &perm = i->second;
+ VarSet &vs = _varsets[i->first];
- Factor f(vs, 0.0);
- for (size_t entry = 0; entry < f.states(); ++entry)
+ Factor f( vs, 0.0 );
+ for( size_t entry = 0; entry < f.states(); ++entry )
f[perm.convert_linear_index(entry)] = p[entry];
- fg.setFactor(i->first, f);
+ fg.setFactor( i->first, f );
}
}
-MaximizationStep::MaximizationStep( std::istream& is, const FactorGraph& fg_varlookup )
- : _params()
-{
+MaximizationStep::MaximizationStep( std::istream &is, const FactorGraph &fg_varlookup ) : _params() {
size_t num_params = -1;
is >> num_params;
- _params.reserve(num_params);
- for (size_t i = 0; i < num_params; ++i)
+ _params.reserve( num_params );
+ for( size_t i = 0; i < num_params; ++i )
_params.push_back( SharedParameters( is, fg_varlookup ) );
}
-void MaximizationStep::addExpectations(InfAlg& alg) {
- for (size_t i = 0; i < _params.size(); ++i)
- _params[i].collectSufficientStatistics(alg);
+void MaximizationStep::addExpectations( InfAlg &alg ) {
+ for( size_t i = 0; i < _params.size(); ++i )
+ _params[i].collectSufficientStatistics( alg );
}
-void MaximizationStep::maximize(FactorGraph& fg) {
- for (size_t i = 0; i < _params.size(); ++i)
- _params[i].setParameters(fg);
+void MaximizationStep::maximize( FactorGraph &fg ) {
+ for( size_t i = 0; i < _params.size(); ++i )
+ _params[i].setParameters( fg );
}
const Real EMAlg::LOG_Z_TOL_DEFAULT = 0.01;
-EMAlg::EMAlg(const Evidence& evidence, InfAlg& estep, std::istream& msteps_file)
+EMAlg::EMAlg( const Evidence &evidence, InfAlg &estep, std::istream &msteps_file )
: _evidence(evidence), _estep(estep), _msteps(), _iters(0), _lastLogZ(), _max_iters(MAX_ITERS_DEFAULT), _log_z_tol(LOG_Z_TOL_DEFAULT)
{
msteps_file.exceptions( std::istream::eofbit | std::istream::failbit | std::istream::badbit );
size_t num_msteps = -1;
msteps_file >> num_msteps;
_msteps.reserve(num_msteps);
- for (size_t i = 0; i < num_msteps; ++i)
+ for( size_t i = 0; i < num_msteps; ++i )
_msteps.push_back( MaximizationStep( msteps_file, estep.fg() ) );
}
-void EMAlg::setTermConditions(const PropertySet &p) {
- if (p.hasKey(MAX_ITERS_KEY))
+void EMAlg::setTermConditions( const PropertySet &p ) {
+ if( p.hasKey(MAX_ITERS_KEY) )
_max_iters = p.getStringAs<size_t>(MAX_ITERS_KEY);
- if (p.hasKey(LOG_Z_TOL_KEY))
+ if( p.hasKey(LOG_Z_TOL_KEY) )
_log_z_tol = p.getStringAs<Real>(LOG_Z_TOL_KEY);
}
bool EMAlg::hasSatisfiedTermConditions() const {
- if (_iters >= _max_iters) {
+ if( _iters >= _max_iters )
return true;
- } else if (_lastLogZ.size() < 3) {
+ else if( _lastLogZ.size() < 3 )
// need at least 2 to calculate ratio
// Also, throw away first iteration, as the parameters may not
// have been normalized according to the estimation method
return false;
- } else {
+ else {
Real current = _lastLogZ[_lastLogZ.size() - 1];
Real previous = _lastLogZ[_lastLogZ.size() - 2];
- if (previous == 0)
+ if( previous == 0 )
return false;
Real diff = current - previous;
- if (diff < 0) {
+ if( diff < 0 ) {
std::cerr << "Error: in EM log-likehood decreased from " << previous << " to " << current << std::endl;
return true;
}
}
-Real EMAlg::iterate( MaximizationStep& mstep ) {
+Real EMAlg::iterate( MaximizationStep &mstep ) {
Real logZ = 0;
// Expectation calculation
for( Evidence::const_iterator e = _evidence.begin(); e != _evidence.end(); ++e ) {
InfAlg* clamped = _estep.clone();
- e->applyEvidence(*clamped);
+ e->applyEvidence( *clamped );
clamped->init();
clamped->run();
logZ += clamped->logZ();
- mstep.addExpectations(*clamped);
+ mstep.addExpectations( *clamped );
delete clamped;
}
// Maximization of parameters
- mstep.maximize(_estep.fg());
+ mstep.maximize( _estep.fg() );
return logZ;
}
Real EMAlg::iterate() {
Real likelihood;
- for (size_t i = 0; i < _msteps.size(); ++i)
- likelihood = iterate(_msteps[i]);
- _lastLogZ.push_back(likelihood);
+ for( size_t i = 0; i < _msteps.size(); ++i )
+ likelihood = iterate( _msteps[i] );
+ _lastLogZ.push_back( likelihood );
++_iters;
return likelihood;
}
void EMAlg::run() {
- while(!hasSatisfiedTermConditions())
+ while( !hasSatisfiedTermConditions() )
iterate();
}
}
-void Observation::applyEvidence( InfAlg& alg ) const {
- std::map<Var, size_t>::const_iterator i = _obs.begin();
- for( ; i != _obs.end(); ++i )
+void Observation::applyEvidence( InfAlg &alg ) const {
+ for( std::map<Var, size_t>::const_iterator i = _obs.begin(); i != _obs.end(); ++i )
alg.clamp( i->first, i->second );
}
-void Evidence::addEvidenceTabFile( std::istream& is, FactorGraph& fg ) {
+void Evidence::addEvidenceTabFile( std::istream &is, FactorGraph &fg ) {
std::map<std::string, Var> varMap;
- std::vector<Var>::const_iterator v = fg.vars().begin();
- for( ; v != fg.vars().end(); ++v ) {
+ for( std::vector<Var>::const_iterator v = fg.vars().begin(); v != fg.vars().end(); ++v ) {
std::stringstream s;
s << v->label();
varMap[s.str()] = *v;
}
-void Evidence::addEvidenceTabFile( std::istream& is, std::map<std::string, Var>& varMap ) {
- std::vector<std::string> header_fields;
- std::vector<Var> vars;
+void Evidence::addEvidenceTabFile( std::istream &is, std::map<std::string, Var> &varMap ) {
std::string line;
getline( is, line );
// Parse header
+ std::vector<std::string> header_fields;
tokenizeString( line, header_fields );
std::vector<std::string>::const_iterator p_field = header_fields.begin();
-
if( p_field == header_fields.end() )
DAI_THROW(INVALID_EVIDENCE_LINE);
+ std::vector<Var> vars;
for( ; p_field != header_fields.end(); ++p_field ) {
std::map<std::string, Var>::iterator elem = varMap.find( *p_field );
if( elem == varMap.end() )
// Read samples
while( getline(is, line) ) {
std::vector<std::string> fields;
-
tokenizeString( line, fields );
-
if( fields.size() != vars.size() )
DAI_THROW(INVALID_EVIDENCE_LINE);
using namespace dai;
-void usage( const string& msg ) {
+void usage( const string &msg ) {
cerr << msg << endl;
cerr << "Usage:" << endl;
cerr << " testem factorgraph.fg evidence.tab emconfig.em" << endl;
projects / libdai.git / commitdiff