Merged mf.* from SVN head (which implements damping)...
authorJoris Mooij <jorism@marvin.jorismooij.nl>
Fri, 26 Sep 2008 14:16:41 +0000 (16:16 +0200)
committerJoris Mooij <jorism@marvin.jorismooij.nl>
Fri, 26 Sep 2008 14:16:41 +0000 (16:16 +0200)
...and renamed the create() methods to construct() to avoid confusion
with the virtual constructor which is also called create()

19 files changed:
ChangeLog
STATUS
include/dai/bipgraph.h
include/dai/bp.h
include/dai/exactinf.h
include/dai/factorgraph.h
include/dai/mf.h
include/dai/regiongraph.h
src/bp.cpp
src/clustergraph.cpp
src/exactinf.cpp
src/factorgraph.cpp
src/jtree.cpp
src/mf.cpp
src/regiongraph.cpp
src/treeep.cpp
tests/aliases.conf
tests/test.cpp
utils/createfg.cpp

index 28fe4ae..3cb88ac 100644 (file)
--- 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 (file)
--- 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
index d9b83e6..01229e7 100644 (file)
@@ -108,7 +108,7 @@ class BipartiteGraph {
          *  The value_type of an EdgeInputIterator should be Edge.
          */
         template<typename EdgeInputIterator>
-        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<typename EdgeInputIterator>
         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<typename EdgeInputIterator>
-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();
index 324e644..5d6b456 100644 (file)
@@ -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 );
index 7dd0bcb..77c3a64 100644 (file)
@@ -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;
index 3cc0a9f..0260864 100644 (file)
@@ -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 );
 }
 
 
index 6318886..60a5b1f 100644 (file)
@@ -35,57 +35,87 @@ namespace dai {
 class MF : public DAIAlgFG {
     protected:
         std::vector<Factor>  _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<Factor> 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<Factor> 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;
 };
 
 
index d83bf04..051d7b9 100644 (file)
@@ -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 ) {
index 79d5919..aeaeaae 100644 (file)
@@ -77,7 +77,7 @@ string BP::printProperties() const {
 }
 
 
-void BP::create() {
+void BP::construct() {
     // create edge properties
     edges.clear();
     edges.reserve( nrVars() );
index 4b0695e..f823fd8 100644 (file)
@@ -51,7 +51,7 @@ ClusterGraph::ClusterGraph( const std::vector<VarSet> & 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() );
 }
 
 
index d6c59eb..1940025 100644 (file)
@@ -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() );
index 7834467..c28e864 100644 (file)
@@ -55,12 +55,12 @@ FactorGraph::FactorGraph( const std::vector<Factor> &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<size_t, size_t> 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() );
 }
 
 
index 147772e..810dfa5 100644 (file)
@@ -133,7 +133,7 @@ void JTree::GenerateJT( const std::vector<VarSet> &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();
index 526c776..aab55ab 100644 (file)
@@ -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<double>("tol");
     props.maxiter = opts.getStringAs<size_t>("maxiter");
-    props.verbose = opts.getStringAs<size_t>("verbose");
+    if( opts.hasKey("verbose") )
+        props.verbose = opts.getStringAs<size_t>("verbose");
+    else
+        props.verbose = 0U;
+    if( opts.hasKey("damping") )
+        props.damping = opts.getStringAs<double>("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;
index de21ac2..1e52bd4 100644 (file)
@@ -54,7 +54,7 @@ RegionGraph::RegionGraph( const FactorGraph &fg, const std::vector<Region> &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<VarSet> &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();
index 54d168d..56924ae 100644 (file)
@@ -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();
index 3152123..0c0d5c5 100644 (file)
@@ -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 ------------------
 
index a4bdcc7..7d06692 100644 (file)
@@ -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;
index 8796f55..ebfdb54 100644 (file)
@@ -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;
 }