From 0e1e8b6c929541ebab29600d47244ea6ea93d9c4 Mon Sep 17 00:00:00 2001 From: Joris Mooij Date: Wed, 10 Feb 2010 09:50:48 +0100 Subject: [PATCH] Added some functionality to create various standard factors and renamed "Clamped BP" into "Conditioned BP" --- ChangeLog | 2 + Makefile | 13 +++++-- README | 2 +- include/dai/cbp.h | 4 +- include/dai/doc.h | 4 +- include/dai/factor.h | 39 ++++++++++++++++++++ src/factor.cpp | 66 +++++++++++++++++++++++++++++++++ utils/createfg.cpp | 87 +++++++++++++------------------------------- 8 files changed, 146 insertions(+), 71 deletions(-) create mode 100644 src/factor.cpp diff --git a/ChangeLog b/ChangeLog index 40129cf..0c058e6 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,5 @@ +* Added some functionality to create various standard factors to factor.cpp +* Renamed "Clamped BP" into "Conditioned BP" * Improved documentation * Documented tests/testdai * Moved platform independent build options into Makefile.ALL diff --git a/Makefile b/Makefile index b592e2c..c26f14a 100644 --- a/Makefile +++ b/Makefile @@ -168,6 +168,9 @@ lc$(OE) : $(SRC)/lc.cpp $(INC)/lc.h $(HEADERS) mf$(OE) : $(SRC)/mf.cpp $(INC)/mf.h $(HEADERS) $(CC) -c $(SRC)/mf.cpp +factor$(OE) : $(SRC)/factor.cpp $(INC)/factor.h $(HEADERS) + $(CC) -c $(SRC)/factor.cpp + factorgraph$(OE) : $(SRC)/factorgraph.cpp $(INC)/factorgraph.h $(HEADERS) $(CC) -c $(SRC)/factorgraph.cpp @@ -286,14 +289,16 @@ utils/fginfo$(EE) : utils/fginfo.cpp $(HEADERS) $(LIB)/libdai$(LE) # LIBRARY ########## +OBJECTS:=bipgraph$(OE) varset$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factor$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS) + ifneq ($(OS),WINDOWS) -$(LIB)/libdai$(LE) : bipgraph$(OE) varset$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS) +$(LIB)/libdai$(LE) : $(OBJECTS) -mkdir -p lib - ar rcus $(LIB)/libdai$(LE) bipgraph$(OE) varset$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS) + ar rcus $(LIB)/libdai$(LE) $(OBJECTS) else -$(LIB)/libdai$(LE) : bipgraph$(OE) varset$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS) +$(LIB)/libdai$(LE) : $(OBJECTS) -mkdir lib - lib /out:$(LIB)/libdai$(LE) bipgraph$(OE) varset$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS) + lib /out:$(LIB)/libdai$(LE) $(OBJECTS) endif diff --git a/README b/README index 58403ae..7245cb8 100644 --- a/README +++ b/README @@ -80,7 +80,7 @@ Currently, libDAI supports the following (approximate) inference methods: * Double-loop GBP [HAK03]; * Various variants of Loop Corrected Belief Propagation [MoK07, MoR05]; * Gibbs sampler; - * Clamped Belief Propagation [EaG09]. + * Conditioned Belief Propagation [EaG09]. These inference methods can be used to calculate partition sums, marginals over subsets of variables, and MAP states (the joint state of variables that has diff --git a/include/dai/cbp.h b/include/dai/cbp.h index 35bc771..57f9281 100644 --- a/include/dai/cbp.h +++ b/include/dai/cbp.h @@ -9,7 +9,7 @@ /// \file -/// \brief Defines class CBP, which implements Clamped Belief Propagation +/// \brief Defines class CBP, which implements Conditioned Belief Propagation #ifndef __defined_libdai_cbp_h @@ -26,7 +26,7 @@ namespace dai { -/// Class for CBP (Clamped Belief Propagation) [\ref EaG09] +/// Class for CBP (Conditioned Belief Propagation) [\ref EaG09] /** This approximate inference algorithm uses configurable heuristics to choose a variable * \f$ x_i \f$ and a state \f$ x_i^* \f$. Inference is done with \f$ x_i \f$ "clamped" to \f$ x_i^* \f$ * (i.e., conditional on \f$ x_i = x_i^* \f$), and also with the negation of this condition. diff --git a/include/dai/doc.h b/include/dai/doc.h index 254a0b8..7d6383a 100644 --- a/include/dai/doc.h +++ b/include/dai/doc.h @@ -82,7 +82,7 @@ * - Various variants of Loop Corrected Belief Propagation * [\ref MoK07, \ref MoR05]; * - Gibbs sampler; - * - Clamped Belief Propagation [\ref EaG09]. + * - Conditioned Belief Propagation [\ref EaG09]. * * These inference methods can be used to calculate partition sums, marginals * over subsets of variables, and MAP states (the joint state of variables that @@ -437,7 +437,7 @@ * - Double-loop GBP: dai::HAK [\ref HAK03] * - Loop Corrected Belief Propagation: dai::MR [\ref MoR05] and dai::LC [\ref MoK07] * - Gibbs sampling: dai::Gibbs - * - Clamped Belief Propagation: dai::CBP [\ref EaG09] + * - Conditioned Belief Propagation: dai::CBP [\ref EaG09] * * Not all inference tasks are implemented by each method: calculating MAP states * is only possible with dai::JTree and dai::BP, calculating partition sums is diff --git a/include/dai/factor.h b/include/dai/factor.h index 4602317..50cc961 100644 --- a/include/dai/factor.h +++ b/include/dai/factor.h @@ -591,6 +591,45 @@ template T MutualInfo(const TFactor &f) { typedef TFactor Factor; +/// Returns a binary single-variable factor \f$ \exp(hx) \f$ where \f$ x = \pm 1 \f$ +/** \param x Variable (should be binary) + * \param h Field strength + */ +Factor BinaryFactor( const Var &x, Real h ); + + +/// Returns a binary pairwise factor \f$ \exp(J x_1 x_2) \f$ where \f$ x_1, x_2 = \pm 1 \f$ +/** \param x1 First variable (should be binary) + * \param x2 Second variable (should be binary) + * \param J Coupling strength + */ +Factor BinaryFactor( const Var &x1, const Var &x2, Real J ); + + +/// Returns a random factor on the variables \a vs with strength \a beta +/** Each entry are set by drawing a normally distributed random with mean + * 0 and standard-deviation \a beta, and taking its exponent. + * \param vs Variables + * \param beta Factor strength (inverse temperature) + */ +Factor RandomFactor( const VarSet &vs, Real beta ); + + +/// Returns a pairwise Potts factor \f$ \exp( J \delta_{x_1, x_2} ) \f$ +/** \param x1 First variable + * \param x2 Second variable (should have the same number of states as \a x1) + * \param J Factor strength + */ +Factor PottsFactor( const Var &x1, const Var &x2, Real J ); + + +/// Returns a Kronecker delta point mass +/** \param v Variable + * \param state The state of \a v that should get value 1 + */ +Factor DeltaFactor( const Var &v, size_t state ); + + } // end of namespace dai diff --git a/src/factor.cpp b/src/factor.cpp new file mode 100644 index 0000000..b4f69de --- /dev/null +++ b/src/factor.cpp @@ -0,0 +1,66 @@ +/* This file is part of libDAI - http://www.libdai.org/ + * + * libDAI is licensed under the terms of the GNU General Public License version + * 2, or (at your option) any later version. libDAI is distributed without any + * warranty. See the file COPYING for more details. + * + * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org] + * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands + */ + + +#include + + +namespace dai { + + +using namespace std; + + +Factor BinaryFactor( const Var &n, Real h ) { + DAI_ASSERT( n.states() == 2 ); + Real buf[2]; + buf[0] = std::exp(-h); + buf[1] = std::exp(h); + return Factor(n, &buf[0]); +} + + +Factor BinaryFactor( const Var &n1, const Var &n2, Real J ) { + DAI_ASSERT( n1.states() == 2 ); + DAI_ASSERT( n2.states() == 2 ); + DAI_ASSERT( n1 != n2 ); + Real buf[4]; + buf[0] = (buf[3] = std::exp(J)); + buf[1] = (buf[2] = std::exp(-J)); + return Factor( VarSet(n1, n2), &buf[0] ); +} + + +Factor RandomFactor( const VarSet &ns, Real beta ) { + Factor fac( ns ); + for( size_t t = 0; t < fac.states(); t++ ) + fac[t] = std::exp(rnd_stdnormal() * beta); + return fac; +} + + +Factor PottsFactor( const Var &n1, const Var &n2, Real J ) { + Factor fac( VarSet( n1, n2 ), 1.0 ); + DAI_ASSERT( n1.states() == n2.states() ); + for( size_t s = 0; s < n1.states(); s++ ) + fac[ s * (n1.states() + 1) ] = std::exp(J); + return fac; +} + + +Factor DeltaFactor( const Var &v, size_t state ) { + Factor fac( v, 0.0 ); + DAI_ASSERT( state < v.states() ); + fac[state] = 1.0; + return fac; +} + + +} // end of namespace dai diff --git a/utils/createfg.cpp b/utils/createfg.cpp index 627b978..9dfd1ca 100644 --- a/utils/createfg.cpp +++ b/utils/createfg.cpp @@ -30,40 +30,35 @@ typedef matrix::value_array_type::const_iterator matrix_vcit; typedef matrix::index_array_type::const_iterator matrix_icit; -Factor BinaryFactor( const Var &n, Real field ) { - DAI_ASSERT( n.states() == 2 ); - Real buf[2]; - buf[0] = std::exp(-field); - buf[1] = std::exp(field); - return Factor(n, &buf[0]); -} - - -Factor BinaryFactor( const Var &n1, const Var &n2, Real coupling ) { - DAI_ASSERT( n1.states() == 2 ); - DAI_ASSERT( n2.states() == 2 ); - DAI_ASSERT( n1 != n2 ); - Real buf[4]; - buf[0] = (buf[3] = std::exp(coupling)); - buf[1] = (buf[2] = std::exp(-coupling)); - return Factor( VarSet(n1, n2), &buf[0] ); -} +// w should be upper triangular or lower triangular +void WTh2FG( const matrix &w, const vector &th, FactorGraph &fg ) { + vector vars; + vector factors; + size_t N = th.size(); + DAI_ASSERT( (w.size1() == N) && (w.size2() == N) ); -Factor RandomFactor( const VarSet &ns, Real beta ) { - Factor fac( ns ); - for( size_t t = 0; t < fac.states(); t++ ) - fac[t] = std::exp(rnd_stdnormal() * beta); - return fac; -} + vars.reserve(N); + for( size_t i = 0; i < N; i++ ) + vars.push_back(Var(i,2)); + factors.reserve( w.nnz() + N ); + // walk through the sparse array structure + // this is similar to matlab sparse arrays + // index2 gives the column index (similar to ir in matlab) + // index1 gives the starting indices for each row (similar to jc in matlab) + size_t i = 0; + for( size_t pos = 0; pos < w.nnz(); pos++ ) { + while( pos == w.index1_data()[i+1] ) + i++; + size_t j = w.index2_data()[pos]; + Real w_ij = w.value_data()[pos]; + factors.push_back( BinaryFactor( vars[i], vars[j], w_ij ) ); + } + for( size_t i = 0; i < N; i++ ) + factors.push_back( BinaryFactor( vars[i], th[i] ) ); -Factor PottsFactor( const Var &n1, const Var &n2, Real beta ) { - Factor fac( VarSet( n1, n2 ), 1.0 ); - DAI_ASSERT( n1.states() == n2.states() ); - for( size_t s = 0; s < n1.states(); s++ ) - fac[ s * (n1.states() + 1) ] = std::exp(beta); - return fac; + fg = FactorGraph( factors.begin(), factors.end(), vars.begin(), vars.end(), factors.size(), vars.size() ); } @@ -94,38 +89,6 @@ void MakeHOIFG( size_t N, size_t M, size_t k, Real sigma, FactorGraph &fg ) { } -// w should be upper triangular or lower triangular -void WTh2FG( const matrix &w, const vector &th, FactorGraph &fg ) { - vector vars; - vector factors; - - size_t N = th.size(); - DAI_ASSERT( (w.size1() == N) && (w.size2() == N) ); - - vars.reserve(N); - for( size_t i = 0; i < N; i++ ) - vars.push_back(Var(i,2)); - - factors.reserve( w.nnz() + N ); - // walk through the sparse array structure - // this is similar to matlab sparse arrays - // index2 gives the column index (similar to ir in matlab) - // index1 gives the starting indices for each row (similar to jc in matlab) - size_t i = 0; - for( size_t pos = 0; pos < w.nnz(); pos++ ) { - while( pos == w.index1_data()[i+1] ) - i++; - size_t j = w.index2_data()[pos]; - Real w_ij = w.value_data()[pos]; - factors.push_back( BinaryFactor( vars[i], vars[j], w_ij ) ); - } - for( size_t i = 0; i < N; i++ ) - factors.push_back( BinaryFactor( vars[i], th[i] ) ); - - fg = FactorGraph( factors.begin(), factors.end(), vars.begin(), vars.end(), factors.size(), vars.size() ); -} - - void MakeFullFG( size_t N, Real mean_w, Real mean_th, Real sigma_w, Real sigma_th, FactorGraph &fg ) { matrix w(N,N,N*(N-1)/2); vector th(N,0.0); -- 2.20.1