1 /* This file is part of libDAI - http://www.libdai.org/
2 *
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2009 Frederik Eaton [frederik at ofb dot net]
8 */
11 #include <iostream>
12 #include <sstream>
13 #include <map>
14 #include <set>
15 #include <algorithm>
17 #include <dai/util.h>
18 #include <dai/properties.h>
19 #include <dai/gibbs.h>
20 #include <dai/bp.h>
21 #include <dai/cbp.h>
22 #include <dai/bbp.h>
25 namespace dai {
28 using namespace std;
29 using boost::shared_ptr;
32 /// Given a sorted vector of states \a xis and total state count \a n_states, return a vector of states not in \a xis
33 vector<size_t> complement( vector<size_t> &xis, size_t n_states ) {
34 vector<size_t> cmp_xis( 0 );
35 size_t j = 0;
36 for( size_t xi = 0; xi < n_states; xi++ ) {
37 while( j < xis.size() && xis[j] < xi )
38 j++;
39 if( j >= xis.size() || xis[j] > xi )
40 cmp_xis.push_back(xi);
41 }
42 DAI_ASSERT( xis.size()+cmp_xis.size() == n_states );
43 return cmp_xis;
44 }
47 /// Computes \f$\frac{\exp(a)}{\exp(a)+\exp(b)}\f$
48 Real unSoftMax( Real a, Real b ) {
49 if( a > b )
50 return 1.0 / (1.0 + exp(b-a));
51 else
52 return exp(a-b) / (exp(a-b) + 1.0);
53 }
56 /// Computes log of sum of exponents, i.e., \f$\log\left(\exp(a) + \exp(b)\right)\f$
57 Real logSumExp( Real a, Real b ) {
58 if( a > b )
59 return a + log1p( exp( b-a ) );
60 else
61 return b + log1p( exp( a-b ) );
62 }
65 /// Compute sum of pairwise L-infinity distances of the first \a nv factors in each vector
66 Real dist( const vector<Factor> &b1, const vector<Factor> &b2, size_t nv ) {
67 Real d = 0.0;
68 for( size_t k = 0; k < nv; k++ )
69 d += dist( b1[k], b2[k], DISTLINF );
70 return d;
71 }
74 void CBP::setBeliefs( const std::vector<Factor> &bs, Real logZ ) {
75 size_t i = 0;
76 _beliefsV.clear();
77 _beliefsV.reserve( nrVars() );
78 _beliefsF.clear();
79 _beliefsF.reserve( nrFactors() );
80 for( i = 0; i < nrVars(); i++ )
81 _beliefsV.push_back( bs[i] );
82 for( ; i < nrVars() + nrFactors(); i++ )
83 _beliefsF.push_back( bs[i] );
84 _logZ = logZ;
85 }
88 void CBP::construct() {
89 _beliefsV.clear();
90 _beliefsV.reserve(nrVars());
91 for( size_t i = 0; i < nrVars(); i++ )
92 _beliefsV.push_back( Factor(var(i)).normalized() );
94 _beliefsF.clear();
95 _beliefsF.reserve(nrFactors());
96 for( size_t I = 0; I < nrFactors(); I++ ) {
97 Factor f = factor(I);
98 f.fill(1); f.normalize();
99 _beliefsF.push_back( f );
100 }
102 // to compute average level
103 _sum_level = 0;
104 _num_leaves = 0;
106 _maxdiff = 0;
107 _iters = 0;
109 if( props.clamp_outfile.length() > 0 ) {
110 _clamp_ofstream = shared_ptr<ofstream>(new ofstream( props.clamp_outfile.c_str(), ios_base::out|ios_base::trunc ));
111 *_clamp_ofstream << "# COUNT LEVEL VAR STATE" << endl;
112 }
113 }
116 /// Calculates a vector of mixtures p * b + (1-p) * c
117 static vector<Factor> mixBeliefs( Real p, const vector<Factor> &b, const vector<Factor> &c ) {
118 vector<Factor> out;
119 DAI_ASSERT( b.size() == c.size() );
120 out.reserve( b.size() );
121 Real pc = 1 - p;
122 for( size_t i = 0; i < b.size(); i++ )
123 // probably already normalized, but do it again just in case
124 out.push_back( b[i].normalized() * p + c[i].normalized() * pc );
125 return out;
126 }
129 Real CBP::run() {
130 size_t seed = props.rand_seed;
131 if( seed > 0 )
132 rnd_seed( seed );
134 InfAlg *bp = getInfAlg();
135 bp->init();
136 bp->run();
137 _iters += bp->Iterations();
139 vector<Factor> beliefs_out;
140 Real lz_out;
141 size_t choose_count=0;
142 runRecurse( bp, bp->logZ(), vector<size_t>(0), _num_leaves, choose_count, _sum_level, lz_out, beliefs_out );
143 if( props.verbose >= 1 )
144 cerr << "CBP average levels = " << (_sum_level / _num_leaves) << ", leaves = " << _num_leaves << endl;
145 setBeliefs( beliefs_out, lz_out );
146 return 0.0;
147 }
150 InfAlg* CBP::getInfAlg() {
151 PropertySet bpProps;
153 bpProps.set("tol", props.tol);
154 bpProps.set("maxiter", props.maxiter);
155 bpProps.set("verbose", props.verbose);
156 bpProps.set("logdomain", false);
157 bpProps.set("damping", (Real)0.0);
158 BP *bp = new BP( *this, bpProps );
159 bp->recordSentMessages = true;
160 bp->init();
161 return bp;
162 }
165 void CBP::runRecurse( InfAlg *bp, Real orig_logZ, vector<size_t> clamped_vars_list, size_t &num_leaves,
166 size_t &choose_count, Real &sum_level, Real &lz_out, vector<Factor>& beliefs_out) {
167 // choose a variable/states to clamp:
168 size_t i;
169 vector<size_t> xis;
170 Real maxVar = 0.0;
171 bool found;
172 bool clampingVar = (props.clamp == Properties::ClampType::CLAMP_VAR);
174 if( props.recursion == Properties::RecurseType::REC_LOGZ && props.rec_tol > 0 && exp( bp->logZ() - orig_logZ ) < props.rec_tol )
175 found = false;
176 else
177 found = chooseNextClampVar( bp, clamped_vars_list, i, xis, &maxVar );
179 if( !found ) {
180 num_leaves++;
181 sum_level += clamped_vars_list.size();
182 beliefs_out = bp->beliefs();
183 lz_out = bp->logZ();
184 return;
185 }
187 choose_count++;
188 if( props.clamp_outfile.length() > 0 )
189 *_clamp_ofstream << choose_count << "\t" << clamped_vars_list.size() << "\t" << i << "\t" << xis[0] << endl;
191 if( clampingVar )
192 foreach( size_t xi, xis )
193 DAI_ASSERT(/*0<=xi &&*/ xi < var(i).states() );
194 else
195 foreach( size_t xI, xis )
196 DAI_ASSERT(/*0<=xI &&*/ xI < factor(i).nrStates() );
197 // - otherwise, clamp and recurse, saving margin estimates for each
198 // clamp setting. afterwards, combine estimates.
200 // compute complement of 'xis'
201 vector<size_t> cmp_xis = complement( xis, clampingVar ? var(i).states() : factor(i).nrStates() );
203 /// \idea dai::CBP::runRecurse() could be implemented more efficiently with a nesting version of backupFactors/restoreFactors
204 // this improvement could also be done locally: backup the clamped factor in a local variable,
205 // and restore it just before we return.
206 Real lz;
207 vector<Factor> b;
208 InfAlg *bp_c = bp->clone();
209 if( clampingVar ) {
210 bp_c->fg().clampVar( i, xis );
211 bp_c->init( var(i) );
212 } else {
213 bp_c->fg().clampFactor( i, xis );
214 bp_c->init( factor(i).vars() );
215 }
216 bp_c->run();
217 _iters += bp_c->Iterations();
219 lz = bp_c->logZ();
220 b = bp_c->beliefs();
222 Real cmp_lz;
223 vector<Factor> cmp_b;
224 InfAlg *cmp_bp_c = bp->clone();
225 if( clampingVar ) {
226 cmp_bp_c->fg().clampVar( i, cmp_xis );
227 cmp_bp_c->init(var(i));
228 } else {
229 cmp_bp_c->fg().clampFactor( i, cmp_xis );
230 cmp_bp_c->init( factor(i).vars() );
231 }
232 cmp_bp_c->run();
233 _iters += cmp_bp_c->Iterations();
235 cmp_lz = cmp_bp_c->logZ();
236 cmp_b = cmp_bp_c->beliefs();
238 Real p = unSoftMax( lz, cmp_lz );
239 Real bp__d = 0.0;
241 if( props.recursion == Properties::RecurseType::REC_BDIFF && props.rec_tol > 0 ) {
242 vector<Factor> combined_b( mixBeliefs( p, b, cmp_b ) );
243 Real new_lz = logSumExp( lz,cmp_lz );
244 bp__d = dist( bp->beliefs(), combined_b, nrVars() );
245 if( exp( new_lz - orig_logZ) * bp__d < props.rec_tol ) {
246 num_leaves++;
247 sum_level += clamped_vars_list.size();
248 beliefs_out = combined_b;
249 lz_out = new_lz;
250 return;
251 }
252 }
254 // either we are not doing REC_BDIFF or the distance was large
255 // enough to recurse:
256 runRecurse( bp_c, orig_logZ, clamped_vars_list, num_leaves, choose_count, sum_level, lz, b );
257 runRecurse( cmp_bp_c, orig_logZ, clamped_vars_list, num_leaves, choose_count, sum_level, cmp_lz, cmp_b );
259 p = unSoftMax( lz, cmp_lz );
261 beliefs_out = mixBeliefs( p, b, cmp_b );
262 lz_out = logSumExp( lz, cmp_lz );
264 if( props.verbose >= 2 ) {
265 Real d = dist( bp->beliefs(), beliefs_out, nrVars() );
266 cerr << "Distance (clamping " << i << "): " << d;
267 if( props.recursion == Properties::RecurseType::REC_BDIFF )
268 cerr << "; bp_dual predicted " << bp__d;
269 cerr << "; max_adjoint = " << maxVar << "; logZ = " << lz_out << " (in " << bp->logZ() << ") (orig " << orig_logZ << "); p = " << p << "; level = " << clamped_vars_list.size() << endl;
270 }
272 delete bp_c;
273 delete cmp_bp_c;
274 }
277 // 'xis' must be sorted
278 bool CBP::chooseNextClampVar( InfAlg *bp, vector<size_t> &clamped_vars_list, size_t &i, vector<size_t> &xis, Real *maxVarOut ) {
279 Real tiny = 1.0e-14;
280 if( props.verbose >= 3 )
281 cerr << "clamped_vars_list" << clamped_vars_list << endl;
282 if( clamped_vars_list.size() >= props.max_levels )
283 return false;
284 if( props.choose == Properties::ChooseMethodType::CHOOSE_RANDOM ) {
285 if( props.clamp == Properties::ClampType::CLAMP_VAR ) {
286 int t = 0, t1 = 100;
287 do {
288 i = rnd( nrVars() );
289 t++;
290 } while( abs( bp->beliefV(i).p().max() - 1) < tiny && t < t1 );
291 if( t == t1 ) {
292 return false;
293 // die("Too many levels requested in CBP");
294 }
295 // only pick probable values for variable
296 size_t xi;
297 do {
298 xi = rnd( var(i).states() );
299 t++;
300 } while( bp->beliefV(i).p()[xi] < tiny && t < t1 );
301 DAI_ASSERT( t < t1 );
302 xis.resize( 1, xi );
303 // DAI_ASSERT(!_clamped_vars.count(i)); // not true for >2-ary variables
304 DAI_IFVERB(2, "CHOOSE_RANDOM at level " << clamped_vars_list.size() << " chose variable " << i << " state " << xis[0] << endl);
305 } else {
306 int t = 0, t1 = 100;
307 do {
308 i = rnd( nrFactors() );
309 t++;
310 } while( abs( bp->beliefF(i).p().max() - 1) < tiny && t < t1 );
311 if( t == t1 )
312 return false;
313 // die("Too many levels requested in CBP");
314 // only pick probable values for variable
315 size_t xi;
316 do {
317 xi = rnd( factor(i).nrStates() );
318 t++;
319 } while( bp->beliefF(i).p()[xi] < tiny && t < t1 );
320 DAI_ASSERT( t < t1 );
321 xis.resize( 1, xi );
322 // DAI_ASSERT(!_clamped_vars.count(i)); // not true for >2-ary variables
323 DAI_IFVERB(2, endl<<"CHOOSE_RANDOM chose factor "<<i<<" state "<<xis[0]<<endl);
324 }
325 } else if( props.choose == Properties::ChooseMethodType::CHOOSE_MAXENT ) {
326 if( props.clamp == Properties::ClampType::CLAMP_VAR ) {
327 Real max_ent = -1.0;
328 int win_k = -1, win_xk = -1;
329 for( size_t k = 0; k < nrVars(); k++ ) {
330 Real ent=bp->beliefV(k).entropy();
331 if( max_ent < ent ) {
332 max_ent = ent;
333 win_k = k;
334 win_xk = bp->beliefV(k).p().argmax().first;
335 }
336 }
337 DAI_ASSERT( win_k >= 0 );
338 DAI_ASSERT( win_xk >= 0 );
339 i = win_k;
340 xis.resize( 1, win_xk );
341 DAI_IFVERB(2, endl<<"CHOOSE_MAXENT chose variable "<<i<<" state "<<xis[0]<<endl);
342 if( bp->beliefV(i).p()[xis[0]] < tiny ) {
343 DAI_IFVERB(2, "Warning: CHOOSE_MAXENT found unlikely state, not recursing");
344 return false;
345 }
346 } else {
347 Real max_ent = -1.0;
348 int win_k = -1, win_xk = -1;
349 for( size_t k = 0; k < nrFactors(); k++ ) {
350 Real ent = bp->beliefF(k).entropy();
351 if( max_ent < ent ) {
352 max_ent = ent;
353 win_k = k;
354 win_xk = bp->beliefF(k).p().argmax().first;
355 }
356 }
357 DAI_ASSERT( win_k >= 0 );
358 DAI_ASSERT( win_xk >= 0 );
359 i = win_k;
360 xis.resize( 1, win_xk );
361 DAI_IFVERB(2, endl<<"CHOOSE_MAXENT chose factor "<<i<<" state "<<xis[0]<<endl);
362 if( bp->beliefF(i).p()[xis[0]] < tiny ) {
363 DAI_IFVERB(2, "Warning: CHOOSE_MAXENT found unlikely state, not recursing");
364 return false;
365 }
366 }
367 } else if( props.choose==Properties::ChooseMethodType::CHOOSE_BP_L1 ||
368 props.choose==Properties::ChooseMethodType::CHOOSE_BP_CFN ) {
369 bool doL1 = (props.choose == Properties::ChooseMethodType::CHOOSE_BP_L1);
370 vector<size_t> state;
371 if( !doL1 && props.bbp_cfn.needGibbsState() )
372 state = getGibbsState( bp->fg(), 2*bp->Iterations() );
373 // try clamping each variable manually
374 DAI_ASSERT( props.clamp == Properties::ClampType::CLAMP_VAR );
375 Real max_cost = 0.0;
376 int win_k = -1, win_xk = -1;
377 for( size_t k = 0; k < nrVars(); k++ ) {
378 for( size_t xk = 0; xk < var(k).states(); xk++ ) {
379 if( bp->beliefV(k)[xk] < tiny )
380 continue;
381 InfAlg *bp1 = bp->clone();
382 bp1->clamp( k, xk );
383 bp1->init( var(k) );
384 bp1->run();
385 Real cost = 0;
386 if( doL1 )
387 for( size_t j = 0; j < nrVars(); j++ )
388 cost += dist( bp->beliefV(j), bp1->beliefV(j), DISTL1 );
389 else
390 cost = props.bbp_cfn.evaluate( *bp1, &state );
391 if( cost > max_cost || win_k == -1 ) {
392 max_cost = cost;
393 win_k = k;
394 win_xk = xk;
395 }
396 delete bp1;
397 }
398 }
399 DAI_ASSERT( win_k >= 0 );
400 DAI_ASSERT( win_xk >= 0 );
401 i = win_k;
402 xis.resize( 1, win_xk );
403 } else if( props.choose == Properties::ChooseMethodType::CHOOSE_BBP ) {
404 Real mvo;
405 if( !maxVarOut )
406 maxVarOut = &mvo;
407 bool clampingVar = (props.clamp == Properties::ClampType::CLAMP_VAR);
408 pair<size_t, size_t> cv = BBPFindClampVar( *bp, clampingVar, props.bbp_props, props.bbp_cfn, &mvo );
410 // if slope isn't big enough then don't clamp
411 if( mvo < props.min_max_adj )
412 return false;
414 size_t xi = cv.second;
415 i = cv.first;
416 #define VAR_INFO (clampingVar?"variable ":"factor ") \
417 << i << " state " << xi \
418 << " (p=" << (clampingVar?bp->beliefV(i)[xi]:bp->beliefF(i)[xi]) \
419 << ", entropy = " << (clampingVar?bp->beliefV(i):bp->beliefF(i)).entropy() \
420 << ", maxVar = "<< mvo << ")"
421 Prob b = ( clampingVar ? bp->beliefV(i).p() : bp->beliefF(i).p());
422 if( b[xi] < tiny ) {
423 cerr << "Warning, at level " << clamped_vars_list.size() << ", BBPFindClampVar found unlikely " << VAR_INFO << endl;
424 return false;
425 }
426 if( abs(b[xi] - 1) < tiny ) {
427 cerr << "Warning at level " << clamped_vars_list.size() << ", BBPFindClampVar found overly likely " << VAR_INFO << endl;
428 return false;
429 }
431 xis.resize( 1, xi );
432 if( clampingVar )
433 DAI_ASSERT(/*0<=xi &&*/ xi < var(i).states() );
434 else
435 DAI_ASSERT(/*0<=xi &&*/ xi < factor(i).nrStates() );
436 DAI_IFVERB(2, "CHOOSE_BBP (num clamped = " << clamped_vars_list.size() << ") chose " << i << " state " << xi << endl);
437 } else
438 DAI_THROW(UNKNOWN_ENUM_VALUE);
439 clamped_vars_list.push_back( i );
440 return true;
441 }
444 void CBP::printDebugInfo() {
445 DAI_PV(_beliefsV);
446 DAI_PV(_beliefsF);
447 DAI_PV(_logZ);
448 }
451 std::pair<size_t, size_t> BBPFindClampVar( const InfAlg &in_bp, bool clampingVar, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real *maxVarOut ) {
452 BBP bbp( &in_bp, bbp_props );
454 bbp.run();
456 // find and return the (variable,state) with the largest adj_psi_V
457 size_t argmax_var = 0;
458 size_t argmax_var_state = 0;
459 Real max_var = 0;
460 if( clampingVar ) {
461 for( size_t i = 0; i < in_bp.fg().nrVars(); i++ ) {
463 if(0) {
464 // helps to account for amount of movement possible in variable
465 // i's beliefs? seems not..
467 }
468 if(0){
471 }
472 // try to compensate for effect on same variable (doesn't work)
476 if( i == 0 || argmax_state.second > max_var ) {
477 argmax_var = i;
478 max_var = argmax_state.second;
479 argmax_var_state = argmax_state.first;
480 }
481 }
482 DAI_ASSERT(/*0 <= argmax_var_state &&*/
483 argmax_var_state < in_bp.fg().var(argmax_var).states() );
484 } else {
485 for( size_t I = 0; I < in_bp.fg().nrFactors(); I++ ) {
487 if(0) {
488 // helps to account for amount of movement possible in variable
489 // i's beliefs? seems not..
491 }
492 // try to compensate for effect on same variable (doesn't work)
496 if( I == 0 || argmax_state.second > max_var ) {
497 argmax_var = I;
498 max_var = argmax_state.second;
499 argmax_var_state = argmax_state.first;
500 }
501 }
502 DAI_ASSERT(/*0 <= argmax_var_state &&*/
503 argmax_var_state < in_bp.fg().factor(argmax_var).nrStates() );
504 }
505 if( maxVarOut )
506 *maxVarOut = max_var;
507 return make_pair( argmax_var, argmax_var_state );
508 }
511 } // end of namespace dai
514 /* {{{ GENERATED CODE: DO NOT EDIT. Created by
515 ./scripts/regenerate-properties include/dai/cbp.h src/cbp.cpp
516 */
517 namespace dai {
519 void CBP::Properties::set(const PropertySet &opts)
520 {
521 const std::set<PropertyKey> &keys = opts.keys();
522 std::string errormsg;
523 for( std::set<PropertyKey>::const_iterator i = keys.begin(); i != keys.end(); i++ ) {
524 if( *i == "verbose" ) continue;
525 if( *i == "tol" ) continue;
526 if( *i == "updates" ) continue;
527 if( *i == "maxiter" ) continue;
528 if( *i == "rec_tol" ) continue;
529 if( *i == "max_levels" ) continue;
530 if( *i == "min_max_adj" ) continue;
531 if( *i == "choose" ) continue;
532 if( *i == "recursion" ) continue;
533 if( *i == "clamp" ) continue;
534 if( *i == "bbp_props" ) continue;
535 if( *i == "bbp_cfn" ) continue;
536 if( *i == "rand_seed" ) continue;
537 if( *i == "clamp_outfile" ) continue;
538 errormsg = errormsg + "CBP: Unknown property " + *i + "\n";
539 }
540 if( !errormsg.empty() )
541 DAI_THROWE(UNKNOWN_PROPERTY, errormsg);
543 errormsg = errormsg + "CBP: Missing property \"tol\" for method \"CBP\"\n";
545 errormsg = errormsg + "CBP: Missing property \"updates\" for method \"CBP\"\n";
547 errormsg = errormsg + "CBP: Missing property \"maxiter\" for method \"CBP\"\n";
549 errormsg = errormsg + "CBP: Missing property \"rec_tol\" for method \"CBP\"\n";
551 errormsg = errormsg + "CBP: Missing property \"min_max_adj\" for method \"CBP\"\n";
553 errormsg = errormsg + "CBP: Missing property \"choose\" for method \"CBP\"\n";
555 errormsg = errormsg + "CBP: Missing property \"recursion\" for method \"CBP\"\n";
557 errormsg = errormsg + "CBP: Missing property \"clamp\" for method \"CBP\"\n";
559 errormsg = errormsg + "CBP: Missing property \"bbp_props\" for method \"CBP\"\n";
561 errormsg = errormsg + "CBP: Missing property \"bbp_cfn\" for method \"CBP\"\n";
562 if( !errormsg.empty() )
563 DAI_THROWE(NOT_ALL_PROPERTIES_SPECIFIED,errormsg);
565 verbose = opts.getStringAs<size_t>("verbose");
566 } else {
567 verbose = 0;
568 }
569 tol = opts.getStringAs<Real>("tol");
571 maxiter = opts.getStringAs<size_t>("maxiter");
572 rec_tol = opts.getStringAs<Real>("rec_tol");
574 max_levels = opts.getStringAs<size_t>("max_levels");
575 } else {
576 max_levels = 10;
577 }
579 choose = opts.getStringAs<ChooseMethodType>("choose");
580 recursion = opts.getStringAs<RecurseType>("recursion");
581 clamp = opts.getStringAs<ClampType>("clamp");
582 bbp_props = opts.getStringAs<PropertySet>("bbp_props");
583 bbp_cfn = opts.getStringAs<BBPCostFunction>("bbp_cfn");
585 rand_seed = opts.getStringAs<size_t>("rand_seed");
586 } else {
587 rand_seed = 0;
588 }
590 clamp_outfile = opts.getStringAs<std::string>("clamp_outfile");
591 } else {
592 clamp_outfile = "";
593 }
594 }
595 PropertySet CBP::Properties::get() const {
596 PropertySet opts;
597 opts.set("verbose", verbose);
598 opts.set("tol", tol);
600 opts.set("maxiter", maxiter);
601 opts.set("rec_tol", rec_tol);
602 opts.set("max_levels", max_levels);
604 opts.set("choose", choose);
605 opts.set("recursion", recursion);
606 opts.set("clamp", clamp);
607 opts.set("bbp_props", bbp_props);
608 opts.set("bbp_cfn", bbp_cfn);
609 opts.set("rand_seed", rand_seed);
610 opts.set("clamp_outfile", clamp_outfile);
611 return opts;
612 }
613 string CBP::Properties::toString() const {
614 stringstream s(stringstream::out);
615 s << "[";
616 s << "verbose=" << verbose << ",";
617 s << "tol=" << tol << ",";
619 s << "maxiter=" << maxiter << ",";
620 s << "rec_tol=" << rec_tol << ",";
621 s << "max_levels=" << max_levels << ",";