WITH_JTREE=true
WITH_MR=true
WITH_GIBBS=true
-WITH_BP_DUAL=true
WITH_CBP=true
# Build doxygen documentation?
WITH_DOC=true
WITH_JTREE=true
WITH_MR=true
WITH_GIBBS=true
-WITH_BP_DUAL=true
WITH_CBP=true
# Build doxygen documentation?
WITH_DOC=true
WITH_JTREE=true
WITH_MR=true
WITH_GIBBS=true
-WITH_BP_DUAL=true
WITH_CBP=true
# Build doxygen documentation?
WITH_DOC=true
WITH_JTREE=true
WITH_MR=true
WITH_GIBBS=true
-WITH_BP_DUAL=true
WITH_CBP=true
# Build doxygen documentation?
WITH_DOC=
#ifdef DAI_WITH_GIBBS
#include <dai/gibbs.h>
#endif
-#ifdef DAI_WITH_BP_DUAL
- #include <dai/bp_dual.h>
-#endif
#ifdef DAI_WITH_CBP
#include <dai/cbp.h>
#endif
DAI_ACCMUT(Prob& adj_m(size_t i, size_t _I), { return _adj_m[i][_I]; });
public:
+ /// Parameters of this inference algorithm
/* PROPERTIES(props,BBP) {
DAI_ENUM(UpdateType,SEQ_FIX,SEQ_MAX,SEQ_BP_REV,SEQ_BP_FWD,PAR);
size_t verbose;
std::vector<size_t> ind2; // indices of nodes of type 2
};
- /// Support for some backwards compatibility with old interface
- /** Call indexEdges() first to initialize these members
- */
+ /// @name Backwards compatibility layer (to be removed soon)
+ //@{
+ /// Enable backwards compatibility layer?
bool _edge_indexed;
+ /// Call indexEdges() first to initialize these members
std::vector<Edge> _edges;
+ /// Call indexEdges() first to initialize these members
hash_map<Edge,size_t> _vv2e;
+ //}@
public:
/// Default constructor (creates an empty bipartite graph)
/// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
void printDot( std::ostream& os ) const;
- // ----------------------------------------------------------------
- // backwards compatibility layer
+ /// @name Backwards compatibility layer (to be removed soon)
+ //@{
void indexEdges() {
_edges.clear();
_vv2e.clear();
assert(_edge_indexed);
return _edges.size();
}
+ //}@
private:
/// Checks internal consistency
*/
class BP_dual {
-protected:
- template<class T>
- struct _edges_t : public std::vector<std::vector<T> > {};
-
- struct messages {
- // messages:
- _edges_t<Prob> n;
- _edges_t<Real> Zn;
- _edges_t<Prob> m;
- _edges_t<Real> Zm;
- };
- messages _msgs;
-
- struct beliefs {
- // beliefs:
- // indexed by node
- std::vector<Prob> b1;
- std::vector<Real> Zb1;
- // indexed by factor
- std::vector<Prob> b2;
- std::vector<Real> Zb2;
- };
- beliefs _beliefs;
-
- const InfAlg *_ia;
-
- void Init();
-
- void RegenerateMessages();
- void RegenerateBeliefs();
-
- void CalcMessages();
- void CalcBeliefV(size_t i);
- void CalcBeliefF(size_t I);
- void CalcBeliefs();
-
- void calcNewM(size_t i, size_t _I);
- void calcNewN(size_t i, size_t _I);
-public:
-
- /// Construct BP_dual object from (converged) InfAlg object's beliefs and factors.
- /* A pointer to the the InfAlg object is
- * stored, so the object must not be destroyed before the BP_dual
- */
- BP_dual(const InfAlg *ia) : _ia(ia) {
- Init();
- }
-
- const FactorGraph& fg() const { return _ia->fg(); }
-
- /// msgM: factor -> var messages
- DAI_ACCMUT(Prob & msgM(size_t i, size_t _I), { return _msgs.m[i][_I]; });
- /// msgN: var -> factor messages
- DAI_ACCMUT(Prob & msgN(size_t i, size_t _I), { return _msgs.n[i][_I]; });
- /// Normalizer for msgM
- DAI_ACCMUT(Real & zM(size_t i, size_t _I), { return _msgs.Zm[i][_I]; });
- /// Normalizer for msgN
- DAI_ACCMUT(Real & zN(size_t i, size_t _I), { return _msgs.Zn[i][_I]; });
-
- /// Variable beliefs
- Factor beliefV(size_t i) const { return Factor(_ia->fg().var(i), _beliefs.b1[i]); }
- /// Factor beliefs
- Factor beliefF(size_t I) const { return Factor(_ia->fg().factor(I).vars(), _beliefs.b2[I]); }
-
- /// Normalizer for variable beliefs
- Real beliefVZ(size_t i) const { return _beliefs.Zb1[i]; }
- /// Normalizer for factor beliefs
- Real beliefFZ(size_t I) const { return _beliefs.Zb2[I]; }
+ protected:
+ /// Convenience label for storing edge properties
+ template<class T>
+ struct _edges_t : public std::vector<std::vector<T> > {};
+
+ /// Groups together the data structures for storing the two types of messages and their normalizers
+ struct messages {
+ _edges_t<Prob> n;
+ _edges_t<Real> Zn;
+ _edges_t<Prob> m;
+ _edges_t<Real> Zm;
+ };
+ messages _msgs;
+
+ /// Groups together the data structures for storing the two types of beliefs and their normalizers
+ struct beliefs {
+ // indexed by node
+ std::vector<Prob> b1;
+ std::vector<Real> Zb1;
+ // indexed by factor
+ std::vector<Prob> b2;
+ std::vector<Real> Zb2;
+ };
+ beliefs _beliefs;
+
+ const InfAlg *_ia;
+
+ void init();
+
+ void regenerateMessages();
+ void regenerateBeliefs();
+
+ void calcMessages();
+ void calcBeliefV(size_t i);
+ void calcBeliefF(size_t I);
+ void calcBeliefs();
+
+ void calcNewM(size_t i, size_t _I);
+ void calcNewN(size_t i, size_t _I);
+
+ public:
+ /// Construct BP_dual object from (converged) InfAlg object's beliefs and factors.
+ /* A pointer to the the InfAlg object is stored,
+ * so the object must not be destroyed before the BP_dual is destroyed.
+ */
+ BP_dual( const InfAlg *ia ) : _ia(ia) { init(); }
+
+ const FactorGraph& fg() const { return _ia->fg(); }
+
+ /// factor -> var message
+ DAI_ACCMUT(Prob & msgM(size_t i, size_t _I), { return _msgs.m[i][_I]; });
+ /// var -> factor message
+ DAI_ACCMUT(Prob & msgN(size_t i, size_t _I), { return _msgs.n[i][_I]; });
+ /// Normalizer for msgM
+ DAI_ACCMUT(Real & zM(size_t i, size_t _I), { return _msgs.Zm[i][_I]; });
+ /// Normalizer for msgN
+ DAI_ACCMUT(Real & zN(size_t i, size_t _I), { return _msgs.Zn[i][_I]; });
+
+ /// Variable belief
+ Factor beliefV(size_t i) const { return Factor(_ia->fg().var(i), _beliefs.b1[i]); }
+ /// Factor belief
+ Factor beliefF(size_t I) const { return Factor(_ia->fg().factor(I).vars(), _beliefs.b2[I]); }
+
+ /// Normalizer for variable belief
+ Real beliefVZ(size_t i) const { return _beliefs.Zb1[i]; }
+ /// Normalizer for factor belief
+ Real beliefFZ(size_t I) const { return _beliefs.Zb2[I]; }
};
//----------------------------------------------------------------
public:
+ /// Parameters of this inference algorithm
/* PROPERTIES(props,CBP) {
typedef BP::Properties::UpdateType UpdateType;
DAI_ENUM(RecurseType,REC_FIXED,REC_LOGZ,REC_BDIFF);
friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
+ /// @name Backwards compatibility layer (to be removed soon)
+ //@{
size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
const Edge& edge(size_t e) const { return G.edge(e); }
void indexEdges() { G.indexEdges(); }
size_t nr_edges() const { return G.nr_edges(); }
const std::vector<Edge>& edges() const { return G.edges(); }
+ //}@
private:
/// Part of constructors (creates edges, neighbors and adjacency matrix)
using namespace std;
-InfAlg *newInfAlg( const string &name, const FactorGraph &fg, const PropertySet &opts ) {
+InfAlg *newInfAlg( const std::string &name, const FactorGraph &fg, const PropertySet &opts ) {
if( name == ExactInf::Name )
return new ExactInf (fg, opts);
#ifdef DAI_WITH_BP
typedef BipartiteGraph::Neighbor Neighbor;
-void BP_dual::RegenerateMessages() {
+void BP_dual::regenerateMessages() {
size_t nv = fg().nrVars();
_msgs.Zn.resize(nv);
_msgs.Zm.resize(nv);
_msgs.m.resize(nv);
_msgs.n.resize(nv);
- for(size_t i=0; i<nv; i++) {
+ for( size_t i = 0; i < nv; i++ ) {
size_t nvf = fg().nbV(i).size();
_msgs.Zn[i].resize(nvf, 1.0);
_msgs.Zm[i].resize(nvf, 1.0);
}
-void BP_dual::RegenerateBeliefs() {
+void BP_dual::regenerateBeliefs() {
_beliefs.b1.clear();
_beliefs.b1.reserve(fg().nrVars());
_beliefs.Zb1.resize(fg().nrVars(), 1.0);
_beliefs.b2.reserve(fg().nrFactors());
_beliefs.Zb2.resize(fg().nrFactors(), 1.0);
- for(size_t i=0; i<fg().nrVars(); i++) {
+ for( size_t i = 0; i < fg().nrVars(); i++ )
_beliefs.b1.push_back( Prob( fg().var(i).states() ) );
- }
- for(size_t I=0; I<fg().nrFactors(); I++) {
+ for( size_t I = 0; I < fg().nrFactors(); I++ )
_beliefs.b2.push_back( Prob( fg().factor(I).states() ) );
- }
}
-void BP_dual::Init() {
- RegenerateMessages();
- RegenerateBeliefs();
- CalcMessages();
- CalcBeliefs();
+void BP_dual::init() {
+ regenerateMessages();
+ regenerateBeliefs();
+ calcMessages();
+ calcBeliefs();
}
-void BP_dual::CalcMessages() {
+void BP_dual::calcMessages() {
// calculate 'n' messages from "factor marginal / factor"
vector<Factor> bs;
size_t nf = fg().nrFactors();
for( size_t I = 0; I < nf; I++ ) {
Factor f = bs[I];
f /= fg().factor(I);
- foreach(const Neighbor &i, fg().nbF(I)) {
+ foreach(const Neighbor &i, fg().nbF(I))
msgN(i, i.dual) = f.marginal(fg().var(i)).p();
- }
}
// calculate 'm' messages and normalizers from 'n' messages
for( size_t i = 0; i < fg().nrVars(); i++ )
}
-void BP_dual::CalcBeliefV(size_t i) {
+void BP_dual::calcBeliefV(size_t i) {
Prob prod( fg().var(i).states(), 1.0 );
- foreach(const Neighbor &I, fg().nbV(i)) {
+ foreach(const Neighbor &I, fg().nbV(i))
prod *= msgM(i,I.iter);
- }
_beliefs.Zb1[i] = prod.normalize();
_beliefs.b1[i] = prod;
}
-void BP_dual::CalcBeliefF(size_t I) {
+void BP_dual::calcBeliefF(size_t I) {
Prob prod( fg().factor(I).p() );
foreach(const Neighbor &j, fg().nbF(I)) {
IndexFor ind (fg().var(j), fg().factor(I).vars() );
Prob n(msgN(j,j.dual));
- for(size_t x=0; ind >= 0; x++, ++ind) {
+ for(size_t x=0; ind >= 0; x++, ++ind)
prod[x] *= n[ind];
- }
}
_beliefs.Zb2[I] = prod.normalize();
_beliefs.b2[I] = prod;
// called after run()
-void BP_dual::CalcBeliefs() {
+void BP_dual::calcBeliefs() {
for( size_t i = 0; i < fg().nrVars(); i++ )
- CalcBeliefV(i); // calculate b_i
+ calcBeliefV(i); // calculate b_i
for( size_t I = 0; I < fg().nrFactors(); I++ )
- CalcBeliefF(I); // calculate b_I
+ calcBeliefF(I); // calculate b_I
}
const Neighbor &I = fg().nbV(i)[_I];
Prob prod(fg().var(i).states(), 1.0);
foreach(const Neighbor &J, fg().nbV(i)) {
- if(J.node != I.node) { // for all J in i \ I
+ if(J.node != I.node) // for all J in i \ I
prod *= msgM(i,J.iter);
- }
}
_msgs.Zn[i][_I] = prod.normalize();
_msgs.n[i][_I] = prod;
GIBBS_1e8: GIBBS[iters=100000000]
GIBBS_1e9: GIBBS[iters=1000000000]
-# --- BP_dual ---------------------
-
-BP_dual: BP_dual[updates=SEQFIX,tol=1e-9,maxiter=10000,verbose=0]
-BP_dual_SEQFIX: BP_dual[updates=SEQFIX,tol=1e-9,maxiter=10000,verbose=0]
-
# --- CBP ---------------------
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,verbose=0,rand_seed=0,bbp_props=[verbose=0,tol=1.0e-9,maxiter=5000,damping=0,updates=SEQ_BP_REV,clean_updates=0],clamp_outfile=]