[Frederik Eaton] Added BP_Dual, BBP and CBP algorithms
[libdai.git] / include / dai / cbp.h
1 #ifndef ____defined_libdai_cbp_h__
2 #define ____defined_libdai_cbp_h__
3
4 #include <dai/daialg.h>
5
6 #include <dai/cbp.h>
7 #include <dai/bbp.h>
8
9 using namespace std;
10
11 /* Class for "clamped belief propagation".
12
13 'chooseNextClamp' can be overridden (e.g. in BPC); this version
14 randomly chooses variables to clamp.
15 */
16
17 namespace dai {
18
19 template<class T>
20 vector<T> concat(const vector<T>& u, const vector<T>& v) {
21 vector<T> w;
22 w.reserve(u.size()+v.size());
23 for(size_t i=0; i<u.size(); i++)
24 w.push_back(u[i]);
25 for(size_t i=0; i<v.size(); i++)
26 w.push_back(v[i]);
27 return w;
28 }
29
30 class CBP : public DAIAlgFG {
31 vector<Factor> _beliefs1;
32 vector<Factor> _beliefs2;
33 double _logZ;
34 double _est_logZ;
35 double _old_est_logZ;
36
37 double _sum_level;
38 size_t _num_leaves;
39
40 size_t maxClampLevel() { return props.max_levels; }
41 double minMaxAdj() { return props.min_max_adj; }
42 double recTol() { return props.rec_tol; }
43
44
45 bbp_cfn_t BBP_cost_function() {
46 return props.bbp_cfn;
47 }
48
49 void printDebugInfo();
50
51 void runRecurse(BP_dual &bp_dual,
52 double orig_logZ,
53 vector<size_t> clamped_vars_list,
54 set<size_t> clamped_vars,
55 size_t &num_leaves,
56 double &sum_level,
57 Real &lz_out, vector<Factor>& beliefs_out);
58
59 BP getBP();
60 BP_dual getBP_dual();
61
62 public:
63 size_t _iters;
64 double _maxdiff;
65
66 struct Properties {
67 typedef BP::Properties::UpdateType UpdateType;
68 DAI_ENUM(RecurseType,REC_FIXED,REC_LOGZ,REC_BDIFF);
69 DAI_ENUM(ChooseMethodType,CHOOSE_RANDOM,CHOOSE_BBP,CHOOSE_BP_ALL);
70 DAI_ENUM(ClampType,CLAMP_VAR,CLAMP_FACTOR);
71
72 double tol;
73 double rec_tol;
74 size_t maxiter;
75 size_t verbose;
76 UpdateType updates;
77 size_t max_levels;
78 double min_max_adj;
79
80 ChooseMethodType choose;
81 RecurseType recursion;
82 ClampType clamp;
83 bbp_cfn_t bbp_cfn;
84 size_t rand_seed;
85 } props;
86
87 Properties::ChooseMethodType ChooseMethod() { return props.choose; }
88 Properties::RecurseType Recursion() { return props.recursion; }
89 Properties::ClampType Clamping() { return props.clamp; }
90
91 //----------------------------------------------------------------
92
93 // construct CBP object from FactorGraph
94 CBP(const FactorGraph &fg, const PropertySet &opts) : DAIAlgFG(fg) {
95 setProperties(opts);
96 construct();
97 }
98
99 static const char *Name;
100 /// List of property names
101 static const char *PropertyList[];
102
103 /// @name General InfAlg interface
104 //@{
105 virtual CBP* clone() const { return new CBP(*this); }
106 // virtual CBP* create() const { return new CBP(); }
107 virtual CBP* create() const { throw "Unimplemented"; }
108 virtual std::string identify() const { return string(Name) + printProperties(); }
109 virtual Factor belief (const Var &n) const { return _beliefs1[findVar(n)]; }
110 virtual Factor belief (const VarSet &) const { assert(0); }
111 virtual vector<Factor> beliefs() const { return concat(_beliefs1, _beliefs2); }
112 virtual Real logZ() const { return _logZ; }
113 virtual void init() {};
114 virtual void init( const VarSet & ) {};
115 virtual double run();
116 virtual double maxDiff() const { return _maxdiff; }
117 virtual size_t Iterations() const { return _iters; }
118 //@}
119
120
121 //----------------------------------------------------------------
122
123 virtual bool chooseNextClampVar(BP_dual& bp,
124 vector<size_t> &clamped_vars_list,
125 set<size_t> &clamped_vars,
126 size_t &i, vector<size_t> &xis, Real *maxVarOut);
127
128 //----------------------------------------------------------------
129
130 void setBeliefsFrom(const BP& b);
131 void setBeliefs(const vector<Factor>& bs, double logZ) {
132 size_t i=0;
133 _beliefs1.clear(); _beliefs1.reserve(nrVars());
134 _beliefs2.clear(); _beliefs2.reserve(nrFactors());
135 for(i=0; i<nrVars(); i++) _beliefs1.push_back(bs[i]);
136 for(; i<nrVars()+nrFactors(); i++) _beliefs2.push_back(bs[i]);
137 _logZ = logZ;
138 }
139 Factor belief1 (size_t i) const { return _beliefs1[i]; }
140 Factor belief2 (size_t I) const { return _beliefs2[I]; }
141
142 //----------------------------------------------------------------
143
144 void construct();
145
146 void setProperties( const PropertySet &opts );
147 PropertySet getProperties() const;
148 std::string printProperties() const;
149 };
150
151 pair<size_t, size_t> bbpFindClampVar(BP_dual &in_bp_dual, bool clampVar, size_t numClamped, bbp_cfn_t cfn, const PropertySet &props, Real *maxVarOut);
152
153 }
154
155 #endif