* \f$x_1 = 1, x_3 = 0, x_2 = 1\f$, and the third observation being
* \f$x_1 = 1, x_2 = 1\f$ (where the state of \f$x_3\f$ is missing).
*
- * \section fileformats-sharedparameters Shared parameters section in EM file
+ * \section fileformats-emalg Expectation Maximization (.em) file format
*
- * This section describes the file format of part of an .em file, namely a
- * section describing one SharedParameters object.
+ * This section describes the file format of .em files, which are used
+ * to specify a particular EM algorithm. The .em files are complementary
+ * to .fg files; in other words, an .em file without a corresponding .fg
+ * file is useless. Furthermore, one also needs a corresponding .tab file
+ * containing the data used for parameter learning.
*
- * The first line should consist of the name of a ParameterEstimation subclass
+ * An .em file starts with a line specifying the number of maximization steps.
+ * Then, for each maximization step, its description follows in the format
+ * described in the next section.
+ *
+ * \subsection fileformats-emalg-maximizationstep Maximization Step section in EM file
+ *
+ * A maximization step section of an .em file starts with a single line
+ * describing the number of shared parameters sections that will follow.
+ * Then, precisely that number of shared parameters sections follow,
+ * where each of those sections follows the format described in the next
+ * subsection.
+ *
+ * \subsection fileformats-sharedparameters Shared parameters section in EM file
+ *
+ * A shared parameters section of an .em file starts with a single line
+ * consisting of the name of a ParameterEstimation subclass
* and its parameters in the format of a PropertySet. For example:
*
* <pre>
* ConditionalProbEstimation [target_dim=2,total_dim=4,pseudo_count=1]
* </pre>
*
- * The next line contains the number of factors that share parameters.
- * Then, possibly seperated by empty lines, we for each factor FIXME
+ * The next line contains the number of factors that share their parameters.
+ * Then, each of these factors is specified on separate lines (possibly
+ * seperated by empty lines), where each line consists of several fields
+ * seperated by a space or a tab character. The first field contains
+ * the index of the factor in the factor graph. The
+ * following fields specify the ordering of the variables on which that
+ * factor depends, i.e., they form a permutation of the labels of the
+ * variables belonging to that factor. The permutation corresponds to the
+ * mapping from the ordering of the variables that is used in the
+ * SharedParameters object to the canonical ordering of the variables
+ * (i.e., sorted ascendingly according to their labels) which is used in
+ * the internal representation of the Factor object.
*/
/** \page license License
*/
SharedParameters( const FactorOrientations &varorders, ParameterEstimation *estimation, bool ownPE=false );
- /// Construct a SharedParameters object from a stream \a is and a factor graph \a fg
- /** \see \ref fileformats-sharedparameters
+ /// Construct a SharedParameters object from an input stream \a is and a factor graph \a fg
+ /** \see \ref fileformats-emalg-sharedparameters
*/
SharedParameters( std::istream &is, const FactorGraph &fg );
delete _estimation;
}
- /// Collect the necessary statistics from expected values
+ /// Collect the sufficient statistics from expected values (beliefs) according to \a alg
+ /** For each of the relevant factors (that shares the parameters we are interested in),
+ * the corresponding belief according to \a alg is obtained and its entries are permuted
+ * such that their ordering corresponds with the shared parameters that we are estimating.
+ * Then, the parameter estimation subclass method addSufficientStatistics() is called with
+ * this vector of expected values of the parameters as input.
+ */
void collectSufficientStatistics( InfAlg &alg );
/// Estimate and set the shared parameters
+ /** Based on the sufficient statistics collected so far, the shared parameters are estimated
+ * using the parameter estimation subclass method estimate(). Then, each of the relevant
+ * factors in \a fg (that shares the parameters we are interested in) is set according
+ * to those parameters (permuting the parameters accordingly).
+ */
void setParameters( FactorGraph &fg );
-
- /// Returns the parameters
- void collectParameters( const FactorGraph &fg, std::vector<Real> &outVals, std::vector<Var> &outVarOrder );
};
-/// A MaximizationStep groups together several parameter estimation tasks into a single unit.
+/// A MaximizationStep groups together several parameter estimation tasks (SharedParameters objects) into a single unit.
/** \author Charles Vaske
*/
class MaximizationStep {
/// Default constructor
MaximizationStep() : _params() {}
- /// Constructor from a vector of SharedParameters objects
+ /// Construct MaximizationStep from a vector of parameter estimation tasks
MaximizationStep( std::vector<SharedParameters> &maximizations ) : _params(maximizations) {}
/// Constructor from an input stream and a corresponding factor graph
+ /** \see \ref fileformats-emalg-maximizationstep
+ */
MaximizationStep( std::istream &is, const FactorGraph &fg_varlookup );
- /// Collect the beliefs from this InfAlg as expectations for the next Maximization step.
+ /// 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.
/// \name Iterator interface
//@{
+ /// Iterator over the parameter estimation tasks
typedef std::vector<SharedParameters>::iterator iterator;
+ /// Constant iterator over the parameter estimation tasks
typedef std::vector<SharedParameters>::const_iterator const_iterator;
+
+ /// Returns iterator that points to the first parameter estimation task
iterator begin() { return _params.begin(); }
+ /// Returns constant iterator that points to the first parameter estimation task
const_iterator begin() const { return _params.begin(); }
+ /// Returns iterator that points beyond the last parameter estimation task
iterator end() { return _params.end(); }
+ /// Returns constant iterator that points beyond the last parameter estimation task
const_iterator end() const { return _params.end(); }
//@}
};
/// 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 MaximizationStep 's steps to be performed.
*
* This implementation can perform incremental EM by using multiple
- * MaximizationSteps. An expectation step is performed between execution
- * of each MaximizationStep. A call to iterate() will cycle through all
- * MaximizationSteps.
+ * MaximizationSteps. An expectation step is performed between execution
+ * of each MaximizationStep. A call to iterate() will cycle through all
+ * MaximizationStep 's. A call to run() will call iterate() until the
+ * termination criteria have been met.
*
* Having multiple and separate maximization steps allows for maximizing some
- * parameters, performing another E step, and then maximizing separate
+ * parameters, performing another E-step, and then maximizing separate
* parameters, which may result in faster convergence in some cases.
*
* \author Charles Vaske
Real _log_z_tol;
public:
- /// Key for setting maximum iterations @see setTermConditions
+ /// Key for setting maximum iterations
static const std::string MAX_ITERS_KEY;
- /// Default maximum iterations @see setTermConditions
+ /// Default maximum iterations
static const size_t MAX_ITERS_DEFAULT;
- /// Key for setting likelihood termination condition @see setTermConditions
+ /// Key for setting likelihood termination condition
static const std::string LOG_Z_TOL_KEY;
- /// Default likelihood tolerance @see setTermConditions
+ /// Default likelihood tolerance
static const Real LOG_Z_TOL_DEFAULT;
- /// Construct an EMAlg from all these objects
+ /// Construct an EMAlg from several objects
+ /** \param evidence Specifies the observed evidence
+ * \param estep Inference algorithm to be used for the E-step
+ * \param msteps Vector of maximization steps, each of which is a group of parameter estimation tasks
+ * \param termconditions Termination conditions @see setTermConditions()
+ */
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 Evidence object, an InfAlg object, and an input stream
+ /// Construct an EMAlg from Evidence \a evidence, an InfAlg \a estep, and an input stream \a mstep_file
+ /** \see \ref fileformats-emalg
+ */
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
- * - log_z_tol proportion of increase in logZ
+ /** There are two possible parameters in the PropertySet \a p:
+ * - \a max_iters maximum number of iterations
+ * - \a log_z_tol critical proportion of increase in logZ
*
* \see hasSatisifiedTermConditions()
*/
bool hasSatisfiedTermConditions() const;
/// Return the last calculated log likelihood
- Real getLogZ() const { return _lastLogZ.back(); }
+ Real logZ() const { return _lastLogZ.back(); }
/// Returns number of iterations done so far
- size_t getCurrentIters() const { return _iters; }
+ size_t Iterations() const { return _iters; }
- /// Get the iteration method used
+ /// Get the E-step method used
const InfAlg& eStep() const { return _estep; }
- /// Perform an iteration over all maximization steps
+ /// Iterate once over all maximization steps
+ /** \return Log-likelihood after iteration
+ */
Real iterate();
- /// Perform an iteration over a single MaximizationStep
+ /// Iterate over a single MaximizationStep
Real iterate( MaximizationStep &mstep );
/// Iterate until termination conditions are satisfied
/// \name Iterator interface
//@{
+ /// Iterator over the maximization steps
typedef std::vector<MaximizationStep>::iterator s_iterator;
+ /// Constant iterator over the maximization steps
typedef std::vector<MaximizationStep>::const_iterator const_s_iterator;
+
+ /// Returns iterator that points to the first maximization step
s_iterator s_begin() { return _msteps.begin(); }
+ /// Returns constant iterator that points to the first maximization step
const_s_iterator s_begin() const { return _msteps.begin(); }
+ /// Returns iterator that points beyond the last maximization step
s_iterator s_end() { return _msteps.end(); }
+ /// Returns constant iterator that points beyond the last maximization step
const_s_iterator s_end() const { return _msteps.end(); }
//@}
};