Improved HAK (added 'maxtime' property)
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Tue, 3 Aug 2010 14:38:07 +0000 (16:38 +0200)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Tue, 3 Aug 2010 14:38:07 +0000 (16:38 +0200)
ChangeLog
include/dai/hak.h
include/dai/regiongraph.h
src/hak.cpp
src/regiongraph.cpp

index 33fe4c6..05786ee 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,6 @@
 git HEAD
 --------
+* Improved HAK (added 'maxtime' property)
 * Improved TreeEP (added 'maxtime' property)
 * Added FactorGraph::logScore( const std::vector<size_t>& statevec )
 * Improved Gibbs
index 17d3083..bf37618 100644 (file)
@@ -68,6 +68,9 @@ class HAK : public DAIAlgRG {
             /// Maximum number of iterations
             size_t maxiter;
 
+            /// Maximum time (in seconds)
+            double maxtime;
+
             /// Tolerance for convergence test
             Real tol;
 
index d6b7870..9a72a83 100644 (file)
@@ -260,7 +260,7 @@ class RegionGraph : public FactorGraph {
         void construct( const FactorGraph& fg, const std::vector<VarSet>& ors, const std::vector<Region>& irs, const std::vector<std::pair<size_t,size_t> >& edges );
 
         /// Helper function for constructors (CVM style)
-        void constructCVM( const FactorGraph& fg, const std::vector<VarSet>& cl );
+        void constructCVM( const FactorGraph& fg, const std::vector<VarSet>& cl, size_t verbose=0 );
 
         /// Recompute all outer regions
         /** The factor contents of each outer region is set to the product of the factors belonging to that region.
index 8f8c5fe..924be17 100644 (file)
@@ -45,15 +45,21 @@ TFactor<T>& makeZero( TFactor<T> &f, T epsilon ) {
 
 void HAK::setProperties( const PropertySet &opts ) {
     DAI_ASSERT( opts.hasKey("tol") );
-    DAI_ASSERT( opts.hasKey("maxiter") );
     DAI_ASSERT( opts.hasKey("doubleloop") );
     DAI_ASSERT( opts.hasKey("clusters") );
 
     props.tol = opts.getStringAs<Real>("tol");
-    props.maxiter = opts.getStringAs<size_t>("maxiter");
     props.doubleloop = opts.getStringAs<bool>("doubleloop");
     props.clusters = opts.getStringAs<Properties::ClustersType>("clusters");
 
+    if( opts.hasKey("maxiter") )
+        props.maxiter = opts.getStringAs<size_t>("maxiter");
+    else
+        props.maxiter = 10000;
+    if( opts.hasKey("maxtime") )
+        props.maxtime = opts.getStringAs<Real>("maxtime");
+    else
+        props.maxtime = INFINITY;
     if( opts.hasKey("verbose") )
         props.verbose = opts.getStringAs<size_t>("verbose");
     else
@@ -77,6 +83,7 @@ PropertySet HAK::getProperties() const {
     PropertySet opts;
     opts.set( "tol", props.tol );
     opts.set( "maxiter", props.maxiter );
+    opts.set( "maxtime", props.maxtime );
     opts.set( "verbose", props.verbose );
     opts.set( "doubleloop", props.doubleloop );
     opts.set( "clusters", props.clusters );
@@ -92,6 +99,7 @@ string HAK::printProperties() const {
     s << "[";
     s << "tol=" << props.tol << ",";
     s << "maxiter=" << props.maxiter << ",";
+    s << "maxtime=" << props.maxtime << ",";
     s << "verbose=" << props.verbose << ",";
     s << "doubleloop=" << props.doubleloop << ",";
     s << "clusters=" << props.clusters << ",";
@@ -175,11 +183,15 @@ HAK::HAK(const FactorGraph & fg, const PropertySet &opts) : DAIAlgRG(), _Qa(), _
     } else if( props.clusters == Properties::ClustersType::LOOP ) {
         cl = fg.maximalFactorDomains();
         set<VarSet> scl;
+        if( props.verbose >= 2 )
+            cerr << "Searching loops...";
         for( size_t i0 = 0; i0 < fg.nrVars(); i0++ ) {
             VarSet i0d = fg.delta(i0);
             if( props.loopdepth > 1 )
                 findLoopClusters( fg, scl, fg.var(i0), fg.var(i0), props.loopdepth - 1, fg.delta(i0) );
         }
+        if( props.verbose >= 2 )
+            cerr << "done" << endl;
         for( set<VarSet>::const_iterator c = scl.begin(); c != scl.end(); c++ )
             cl.push_back(*c);
         if( props.verbose >= 3 ) {
@@ -497,7 +509,7 @@ Real HAK::doDoubleLoop() {
     size_t outer_iter = 0;
     size_t total_iter = 0;
     Real maxDiff = INFINITY;
-    for( outer_iter = 0; outer_iter < outer_maxiter && maxDiff > outer_tol; outer_iter++ ) {
+    for( outer_iter = 0; outer_iter < outer_maxiter && maxDiff > outer_tol && (toc() - tic) < props.maxtime; outer_iter++ ) {
         // Calculate new outer regions
         for( size_t alpha = 0; alpha < nrORs(); alpha++ ) {
             OR(alpha) = org_ORs[alpha];
@@ -548,7 +560,7 @@ Real HAK::doDoubleLoop() {
         if( maxDiff > props.tol ) {
             if( props.verbose == 1 )
                 cerr << endl;
-                cerr << Name << "::doDoubleLoop:  WARNING: not converged within " << outer_maxiter << " passes (" << toc() - tic << " seconds)...final maxdiff:" << maxDiff << endl;
+                cerr << Name << "::doDoubleLoop:  WARNING: not converged after " << total_iter << " passes (" << toc() - tic << " seconds)...final maxdiff:" << maxDiff << endl;
             } else {
                 if( props.verbose >= 3 )
                     cerr << Name << "::doDoubleLoop:  ";
index 05c4c16..50b5d04 100644 (file)
@@ -56,12 +56,21 @@ void RegionGraph::construct( const FactorGraph &fg, const std::vector<VarSet> &o
 }
 
 
-void RegionGraph::constructCVM( const FactorGraph &fg, const std::vector<VarSet> &cl ) {
+void RegionGraph::constructCVM( const FactorGraph &fg, const std::vector<VarSet> &cl, size_t verbose ) {
+    if( verbose )
+        cerr << "constructCVM called (" << fg.nrVars() << " vars, " << fg.nrFactors() << " facs, " << cl.size() << " clusters)" << endl;
+
     // Retain only maximal clusters
+    if( verbose )
+        cerr << "  Constructing ClusterGraph" << endl;
     ClusterGraph cg( cl );
+    if( verbose )
+        cerr << "  Erasing non-maximal clusters" << endl;
     cg.eraseNonMaximal();
 
     // Create inner regions - first pass
+    if( verbose )
+        cerr << "  Creating inner regions (first pass)" << endl;
     set<VarSet> betas;
     for( size_t alpha = 0; alpha < cg.nrClusters(); alpha++ )
         for( size_t alpha2 = alpha; (++alpha2) != cg.nrClusters(); ) {
@@ -71,6 +80,8 @@ void RegionGraph::constructCVM( const FactorGraph &fg, const std::vector<VarSet>
         }
 
     // Create inner regions - subsequent passes
+    if( verbose )
+        cerr << "  Creating inner regions (next passes)" << endl;
     set<VarSet> new_betas;
     do {
         new_betas.clear();
@@ -84,12 +95,16 @@ void RegionGraph::constructCVM( const FactorGraph &fg, const std::vector<VarSet>
     } while( new_betas.size() );
 
     // Create inner regions - final phase
+    if( verbose )
+        cerr << "  Creating inner regions (final phase)" << endl;
     vector<Region> irs;
     irs.reserve( betas.size() );
     for( set<VarSet>::const_iterator beta = betas.begin(); beta != betas.end(); beta++ )
         irs.push_back( Region(*beta,0.0) );
 
     // Create edges
+    if( verbose )
+        cerr << "  Creating edges" << endl;
     vector<pair<size_t,size_t> > edges;
     for( size_t beta = 0; beta < irs.size(); beta++ )
         for( size_t alpha = 0; alpha < cg.nrClusters(); alpha++ )
@@ -97,10 +112,17 @@ void RegionGraph::constructCVM( const FactorGraph &fg, const std::vector<VarSet>
                 edges.push_back( pair<size_t,size_t>(alpha,beta) );
 
     // Construct region graph
+    if( verbose )
+        cerr << "  Constructing region graph" << endl;
     construct( fg, cg.clusters(), irs, edges );
 
     // Calculate counting numbers
+    if( verbose )
+        cerr << "  Calculating counting numbers" << endl;
     calcCVMCountingNumbers();
+    
+    if( verbose )
+        cerr << "Done." << endl;
 }