Fixed bug in BP (introduced in commit b8f96214...) and added regression test for...
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 4 Aug 2010 09:21:57 +0000 (11:21 +0200)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 4 Aug 2010 09:21:57 +0000 (11:21 +0200)
include/dai/bp.h
src/bp.cpp
src/jtree.cpp
tests/aliases.conf
tests/testall
tests/testall.bat
tests/testem/testem.cpp
tests/testfast.out

index c319f88..635ae4c 100644 (file)
@@ -88,6 +88,12 @@ class BP : public DAIAlgFG {
         size_t _iters;
         /// The history of message updates (only recorded if \a recordSentMessages is \c true)
         std::vector<std::pair<std::size_t, std::size_t> > _sentMessages;
+        /// Stores variable beliefs of previous iteration
+        std::vector<Factor> _oldBeliefsV;
+        /// Stores factor beliefs of previous iteration
+        std::vector<Factor> _oldBeliefsF;
+        /// Stores the update schedule
+        std::vector<Edge> _updateSeq;
 
     public:
         /// Parameters for BP
@@ -139,35 +145,23 @@ class BP : public DAIAlgFG {
         /// Specifies whether the history of message updates should be recorded
         bool recordSentMessages;
 
-        /// Stores variable beliefs of previous iteration
-        std::vector<Factor> oldBeliefsV;
-
-        /// Stores factor beliefs of previous iteration
-        std::vector<Factor> oldBeliefsF;
-
-        /// Stores the update schedule
-        std::vector<Edge> updateSeq;
-
     public:
     /// \name Constructors/destructors
     //@{
         /// Default constructor
-        BP() : DAIAlgFG(), _edges(), _edge2lut(), _lut(), _maxdiff(0.0), _iters(0U), _sentMessages(), props(), recordSentMessages(false) {}
+        BP() : DAIAlgFG(), _edges(), _edge2lut(), _lut(), _maxdiff(0.0), _iters(0U), _sentMessages(), _oldBeliefsV(), _oldBeliefsF(), _updateSeq(), props(), recordSentMessages(false) {}
 
         /// Construct from FactorGraph \a fg and PropertySet \a opts
         /** \param fg Factor graph.
          *  \param opts Parameters @see Properties
          */
-        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), _sentMessages(), props(), recordSentMessages(false) {
+        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), _sentMessages(), _oldBeliefsV(), _oldBeliefsF(), _updateSeq(), props(), recordSentMessages(false) {
             setProperties( opts );
             construct();
         }
 
         /// Copy constructor
-        BP( const BP &x ) : DAIAlgFG(x), _edges(x._edges), _edge2lut(x._edge2lut),
-            _lut(x._lut), _maxdiff(x._maxdiff), _iters(x._iters), _sentMessages(x._sentMessages),
-            props(x.props), recordSentMessages(x.recordSentMessages)
-        {
+        BP( const BP &x ) : DAIAlgFG(x), _edges(x._edges), _edge2lut(x._edge2lut), _lut(x._lut), _maxdiff(x._maxdiff), _iters(x._iters), _sentMessages(x._sentMessages), _oldBeliefsV(x._oldBeliefsV), _oldBeliefsF(x._oldBeliefsF), _updateSeq(x._updateSeq), props(x.props), recordSentMessages(x.recordSentMessages) {
             for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
                 _edge2lut[l->second.first][l->second.second] = l;
         }
@@ -183,6 +177,9 @@ class BP : public DAIAlgFG {
                 _maxdiff = x._maxdiff;
                 _iters = x._iters;
                 _sentMessages = x._sentMessages;
+                _oldBeliefsV = x._oldBeliefsV;
+                _oldBeliefsF = x._oldBeliefsF;
+                _updateSeq = x._updateSeq;
                 props = x.props;
                 recordSentMessages = x.recordSentMessages;
             }
index db2ab72..da8f343 100644 (file)
@@ -126,21 +126,21 @@ void BP::construct() {
     }
 
     // create old beliefs
-    oldBeliefsV.clear();
-    oldBeliefsV.reserve( nrVars() );
+    _oldBeliefsV.clear();
+    _oldBeliefsV.reserve( nrVars() );
     for( size_t i = 0; i < nrVars(); ++i )
-        oldBeliefsV.push_back( Factor( var(i) ) );
-    oldBeliefsF.clear();
-    oldBeliefsF.reserve( nrFactors() );
+        _oldBeliefsV.push_back( Factor( var(i) ) );
+    _oldBeliefsF.clear();
+    _oldBeliefsF.reserve( nrFactors() );
     for( size_t I = 0; I < nrFactors(); ++I )
-        oldBeliefsF.push_back( Factor( factor(I).vars() ) );
+        _oldBeliefsF.push_back( Factor( factor(I).vars() ) );
     
     // create update sequence
-    updateSeq.clear();
-    updateSeq.reserve( nrEdges() );
+    _updateSeq.clear();
+    _updateSeq.reserve( nrEdges() );
     for( size_t I = 0; I < nrFactors(); I++ )
         foreach( const Neighbor &i, nbF(I) )
-            updateSeq.push_back( Edge( i, i.dual ) );
+            _updateSeq.push_back( Edge( i, i.dual ) );
 }
 
 
@@ -284,7 +284,7 @@ Real BP::run() {
                       calcNewMessage( i, I.iter );
             }
             // Maximum-Residual BP [\ref EMK06]
-            for( size_t t = 0; t < updateSeq.size(); ++t ) {
+            for( size_t t = 0; t < _updateSeq.size(); ++t ) {
                 // update the message with the largest residual
                 size_t i, _I;
                 findMaxResidual( i, _I );
@@ -314,9 +314,9 @@ Real BP::run() {
         } else {
             // Sequential updates
             if( props.updates == Properties::UpdateType::SEQRND )
-                random_shuffle( updateSeq.begin(), updateSeq.end() );
+                random_shuffle( _updateSeq.begin(), _updateSeq.end() );
 
-            foreach( const Edge &e, updateSeq ) {
+            foreach( const Edge &e, _updateSeq ) {
                 calcNewMessage( e.first, e.second );
                 updateMessage( e.first, e.second );
             }
@@ -326,13 +326,13 @@ Real BP::run() {
         maxDiff = -INFINITY;
         for( size_t i = 0; i < nrVars(); ++i ) {
             Factor b( beliefV(i) );
-            maxDiff = std::max( maxDiff, dist( b, oldBeliefsV[i], DISTLINF ) );
-            oldBeliefsV[i] = b;
+            maxDiff = std::max( maxDiff, dist( b, _oldBeliefsV[i], DISTLINF ) );
+            _oldBeliefsV[i] = b;
         }
         for( size_t I = 0; I < nrFactors(); ++I ) {
             Factor b( beliefF(I) );
-            maxDiff = std::max( maxDiff, dist( b, oldBeliefsF[I], DISTLINF ) );
-            oldBeliefsF[I] = b;
+            maxDiff = std::max( maxDiff, dist( b, _oldBeliefsF[I], DISTLINF ) );
+            _oldBeliefsF[I] = b;
         }
 
         if( props.verbose >= 3 )
index 3347703..186a635 100644 (file)
@@ -108,7 +108,11 @@ JTree::JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic ) :
         memneeded *= sizeof(Real) * fudge;
         if( props.verbose >= 1 ) {
             cerr << "Estimate of needed memory: " << memneeded / 1024 << "kB" << endl;
-            cerr << "Maximum memory: " << props.maxmem / 1024 << "kB" << endl;
+            cerr << "Maximum memory: ";
+            if( props.maxmem )
+               cerr << props.maxmem / 1024 << "kB" << endl;
+            else
+               cerr << "unlimited" << endl;
         }
         if( props.maxmem && memneeded > props.maxmem )
             DAI_THROW(OUT_OF_MEMORY);
index 1e50296..d0e2c91 100644 (file)
@@ -177,3 +177,7 @@ GIBBS:                          GIBBS[iters=10000,burnin=100,restart=1000]
 
 CBP:                            CBP[max_levels=12,updates=SEQMAX,tol=1e-9,rec_tol=1e-9,maxiter=500,choose=CHOOSE_RANDOM,recursion=REC_FIXED,clamp=CLAMP_VAR,min_max_adj=1.0e-9,bbp_cfn=CFN_FACTOR_ENT,rand_seed=0,bbp_props=[tol=1.0e-9,maxiter=10000,damping=0,updates=SEQ_BP_REV],clamp_outfile=]
 BBP:                            CBP[choose=CHOOSE_BBP]
+
+# --- DECMAP ------------------
+
+DECMAP:                                DECMAP[ianame=BP,iaopts=[inference=MAXPROD,updates=SEQRND,logdomain=1,tol=1e-9,maxiter=10000,damping=0.1,verbose=0],reinit=1,verbose=0]
index f192b86..5607188 100755 (executable)
@@ -3,5 +3,5 @@
 ./testdai --report-iters false --report-time false --marginals VAR --aliases aliases.conf --filename $1 --methods EXACT JTREE_MINFILL_HUGIN JTREE_MINFILL_SHSH JTREE_WEIGHTEDMINFILL_HUGIN JTREE_WEIGHTEDMINFILL_SHSH JTREE_MINWEIGHT_HUGIN JTREE_MINWEIGHT_SHSH JTREE_MINNEIGHBORS_HUGIN JTREE_MINNEIGHBORS_SHSH BP BP_SEQFIX BP_SEQRND BP_SEQMAX BP_PARALL BP_SEQFIX_LOG BP_SEQRND_LOG BP_SEQMAX_LOG BP_PARALL_LOG FBP FBP_SEQFIX FBP_SEQRND FBP_SEQMAX FBP_PARALL FBP_SEQFIX_LOG FBP_SEQRND_LOG FBP_SEQMAX_LOG FBP_PARALL_LOG TRWBP TRWBP_SEQFIX TRWBP_SEQRND TRWBP_SEQMAX TRWBP_PARALL TRWBP_SEQFIX_LOG TRWBP_SEQRND_LOG TRWBP_SEQMAX_LOG TRWBP_PARALL_LOG MF MF_NAIVE_UNI MF_NAIVE_RND MF_HARDSPIN_UNI MF_HARDSPIN_RND TREEEP TREEEPWC GBP_MIN GBP_BETHE GBP_LOOP3 HAK_MIN HAK_BETHE HAK_DELTA HAK_LOOP3 HAK_LOOP4 HAK_LOOP5 MR_RESPPROP_FULL MR_CLAMPING_FULL MR_EXACT_FULL MR_RESPPROP_LINEAR MR_CLAMPING_LINEAR MR_EXACT_LINEAR LCBP LCBP_FULLCAV_SEQFIX LCBP_FULLCAVin_SEQFIX LCBP_FULLCAV_SEQRND LCBP_FULLCAVin_SEQRND LCBP_FULLCAV_NONE LCBP_FULLCAVin_NONE LCBP_PAIRCAV_SEQFIX LCBP_PAIRCAVin_SEQFIX LCBP_PAIRCAV_SEQRND LCBP_PAIRCAVin_SEQRND LCBP_PAIRCAV_NONE LCBP_PAIRCAVin_NONE LCBP_PAIR2CAV_SEQFIX LCBP_PAIR2CAVin_SEQFIX LCBP_PAIR2CAV_SEQRND LCBP_PAIR2CAVin_SEQRND LCBP_PAIR2CAV_NONE LCBP_PAIR2CAVin_NONE LCBP_UNICAV_SEQFIX LCBP_UNICAV_SEQRND LCTREEEP BBP
 # GBP_DELTA, GBP_LOOP4, GBP_LOOP5, GBP_LOOP6, GBP_LOOP7 misbehave
 # MAP inference
-./testdai --report-iters false --report-time false --marginals VAR --aliases aliases.conf --filename $1 --methods JTREE_MINFILL_HUGIN_MAP JTREE_MINFILL_SHSH_MAP JTREE_WEIGHTEDMINFILL_HUGIN_MAP JTREE_WEIGHTEDMINFILL_SHSH_MAP JTREE_MINWEIGHT_HUGIN_MAP JTREE_MINWEIGHT_SHSH_MAP JTREE_MINNEIGHBORS_HUGIN_MAP JTREE_MINNEIGHBORS_SHSH_MAP MP_SEQFIX MP_SEQRND MP_PARALL MP_SEQFIX_LOG MP_SEQRND_LOG MP_PARALL_LOG FMP_SEQFIX FMP_SEQRND FMP_PARALL FMP_SEQFIX_LOG FMP_SEQRND_LOG FMP_PARALL_LOG TRWMP_SEQFIX TRWMP_SEQRND TRWMP_PARALL TRWMP_SEQFIX_LOG TRWMP_SEQRND_LOG TRWMP_PARALL_LOG
+./testdai --report-iters false --report-time false --marginals VAR --aliases aliases.conf --filename $1 --methods JTREE_MINFILL_HUGIN_MAP JTREE_MINFILL_SHSH_MAP JTREE_WEIGHTEDMINFILL_HUGIN_MAP JTREE_WEIGHTEDMINFILL_SHSH_MAP JTREE_MINWEIGHT_HUGIN_MAP JTREE_MINWEIGHT_SHSH_MAP JTREE_MINNEIGHBORS_HUGIN_MAP JTREE_MINNEIGHBORS_SHSH_MAP MP_SEQFIX MP_SEQRND MP_PARALL MP_SEQFIX_LOG MP_SEQRND_LOG MP_PARALL_LOG FMP_SEQFIX FMP_SEQRND FMP_PARALL FMP_SEQFIX_LOG FMP_SEQRND_LOG FMP_PARALL_LOG TRWMP_SEQFIX TRWMP_SEQRND TRWMP_PARALL TRWMP_SEQFIX_LOG TRWMP_SEQRND_LOG TRWMP_PARALL_LOG DECMAP
 # *MP_SEQMAX and *MP_SEQMAX_LOG make no sense, apparently
index 6bf284e..f2931aa 100755 (executable)
@@ -4,5 +4,5 @@ REM Marginal inference
 REM GBP_DELTA, GBP_LOOP4, GBP_LOOP5, GBP_LOOP6, GBP_LOOP7 misbehave
 
 REM MAP inference
-@testdai --report-iters false --report-time false --marginals VAR --aliases aliases.conf --filename %1 --methods JTREE_MINFILL_HUGIN_MAP JTREE_MINFILL_SHSH_MAP JTREE_WEIGHTEDMINFILL_HUGIN_MAP JTREE_WEIGHTEDMINFILL_SHSH_MAP JTREE_MINWEIGHT_HUGIN_MAP JTREE_MINWEIGHT_SHSH_MAP JTREE_MINNEIGHBORS_HUGIN_MAP JTREE_MINNEIGHBORS_SHSH_MAP MP_SEQFIX MP_SEQRND MP_PARALL MP_SEQFIX_LOG MP_SEQRND_LOG MP_PARALL_LOG FMP_SEQFIX FMP_SEQRND FMP_PARALL FMP_SEQFIX_LOG FMP_SEQRND_LOG FMP_PARALL_LOG TRWMP_SEQFIX TRWMP_SEQRND TRWMP_PARALL TRWMP_SEQFIX_LOG TRWMP_SEQRND_LOG TRWMP_PARALL_LOG
+@testdai --report-iters false --report-time false --marginals VAR --aliases aliases.conf --filename %1 --methods JTREE_MINFILL_HUGIN_MAP JTREE_MINFILL_SHSH_MAP JTREE_WEIGHTEDMINFILL_HUGIN_MAP JTREE_WEIGHTEDMINFILL_SHSH_MAP JTREE_MINWEIGHT_HUGIN_MAP JTREE_MINWEIGHT_SHSH_MAP JTREE_MINNEIGHBORS_HUGIN_MAP JTREE_MINNEIGHBORS_SHSH_MAP MP_SEQFIX MP_SEQRND MP_PARALL MP_SEQFIX_LOG MP_SEQRND_LOG MP_PARALL_LOG FMP_SEQFIX FMP_SEQRND FMP_PARALL FMP_SEQFIX_LOG FMP_SEQRND_LOG FMP_PARALL_LOG TRWMP_SEQFIX TRWMP_SEQRND TRWMP_PARALL TRWMP_SEQFIX_LOG TRWMP_SEQRND_LOG TRWMP_PARALL_LOG DECMAP
 REM *MP_SEQMAX and *MP_SEQMAX_LOG make no sense, apparently
index c55296e..05b6e2e 100644 (file)
@@ -38,7 +38,7 @@ int main( int argc, char** argv ) {
     fg.ReadFromFile( argv[1] );
 
     PropertySet infprops;
-    infprops.set( "verbose", (size_t)1 );
+    infprops.set( "verbose", (size_t)0 );
     infprops.set( "updates", string("HUGIN") );
     InfAlg* inf = newInfAlg( "JTREE", fg, infprops );
     inf->init();
index 1cfb005..a157b49 100644 (file)
@@ -1821,3 +1821,20 @@ TRWMP_PARALL_LOG                         1.313e-01       4.991e-02       1.702e-01       6.840e-02
 # ({x13}, (9.230e-01, 7.703e-02))
 # ({x14}, (3.953e-01, 6.047e-01))
 # ({x15}, (6.047e-01, 3.953e-01))
+DECMAP                                         4.617e-01       3.126e-01       6.691e-01       4.224e-01       -9.136e-01      1.000e-09       
+# ({x0}, (0.000e+00, 1.000e+00))
+# ({x1}, (1.000e+00, 0.000e+00))
+# ({x2}, (1.000e+00, 0.000e+00))
+# ({x3}, (1.000e+00, 0.000e+00))
+# ({x4}, (0.000e+00, 1.000e+00))
+# ({x5}, (1.000e+00, 0.000e+00))
+# ({x6}, (1.000e+00, 0.000e+00))
+# ({x7}, (0.000e+00, 1.000e+00))
+# ({x8}, (0.000e+00, 1.000e+00))
+# ({x9}, (1.000e+00, 0.000e+00))
+# ({x10}, (1.000e+00, 0.000e+00))
+# ({x11}, (1.000e+00, 0.000e+00))
+# ({x12}, (0.000e+00, 1.000e+00))
+# ({x13}, (1.000e+00, 0.000e+00))
+# ({x14}, (0.000e+00, 1.000e+00))
+# ({x15}, (1.000e+00, 0.000e+00))