1 #include "surfpack_system_headers.h"
2 #include "RadialBasisFunctionModel.h"
3 #include "surfpack.h"
4 #include "AxesBounds.h"
5 #include "ModelFitness.h"
6
7 using std::cout;
8 using std::endl;
9 using std::vector;
10 using std::string;
11 using std::max;
12 using std::min;
13 using surfpack::shared_rng;
14 using surfpack::fromVec;
15
16
17 #ifdef SURFPACK_HAVE_BOOST_SERIALIZATION
BOOST_CLASS_EXPORT(RadialBasisFunctionModel)18 BOOST_CLASS_EXPORT(RadialBasisFunctionModel)
19 #endif
20
21
22 SurfPoint computeCentroid(const SurfData& sd)
23 {
24 assert(sd.size());
25 assert(sd.xSize());
26 VecDbl center(sd.xSize(),0.0);
27 for (unsigned pt = 0; pt < sd.size(); pt++) {
28 for (unsigned dim = 0; dim < sd.xSize(); dim++) {
29 center[dim] += sd(pt,dim);
30 }
31 }
32 for (unsigned dim = 0; dim < center.size(); dim++) {
33 center[dim] /= sd.size();
34 }
35 return SurfPoint(center);
36 }
37
updateCentroid(VecDbl & centroid,const VecDbl & newpt,unsigned weight)38 void updateCentroid(VecDbl& centroid, const VecDbl& newpt, unsigned weight)
39 {
40 assert(centroid.size() == newpt.size());
41 for (unsigned i = 0; i < centroid.size(); i++) {
42 if (!weight) centroid[i] = newpt[i];
43 else centroid[i] = (weight*centroid[i]+newpt[i])/(weight+1);
44 }
45 }
46
findClosest(const SurfData & sd,VecDbl pt)47 unsigned findClosest(const SurfData& sd, VecDbl pt)
48 {
49 assert(sd.size());
50 double mindist = surfpack::euclideanDistance(sd(0),pt);
51 unsigned argmin = 0;
52 for (unsigned i = 1; i < sd.size(); i++) {
53 double distance = surfpack::euclideanDistance(sd(i),pt);
54 if (distance < mindist) {
55 mindist = distance;
56 argmin = i;
57 }
58 }
59 return argmin;
60 }
61
radii(const SurfData & generators)62 SurfData radii(const SurfData& generators)
63 {
64 SurfData result;
65 for (unsigned i = 0; i < generators.size(); i++) {
66 VecDbl radius(generators.xSize(),std::numeric_limits<double>::max());
67 for (unsigned j = 0; j < generators.size(); j++) {
68 if (i != j) {
69 for (unsigned dim = 0; dim < generators.xSize(); dim++) {
70 double distance = fabs(generators(i,dim)-generators(j,dim));
71 if (distance < radius[dim]) radius[dim] = distance;
72 }
73 }
74 }
75 result.addPoint(SurfPoint(radius));
76 }
77 return result;
78 }
79
cvts(const AxesBounds & ab,unsigned ngenerators,unsigned ninfluencers,double minalpha=.5,double maxalpha=.99)80 SurfData cvts(const AxesBounds& ab, unsigned ngenerators, unsigned ninfluencers,
81 double minalpha = .5, double maxalpha = .99)
82 {
83 assert(ninfluencers > ngenerators);
84 SurfData* generators = ab.sampleMonteCarlo(ngenerators);
85 unsigned iters = 10;
86 for (unsigned i = 0; i < iters; i++) {
87 SurfData* influencers = ab.sampleMonteCarlo(ninfluencers);
88 vector<SurfData> closestSets(ngenerators);
89 for (unsigned samp = 0; samp < influencers->size(); samp++) {
90 unsigned nearest = findClosest(*generators,(*influencers)(samp));
91 closestSets[nearest].addPoint((*influencers)[samp]);
92 } // for each sample pt
93 // Find centroids, update generators
94 SurfData* new_generators = new SurfData;
95 for (unsigned gen = 0; gen < ngenerators; gen++) {
96 if (closestSets[gen].size() != 0) {
97 SurfPoint center = computeCentroid(closestSets[gen]);
98 double genweight = minalpha + (maxalpha - minalpha)*((double)i/iters);
99 new_generators->addPoint(SurfPoint(
100 surfpack::weightedAvg((*generators)(gen),center.X(),genweight)));
101 } else {
102 new_generators->addPoint((*generators)(gen));
103 }
104 }
105 delete generators; generators = new_generators;
106 delete influencers;
107 } // end iteration
108 SurfData result(*generators);
109 delete generators;
110 return result;
111 }
112
makeRbfs(const SurfData & generators,const SurfData & radii)113 VecRbf makeRbfs(const SurfData& generators, const SurfData& radii)
114 {
115 assert(generators.size());
116 assert(generators.size() == radii.size());
117 vector<RadialBasisFunction> rbfs;
118 for (unsigned i = 0; i < generators.size(); i++) {
119 rbfs.push_back(RadialBasisFunction(generators(i),radii(i)));
120 }
121 return rbfs;
122 }
123
124 // Add additional rbfs with broader support to set of candidates
augment(VecRbf & rbfs)125 void augment(VecRbf& rbfs)
126 {
127 assert(rbfs.size());
128 unsigned toAdd = rbfs.size();
129 for (unsigned i = 0; i < toAdd; i++) {
130 unsigned first = shared_rng()(rbfs.size());
131 unsigned second = shared_rng()(rbfs.size());
132 //cout << "new basis from " << first << " " << second << endl;
133 VecDbl newRadius = rbfs[first].radius;
134 if (first == second) { // new function with same center/double radius
135 for (unsigned dim = 0; dim < newRadius.size(); dim++) {
136 newRadius[dim] *= 2.0;
137 }
138 rbfs.push_back(RadialBasisFunction(rbfs[first].center,newRadius));
139 } else { // new function with avg center, sum of radii
140 VecDbl newCenter = surfpack::weightedAvg(rbfs[first].center,rbfs[second].center);
141 for (unsigned dim = 0; dim < newRadius.size(); dim++) {
142 newRadius[dim] += rbfs[second].radius[dim];
143 }
144 rbfs.push_back(RadialBasisFunction(newCenter,newRadius));
145 }
146 }
147 }
148
getMatrix(const SurfData & sd,const VecRbf & candidates,VecUns used)149 MtxDbl getMatrix(const SurfData& sd, const VecRbf& candidates, VecUns used)
150 {
151 std::sort(used.begin(),used.end());
152 MtxDbl A(sd.size(),used.size(),true);
153 unsigned nrows = sd.size();
154 unsigned ncols = used.size();
155 for (unsigned rowa = 0; rowa < nrows; rowa++) {
156 for (unsigned cola = 0; cola < ncols; cola++) {
157 assert(used[cola] < candidates.size());
158 A(rowa,cola) = candidates[used[cola]](sd(rowa));
159 }
160 }
161 return A;
162 }
163
probInclusion(unsigned vec_size,unsigned max_size,double prob)164 VecUns probInclusion(unsigned vec_size, unsigned max_size, double prob)
165 {
166 assert(prob >= 0.0);
167 assert(prob <= 1.0);
168 assert(vec_size);
169 VecUns result;
170 for (unsigned i = 0; i < vec_size; i++) {
171 if (result.size() >= max_size) break;
172 if (shared_rng().randExc() < prob) result.push_back(i);
173 }
174 return result;
175 }
176
fullCoeff(unsigned vec_size,const VecDbl & coeffs,VecUns & incl)177 VecDbl fullCoeff(unsigned vec_size, const VecDbl& coeffs, VecUns& incl)
178 {
179 VecDbl result(vec_size,0.0);
180 for (unsigned i = 0; i < incl.size(); i++) {
181 result[incl[i]] = coeffs[i];
182 }
183 return result;
184 }
185
186 ///\todo The exp() function can eat up a lot of time in this method
187 /// If it becomes a bottleneck, switch to a cached lookup table for
188 /// the values of exp(x)
189 //const unsigned granularity = 1000;
190 //const double maxe = 8.0;
191 //VecDbl initExps()
192 //{
193 // VecDbl exps;
194 // exps.reserve(granularity);
195 // for (unsigned i = 0; i < granularity; i++) {
196 // exps.push_back(exp(-(double)i/granularity*maxe));
197 // }
198 // cout << "Initialized " << endl;
199 // return exps;
200 //}
201 //
202 //double myexp(const double x)
203 //{
204 // assert(x >= 0.0);
205 // static VecDbl exps(initExps());
206 // if (x > maxe) return 0.0;
207 // return exps[(unsigned)(x/maxe*granularity)];
208 //}
209
RadialBasisFunction(const VecDbl & center_in,const VecDbl & radius_in)210 RadialBasisFunction::RadialBasisFunction(const VecDbl& center_in, const VecDbl& radius_in)
211 : center(center_in), radius(radius_in)
212 {
213 assert(!center.empty());
214 assert(center.size() == radius.size());
215 }
216
RadialBasisFunction(const std::string & center_in,const std::string & radius_in)217 RadialBasisFunction::RadialBasisFunction(const std::string& center_in, const std::string& radius_in)
218 : center(surfpack::toVec<double>(center_in)),
219 radius(surfpack::toVec<double>(radius_in))
220 {
221 assert(!center.empty());
222 assert(!radius.empty());
223 assert(center.size() == radius.size());
224 }
225
operator ()(const VecDbl & x) const226 double RadialBasisFunction::operator()(const VecDbl& x) const
227 {
228 assert(x.size() == center.size());
229 double sum = 0.0;
230 double temp;
231 for (unsigned i = 0; i < center.size(); i++) {
232 temp = x[i] - center[i];
233 sum += temp*temp*radius[i];
234 };
235 //return myexp(sum);
236 return exp(-sum);
237 }
238
deriv(const VecDbl & x,const VecUns & vars) const239 double RadialBasisFunction::deriv(const VecDbl& x, const VecUns& vars) const
240 {
241 assert(vars.size() == 1);
242 assert(!center.empty());
243 assert(!radius.empty());
244 assert(x.size() == center.size());
245 unsigned i = vars[0];
246 return -2.0*radius[i]*(x[i]-center[i])*(*this)(x);
247 }
248
asString() const249 std::string RadialBasisFunction::asString() const
250 {
251 std::ostringstream os;
252 os << "center: ";
253 copy(center.begin(),center.end(),std::ostream_iterator<double>(os," "));
254 os << " radius: ";
255 copy(radius.begin(),radius.end(),std::ostream_iterator<double>(os," "));
256 os << std::endl;
257 return os.str();
258 }
259
260
RadialBasisFunctionModel(const VecRbf & rbfs_in,const VecDbl & coeffs_in)261 RadialBasisFunctionModel::RadialBasisFunctionModel(const VecRbf& rbfs_in, const VecDbl& coeffs_in)
262 : SurfpackModel(1), rbfs(rbfs_in),coeffs(coeffs_in)
263 {
264 assert(!rbfs.empty());
265 this->ndims = rbfs[0].center.size();
266 assert(this->size() != 0);
267 assert(rbfs.size() == coeffs.size());
268 }
269
evaluate(const VecDbl & x) const270 double RadialBasisFunctionModel::evaluate(const VecDbl& x) const
271 {
272 double sum = 0.0;
273 for (unsigned i = 0; i < rbfs.size(); i++) {
274 sum += coeffs[i]*rbfs[i](x);
275 }
276 return sum;
277 }
278
279 /// Currently set up so that operator() must be called immediately before
280 /// Not good assumption
gradient(const VecDbl & x) const281 VecDbl RadialBasisFunctionModel::gradient(const VecDbl& x) const
282 {
283 /// code copied straight from LRM
284 assert(!x.empty());
285 //assert(coeffs.size() == bs.bases.size());
286 VecUns diff_var(1,0); // variable with which to differentiate
287 VecDbl result(x.size(),0.0);
288 for (unsigned i = 0; i < x.size(); i++) {
289 diff_var[0] = i;
290 for (unsigned j = 0; j < rbfs.size(); j++) {
291 result[i] += coeffs[j]*rbfs[j].deriv(x,diff_var);
292 }
293 }
294 return result;
295 }
296
asString() const297 std::string RadialBasisFunctionModel::asString() const
298 {
299 std::ostringstream os;
300 unsigned num_bases = rbfs.size();
301 unsigned num_vars = ndims;
302 os << "-----\n";
303 os << "Surfpack Radial Basis Function model\n";
304 os << "f(x) = w*phi(x) and phi_k(x) = exp{-r_k*(x-c_k^T).^2}; where\n\n";
305 os << "inputs = " << num_vars << "\n";
306 os << "bases = " << num_bases << "\n";
307
308 os << std::scientific << std::setprecision(16);
309 os << "\nw (1 x bases) =\n";
310 for(unsigned i=0; i < num_bases; i++)
311 os << std::setw(23) << coeffs[i] << " ";
312 os << "\n\nr (bases x inputs) = \n";
313 for(unsigned i=0; i < num_bases; i++) {
314 for(unsigned j=0; j < num_vars; j++) {
315 os << std::setw(23) << rbfs[i].radius[j] << " ";
316 }
317 os << "\n";
318 }
319 os << "\nc (bases x inputs) = \n";
320 for(unsigned i=0; i < num_bases; i++) {
321 for(unsigned j=0; j < num_vars; j++) {
322 os << std::setw(23) << rbfs[i].center[j] << " ";
323 }
324 os << "\n";
325 }
326 os << "\n-----\n";
327 return os.str();
328 }
329
330
331 typedef std::pair<double,VecUns> RbfBest;
332 ///////////////////////////////////////////////////////////
333 /// Moving Least Squares Model Factory
334 ///////////////////////////////////////////////////////////
335
RadialBasisFunctionModelFactory()336 RadialBasisFunctionModelFactory::RadialBasisFunctionModelFactory()
337 : SurfpackModelFactory(), nCenters(0), cvtPts(0), maxSubsets(0),
338 minPartition(1)
339 {
340
341 }
342
RadialBasisFunctionModelFactory(const ParamMap & args)343 RadialBasisFunctionModelFactory::RadialBasisFunctionModelFactory(const ParamMap& args)
344 : SurfpackModelFactory(args), nCenters(0), cvtPts(0), maxSubsets(0),
345 minPartition(1)
346 {
347
348 }
349
config()350 void RadialBasisFunctionModelFactory::config()
351 {
352 SurfpackModelFactory::config();
353 string strarg;
354 strarg = params["centers"];
355 if (strarg != "") nCenters = std::atoi(strarg.c_str());
356 strarg = params["cvt_pts"];
357 if (strarg != "") cvtPts = std::atoi(strarg.c_str());
358 strarg = params["max_subsets"];
359 if (strarg != "") maxSubsets = std::atoi(strarg.c_str());
360 strarg = params["min_partition"];
361 if (strarg != "") minPartition = std::atoi(strarg.c_str());
362 }
363
Create(const SurfData & sd)364 SurfpackModel* RadialBasisFunctionModelFactory::Create(const SurfData& sd)
365 {
366 unsigned max_centers = 100;
367 unsigned max_max_subsets = 100;
368 if (nCenters == 0) nCenters = min(max_centers,sd.size());
369 if (cvtPts == 0) cvtPts = 10*nCenters;
370 if (maxSubsets == 0) maxSubsets = min(max_max_subsets,3*nCenters);
371 RbfBest bestset(std::numeric_limits<double>::max(),VecUns());
372
373 SurfData centers = cvts(AxesBounds::boundingBox(sd),nCenters,cvtPts);
374 SurfData radiuses = radii(centers);
375 VecDbl b = sd.getResponses();
376 VecRbf candidates = makeRbfs(centers,radiuses);
377 augment(candidates);
378 assert(candidates.size() == 2*nCenters);
379 for (unsigned i = 0; i < maxSubsets; i++) {
380 VecUns used = probInclusion(candidates.size(),sd.size(),.5);
381 MtxDbl A = getMatrix(sd,candidates,used);
382 VecDbl x;
383 surfpack::linearSystemLeastSquares(A,x,b);
384 VecDbl coeffs = fullCoeff(candidates.size(),x,used);
385 RadialBasisFunctionModel rbfm(candidates,coeffs);
386 StandardFitness sf;
387 double fitness = sf(rbfm,sd);
388 if (fitness < bestset.first) bestset = RbfBest(fitness,used);
389 }
390 VecUns used = bestset.second;
391 VecRbf final_rbfs;
392 VecUns final_used(used.size());
393 for (unsigned i = 0; i < used.size(); i++) {
394 final_used[i] = i;
395 final_rbfs.push_back(candidates[used[i]]);
396 }
397 // Recompute the coefficients. If we cached the result, we wouldn't
398 // have to do it again.
399 MtxDbl A = getMatrix(sd,final_rbfs,final_used);
400 VecDbl x;
401 surfpack::linearSystemLeastSquares(A,x,b);
402 SurfpackModel* sm = new RadialBasisFunctionModel(final_rbfs, x);
403 StandardFitness sf;
404 double fitness = sf(*sm,sd);
405 //cout << "Cached fitness: " << bestset.first << " recomputed: " << fitness << endl;
406 assert(sm);
407 return sm;
408 }
409
410