Added max-product version of BP
authorJoris Mooij <jorism@marvin.jorismooij.nl>
Mon, 29 Sep 2008 16:49:33 +0000 (18:49 +0200)
committerJoris Mooij <jorism@marvin.jorismooij.nl>
Mon, 29 Sep 2008 16:49:33 +0000 (18:49 +0200)
STATUS
include/dai/bp.h
src/bp.cpp
tests/aliases.conf

diff --git a/STATUS b/STATUS
index de239bb..940897a 100644 (file)
--- a/STATUS
+++ b/STATUS
@@ -8,7 +8,6 @@ OPTIMIZATION:
 
 - Idea: use a PropertySet as output of a DAIAlg, instead of functions like maxDiff and Iterations().
 - A DAIAlg<T> should not inherit from a FactorGraph/RegionGraph, but should store a reference to it
-- Add max-product to BP
 
 TODO FOR RELEASE:
 - http://www.boost.org/development/requirements.html#Design_and_Programming
index f5b4886..ba75fbd 100644 (file)
@@ -57,6 +57,8 @@ class BP : public DAIAlgFG {
             double damping;
             DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL)
             UpdateType updates;
+            DAI_ENUM(InfType,SUMPROD,MAXPROD)
+            InfType inference;
         } props;
         static const char *Name;
 
index fb7220a..ac431a2 100644 (file)
@@ -58,6 +58,10 @@ void BP::setProperties( const PropertySet &opts ) {
         props.damping = opts.getStringAs<double>("damping");
     else
         props.damping = 0.0;
+    if( opts.hasKey("inference") )
+        props.inference = opts.getStringAs<Properties::InfType>("inference");
+    else
+        props.inference = Properties::InfType::SUMPROD;
 }
 
 
@@ -69,6 +73,7 @@ PropertySet BP::getProperties() const {
     opts.Set( "logdomain", props.logdomain );
     opts.Set( "updates", props.updates );
     opts.Set( "damping", props.damping );
+    opts.Set( "inference", props.inference );
     return opts;
 }
 
@@ -81,7 +86,8 @@ string BP::printProperties() const {
     s << "verbose=" << props.verbose << ",";
     s << "logdomain=" << props.logdomain << ",";
     s << "updates=" << props.updates << ",";
-    s << "damping=" << props.damping << "]";
+    s << "damping=" << props.damping << ",";
+    s << "inference=" << props.inference << "]";
     return s.str();
 }
 
@@ -189,8 +195,13 @@ void BP::calcNewMessage( size_t i, size_t _I ) {
         Prob marg( var(i).states(), 0.0 );
         // ind is the precalculated IndexFor(i,I) i.e. to x_I == k corresponds x_i == ind[k]
         const ind_t ind = index(i,_I);
-        for( size_t r = 0; r < prod.size(); ++r )
-            marg[ind[r]] += prod[r];
+        if( props.inference == Properties::InfType::SUMPROD ) 
+            for( size_t r = 0; r < prod.size(); ++r )
+                marg[ind[r]] += prod[r];
+        else
+            for( size_t r = 0; r < prod.size(); ++r )
+                if( prod[r] > marg[ind[r]] ) 
+                    marg[ind[r]] = prod[r];
         marg.normalize();
 
         // Store result
index b3fd1da..d25cb74 100644 (file)
@@ -8,6 +8,14 @@ BP_SEQFIX_LOG:                  BP[updates=SEQFIX,tol=1e-9,maxiter=10000,logdoma
 BP_SEQRND_LOG:                  BP[updates=SEQRND,tol=1e-9,maxiter=10000,logdomain=1]
 BP_SEQMAX_LOG:                  BP[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=1]
 BP_PARALL_LOG:                  BP[updates=PARALL,tol=1e-9,maxiter=10000,logdomain=1]
+MP_SEQFIX:                      BP[updates=SEQFIX,tol=1e-9,maxiter=10000,logdomain=0,inference=MAXPROD]
+MP_SEQRND:                      BP[updates=SEQRND,tol=1e-9,maxiter=10000,logdomain=0,inference=MAXPROD]
+MP_SEQMAX:                      BP[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0,inference=MAXPROD]
+MP_PARALL:                      BP[updates=PARALL,tol=1e-9,maxiter=10000,logdomain=0,inference=MAXPROD]
+MP_SEQFIX_LOG:                  BP[updates=SEQFIX,tol=1e-9,maxiter=10000,logdomain=1,inference=MAXPROD]
+MP_SEQRND_LOG:                  BP[updates=SEQRND,tol=1e-9,maxiter=10000,logdomain=1,inference=MAXPROD]
+MP_SEQMAX_LOG:                  BP[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=1,inference=MAXPROD]
+MP_PARALL_LOG:                  BP[updates=PARALL,tol=1e-9,maxiter=10000,logdomain=1,inference=MAXPROD]
 
 # --- JTREE -------------------