Fleet  0.0.9
Inference in the LOT
HillClimbing.h
Go to the documentation of this file.
1 # pragma once
2 
3 #include "TopN.h"
4 #include "SampleStreams.h"
5 
19 template<typename HYP>
20 class HillClimbing {
21 public:
22 
24  size_t N; // how big is top?
25  size_t inner_samples;
26  typename HYP::data_t* data;
27  double T = 1.0;
28 
29  HillClimbing(HYP& h0, typename HYP::data_t* d, size_t n=1, size_t is=100) : N(n), inner_samples(is), data(d) {
30  top.set_size(N);
31 
32  // add this h0
33  h0.compute_posterior(*data);
34  top << h0;
35  }
36 
38 
39  if(ctl.restart == 0) {
40  CERR "# Warning: HillClimbing without restarts is probably a bad idea because it will only climb once." ENDL;
41  }
42 
43  size_t samples = 0;
44  size_t steps_since_improvement = 0;
45 
46  ctl.start();
47  while(ctl.running()) {
48  if(ctl.steps > 0 and samples > ctl.steps) break;
49 
50  // if we restart or if top is empty, we need to fill it up
51  if(top.empty() or (ctl.restart>0 and steps_since_improvement > ctl.restart)) {
52  [[unlikely]];
53 
54  steps_since_improvement = 0; // reset the couter
55 
56  while(true) { // avoid -infs
57  auto current = top.best().restart();
58  //CERR "# Restarting " TAB current.string() ENDL;
59  current.compute_posterior(*data);
60  if(current.posterior == -infinity) continue;
61 
62  co_yield current;
63 
64  TopN<HYP> newTop(N);
65  newTop << current;
66  top = std::move(newTop);
67  break;
68  }
69  continue;
70  }
71 
72  //CERR "# Top best: " TAB top.best().posterior TAB top.best().string() ENDL;
73 
74  TopN<HYP> newTop(N);
75  //auto z = top.Z(T); // use this temperature
76  for(auto& h : top.sorted(false)) {
77 
78  newTop << h;
79 
80  // compute how many samples to take
81  // let's always do 1 to anything we store since otherwise we don't explore much
82  //size_t mysamples = 1+inner_samples * exp(h.at_temperature(T) - z); // Do we want +1 here??
83 
84  size_t mysamples = std::ceil(inner_samples / double(N)); // equal distribution
85 
86  // since we are going best to worst, if we have zero sample we can stop
87  if(mysamples == 0) break;
88 
89  //CERR "# Proposing to " TAB h.posterior TAB mysamples TAB h.string() ENDL;
90 
91  for(size_t i=0;i<mysamples;i++) { // TODO: divide these proposals up uniformly to nodes...
92  if(not ctl.running()) break;
93  if(ctl.steps > 0 and samples++ > ctl.steps) break;
94 
95  // now propose to this
96  auto pr = h.propose();
97  if(pr) {
98 
99  auto [proposal, fb] = pr.value();
100  // A lot of proposals end up with the same function, so if so, save time by not
101  // computing the posterior
102  if(proposal != h) {
103  proposal.compute_posterior(*data);
104 
105  if(proposal.posterior > -infinity)
106  newTop << proposal;
107 
108  co_yield proposal;
109  }
110 
111  if(proposal.posterior > top.best().posterior) {
112  steps_since_improvement = 0;
113  }
114  else {
115  steps_since_improvement++;
116  }
117 
118  }
119  }
120  }
121 
122  // and move it over
123  top = std::move(newTop);
124  }
125  }
126 
127 };
128 
129 
130 
unsigned long steps
Definition: Control.h:24
size_t N
Definition: HillClimbing.h:24
std::vector< T > sorted(bool increasing=true) const
Sorted values.
Definition: TopN.h:266
const T & best() const
Definition: TopN.h:219
generator< HYP & > run(Control ctl)
Definition: HillClimbing.h:37
void set_size(size_t n)
Definition: TopN.h:78
double T
Definition: HillClimbing.h:27
void start()
Definition: Control.h:54
Definition: Control.h:23
constexpr double infinity
Definition: Numerics.h:20
Definition: generator.hpp:21
HYP::data_t * data
Definition: HillClimbing.h:26
#define CERR
Definition: IO.h:23
TopN< HYP > top
Definition: HillClimbing.h:23
#define ENDL
Definition: IO.h:21
bool running()
Definition: Control.h:63
size_t inner_samples
Definition: HillClimbing.h:25
bool empty() const
Definition: TopN.h:103
unsigned long restart
Definition: Control.h:27
HillClimbing(HYP &h0, typename HYP::data_t *d, size_t n=1, size_t is=100)
Definition: HillClimbing.h:29
Definition: HillClimbing.h:20