From 99ef805df2357849d330ca136cadbedf7d4114ad Mon Sep 17 00:00:00 2001 From: Joris Mooij Date: Fri, 26 Sep 2008 16:16:41 +0200 Subject: [PATCH] Merged mf.* from SVN head (which implements damping)... ...and renamed the create() methods to construct() to avoid confusion with the virtual constructor which is also called create() --- ChangeLog | 2 +- STATUS | 5 +-- include/dai/bipgraph.h | 6 +-- include/dai/bp.h | 4 +- include/dai/exactinf.h | 8 ++-- include/dai/factorgraph.h | 12 ++---- include/dai/mf.h | 78 +++++++++++++++++++++++++++------------ include/dai/regiongraph.h | 8 +--- src/bp.cpp | 2 +- src/clustergraph.cpp | 2 +- src/exactinf.cpp | 2 +- src/factorgraph.cpp | 6 +-- src/jtree.cpp | 2 +- src/mf.cpp | 37 ++++++++++++------- src/regiongraph.cpp | 4 +- src/treeep.cpp | 2 +- tests/aliases.conf | 2 +- tests/test.cpp | 5 ++- utils/createfg.cpp | 6 +-- 19 files changed, 112 insertions(+), 81 deletions(-) diff --git a/ChangeLog b/ChangeLog index 28fe4ae..3cb88ac 100644 --- a/ChangeLog +++ b/ChangeLog @@ -97,7 +97,7 @@ libDAI-0.2.2 (2008-??-??) nr_IRs() -> nrIRs() ORs() -> ORs IRs() -> IRs - - *::Regenerate() -> *::create() + - *::Regenerate() -> *::construct() - Renamed Index -> IndexFor - Diffs: max() -> maxDiff() diff --git a/STATUS b/STATUS index a05c444..eb8efce 100644 --- a/STATUS +++ b/STATUS @@ -79,7 +79,6 @@ matlab/ dai_writefg.m matlab.cpp matlab.h - utils/ fg2dot.cpp fginfo.cpp @@ -96,6 +95,8 @@ tests/ testall testregression test.cpp +mf.h +mf.cpp FILES IN SVN HEAD THAT ARE STILL RELEVANT: ChangeLog @@ -110,8 +111,6 @@ jtree.h jtree.cpp lc.h lc.cpp -mf.h -mf.cpp mr.h mr.cpp treeep.h diff --git a/include/dai/bipgraph.h b/include/dai/bipgraph.h index d9b83e6..01229e7 100644 --- a/include/dai/bipgraph.h +++ b/include/dai/bipgraph.h @@ -108,7 +108,7 @@ class BipartiteGraph { * The value_type of an EdgeInputIterator should be Edge. */ template - void create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ); + void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ); /// Construct bipartite graph from a range of edges. /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2. @@ -116,7 +116,7 @@ class BipartiteGraph { */ template BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) { - create( nr1, nr2, begin, end ); + construct( nr1, nr2, begin, end ); } /// Returns constant reference to the _i2'th neighbor of node i1 of type 1 @@ -299,7 +299,7 @@ class BipartiteGraph { template -void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) { +void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) { _nb1.clear(); _nb1.resize( nr1 ); _nb2.clear(); diff --git a/include/dai/bp.h b/include/dai/bp.h index 324e644..5d6b456 100644 --- a/include/dai/bp.h +++ b/include/dai/bp.h @@ -67,7 +67,7 @@ class BP : public DAIAlgFG { /// Construct from FactorGraph fg and PropertySet opts BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), edges(), props(), maxdiff(0.0) { setProperties( opts ); - create(); + construct(); } /// Assignment operator BP& operator=( const BP & x ) { @@ -92,7 +92,7 @@ class BP : public DAIAlgFG { const double & residual(size_t i, size_t _I) const { return edges[i][_I].residual; } std::string identify() const; - void create(); + void construct(); void init(); /// Clear messages and beliefs corresponding to the nodes in ns virtual void init( const VarSet &ns ); diff --git a/include/dai/exactinf.h b/include/dai/exactinf.h index 7dd0bcb..77c3a64 100644 --- a/include/dai/exactinf.h +++ b/include/dai/exactinf.h @@ -58,7 +58,7 @@ class ExactInf : public DAIAlgFG { /// Construct from FactorGraph fg and PropertySet opts ExactInf( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), props(), _beliefsV(), _beliefsF(), _logZ() { setProperties( opts ); - create(); + construct(); } /// Assignment operator @@ -74,9 +74,7 @@ class ExactInf : public DAIAlgFG { } /// Create (virtual constructor) - virtual ExactInf* create() const { - return new ExactInf(); - } + virtual ExactInf* create() const { return new ExactInf(); } /// Return maximum difference between single node /// beliefs for two consecutive iterations @@ -118,7 +116,7 @@ class ExactInf : public DAIAlgFG { /// Name of this inference method static const char *Name; - void create(); + void construct(); void restoreFactors( const VarSet &ns ) { FactorGraph::restoreFactors(ns); init(ns); } void setProperties( const PropertySet &opts ); PropertySet getProperties() const; diff --git a/include/dai/factorgraph.h b/include/dai/factorgraph.h index 3cc0a9f..0260864 100644 --- a/include/dai/factorgraph.h +++ b/include/dai/factorgraph.h @@ -68,14 +68,10 @@ class FactorGraph { virtual ~FactorGraph() {} /// Create (virtual default constructor) - virtual FactorGraph* create() const { - return new FactorGraph(*this); - } + virtual FactorGraph* create() const { return new FactorGraph(*this); } /// Clone (virtual copy constructor) - virtual FactorGraph* clone() const { - return new FactorGraph(); - } + virtual FactorGraph* clone() const { return new FactorGraph(); } // aliases Var & var(size_t i) { return vars[i]; } @@ -207,7 +203,7 @@ class FactorGraph { void restoreFactors( const VarSet &ns ); void backupFactors( const VarSet &ns ); /// Part of constructors (creates edges, neighbors and adjacency matrix) - void createGraph( size_t nrEdges ); + void constructGraph( size_t nrEdges ); }; @@ -228,7 +224,7 @@ FactorGraph::FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fac vars.push_back( *p1 ); // create graph structure - createGraph( nrEdges ); + constructGraph( nrEdges ); } diff --git a/include/dai/mf.h b/include/dai/mf.h index 6318886..60a5b1f 100644 --- a/include/dai/mf.h +++ b/include/dai/mf.h @@ -35,57 +35,87 @@ namespace dai { class MF : public DAIAlgFG { protected: std::vector _beliefs; + /// Maximum difference encountered so far + double _maxdiff; + /// Number of iterations needed + size_t _iters; public: struct Properties { size_t verbose; size_t maxiter; double tol; + double damping; } props; - double maxdiff; - + static const char *Name; + public: - // default constructor - MF() : DAIAlgFG(), _beliefs(), props(), maxdiff(0.0) {} - // copy constructor - MF( const MF& x ) : DAIAlgFG(x), _beliefs(x._beliefs), props(x.props), maxdiff(x.maxdiff) {} - MF* clone() const { return new MF(*this); } - /// Create (virtual constructor) - virtual MF* create() const { return new MF(); } + /// Default constructor + MF() : DAIAlgFG(), _beliefs(), _maxdiff(0.0), _iters(0U), props() {} + // construct MF object from FactorGraph - MF( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _beliefs(), props(), maxdiff(0.0) { + MF( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), _beliefs(), _maxdiff(0.0), _iters(0U), props() { setProperties( opts ); - create(); + construct(); } - // assignment operator - MF& operator=( const MF &x ) { + + /// Copy constructor + MF( const MF &x ) : DAIAlgFG(x), _beliefs(x._beliefs), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {} + + /// Assignment operator + MF & operator=( const MF &x ) { if( this != &x ) { DAIAlgFG::operator=( x ); _beliefs = x._beliefs; - props = x.props; - maxdiff = x.maxdiff; + _maxdiff = x._maxdiff; + _iters = x._iters; + props = x.props; } return *this; } - static const char *Name; + /// Clone *this (virtual copy constructor) + virtual MF* clone() const { return new MF(*this); } + + /// Create (virtual constructor) + virtual MF* create() const { return new MF(); } + + /// Return number of passes over the factorgraph needed + virtual size_t Iterations() const { return _iters; } + + /// Return maximum difference between single node beliefs for two consecutive iterations + double maxDiff() const { return _maxdiff; } + + /// Identify *this for logging purposes std::string identify() const; - void create(); + + /// Get single node belief + Factor belief( const Var &n ) const; + + /// Get general belief + Factor belief( const VarSet &ns ) const; + + /// Get all beliefs + std::vector beliefs() const; + + /// Get log partition sum + Real logZ() const; + + void construct(); + void init(); + /// Clear messages and beliefs corresponding to the nodes in ns virtual void init( const VarSet &ns ); + + /// The actual approximate inference algorithm double run(); - Factor beliefV (size_t i) const; - Factor belief (const Var &n) const; - Factor belief (const VarSet &ns) const; - std::vector beliefs() const; - Real logZ() const; - void restoreFactors( const VarSet &ns ) { FactorGraph::restoreFactors(ns); init(ns); } void setProperties( const PropertySet &opts ); PropertySet getProperties() const; std::string printProperties() const; - double maxDiff() const { return maxdiff; } + + Factor beliefV( size_t i ) const; }; diff --git a/include/dai/regiongraph.h b/include/dai/regiongraph.h index d83bf04..051d7b9 100644 --- a/include/dai/regiongraph.h +++ b/include/dai/regiongraph.h @@ -137,14 +137,10 @@ class RegionGraph : public FactorGraph { } /// Create (virtual default constructor) - virtual RegionGraph* create() const { - return new RegionGraph(); - } + virtual RegionGraph* create() const { return new RegionGraph(); } /// Clone (virtual copy constructor) - virtual RegionGraph* clone() const { - return new RegionGraph(*this); - } + virtual RegionGraph* clone() const { return new RegionGraph(*this); } /// Set the content of the I'th factor and make a backup of its old content if backup == true virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) { diff --git a/src/bp.cpp b/src/bp.cpp index 79d5919..aeaeaae 100644 --- a/src/bp.cpp +++ b/src/bp.cpp @@ -77,7 +77,7 @@ string BP::printProperties() const { } -void BP::create() { +void BP::construct() { // create edge properties edges.clear(); edges.reserve( nrVars() ); diff --git a/src/clustergraph.cpp b/src/clustergraph.cpp index 4b0695e..f823fd8 100644 --- a/src/clustergraph.cpp +++ b/src/clustergraph.cpp @@ -51,7 +51,7 @@ ClusterGraph::ClusterGraph( const std::vector & cls ) : G(), vars(), clu } // Create bipartite graph - G.create( vars.size(), clusters.size(), edges.begin(), edges.end() ); + G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() ); } diff --git a/src/exactinf.cpp b/src/exactinf.cpp index d6c59eb..1940025 100644 --- a/src/exactinf.cpp +++ b/src/exactinf.cpp @@ -54,7 +54,7 @@ string ExactInf::printProperties() const { } -void ExactInf::create() { +void ExactInf::construct() { // clear variable beliefs and reserve space _beliefsV.clear(); _beliefsV.reserve( nrVars() ); diff --git a/src/factorgraph.cpp b/src/factorgraph.cpp index 7834467..c28e864 100644 --- a/src/factorgraph.cpp +++ b/src/factorgraph.cpp @@ -55,12 +55,12 @@ FactorGraph::FactorGraph( const std::vector &P ) : G(), _backup() { vars.push_back( *p1 ); // create graph structure - createGraph( nrEdges ); + constructGraph( nrEdges ); } /// Part of constructors (creates edges, neighbours and adjacency matrix) -void FactorGraph::createGraph( size_t nrEdges ) { +void FactorGraph::constructGraph( size_t nrEdges ) { // create a mapping for indices hash_map hashmap; @@ -77,7 +77,7 @@ void FactorGraph::createGraph( size_t nrEdges ) { } // create bipartite graph - G.create( nrVars(), nrFactors(), edges.begin(), edges.end() ); + G.construct( nrVars(), nrFactors(), edges.begin(), edges.end() ); } diff --git a/src/jtree.cpp b/src/jtree.cpp index 147772e..810dfa5 100644 --- a/src/jtree.cpp +++ b/src/jtree.cpp @@ -133,7 +133,7 @@ void JTree::GenerateJT( const std::vector &Cliques ) { } // create bipartite graph - G.create( nrORs(), nrIRs(), edges.begin(), edges.end() ); + G.construct( nrORs(), nrIRs(), edges.begin(), edges.end() ); // Create messages and beliefs _Qa.clear(); diff --git a/src/mf.cpp b/src/mf.cpp index 526c776..aab55ab 100644 --- a/src/mf.cpp +++ b/src/mf.cpp @@ -40,11 +40,17 @@ const char *MF::Name = "MF"; void MF::setProperties( const PropertySet &opts ) { assert( opts.hasKey("tol") ); assert( opts.hasKey("maxiter") ); - assert( opts.hasKey("verbose") ); props.tol = opts.getStringAs("tol"); props.maxiter = opts.getStringAs("maxiter"); - props.verbose = opts.getStringAs("verbose"); + if( opts.hasKey("verbose") ) + props.verbose = opts.getStringAs("verbose"); + else + props.verbose = 0U; + if( opts.hasKey("damping") ) + props.damping = opts.getStringAs("damping"); + else + props.damping = 0.0; } @@ -53,6 +59,7 @@ PropertySet MF::getProperties() const { opts.Set( "tol", props.tol ); opts.Set( "maxiter", props.maxiter ); opts.Set( "verbose", props.verbose ); + opts.Set( "damping", props.damping ); return opts; } @@ -62,19 +69,18 @@ string MF::printProperties() const { s << "["; s << "tol=" << props.tol << ","; s << "maxiter=" << props.maxiter << ","; - s << "verbose=" << props.verbose << "]"; + s << "verbose=" << props.verbose << ","; + s << "damping=" << props.damping << "]"; return s.str(); } -void MF::create() { - // clear beliefs +void MF::construct() { + // create beliefs _beliefs.clear(); _beliefs.reserve( nrVars() ); - - // create beliefs for( size_t i = 0; i < nrVars(); ++i ) - _beliefs.push_back(Factor(var(i))); + _beliefs.push_back( Factor( var(i) ) ); } @@ -117,20 +123,23 @@ double MF::run() { jan *= piet; } - jan.normalize( Prob::NORMPROB ); + jan.normalize(); if( jan.hasNaNs() ) { cout << "MF::run(): ERROR: jan has NaNs!" << endl; return 1.0; } + if( props.damping != 0.0 ) + jan = (jan^(1.0 - props.damping)) * (_beliefs[i]^props.damping); diffs.push( dist( jan, _beliefs[i], Prob::DISTLINF ) ); _beliefs[i] = jan; } - if( diffs.maxDiff() > maxdiff ) - maxdiff = diffs.maxDiff(); + _iters = t / pass_size; + if( diffs.maxDiff() > _maxdiff ) + _maxdiff = diffs.maxDiff(); if( props.verbose >= 1 ) { if( diffs.maxDiff() > props.tol ) { @@ -148,10 +157,10 @@ double MF::run() { } -Factor MF::beliefV (size_t i) const { +Factor MF::beliefV( size_t i ) const { Factor piet; piet = _beliefs[i]; - piet.normalize( Prob::NORMPROB ); + piet.normalize(); return(piet); } @@ -188,7 +197,7 @@ Real MF::logZ() const { Factor henk; foreach( const Neighbor &j, nbF(I) ) // for all j in I henk *= _beliefs[j]; - henk.normalize( Prob::NORMPROB ); + henk.normalize(); Factor piet; piet = factor(I).log0(); piet *= henk; diff --git a/src/regiongraph.cpp b/src/regiongraph.cpp index de21ac2..1e52bd4 100644 --- a/src/regiongraph.cpp +++ b/src/regiongraph.cpp @@ -54,7 +54,7 @@ RegionGraph::RegionGraph( const FactorGraph &fg, const std::vector &ors, RecomputeORs(); // create bipartite graph - G.create( nrORs(), nrIRs(), edges.begin(), edges.end() ); + G.construct( nrORs(), nrIRs(), edges.begin(), edges.end() ); // Check counting numbers #ifdef DAI_DEBUG @@ -125,7 +125,7 @@ RegionGraph::RegionGraph( const FactorGraph &fg, const std::vector &cl ) } // create bipartite graph - G.create( nrORs(), nrIRs(), edges.begin(), edges.end() ); + G.construct( nrORs(), nrIRs(), edges.begin(), edges.end() ); // Calculate counting numbers Calc_Counting_Numbers(); diff --git a/src/treeep.cpp b/src/treeep.cpp index 54d168d..56924ae 100644 --- a/src/treeep.cpp +++ b/src/treeep.cpp @@ -322,7 +322,7 @@ void TreeEP::ConstructRG( const DEdgeVec &tree ) { } // create bipartite graph - G.create( nrORs(), nrIRs(), edges.begin(), edges.end() ); + G.construct( nrORs(), nrIRs(), edges.begin(), edges.end() ); // Check counting numbers Check_Counting_Numbers(); diff --git a/tests/aliases.conf b/tests/aliases.conf index 3152123..0c0d5c5 100644 --- a/tests/aliases.conf +++ b/tests/aliases.conf @@ -16,7 +16,7 @@ JTREE_SHSH: JTREE[updates=SHSH,verbose=0] # --- MF ---------------------- -MF_SEQRND: MF[tol=1e-9,maxiter=10000,verbose=0] +MF_SEQRND: MF[tol=1e-9,maxiter=10000] # --- TREEEP ------------------ diff --git a/tests/test.cpp b/tests/test.cpp index a4bdcc7..7d06692 100644 --- a/tests/test.cpp +++ b/tests/test.cpp @@ -59,9 +59,12 @@ class TestDAI { q.clear(); for( size_t i = 0; i < fg.nrVars(); i++ ) q.push_back( Factor(Var(i,2), zero) ); - logZ = NAN; + logZ = 0.0; maxdiff = 0.0; iters = 1; + has_logZ = false; + has_maxdiff = false; + has_iters = false; } else obj = newInfAlg( name, fg, opts ); time += toc() - tic; diff --git a/utils/createfg.cpp b/utils/createfg.cpp index 8796f55..ebfdb54 100644 --- a/utils/createfg.cpp +++ b/utils/createfg.cpp @@ -307,7 +307,7 @@ BipartiteGraph CreateRandomBipartiteGraph( size_t N, size_t K, size_t n, size_t edges.push_back( BipartiteGraph::Edge(stubs1[e], stubs2[e]) ); // finish construction - G.create( N, K, edges.begin(), edges.end() ); + G.construct( N, K, edges.begin(), edges.end() ); return G; } @@ -360,7 +360,7 @@ BipartiteGraph CreateSmallLDPCGraph() { edges.push_back( Edge(1,3) ); edges.push_back( Edge(2,3) ); edges.push_back( Edge(3,3) ); // finish construction - G.create( N, K, edges.begin(), edges.end() ); + G.construct( N, K, edges.begin(), edges.end() ); return G; } @@ -405,7 +405,7 @@ BipartiteGraph CreateGroupStructuredLDPCGraph( size_t p, size_t j, size_t k ) { } // finish construction - G.create( N, K, edges.begin(), edges.end() ); + G.construct( N, K, edges.begin(), edges.end() ); return G; } -- 2.20.1