Improved documentation of include/dai/emalg.h
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 11 Nov 2009 19:56:26 +0000 (20:56 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 11 Nov 2009 20:00:07 +0000 (21:00 +0100)
TODO
include/dai/doc.h
include/dai/emalg.h
src/emalg.cpp
tests/testem/testem.cpp

diff --git a/TODO b/TODO
index 7a43240..516ca72 100644 (file)
--- a/TODO
+++ b/TODO
@@ -2,7 +2,6 @@ To do for the next release (0.2.3):
 
 Improve documentation:
 
-       emalg.h
        doc.h
 
 Improve documentation of all .props structs.
index 06baa10..cc51c53 100644 (file)
  *  \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
index 6f973cc..31c3524 100644 (file)
@@ -191,8 +191,8 @@ class SharedParameters {
          */
         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 );
 
@@ -210,18 +210,26 @@ class SharedParameters {
                 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 {
@@ -232,13 +240,15 @@ 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.
@@ -246,11 +256,18 @@ class MaximizationStep {
 
     /// \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(); }
     //@}
 };
@@ -259,16 +276,17 @@ class MaximizationStep {
 /// 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
@@ -297,29 +315,36 @@ class EMAlg {
         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()
          */
@@ -335,18 +360,20 @@ class EMAlg {
         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
@@ -354,11 +381,18 @@ class EMAlg {
 
     /// \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(); }
     //@}
 };
index a29fec9..cb1a449 100644 (file)
@@ -210,22 +210,6 @@ void SharedParameters::setParameters( FactorGraph &fg ) {
 }
 
 
-void SharedParameters::collectParameters( const FactorGraph &fg, std::vector<Real> &outVals, std::vector<Var> &outVarOrder ) {
-    FactorOrientations::iterator it = _varorders.begin();
-    if( it == _varorders.end() )
-        return;
-    FactorIndex I = it->first;
-    for( std::vector<Var>::const_iterator var_it = _varorders[I].begin(); var_it != _varorders[I].end(); ++var_it )
-        outVarOrder.push_back( *var_it );
-
-    const Factor &f = fg.factor(I);
-    DAI_ASSERT( f.vars() == _varsets[I] );
-    const Permute &perm = _perms[I];
-    for( size_t val_index = 0; val_index < f.states(); ++val_index )
-        outVals.push_back( f[perm.convertLinearIndex(val_index)] );
-}
-
-
 MaximizationStep::MaximizationStep( std::istream &is, const FactorGraph &fg_varlookup ) : _params() {
     size_t num_params = -1;
     is >> num_params;
index 9082a88..919b0d7 100644 (file)
@@ -56,7 +56,7 @@ int main( int argc, char** argv ) {
 
     while( !em.hasSatisfiedTermConditions() ) {
         Real l = em.iterate();
-        cout << "Iteration " << em.getCurrentIters() << " likelihood: " << l <<endl;
+        cout << "Iteration " << em.Iterations() << " likelihood: " << l <<endl;
     }
 
     cout << endl << "Inferred Factor Graph:" << endl << "######################" << endl;