+* Fixed bug in findMaximum(): inconsistent max-beliefs are now detected,
+ instead of returning a MAP state with zero joint probability
+ (reported by Hynek Urban)
* Fixed a Boost-related bug in src/util.cpp (reported by Avneesh Saluja)
(the random seed needs to be an unsigned int on some platforms)
* Fixed two bugs in examples/example_sprinkler_gibbs (reported by Priya)
#include <iostream>
#include <map>
#include <dai/alldai.h> // Include main libDAI header file
+#include <dai/jtree.h>
+#include <dai/bp.h>
+#include <dai/decmap.h>
using namespace dai;
*
* Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
* Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
+ * Copyright (C) 2008-2009 Giuseppe Passino
*/
std::vector<VarSet> maximalFactorDomains() const;
/// Evaluates the log score (i.e., minus the energy) of the joint configuration \a statevec
- Real logScore( const std::vector<size_t>& statevec );
+ Real logScore( const std::vector<size_t>& statevec ) const;
//@}
/// \name Backup/restore mechanism for factors
virtual Real logZ() const;
/** \pre Assumes that run() has been called and that \a props.inference == \c MAXPROD
*/
- std::vector<std::size_t> findMaximum() const { return dai::findMaximum( *this ); }
+ std::vector<std::size_t> findMaximum() const;
virtual void init() {}
virtual void init( const VarSet &/*ns*/ ) {}
virtual Real run();
*
* Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
* Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
+ * Copyright (C) 2008-2009 Giuseppe Passino
*/
*
* Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
* Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
+ * Copyright (C) 2008-2009 Giuseppe Passino
+ * Copyright (C) 2008 Claudio Lima
*/
*
* Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
* Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
+ * Copyright (C) 2008-2009 Giuseppe Passino
*/
vector<bool> visitedVars( obj.fg().nrVars(), false );
vector<bool> visitedFactors( obj.fg().nrFactors(), false );
stack<size_t> scheduledFactors;
- for( size_t i = 0; i < obj.fg().nrVars(); ++i ) {
- if( visitedVars[i] )
+ scheduledFactors.push( 0 );
+ while( !scheduledFactors.empty() ) {
+ size_t I = scheduledFactors.top();
+ scheduledFactors.pop();
+ if( visitedFactors[I] )
continue;
- visitedVars[i] = true;
-
- // Maximise with respect to variable i
- Prob prod = obj.beliefV(i).p();
- maximum[i] = prod.argmax().first;
-
- foreach( const Neighbor &I, obj.fg().nbV(i) )
- if( !visitedFactors[I] )
- scheduledFactors.push(I);
-
- while( !scheduledFactors.empty() ){
- size_t I = scheduledFactors.top();
- scheduledFactors.pop();
- if( visitedFactors[I] )
- continue;
- visitedFactors[I] = true;
-
- // Evaluate if some neighboring variables still need to be fixed; if not, we're done
- bool allDetermined = true;
+ visitedFactors[I] = true;
+
+ // Get marginal of factor I
+ Prob probF = obj.beliefF(I).p();
+
+ // The allowed configuration is restrained according to the variables assigned so far:
+ // pick the argmax amongst the allowed states
+ Real maxProb = -numeric_limits<Real>::max();
+ State maxState( obj.fg().factor(I).vars() );
+ size_t maxcount = 0;
+ for( State s( obj.fg().factor(I).vars() ); s.valid(); ++s ) {
+ // First, calculate whether this state is consistent with variables that
+ // have been assigned already
+ bool allowedState = true;
foreach( const Neighbor &j, obj.fg().nbF(I) )
- if( !visitedVars[j.node] ) {
- allDetermined = false;
+ if( visitedVars[j.node] && maximum[j.node] != s(obj.fg().var(j.node)) ) {
+ allowedState = false;
break;
}
- if( allDetermined )
- continue;
-
- // Get marginal of factor I
- Prob probF = obj.beliefF(I).p();
-
- // The allowed configuration is restrained according to the variables assigned so far:
- // pick the argmax amongst the allowed states
- Real maxProb = -numeric_limits<Real>::max();
- State maxState( obj.fg().factor(I).vars() );
- for( State s( obj.fg().factor(I).vars() ); s.valid(); ++s ) {
- // First, calculate whether this state is consistent with variables that
- // have been assigned already
- bool allowedState = true;
- foreach( const Neighbor &j, obj.fg().nbF(I) )
- if( visitedVars[j.node] && maximum[j.node] != s(obj.fg().var(j.node)) ) {
- allowedState = false;
- break;
- }
- // If it is consistent, check if its probability is larger than what we have seen so far
- if( allowedState && probF[s] > maxProb ) {
+ // If it is consistent, check if its probability is larger than what we have seen so far
+ if( allowedState ) {
+ if( probF[s] > maxProb ) {
maxState = s;
maxProb = probF[s];
- }
+ maxcount = 1;
+ } else
+ maxcount++;
}
-
- // Decode the argmax
- foreach( const Neighbor &j, obj.fg().nbF(I) ) {
- if( visitedVars[j.node] ) {
- // We have already visited j earlier - hopefully our state is consistent
- if( maximum[j.node] != maxState( obj.fg().var(j.node) ) )
- DAI_THROWE(RUNTIME_ERROR,"MAP state inconsistent due to loops");
- } else {
- // We found a consistent state for variable j
- visitedVars[j.node] = true;
- maximum[j.node] = maxState( obj.fg().var(j.node) );
- foreach( const Neighbor &J, obj.fg().nbV(j) )
- if( !visitedFactors[J] )
- scheduledFactors.push(J);
- }
+ }
+ DAI_ASSERT( maxProb != 0.0 );
+ DAI_ASSERT( obj.fg().factor(I).p()[maxState] != 0.0 );
+
+ // Decode the argmax
+ foreach( const Neighbor &j, obj.fg().nbF(I) ) {
+ if( visitedVars[j.node] ) {
+ // We have already visited j earlier - hopefully our state is consistent
+ if( maximum[j.node] != maxState( obj.fg().var(j.node) ) )
+ DAI_THROWE(RUNTIME_ERROR,"MAP state inconsistent due to loops");
+ } else {
+ // We found a consistent state for variable j
+ visitedVars[j.node] = true;
+ maximum[j.node] = maxState( obj.fg().var(j.node) );
+ foreach( const Neighbor &J, obj.fg().nbV(j) )
+ if( !visitedFactors[J] )
+ scheduledFactors.push(J);
}
}
}
*
* Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
* Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
+ * Copyright (C) 2008 Christian Wojek
*/
Ivars.push_back( Var(labels[mi], dims[mi]) );
}
facs.push_back( Factor( VarSet( Ivars.begin(), Ivars.end(), Ivars.size() ), (Real)0 ) );
+ if( verbose >= 3 )
+ cerr << " vardims: " << vardims << endl;
// calculate permutation object
Permute permindex( Ivars );
}
-Real FactorGraph::logScore( const std::vector<size_t>& statevec ) {
+Real FactorGraph::logScore( const std::vector<size_t>& statevec ) const {
// Construct a State object that represents statevec
// This decouples the representation of the joint state in statevec from the factor graph
map<Var, size_t> statemap;
#include <iostream>
+#include <stack>
#include <dai/jtree.h>
}
+std::vector<size_t> JTree::findMaximum() const {
+ vector<size_t> maximum( nrVars() );
+ vector<bool> visitedVars( nrVars(), false );
+ vector<bool> visitedORs( nrORs(), false );
+ stack<size_t> scheduledORs;
+ scheduledORs.push( 0 );
+ while( !scheduledORs.empty() ) {
+ size_t alpha = scheduledORs.top();
+ scheduledORs.pop();
+ if( visitedORs[alpha] )
+ continue;
+ visitedORs[alpha] = true;
+
+ // Get marginal of outer region alpha
+ Prob probF = Qa[alpha].p();
+
+ // The allowed configuration is restrained according to the variables assigned so far:
+ // pick the argmax amongst the allowed states
+ Real maxProb = -numeric_limits<Real>::max();
+ State maxState( OR(alpha).vars() );
+ size_t maxcount = 0;
+ for( State s( OR(alpha).vars() ); s.valid(); ++s ) {
+ // First, calculate whether this state is consistent with variables that
+ // have been assigned already
+ bool allowedState = true;
+ foreach( const Var& j, OR(alpha).vars() ) {
+ size_t j_index = findVar(j);
+ if( visitedVars[j_index] && maximum[j_index] != s(j) ) {
+ allowedState = false;
+ break;
+ }
+ }
+ // If it is consistent, check if its probability is larger than what we have seen so far
+ if( allowedState ) {
+ if( probF[s] > maxProb ) {
+ maxState = s;
+ maxProb = probF[s];
+ maxcount = 1;
+ } else
+ maxcount++;
+ }
+ }
+ DAI_ASSERT( maxProb != 0.0 );
+ DAI_ASSERT( Qa[alpha][maxState] != 0.0 );
+
+ // Decode the argmax
+ foreach( const Var& j, OR(alpha).vars() ) {
+ size_t j_index = findVar(j);
+ if( visitedVars[j_index] ) {
+ // We have already visited j earlier - hopefully our state is consistent
+ if( maximum[j_index] != maxState( j ) )
+ DAI_THROWE(RUNTIME_ERROR,"MAP state inconsistent due to loops");
+ } else {
+ // We found a consistent state for variable j
+ visitedVars[j_index] = true;
+ maximum[j_index] = maxState( j );
+ foreach( const Neighbor &beta, nbOR(alpha) )
+ foreach( const Neighbor &alpha2, nbIR(beta) )
+ if( !visitedORs[alpha2] )
+ scheduledORs.push(alpha2);
+ }
+ }
+ }
+ return maximum;
+}
+
+
} // end of namespace dai
*
* Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
* Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
+ * Copyright (C) 2009 Sebastian Nowozin
*/