emalg.h

Go to the documentation of this file.

/*  This file is part of libDAI - http://www.libdai.org/
 *
 *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
 *
 *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
 */


#ifndef __defined_libdai_emalg_h
#define __defined_libdai_emalg_h


#include <vector>
#include <map>

#include <dai/factor.h>
#include <dai/daialg.h>
#include <dai/evidence.h>
#include <dai/index.h>
#include <dai/properties.h>




namespace dai {



class ParameterEstimation {
    public:
        typedef ParameterEstimation* (*ParamEstFactory)( const PropertySet& );

        virtual ~ParameterEstimation() {}

        virtual ParameterEstimation* clone() const = 0;


        static ParameterEstimation* construct( const std::string &method, const PropertySet &p );

        static void registerMethod( const std::string &method, const ParamEstFactory &f ) {
            if( _registry == NULL )
                loadDefaultRegistry();
            (*_registry)[method] = f;
        }

        virtual Prob estimate(const Prob &p) { return parametersToFactor(parameters(p)); }

        virtual Prob parametersToFactor(const Prob &params) = 0;

        virtual Prob parameters(const Prob &p) = 0;

        virtual size_t probSize() const = 0;

        // Returns the name of the class of this parameter estimation
        virtual const std::string& name() const = 0;

        virtual const PropertySet& properties() const = 0;
    private:
        static std::map<std::string, ParamEstFactory> *_registry;

        static void loadDefaultRegistry();
};



class CondProbEstimation : private ParameterEstimation {
    private:
        size_t _target_dim;
        Prob _initial_stats;

        static std::string _name; // = "CondProbEstimation";

        PropertySet _props;

    public:

        CondProbEstimation( size_t target_dimension, const Prob &pseudocounts );


        static ParameterEstimation* factory( const PropertySet &p );

        virtual ParameterEstimation* clone() const { return new CondProbEstimation( _target_dim, _initial_stats ); }

        virtual ~CondProbEstimation() {}


        virtual Prob parameters(const Prob &p);

        // For a discrete conditional probability distribution,
        // the parameters are equivalent to the resulting factor
        virtual Prob parametersToFactor(const Prob &p);

        virtual size_t probSize() const { return _initial_stats.size(); }
        
        virtual const std::string& name() const { return _name; }
        
        virtual const PropertySet& properties() const { return _props; }
};



class SharedParameters {
    public:
        typedef size_t FactorIndex;
        typedef std::map<FactorIndex, std::vector<Var> > FactorOrientations;

    private:
        std::map<FactorIndex, VarSet> _varsets;
        std::map<FactorIndex, Permute> _perms;
        FactorOrientations _varorders;
        ParameterEstimation *_estimation;
        bool _ownEstimation;
        Prob* _expectations;


        static Permute calculatePermutation( const std::vector<Var> &varOrder, VarSet &outVS );

        void setPermsAndVarSetsFromVarOrders();

    public:

        SharedParameters( const FactorOrientations &varorders, ParameterEstimation *estimation, bool ownPE=false );


        SharedParameters( std::istream &is, const FactorGraph &fg );

        SharedParameters( const SharedParameters &sp ) : _varsets(sp._varsets), _perms(sp._perms), _varorders(sp._varorders), _estimation(sp._estimation), _ownEstimation(sp._ownEstimation), _expectations(NULL) {
            // If sp owns its _estimation object, we should clone it instead of copying the pointer
            if( _ownEstimation )
                _estimation = _estimation->clone();
            _expectations = new Prob(*sp._expectations);
        }

        ~SharedParameters() {
            // If we own the _estimation object, we should delete it now
            if( _ownEstimation )
                delete _estimation;
            if( _expectations != NULL) 
                delete _expectations;
        }


        void collectExpectations( InfAlg &alg );

        const Prob& currentExpectations() const { return *_expectations; }

        ParameterEstimation& getPEst() const { return *_estimation; }


        void setParameters( FactorGraph &fg );


        const FactorOrientations& getFactorOrientations() const { return _varorders; }

        void clear( ) { _expectations->fill(0); }
};



class MaximizationStep {
    private:
        std::vector<SharedParameters> _params;

    public:
        MaximizationStep() : _params() {}

        MaximizationStep( std::vector<SharedParameters> &maximizations ) : _params(maximizations) {}


        MaximizationStep( std::istream &is, const FactorGraph &fg_varlookup );

        void addExpectations( InfAlg &alg );

        void maximize( FactorGraph &fg );
        
        void clear( );


        typedef std::vector<SharedParameters>::iterator iterator;
        typedef std::vector<SharedParameters>::const_iterator const_iterator;

        iterator begin() { return _params.begin(); }
        const_iterator begin() const { return _params.begin(); }
        iterator end() { return _params.end(); }
        const_iterator end() const { return _params.end(); }
};



class EMAlg {
    private:
        const Evidence &_evidence;

        InfAlg &_estep;

        std::vector<MaximizationStep> _msteps;

        size_t _iters;

        std::vector<Real> _lastLogZ;

        size_t _max_iters;

        Real _log_z_tol;

    public:
        static const std::string MAX_ITERS_KEY;
        static const size_t MAX_ITERS_DEFAULT;
        static const std::string LOG_Z_TOL_KEY;
        static const Real 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 );
        }


        EMAlg( const Evidence &evidence, InfAlg &estep, std::istream &mstep_file );


        void setTermConditions( const PropertySet &p );


        bool hasSatisfiedTermConditions() const;

        Real logZ() const { return _lastLogZ.back(); }

        size_t Iterations() const { return _iters; }

        const InfAlg& eStep() const { return _estep; }


        Real iterate();

        Real iterate( MaximizationStep &mstep );

        void run();


        typedef std::vector<MaximizationStep>::iterator s_iterator;
        typedef std::vector<MaximizationStep>::const_iterator const_s_iterator;

        s_iterator s_begin() { return _msteps.begin(); }
        const_s_iterator s_begin() const { return _msteps.begin(); }
        s_iterator s_end() { return _msteps.end(); }
        const_s_iterator s_end() const { return _msteps.end(); }
};


} // end of namespace dai


#endif